I read a C++ implementation of a hash map here. https://www.geeksforgeeks.org/implementing-hash-table-open-addressing-linear-probing-cpp/
Let's say key
k1 has a hash index of
h. Suppose there's a collision with key
k2 such that
hash(k1) == hash(k2). Then won't the new hash index of
Key: k1 Index: h Key: k2 Index: h+1
Suppose we introduce a third key
k3 such that
hash(k3) == h+1. Then when we insert
k3 into the hash map, its hash index will become
Key: k1 Hash value: h Hash table index: h Key: k2 Hash value: h Hash table index: h+1 Key: k3 Hash value: h+1 Hash table index: h+2
This can cause the hash indexes for keys to be shifted over 1 in the case of collisions (as seen above), and if collisions happen frequently then they could be shifted over more than once.
Is this a bad implementation of a hash map? From an aesthetic point of view I prefer the linked approach, where each hash node has a pointer to a next node, such that if multiple nodes have the same hash index, they are all part of the same linked list starting at that hash index.
In the linked approach, at least we have the assurance that a key will logically correspond to its hash index in the hash table, even if it's part of a linked list (in which case it doesn't physically correspond, but logically still does, since the head of the linked list is stored there).
Is the implementation of the hash map in GeeksForGeeks bad? Is the linked approach more logical and intuitive? What are your thoughts?
Note: The linked approach I refer to is simply to store a linked list at each hash index in the hash table, such that if multiple keys are hashed to that index, they are stored in this linked list.