Understanding Hashing and Hash Tables: Achieving O(1) Lookup

When data items are unordered we use linear search (O(n)), and when ordered we can apply binary search (O(log n)). The article asks whether we can further reduce the complexity and answers that we can achieve constant‑time lookup (O(1)) by using hashing.

Hashing maps a data item directly to a storage location called a slot (or bucket) using a hash function, enabling immediate access if the slot is known. A hash table is a collection of such slots, each with a unique name.

Example of a hash function

Given the items 54, 26, 93, 17, 77, 31 and a table size of 11 slots (indices 0‑10), a common hash method is the remainder operation. The hash function is:

h(item) = item % 11

Applying this function yields the following placement:

Item Hash Value 54 10 26 4 93 5 17 6 77 0 31 9

The ratio of stored items to total slots (6/11) is the load factor. After inserting the items, lookup becomes trivial: compute the same hash for the query item and check the corresponding slot, achieving O(1) complexity.

Disadvantages

The example works because each slot holds a unique item. Adding another item, such as 44, results in h(44) = 0 , causing two items to share slot 0 – a collision. The article notes that collision handling will be discussed later.