Hash table idea

The idea behind hash tables is as follows.

A hash table consists of a list of a specific size. Let’s call the size of the list N. An element must be stored in the hash table with a particular “key”, for instance a string. A so-called “hash function” is used to turn that key into a number (how exactly it does that I will not go into here, just assume that there is a hash function that may turn any string into some number, whereby different strings tends to get different numbers). Let’s call this number H. The element is then stored in the list at index H%N (H modulo N).

Consequently, to detect whether an element with a particular key exists in the hash table, you translate that key with the hash function to its associated number H, and check whether there is something stored in the hash table at H%N.

Of course, there are many issues with this procedure. It is very well possible that two different keys end up being hashed to the same number. It is even more likely that two different hash numbers end up at the same index in the hash table. Moreover, even if it would be guaranteed that all hash numbers translate to different indices, at some point the hash table will be completely filled up, and where are new elements going to be stored then?

The issues mentioned are solved as follows:

• For the problem that two different keys lead to the same hash number, the solution is that in the hash table each element is stored as a tuple with the key. Therefore, when you find an element in the hash table, you can check whether indeed it has the key that you are looking for.
• For the problem that two or more elements might be mapped to the same index in the hash table, the solution is that if an element needs to get stored at an index where already an element is stored (called a “collision”), a so-called “perturbation” value is added to the index to create another index. If that slot is empty, the element gets stored in it. If it is full, repeatedly the perturbation value is added to the index, until an empty slot is found. This is called “probing”.
• For the problem of the hash table getting filled up, the solution is that once the hash table is filled for a particular percentage (e.g., 70%), a bigger hash table is created and all elements are moved to the new table. Naturally, this can be an expensive operation.