Wiki
Advanced13 min read

Hash tables

A hash function turns a key into an array index, so lookup is one computation — until two keys collide.

A BST searches in logarithmic time by keeping everything ordered. A hash table throws ordering away and goes straight to the answer: run the key through a hash function to get an array index, then look there. That is O(1)O(1) on average and needs no comparisons — as long as two different keys do not land on the same index.

A coat check, not a library

A library finds a book by category and shelf order. A coat check takes your ticket number, computes where to look, and hands you the coat immediately — no searching at all. The table is only as good as its spreading: if everyone receives the same number, the clerk must rummage.

Insert keys below, shrink the table, and watch collisions appear. Toggle between chaining and linear probing to see two ways of handling them.

Insert keys, shrink the table, and watch collisions appear

size
load 0.71 · collisions 1

bucket 0

bucket 1

bird

bucket 2

bucket 3

catant

bucket 4

fish

bucket 5

bucket 6

dog

Good hashing scatters keys uniformly; collisions are then rare, so the average cost of insert and lookup stays close to O(1). Push the load factor past roughly 0.7 and both chaining and probing degrade — which is why real hash tables resize (rehash) when they fill.

Hash, then index

A hash function maps an arbitrary key to an integer; the index is that integer modulo the table size. A good function is deterministic (same key, same index), uniform (spreads keys evenly), and fast. For strings, a polynomial rolling hash is standard:

h=(∑isi⋅b k−i) mod mh = \left(\sum_{i} s_i \cdot b^{\,k-i}\right) \bmod m

The base bb and modulus mm must be chosen to avoid patterns; the same construction powers the Rabin-Karp string matcher in a later lesson.

Collisions are inevitable

By the pigeonhole principle, distinct keys must sometimes share an index. Two families of fixes:

  • Chaining stores a list per bucket and appends colliding keys. A bucket of length kk costs O(k)O(k) to search, so the average is O(1+α)O(1 + \alpha) where α\alpha is the load factor (keys ÷ buckets).
  • Open addressing keeps everything in the array and probes forward (linear probing) until it finds a free slot. Deletion needs tombstones, or it breaks the probe chain.

Chaining is simpler; open addressing has better cache behaviour in languages where the array is compact.

The load factor is the control knob

As α\alpha grows, collisions multiply and the constant in "average O(1)O(1)" grows with them. Real hash tables resize — allocate a larger array and re-insert every key — once α\alpha crosses a threshold (Python's dict grows around two-thirds full, and resizes under a memory cap too). Rehashing is O(n)O(n), but spread over the insertions that caused it the amortised cost is still O(1)O(1).

Hashing assumes keys do not change

A key's index is computed from its value, so a mutable key whose hash changes after insertion becomes unfindable. This is why dict keys must be immutable and hashable: lists and sets cannot be keys, but tuples (of hashables) and strings can.

Worst case, a hostile input can force every key into one bucket and degrade the table to O(n)O(n) per operation. This is why production hash functions are randomised per process — an attacker cannot predict the buckets.

Illustrative vs real

The explorer uses a tiny table and simple strings so collisions happen often and are visible; real tables are sized in powers of two or primes and hold thousands of entries. It uses a textbook polynomial hash rather than Python's SipHash. The behaviour — average O(1)O(1), collision handling, resizing — is the same; only the numbers differ.

Check yourself

Eduspheria wiki · Programming & Data Structures, Data structures

0 / 5 answered

  1. 1What is the average-case cost of lookup in a well-sized hash table?
    Multiple choice
  2. 2A table has 100 buckets and 75 keys. What is its load factor?
    Numeric answer
  3. 3Which collision strategy stores a list of entries in each bucket?
    Short answer
  4. 4A Python list is a valid dictionary key.
    True / false
  5. 5If every key hashes to the same bucket and the table uses chaining, how many entries must be scanned in the worst case with 8 keys?
    entries
    Numeric answer

From the assignment paper

Modeled on NITJ AI-507, Assignment/Quiz

0 / 5 answered

  1. 1What is double hashing?
    Multiple choice
  2. 2When a collision occurs, what does open addressing do?
    Multiple choice
  3. 3Which collision-resolution technique keeps a list of entries inside each bucket?
    Multiple choice
  4. 4What is the main disadvantage of an array-based dictionary implementation?
    Multiple choice
  5. 5What does a tree-based dictionary implementation such as a binary search tree offer?
    Multiple choice

Where next: graphs — the most general structure, where any node may connect to any other.