Hash Table - Hashing

Hashing

The idea of hashing is to distribute the entries (key/value pairs) across an array of buckets. Given a key, the algorithm computes an index that suggests where the entry can be found:

index = f(key, array_size)

Often this is done in two steps:

hash = hashfunc(key) index = hash % array_size

In this method, the hash is independent of the array size, and it is then reduced to an index (a number between 0 and array_size − 1) using a remainder operation (%).

In case the array size is a power of two, the remainder operation is reduced to masking, which improves speed, but can increase problems with a poor hash function.