Изменение размера HashMap с квадратичным зондированием (реализация резервного массива)

Question

После того, как я проверил, сигнализирует ли коэффициент нагрузки размер базового массива об изменении размера, как я на самом деле делаю изменение размера с квадратичным зондированием?

Вот код Это только часть класса. Кроме того, не могли бы вы проверить, правильно ли я реализую метод add?

import java.util.*;

public class HashMap<K, V> implements HashMapInterface<K, V> {

// Do not make any new instance variables.
private MapEntry<K, V>[] table;
private int size;

/**
 * Create a hash map with no entries.
 */
public HashMap() {
    table = new MapEntry[STARTING_SIZE];
    size = 0;
}

@Override
public V add(K key, V value) {
    if (key == null || value == null) {
        throw new IllegalArgumentException("Passed in null arguments.");
    }
    if (getNextLoadFactor() > MAX_LOAD_FACTOR) {
        resize();
    }
    MapEntry<K, V> entry = new MapEntry<>(key, value);
    V val = null;
    int index = Math.abs(key.hashCode()) % table.length;
    int temp = index;
    int q = 1;
    do {
        if (table[index] == null) {
            table[index] = entry;
        } else if (table[index].getKey().equals(key)) {
            val = table[index].getValue();
            table[index].setValue(value);
        }
        index = index + q*q % table.length;
        q++;
    } while (temp != index);
    size++;
    return val;
}

private double getNextLoadFactor() {
    return (double) size / (double) table.length;
}

private void resize() {
    MapEntry<K, V>[] temp = table;
    table = new MapEntry[table.length * 2 + 1];
    for (int i = 0; i < table.length; i++) {

    }
}

Answer 1

Следуя следующему из вики:

 1. Get the key k
 2. Set counter j = 0
 3. Compute hash function h[k] = k % SIZE
 4. If hashtable[h[k]] is empty
         (4.1) Insert key k at hashtable[h[k]]
         (4.2) Stop
    Else
        (4.3) The key space at hashtable[h[k]] is occupied, so we need to find the next available key space
        (4.4) Increment j
        (4.5) Compute new hash function h[k] = ( k + j * j ) % SIZE
        (4.6) Repeat Step 4 till j is equal to the SIZE of hash table
 5. The hash table is full
 6. Stop

Исходя из вышеизложенного, мне кажется, что в вашем add метод. Обратите внимание на шаги (4.1) и (4.2): если table[index] == null, позиция для ключа была найдена, и вы можете остановиться. Ваш do будет выполняться снова, потому что сразу после вставки вы обновляете индекс, таким образом temp != index будет правдой.

Вы также неправильно рассчитываете следующий индекс, измените

index = index + q*q % table.length;

в

index = (Math.abs(key.hashCode()) + q*q) % table.length;

add таким образом изменится на:

MapEntry<K, V> entry = new MapEntry<>(key, value);
V val = null;
int index = Math.abs(key.hashCode()) % table.length;

int q = 0;

while (table[(index = (Math.abs(key.hashCode()) + q*q++) % table.length)] != null);

table[index] = entry;
size++;
return val;

Можно доказать, что если размер таблицы b за b > 3 первый b/2 позиции будут уникальными, поэтому можно предположить, что если таблица заполнена менее чем на половину (b/2 - 1), вы найдете пустую позицию. Это зависит от вашего MAX_LOAD_FACTOR,

Для изменения размера вам нужно будет перефразировать каждое значение в новую таблицу. Это связано с тем, что ваша хеш-функция использует размер таблицы в качестве модуля. Ваша хеш-функция в основном изменилась, поэтому вам нужно создать новый массив size + 1и прочитал каждый элемент в новый массив.

private void resize() {
    MapEntry<K, V>[] temp = table;
    table = new MapEntry[table.length * 2 + 1];
    for (MapEntry<K, V> entry:temp) {
        this.add(entry.getKey(), entry.getValue());
    }
}

Примечание: я не проверял это, а использовал теорию динамического зондирования и хеш-таблицы для отладки вашего кода. Надеюсь, поможет!