Hash Tables Explained: From Direct Addressing to Open Addressing

The Motivating Idea: Direct-Address Tables

If the universe of possible keys is small, a Direct-Address Table offers a simple and extremely fast solution: an array indexed directly by the key itself, where each slot holds the element with that key (or is empty).

DIRECT-ADDRESS-SEARCH(T, k):
  return T[k]

DIRECT-ADDRESS-INSERT(T, x):
  T[x.key] = x

DIRECT-ADDRESS-DELETE(T, x):
  T[x.key] = NIL

Every operation runs in O(1) time — as fast as possible. The catch is memory: this requires allocating an array as large as the entire universe of possible keys, which is impractical whenever the universe is large (such as all possible strings) or when only a small fraction of possible keys are actually used.

Hash Tables: Trading Some Guarantees for Massive Space Savings

A Hash Table solves this space problem by using a much smaller array of size m, and a Hash Function h(k) that maps each key from the large universe down to an index in [0, m-1]. This dramatically reduces memory usage, at the cost of a new problem: since many possible keys map to the same small set of indices, two different keys can hash to the same slot, an event called a Collision.

Handling Collisions with Chaining

Chaining resolves collisions by storing all elements that hash to the same slot in a linked list, discussed earlier in this series, rooted at that slot.

CHAINED-HASH-INSERT(T, x):
  insert x at the head of list T[h(x.key)]

CHAINED-HASH-SEARCH(T, k):
  search for an element with key k in list T[h(k)]

CHAINED-HASH-DELETE(T, x):
  delete x from list T[h(x.key)]

Insertion is always O(1), since it simply prepends to a list without needing to search. Search and deletion depend on the list's length, which depends on how many keys have collided into that particular slot.

Analyzing Expected Performance

Define the Load Factor α = n/m, the average number of elements per slot, where n is the number of stored elements and m is the number of slots. Under the assumption of Simple Uniform Hashing — that any given key is equally likely to hash to any of the m slots, independent of other keys — the expected length of any chain is exactly α.

Expected time for an unsuccessful search: Θ(1 + α)
Expected time for a successful search:     Θ(1 + α)

If m is chosen proportional to n (so α = O(1)),
all operations run in expected Θ(1) time

This result connects directly to the probabilistic analysis techniques discussed earlier in this series: the expected search time combines the O(1) cost of computing the hash function with the expected chain length, which stays constant as long as the table size grows proportionally with the number of stored elements.

Designing Good Hash Functions

The entire expected-time analysis above depends on the hash function distributing keys roughly uniformly across slots. A poorly chosen hash function can degrade performance to that of a single linked list, Θ(n), regardless of the theoretical guarantees, if many keys collide into the same slots.

The Division Method

The simplest approach maps a key to a slot using the remainder after division:

h(k) = k mod m

This is fast to compute but sensitive to the choice of m. Choosing m as a power of two is a common mistake, since it makes h(k) depend only on the low-order bits of k, ignoring higher-order bits entirely, which can cause poor distribution for certain key patterns. Choosing m as a prime number not too close to a power of two generally produces better, more uniform distributions in practice.

The Multiplication Method

An alternative approach multiplies the key by a constant A between 0 and 1, extracts the fractional part, and scales it to the table size:

h(k) = ⌊m · (k · A mod 1)⌋

This method has the advantage that the specific value of m is not critical to its performance, unlike the division method, giving more flexibility in choosing the table size (often a power of two, for implementation convenience).

Open Addressing: An Alternative to Chaining

Open Addressing avoids linked lists entirely, storing all elements directly within the hash table array itself. When a collision occurs, the algorithm systematically probes alternative slots until an empty one is found, following a deterministic Probe Sequence determined by the key.

HASH-INSERT(T, k):
  i = 0
  repeat:
      j = h(k, i)
      if T[j] == NIL:
          T[j] = k
          return j
      else:
          i = i + 1
  until i == m
  error "hash table overflow"

Linear Probing

The simplest probe sequence, Linear Probing, checks consecutive slots after a collision:

h(k, i) = (h'(k) + i) mod m

This is simple and has good cache performance, discussed earlier in this series regarding memory hierarchy, since consecutive memory locations are checked. However, it suffers from Primary Clustering: long runs of consecutive occupied slots tend to form, since any key hashing anywhere within a cluster extends it further, making future collisions increasingly likely.

Quadratic Probing and Double Hashing

Quadratic Probing uses a quadratic function of the probe number to spread out probes more:

h(k, i) = (h'(k) + c₁i + c₂i²) mod m

Double Hashing uses a second, independent hash function to determine the step size between probes, generally producing the most uniform distribution of the three approaches and coming closest in practice to the theoretical ideal of uniform hashing.

h(k, i) = (h₁(k) + i · h₂(k)) mod m

The Deletion Problem in Open Addressing

Deletion in open addressing is more subtle than in chaining. Simply marking a slot as empty after deletion can break future searches, since a probe sequence for some other key might rely on passing through that now-empty slot to find its actual location further along. The standard solution uses a special DELETED marker distinct from NIL: searches continue past a DELETED marker, but insertions can reuse that slot.

Practical Considerations

Real-world hash table implementations must handle several practical issues beyond the core algorithm. As the load factor grows too high, performance degrades, so implementations typically Rehash — allocate a larger table and reinsert every element — once the load factor exceeds some threshold, such as 0.75. This resizing operation is expensive when it happens, but occurs rarely enough (roughly doubling the table size each time) that its cost, when averaged (or Amortized, a concept explored in depth later in this series) over many insertions, remains O(1) per insertion.

Why Hash Tables Are So Widely Used

Hash tables underlie many of the associative array, dictionary, and set implementations found in virtually every modern programming language's standard library. Their expected O(1) performance for search, insertion, and deletion makes them the default choice whenever fast key-based lookup is needed, a dramatic improvement over the O(log n) of balanced search trees, discussed later in this series, whenever the ordering of keys is not needed and only fast lookup matters.