Separate chaining

Cost and properties

search / insert	~n/m compares
rule of thumb	m ≈ n/5
worst case	n — every key in one list
ordered ops	none

Reference: Sedgewick & Wayne, §3.4.

Separate chaining in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class SeparateChainingHashST:
    # m independent lists. A key lives in the list its hash names, so a
    # search only ever examines keys that COLLIDED with it.

    def __init__(self, m=7):
        self.m = m
        self.chains = [[] for _ in range(m)]
        self.n = 0

    def _hash(self, key):
        h = 0
        for c in str(key):                # Java's String.hashCode
            h = (31 * h + ord(c)) & 0x7fffffff
        return h % self.m                 # mask the sign, then mod m

    def put(self, key, val):
        i = self._hash(key)
        for e in self.chains[i]:          # search the chain first
            if e[0] == key:
                e[1] = val                # already there: overwrite
                return
        self.chains[i].append([key, val])  # a miss: add to the chain
        self.n += 1

    def get(self, key):
        i = self._hash(key)
        for e in self.chains[i]:
            if e[0] == key:
                return e[1]
        return None

Why it works

The uniform hashing assumption

The analysis assumes every key is equally likely to hash to any of the m lists, independently. Under that assumption the number of keys in a list is tightly concentrated around n/m, so search and insert cost ~n/m compares. Keep m proportional to n (the course uses m ≈ n/5, resizing as needed) and that is a constant.

The assumption is doing real work: it is why a bad hash function is a correctness-adjacent bug, not just slow code. A hash that ignores part of the key sends everything to a few lists and the table degenerates into linked lists.

Writing hashCode

h = 31 * h + ord(c) mixes every character into the result, and 31 is odd and prime (multiplying by it is a shift and subtract, and it avoids the information loss of an even multiplier). Then & 0x7fffffff clears the sign bit before % m, because a negative index is not a bucket. In Java that mask matters even more — Math.abs(Integer.MIN_VALUE) is still negative.

Chaining vs probing

• Chaining degrades gracefully: performance drops smoothly as the table fills, and deletion is trivial (remove from a list).
• Linear probing uses less memory and has better cache locality, but needs the table half empty and deletion is genuinely awkward.

Both are constant time under uniform hashing. Which is faster depends on your data and your machine — measure.

What you give up

No ordered operations at all: no min, max, floor, rank, or sorted iteration — the hash deliberately destroys order. That is the trade against balanced BSTs, and it is why the course teaches both. Hash tables are also vulnerable to adversarial input: if an attacker can predict your hash, they can force every key into one bucket, which is a real denial-of-service vector in web servers.

What to try in the animation

Shrink m to force collisions and watch the chains — and the compare counts — grow. The hash shown is Java's String.hashCode, so these are the real bucket numbers.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• course example — m: 7 · insert: S E A R C H E X A M P L E · search: A Z
• too small a table — m: 3 · insert: S E A R C H E X A M P L E · search: A
• roomy table — m: 16 · insert: S E A R C H E X A M P L E · search: X

Open Separate chaining in the player →

The rest of Hash tables

• Linear probing One key per slot: on a collision, step right until you find an empty one.