Resizing a HashMap with quadratic probing (backing array implementation)

Question

After I check to see if the load factor signals the backing array to be resized, how do I actually do the resizing with quadratic probing?

Here is the code. It's only part of the class. Also, could you check if I'm implementing the add method correctly?

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

Following the following from wiki:

 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

According to the above, it seems to me that there is a problem in your add method. Notice step (4.1) and (4.2): if table[index] == null, a position for the key has been found and you can stop. Your do will execute again, because right after the insert, you update the index, thus temp != index will be true.

You are also calculating the next index incorrectly, change

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

to

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

The add will thus change to:

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;

It can be proven that, if the table size b for b > 3 the first b/2 positions will be unique, so it is safe to assume that if the table is less than half full (b/2 - 1), you will find an empty position. This depends on your MAX_LOAD_FACTOR.

For resizing, you will need to rehash each value into the new table. This is due to your hash function using the size of the table as modulus. Your hash function has basically changed, so you need to create the new array of size + 1, and readd every element to the new array.

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());
    }
}

Note: I did not test this and only used the theory behind dynamic probing and hashtables to debug your code. Hope it helps!