Is this a misleading or undesirable implementation of a hash map?

Question

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 k2 become h+1?

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 h+2.

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.

Answer 1

As others have indicated, this code example doesn't do resizing, and this is an important part of a "real" dynamic hash table. Whether or not it's "bad" depends on what it's trying to achieve as an example, but it's certainly not code that you should deploy.

Linear probing isn't necessarily a bad idea. After all, it has excellent locality. But since you asked about a specific scenario, let's explore that. The scenario is where you have two keys, k1 and k2, which have the same hash value h, and a third, k3, with the hash value h+1.

Most hash table designs rely on the premise that the hash function is "good". If you have a "good" hash function, this should be a difficult scenario to engineer on purpose, but it's still possible that it happens with high enough probability just by virtue of storing a lot of entries in the hash table.

Consider an open addressing hash table with $m$ slots and $n$ elements in it. Denote the load factor by $\lambda = \frac{n}{m}$. Then if the hash function is "good", and $m$ and $n$ are large enough, the probability that a given slot has $k$ elements that would "naturally" hash to that slot is given by the Poisson distribution:

$$P(k; \lambda) = \frac{e^{-\lambda} \lambda^k}{k!}$$

So the probability that a given slot has at least 2 elements is:

$$P_1 = 1 - P(0; \lambda) - P(1; \lambda)$$

And the probability that the very next slot has at least 1 element is:

$$P_2 = 1 - P(0; \lambda)$$

The probability of this scenario occurring to a given hash slot is:

$$P_1 P_2 = 1 - e^{-\lambda} (\lambda + 2) + e^{-2\lambda} (\lambda + 1)$$

...and so on. Multiply this by $m$ to give the expected number of times this scenario happens for any $m$ and $n$.

(Exercise: Suppose that you have $m$ pigeonholes and $n$ pigeons, and you assign pigeons to pigeonholes randomly and $m$ is large enough. Then the proportion of pigeonholes with $k$ pigeons assigned follows a Poisson distribution. Show that the expected number of "pigeon collisions" is $\frac{1}{2}$ when $n = \sqrt{m}$.)

Remember, though, that short probes aren't necessarily a problem. What you're trying to avoid is long probes. Specifically, you're trying to ensure that the maximum probe length, that is, the largest distance that an entry is from its "home", is small. This number gives the maximum "work" that you may have to do to look for an entry.

In open addressing, it is common practice to keep track of this maximum probe length, and update it when a new element is inserted. This number is used for (at least!) two purposes: to decide when to stop searching, and to decide when to resize the table.

Answer 2

It's quite normal.

If your hash table is getting too full, you will get a high number of collisions - time to resize the hash table.

If your hash table is not very full, a high number of collisions is possible, but not very likely.