Interesting detail about HashMap's Linear Probing (and a bug!)

I was confused as to how linear probing as described (for handing hash function collisions) could work. Consider the following for a hash function of (key % length) with length 10:

hashmap.put(4, "Blue");
hashmap.put(5, "Green");
hashmap.put(14, "Yellow");  // collision causing probing over cluster
hashmap.remove(5);  // gap opens in cluster
hashmap.get(14);  // === null because it hits the empty cell occupied by key 5

Basically any holes opened in a cluster will cause any keys sitting after the hole (put there by an earlier hashvalue) to never be seen again.

Indeed, Mosh’s implementation of HashMap appears to have this bug.

I looked up Linear Probing and Wikipedia has an excellent article that describes exactly this problem and how to solve it (its kinda ingenious). The remove(key) method needs to be quite a bit more involved than just removing the keyed entry in the table.

Yeah, he did not go into the full details on what happens with probing on deletion. I did not check the article, but I always have assumed you need to remap everything in the cluster since it may have the problem you described. The problem is not restricted to linear probing either. In practice, deletion is actually pretty uncommon for map use cases, so the cost is not that significant in many applications.

@gecko
I had same bug. I think the below code that can helps you anymore.

private int getIndexExists(int key) {
    int steps = 0;
    while (steps != entries.length) {
        int index = index(key, steps++);
        Entry entry = entries[index];
        if (entry != null && entry.key == key)
            return index;
    }
    return -1;
}

public void remove(int key) {
    int index = getIndexExists(key);
    if (index == -1)
        return;

    entries[index] = null;
    count--;
}

Instead of using getIndex, let’s try this getIndexExists that keep looking until we find a slot with the same key.