Написание простого String hashMap с использованием параллельных массивов. Получение нулевого значения для некоторых ключей после перефразировки

Question

В первый раз, когда я получаю коллизию в методе put, т.е. когда hasKey возвращает -1, метод rehashing запускается, и значение, которое вызвало коллизию, передается в удвоенный массив в вероятный пустой слот. Но System.out.println(m.get("1000")); дает мне null для некоторых ключей, что означает, что они были потеряны. Я не понимаю, как они могут быть потеряны, потому что нет ничего, что могло бы переопределить их в keyArray.

import java.util.*;

public class StringMapParallel implements Iterable<String>{

    private int nButckets = 2000;
    private String[] keyArray = new String[nButckets];
    private String[] valueArray = new String[nButckets];
    private int numberOfEntries = 0;

    public static void main(String[] args) {


        StringMapParallel m = new StringMapParallel();
;
        for (int i = 0; i < 8000; i++) {
            m.put(String.valueOf(i), String.valueOf(i));
        }
        System.out.println(m.get("1000"));


    }



    private void rehashing() {
        if (numberOfEntries > (int) (0.3 * nButckets)) {
            int newBucketsNumber = nButckets * 2;
            String[] newKeyArray = new String[newBucketsNumber];
            String[] newValueArray = new String[newBucketsNumber];

            for (int i = 0; i < keyArray.length; i++) {
                if (keyArray[i] != null) {
                    int index = keyArray[i].hashCode() % newBucketsNumber;
                    newKeyArray[index] = keyArray[i];
                    newValueArray[index] = valueArray[keyArray[i].hashCode() % nButckets];
                }
            }           
            /*
            for (String key: this) {
                int index = key.hashCode() % newBucketsNumber;
                newKeyArray[index] = key;
                if (key == null) System.out.println(key); 
                newValueArray[index] = valueArray[key.hashCode() % nButckets];              
            }
            */
            keyArray = newKeyArray;
            valueArray = newValueArray;
            nButckets = newBucketsNumber;
        }
    }

    public void put(String key, String value) {
        int index = key.hashCode() % nButckets;
        int hasKey = hasKey(index, key);
        if (hasKey == 1) {
            valueArray[index] = value;
        } else if (hasKey == 0){
            keyArray[index] = key;
            valueArray[index] = value;
            numberOfEntries++;
        } else {
            rehashing();
            index = key.hashCode() % nButckets;
            keyArray[index] = key;
            valueArray[index] = value;
            numberOfEntries++;
        }
    }

    public String get(String key) {
        int index = key.hashCode() % nButckets;
        if (hasKey(index, key) == 1) return valueArray[index];
        return null;
    }

    private int hasKey(int index, String key) {
        if (keyArray[index] == null) {
            return 0;
        } else if (keyArray[index].equals(key)) {
            return 1;
        } else {
            return -1;
        }
    }

    public Iterator<String> iterator(){
        Iterator<String> iter = new Iterator<String>() {
            private int currentIndex = 0;
            private int nEntries = 0;

            @Override
            public boolean hasNext() {
                return nEntries < numberOfEntries && numberOfEntries != 0;
            }

            @Override
            public String next() {
                for (int i = currentIndex; i < keyArray.length; i++) {
                    if (keyArray[i] != null) {
                        currentIndex = i + 1;
                        nEntries++;
                        return keyArray[i];
                    }
                }
                return null;
            }
        };
        return iter;
    }

}

Answer 1

Значение int index = key.hashCode() % nButckets; в вашем алгоритме для ключей 1000 и 6357 одинаково, то есть 1423. Следовательно, ваш алгоритм перезаписывает keyArray[1423]=1000 с keyArray[1423]=6357

Когда вы печатаете m.get(String.valueOf(1000)), следующий метод get() проверяет index, а также key, следовательно, он возвращает null. Прочитайте комментарий в коде для дальнейшего объяснения.

public String get(String key) {
    //System.out.println(key+" "+ key.hashCode());
    int index = key.hashCode() % nButckets;
    System.out.println(index+"bfb"+hasKey(index, key));
    //hasKey(index, key) would return -1, because key[1423] is 6357, and not 1000 as you expected.
    if (hasKey(index, key) == 1) return valueArray[index]; 
     return null;
}

private int hasKey(int index, String key) {
    //System.out.println(keyArray[index]);
    if (keyArray[index] == null) {
        return 0;
    } else if (keyArray[index].equals(key)) {
        return 1;
    } else {
        return -1;
    }
}