Изменение размера массива, когда элементы больше чем 1/2 его размера

Question

Я пытаюсь изменить размер моего массива, когда N, количество элементов, больше, чем m / 2, m является начальным размером массива, но это не работает, и я не понимаю, почему. Этот массив должен работать как хеш-таблица, поэтому у меня есть функция хеширования перед каждой вставкой, и после изменения размера я хочу снова вставить каждый элемент с новым хэшированием (значение m изменилось). Это ошибка:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at JumpHashing.resize(JumpHashing.java:55)
    at JumpHashing.put(JumpHashing.java:50)
    at JumpHashing.hashing(JumpHashing.java:40)
    at JumpHashing.resize(JumpHashing.java:61)
    at JumpHashing.put(JumpHashing.java:50)
    at JumpHashing.hashing(JumpHashing.java:40)
    at JumpHashing.resize(JumpHashing.java:61)
    at JumpHashing.put(JumpHashing.java:50)
    at JumpHashing.hashing(JumpHashing.java:40)
    at JumpHashing.resize(JumpHashing.java:61)
    at JumpHashing.put(JumpHashing.java:50)
    at JumpHashing.hashing(JumpHashing.java:40)
    at JumpHashing.resize(JumpHashing.java:61)
    at JumpHashing.put(JumpHashing.java:50)
    at JumpHashing.hashing(JumpHashing.java:40)
    at JumpHashing.resize(JumpHashing.java:61)
    at JumpHashing.put(JumpHashing.java:50)
    at JumpHashing.hashing(JumpHashing.java:40)
    at JumpHashing.resize(JumpHashing.java:61)
    at JumpHashing.put(JumpHashing.java:50)
    at JumpHashing.hashing(JumpHashing.java:40)
    at JumpHashing.resize(JumpHashing.java:61)
    at JumpHashing.put(JumpHashing.java:50)
    at JumpHashing.hashing(JumpHashing.java:40)
    at JumpHashing.resize(JumpHashing.java:61)
    at JumpHashing.put(JumpHashing.java:50)
    at JumpHashing.hashing(JumpHashing.java:40)
    at JumpHashing.resize(JumpHashing.java:61)
    at JumpHashing.put(JumpHashing.java:50)
    at JumpHashing.hashing(JumpHashing.java:40)
    at JumpHashing.resize(JumpHashing.java:61)
    at JumpHashing.put(JumpHashing.java:50)

Проблема явно заключается в изменении размера, без него (с менее чем 23 элементами) это работает.

Первоначальный размер m равен 23, это фактический код (класс «В» для чтения файла из algs4):

public class JumpHashing{
    private int m;
    private int[] hashTable; 
    private static int id;
    private int N;

    public JumpHashing(){
        m = 23;
        hashTable = new int[m];
        N = 0;
    }

    public void hashing(int value) {
            int key = (value*11)%m;
            put(key, value);
    }

    public void put(int key, int value) {
        if(N <m/2) {
            hashTable[key] = value;
            N++;
        } else {
            m=m*2;
            N=0;
            resize(m);
        }
    }

    public void resize(int m) { 
        int[] temp = new int[m];
        for(int i=0; i<hashTable.length; i++) {
            temp[i] = hashTable[i];
        }
        hashTable = new int[m];
        for(int i=0; i<temp.length; i++) {
            hashing(temp[i]);
        }
    }

    public static void main(String[] args) {
        JumpHashing hashT1 = new JumpHashing();

        In file = new In("random.txt");
        while(file.hasNextLine()) {
            int value = Integer.parseInt(file.readLine());
            hashT1.hashing(value);
        }   
        for(int j=0; j<hashT1.hashTable.length; j++) {
            StdOut.println("Key: "+j+" Value: "+hashT1.hashTable[j]);
        }
    }
}

Answer 1

Вы заканчиваете тем, что неоднократно звонили resize, пока память не использовалась. Проблема в этой функции:

    public void resize(int m) { 
        int[] temp = new int[m];  // <-- this is the new double-size of m
        for(int i=0; i<hashTable.length; i++) {
            temp[i] = hashTable[i];
        }
        hashTable = new int[m];
        for(int i=0; i<temp.length; i++) {  // <-- here we go too far
            hashing(temp[i]);
        }
    }

Ваш второй l oop проходит через весь новый массив размера m, а не в исходный массив размера m / 2. Половина плюс один через l oop ваш N будет снова больше m/2 и будет вызывать изменение размера каждый раз, когда это происходит.

Вот что вы должны иметь в этой функции:

public void resize(int m) {
    int[] oldHash = hashTable;
    hashTable = new int[m];
    for(int i=0; i<oldHash.length; i++) {
        if (oldHash[i] != 0) {     // <-- don't hash empty slots
            hashing(oldHash[i]);
        }
    }
}

Это также повышает производительность, поскольку вы выполняете l oop всего один раз и не более, чем м / 2 раза.