Hash Tables Under The Hood

In a slightly simplified explanation, hash tables are just arrays that with the keys mapped to the indexes. A key is transformed in an index through a hash function.

A good hash function must be:

• consistent: it should always produce the same output for the same key
• collision-free: it should minimize the number of keys that are mapped to the same number

In case the hash function still causes collisions (e.g. for memory reasons), it could be changed so that an entry in the array no longer contains a single value, but a new data structure (such as a linked list or even a new hash table).