Hash Table

The problem

Suppose you store 1 million student records and want to find the one with roll number 2023CS117. An array needs O(n) scanning; a sorted array with binary search needs O(log n). A hash table can do it in O(1) on average — about the same time for 10 records or 10 million.

The idea: turn the key into an index

A hash function converts a key into a bucket number:

index = hash(key) mod m       (m = number of buckets)

Then we store the item in table[index]. To find it later, we compute the same hash and jump straight there — no searching.

Analogy: a library where the shelf number is calculated from the book title. You never browse; you compute the shelf and walk straight to it.

In the 3D model, the table has m = 7 buckets and the hash function is h(k) = k mod 7.

What makes a good hash function?

• Deterministic — the same key always gives the same index.
• Fast to compute.
• Spreads keys evenly across buckets, so few collisions happen.

For strings, a common choice is a polynomial hash: h(s) = (s[0]·31^(n−1) + s[1]·31^(n−2) + … ) mod m.

Collisions

There are infinitely many keys but only m buckets, so two different keys will eventually get the same index. That’s a collision. In the model, 15, 22 and 29 all give k mod 7 = 1. There are two classic fixes.

1. Separate chaining

Each bucket holds a linked list of everything that hashed there. Insert → add to the list. Search → hash, then walk that one (short) list. This is simple and never “fills up”.

2. Open addressing — linear probing

Every slot holds at most one key. If the slot is taken, try the next slot: (i + 1) mod m, then the next, and so on. Searching probes the same way until it finds the key or an empty slot.

Deleting is tricky: if we simply empty a slot, a later search might stop there and miss a key that had probed past it. So we leave a tombstone (“DELETED”) that searches skip over but inserts may reuse.

Load factor and rehashing

The load factor α = n / m (keys ÷ buckets) controls speed. As α grows, chains get longer (or probes get longer). Real implementations resize — typically doubling m and re-inserting every key — when α passes about 0.75 (Java’s HashMap) or 2/3 (Python’s dict). Resizing is O(n) but rare, so operations stay O(1) amortised.

Code

class HashTable:
    """Separate chaining with Python lists as the chains."""
    def __init__(self, m=7):
        self.m = m
        self.buckets = [[] for _ in range(m)]

    def _h(self, key):
        return hash(key) % self.m

    def put(self, key, value):
        bucket = self.buckets[self._h(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value            # update existing key
                return
        bucket.append([key, value])

    def get(self, key):
        for k, v in self.buckets[self._h(key)]:
            if k == key:
                return v
        raise KeyError(key)

ages = HashTable()
ages.put("asha", 19)
ages.put("ravi", 21)
print(ages.get("ravi"))     # 21

# In practice just use the built-in dict / set:
d = {"asha": 19, "ravi": 21}
print(d["asha"], "ravi" in d)

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, int> age;   // a hash table
    age["asha"] = 19;                 // O(1) average insert
    age["ravi"] = 21;

    cout << age["ravi"] << "\n";      // O(1) average lookup
    if (age.count("meena") == 0) cout << "not found\n";

    age.erase("asha");                // O(1) average delete
    cout << "buckets: " << age.bucket_count()
         << ", load factor: " << age.load_factor() << "\n";
}

Hash table vs other structures

Need	Best choice
“Is this key present?” / lookup by key	Hash table — O(1) average
Keys in sorted order, range queries (“all marks 60–80”)	Balanced BST / TreeMap — O(log n)
Access by position	Array — O(1)

Where are hash tables used?

• Python dict and set, Java HashMap/HashSet, C++ unordered_map, JavaScript objects and Map.
• Caches (e.g. remembering web pages or computed results — memoization).
• Database hash indexes, compilers’ symbol tables, counting word frequencies.
• Coding interviews: “two sum”, “find duplicates”, “group anagrams” are all hash-table problems.

Common mistakes

• Assuming O(1) is guaranteed — a bad hash function (or an attacker) can push everything into one bucket.
• Using mutable objects (like Python lists) as keys — if the key changes, its hash changes and it gets “lost”.
• Forgetting that hash tables do not keep keys in sorted order.