Hash table visualization

A hash table stores keys so that you can add, find and remove one without looking at the others. It keeps an array of buckets and a hash function that turns any key into a bucket number. This lesson uses separate chaining: each bucket holds a linked list (the chain) of the keys that hash to it. The function here is h(k) = k mod 7, with 7 buckets.

How it works

1. insert(k) computes h(k), makes a node for k, and puts it at the front of that bucket's chain.
2. search(k) computes h(k) and walks only that chain, comparing each key with k.
3. remove(k) computes h(k) and walks that chain with prev and cur, exactly as in the linked list, then unlinks the node.

When two keys have the same remainder, they collide: they share a bucket and a chain. The table does not break; it just has a longer chain to walk.

Time and space complexity

• Average, O(1): the hash costs the same for every key, and if the keys spread out, a chain holds about n / m nodes, where m is the number of buckets. That ratio is the load factor. Real tables add buckets as it grows, to keep chains short.
• Worst, O(n): every key lands in the same bucket. The table is then one chain of n nodes, and search walks all of it. Try the preset "Everything in one bucket".
• Space, O(n): one node per key, plus the array of buckets.

A worked example

Insert the keys 50, 700, 76, 85, 92, 73 and 101 into a table of 7 empty buckets, with h(k) = k mod 7. The table lists the bucket each key hashes to, and the chain of that bucket afterwards, first node first.

After the seven inserts, bucket 0 holds 700, bucket 1 holds 92, 85, 50, bucket 3 holds 101, 73, bucket 6 holds 76, and buckets 2, 4 and 5 are empty. The load factor is 7 / 7 = 1.00 and the longest chain has 3 nodes.

search(50) computes h(50) = 1 and walks only that chain: it compares 92, 85 and 50, which is 3 comparisons, and it never looks at the other six buckets. remove(50) walks the same chain, stops with prev at 85 and makes 85's link skip the node. A second search(50) compares 92 and 85, reaches the end of the chain and returns null. A linear scan of 7 keys could need up to 7 comparisons for every search; here the work depends on the chain, not on the table.

Pseudocode

T is an array of m buckets, each NIL or the first node of a chain, and x.key and x.next are a node's key and link. The hash is the division method from CLRS section 11.3, and the extra + m keeps a negative key in range.

HASH(k, m)
    return ((k mod m) + m) mod m

CHAINED-INSERT(T, k)
    i = HASH(k, T.length)
    x = a new node with key k
    x.next = T[i]
    T[i] = x

CHAINED-SEARCH(T, k)
    x = T[HASH(k, T.length)]
    while x != NIL and x.key != k
        x = x.next
    return x                  // NIL if absent

CHAINED-DELETE(T, k)
    i = HASH(k, T.length)
    prev = NIL
    cur = T[i]
    while cur != NIL and cur.key != k
        prev = cur
        cur = cur.next
    if cur == NIL
        return false
    if prev == NIL
        T[i] = cur.next
    else
        prev.next = cur.next
    return true

Insertion has no loop, so it is O(1) even when the chain is long. Search and delete walk one chain, whose length is about the load factor on average.

When to use it, and when not to

• Use it to look things up by key: a dictionary, a set, a cache, counting how often each word appears.
• Avoid it when you need the keys in order, or all keys between two values. A hash scatters neighbors across buckets, so binary search on a sorted array does that better.

Where it is used

• Dictionaries and sets in languages. Python's dict and set and Java's HashMap are hash tables. They differ in how they handle a collision: Java keeps a chain in each bucket, as this lesson does, and Python probes for another free slot in the same array, a method called open addressing. Both give O(1) lookups on average.
• Caches and memoization. A program stores the result of a costly call under its input as the key, and later calls with the same input read the stored result instead of repeating the work. Only exact-key lookup is needed, which is what a hash table does best.
• Counting, duplicates and symbol tables. Counting words is a table from word to count. Finding duplicates is one pass that checks each value and inserts it. A compiler keeps a symbol table that maps each identifier name in the program to what it knows about it, an example CLRS gives in chapter 11.

Common mistake and edge cases

Variations and related ideas

Open addressing stores every key in the bucket array itself and probes other slots on a collision, so it needs no linked list but must keep the table partly empty. Real tables resize: when the load factor passes a limit, they allocate more buckets and move every key to the bucket its hash gives in the new size, which keeps chains short. Better hash functions, such as universal hashing, protect against keys chosen to collide (CLRS, section 11.3). If you need order, ranges or a guaranteed worst case, a binary search tree trades the O(1) average for O(log n) on a balanced tree. For fixed data that is searched often, a sorted array with binary search needs no extra structure.