Hashing: Idea and Buckets

Hashing maps keys to bucket indices. The expected access time is $O(1)$ when the hash function distributes keys well and the table is not overloaded.

Poor hash functions or extreme load factors can lead to chains and $O(n)$ behavior.

$$i = h(k) \bmod m$$

Index instead of a double loop: Two Sum [1].

Where used

Dictionaries, caches, database hash joins, deduplication, sharding. Hashing is the standard method for mapping keys to slots.

Depth

A hash table initially maps a key to an integer hash value and then to a table position. A bucket is the area in which entries with the same computed index are managed. Good distribution reduces the average number of keys that need to be checked there.

The hash value does not replace equality checks. It only narrows down the candidates; within the bucket, the defined key equality must still be checked. The expected constant access time assumes a suitable hash function and controlled occupancy.

Difficulty levels

1. Calculate a valid index from the hash value and table length.
2. Explain why collisions are inevitable despite good distribution.
3. Assess input patterns that concentrate many keys into few buckets.

Pitfalls

The modulo operator can yield a negative value for negative hash values. Moreover, an identical hash is not proof of identical keys; it is merely a reason to perform the actual comparison.