Hashing

Hashing can find an element with just one comparison. The idea: instead of searching for the element, calculate where it must be.

A hash function computes a position (an index) for each element, and the elements are stored at those positions in a list called the hash table.

The simplest hash function is the remainder method: h(element) = element % size of the hash table. For a table of size 10, the hash of 34 is 34 % 10 = 4, of 16 is 6, and of 2 is 2, so they are stored at slots 4, 6 and 2.

To search for a key, compute h(key), and check just that one slot: if the key is there, it is found; if not, it is absent.

A problem arises when two elements get the same hash value: 16 % 10 and 26 % 10 are both 6. This is a collision. There are methods of collision resolution to place the extra elements elsewhere.

A perfect hash function maps every element to a unique index, so no collisions happen. Other techniques for making hash functions also exist, but the remainder method is the simplest.