A hash table implements key-based lookup by using a hash function to map a key to a position in a finite table.

Hash functions

A hash function converts a key into a fixed-size integer-like value. The table uses part of that value to choose an initial bucket or slot.

Different keys can produce the same table position, creating a collision.

Handling collisions

Common approaches include chaining, where each bucket stores several entries, and open addressing, where another table position is searched according to a probing rule.

Load factor

The load factor compares the number of stored entries with the table capacity. As the table becomes crowded, collisions and probing generally increase.

Dynamic hash tables therefore resize and rehash entries when needed.

Complexity

With a suitable hash function and controlled load factor, lookup, insertion and deletion have expected constant-time cost. Their worst case can still be linear when many keys collide.

Hash tables trade ordering and contiguous sequential access for fast key-based retrieval.