Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Hash tables and hash functions

Build, analyze and use hash tables with well-designed hash functions; define load factor, uniform hashing, and evaluate average-case search/insert/delete costs with chaining.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Hash tables give near-constant-time lookup for keys, so engineers use them for symbol tables in compilers, caches in web systems, dictionaries and sets in software, and indexing in file systems and databases. Good hash functions and sound table design avoid long chains or clusters, keeping performance predictable under load.

Key ideas

  • Definition: A hash function h maps a key to an integer index: h: Key → {0, 1, …, m−1}, where m is the number of slots (buckets) in the table. Assumption: h is deterministic (same key maps to same index every time for a given table).
  • Definition: A hash table is an array of size m of buckets; each bucket can hold records directly (open addressing) or a small collection (e.g., a linked list) in the case of separate chaining. In this topic we focus on the table and hash functions; detailed collision resolution techniques like open addressing and full chaining design are covered in “Collision resolution: open addressing and chaining”.
  • Definition: A collision occurs when two different keys hash to the same index, i.e., h(k1) = h(k2) with k1 ≠ k2. Collision handling is mandatory.
  • Definition: The load factor α is the average number of records per bucket: α = n/m, where n is the number of stored records and m is the number of buckets. It quantifies how full the table is.
  • Law (uniform hashing assumption): Under the assumption of simple uniform hashing (each key is equally likely to hash into any of the m slots independently of other keys), the expected chain length (chaining) is α and expected search/insert/delete times are proportional to 1 + α. Assumptions: independent hashing; no adversarial keys; no resizing side-effects.
  • Definition: Universal hashing: A family H of hash functions h: U → {0, …, m−1} is universal if for any distinct x, y ∈ U, Pr_{h∈H}[h(x) = h(y)] ≤ 1/m; choosing h uniformly at random from H yields expected O(1 + α) performance even against adversarially chosen keys.
  • Theorem (expected time for chaining):
    • Unsuccessful search: Expected number of elements examined is Θ(1 + α).
    • Successful search: Expected number of elements examined is Θ(1 + α/2) when each position in the list is equally likely to hold the searched key (random insertion order). Exact expected examined elements is 1 + α/2 on average (1 for the key found plus α/2 other elements under the simple uniform hashing model). Sketch derivation commonly asked: For chaining, unsuccessful search must traverse the entire chain at h(k). Expected chain length = α, so the expected number of examined elements is α (plus O(1) to compute h(k)). For successful search, under simple uniform hashing with random insertion order (e.g., insert-at-head), the expected number of other elements examined before the key is α/2; adding the comparison with the key itself gives 1 + α/2 examined elements. Hash computation is O(1).
  • Definition: The division method of hashing chooses h(k) = k mod m for integer keys. Good choice of m avoids patterns that cause collisions (e.g., choose m prime and not close to a power of 2 when keys have modular patterns).
  • Definition: The multiplication method of hashing chooses h(k) = ⌊ m · frac(k · A) ⌋, where A is a real constant 0 < A < 1 and frac(x) is the fractional part of x. A common choice of A is approximately 0.6180339887 (about (√5 − 1)/2). Advantage: less sensitive to choice of m; m can be a power of 2.
  • Strings to integers: Practical string hashing often uses a polynomial rolling hash: for string s[0..L−1], interpret characters as integers c[i], and compute H = (((c[0]·B + c[1])·B + c[2]) …) mod M; then map to table with h(k) = H mod m. B is a base like 31 or 131. For data structures we target distribution, not cryptographic security.
  • Important distinction: A data-structure hash aims for speed and even spread to minimize collisions. A cryptographic hash (e.g., SHA-256) aims for preimage resistance and collision resistance; it is much slower and is not needed for typical hash tables in RAM.
  • Good-hash design guidelines used in exams:
    • Mix all parts of the key; small changes in key should change many bits of hash.
    • Avoid using only a prefix/suffix of the key.
    • For division method, choose m prime; avoid m sharing large common factors with typical key patterns (e.g., if keys are multiples of 10, do not pick m that is a multiple of 10).
    • Keep α bounded (e.g., α ≤ 1 for chaining, or a stricter bound for open addressing). Use resizing (rehashing) when needed; details in “Rehashing and extendible hashing”.
  • Definition: Perfect hashing means zero collisions for a fixed static set of keys; construction methods exist with two-level schemes and have O(1) worst-case lookup; this is covered in detail in “Perfect hashing”.
  • Definition: Rehashing means building a new table, usually larger m′, and reinserting all keys using the same or a revised hash function. Trigger condition: load factor exceeds a threshold.
  • Diagram to draw and label (for chaining): Draw a horizontal array of m boxes labeled 0, 1, …, m−1. From bucket 0, draw a vertical singly linked list with nodes labeled (k, v). From bucket 1, draw two nodes; from bucket 2, draw none; from some bucket j, draw three nodes to show different chain lengths. Label: “hash table (array)”, “bucket index”, “head pointer”, and “(key, value) node”. Also draw arrows from sample keys through a “hash function h(k)” box to the corresponding indices.

Formulas

  • h(k) = k mod m — Division method for integer keys; k (integer, unitless), m (integer, table size). Use when keys are integers and m is chosen well (preferably prime).
  • h(k) = floor( m · frac(k · A) ) — Multiplication method; A (real, 0 < A < 1), frac(x) is fractional part; k (integer or real cast), m is table size; use when you want reduced sensitivity to m.
  • Expected probes (chaining, unsuccessful) = α — Under simple uniform hashing; unitless count of examined elements.
  • Expected probes (chaining, successful) = 1 + α/2 — Under simple uniform hashing with random insertion order; unitless count.
  • Polynomial rolling hash: H = (…((c0·B + c1)·B + c2)…·B + cL−1) mod M — H is intermediate hash (unitless), ci is integer code of character i, B is base (typical 31 or 131), M is a large modulus (integer). Then map with h(k) = H mod m.
  • Programming syntax to remember (Python-like pseudocode):
    • idx = key % m — division method index
    • idx = int(m * ((key * A) % 1.0)) — multiplication method index
    • Chaining table init: table = [[] for _ in range(m)]
    • Insert/update in chaining: `for i,(k,v) in enumerate(table[idx]): if k==key: table[idx][i]=(key,val) break

else: table[idx].append((key,val))`

  • Search in chaining: next((v for k,v in table[idx] if k==key), None)

Worked examples

Example 1 — Python program: Hash table with separate chaining (integer keys, division method)

Complete program:

# Hash table with chaining, division method h(k) = k % m
# Supports: put k v, get k, del k, show, quit

import sys

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

    def _idx(self, key: int) -> int:
        return key % self.m

    def put(self, key: int, value: str) -> str:
        idx = self._idx(key)
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, value)
                return "UPDATED"
        self.buckets[idx].append((key, value))
        self.n += 1
        return "OK"

    def get(self, key: int) -> str:
        idx = self._idx(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        return "NOTFOUND"

    def delete(self, key: int) -> str:
        idx = self._idx(key)
        chain = self.buckets[idx]
        for i, (k, v) in enumerate(chain):
            if k == key:
                chain.pop(i)
                self.n -= 1
                return "DELETED"
        return "NOTFOUND"

    def show(self) -> str:
        lines = []
        for i in range(self.m):
            chain = self.buckets[i]
            if not chain:
                lines.append(f"{i}: None")
            else:
                s = " -> ".join(f"({k}:{v})" for k, v in chain)
                lines.append(f"{i}: {s} -> None")
        return "\n".join(lines)


def main():
    ht = HashTableChaining(m=7)
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        if line == "quit":
            break
        parts = line.split()
        cmd = parts[0].lower()
        if cmd == "put" and len(parts) >= 3:
            k = int(parts[1])
            v = parts[2]
            print(ht.put(k, v))
        elif cmd == "get" and len(parts) == 2:
            k = int(parts[1])
            print(ht.get(k))
        elif cmd == "del" and len(parts) == 2:
            k = int(parts[1])
            print(ht.delete(k))
        elif cmd == "show":
            print(ht.show())
        else:
            print("ERROR")

if __name__ == "__main__":
    main()

Sample input:

put 15 A
put 11 B
put 27 C
put 8 D
put 12 E
put 14 F
put 5 G
show
get 8
get 2
del 11
del 99
show
quit

Exact output:

OK
OK
OK
OK
OK
OK
OK
0: (14:F) -> None
1: (15:A) -> (8:D) -> None
2: None
3: None
4: (11:B) -> None
5: (12:E) -> (5:G) -> None
6: (27:C) -> None
D
NOTFOUND
DELETED
NOTFOUND
0: (14:F) -> None
1: (15:A) -> (8:D) -> None
2: None
3: None
4: None
5: (12:E) -> (5:G) -> None
6: (27:C) -> None

Notes:

  • With m = 7 and division method, indices are: 15→1, 11→4, 27→6, 8→1, 12→5, 14→0, 5→5.
  • Average chain length α = n/m = 7/7 = 1. Expected successful probes ≈ 1 + α/2 = 1.5; unsuccessful ≈ α = 1.

Example 2 — Python program: Effect of table size choice on collisions (division method)

Complete program:

# Compare bucket load distributions for two table sizes with patterned keys

keys = list(range(0, 92, 7))  # 0, 7, 14, ..., 91 (14 keys)

def bucket_counts(m):
    counts = [0] * m
    for k in keys:
        counts[k % m] += 1
    return counts

if __name__ == "__main__":
    m1 = 14
    m2 = 13
    c1 = bucket_counts(m1)
    c2 = bucket_counts(m2)
    print("keys:", keys)
    print("m = 14 counts:", c1)
    print("m = 13 counts:", c2)

Exact output:

keys: [0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91]
m = 14 counts: [7, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0]
m = 13 counts: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Model answer pattern (theory) — “State and explain the expected cost of successful and unsuccessful search in separate chaining under the simple uniform hashing assumption.”

  • Definition: Load factor α = n/m. Assumption: simple uniform hashing — each of the n keys is equally likely to hash into any of the m buckets independently.
  • Unsuccessful search: We compute h(k) and scan all elements in bucket h(k). Expected chain length equals α. Hence expected examined elements = α; adding O(1) for hash computation yields expected time Θ(1 + α). Exact expected examined elements is α.
  • Successful search: The target key is in its chain. Under simple uniform hashing with random insertion order, the expected number of other elements examined before the key is α/2; including the key itself, the expected examined elements are 1 + α/2. Computing h(k) is O(1), so the expected time is Θ(1 + α). Exact expected examined elements is 1 + α/2.
  • Conclusion: Keep α bounded (e.g., by resizing) to retain constant expected time per operation.

Common mistakes

  • Using only part of the key (e.g., first character) to hash strings, creating heavy skew; not mixing characters with a rolling/polynomial method.
  • Forgetting to update an existing key: inserting duplicates in the same bucket instead of replacing the value when keys are equal.
  • Ignoring load factor: not computing α and not triggering resizing; claiming O(1) time without stating the simple uniform hashing assumption.
  • Confusing hashing for data structures with cryptographic hashing; using SHA-256 in a performance-sensitive hash table example.
  • In deletion (chaining), removing the wrong node or breaking the chain pointers; not considering the empty bucket case.
  • For modulo arithmetic in code, not handling negative keys consistently across languages (Python’s % is non-negative; in some languages the behavior differs or needs adjustment).

For your exam

  • Short notes: properties of a good hash function; choice of table size; string hashing techniques. Full marks: examples showing good vs bad choices.
  • Derivations/proofs: expected time for successful/unsuccessful search in separate chaining; effect of load factor. Full marks: start with α = n/m and the uniform hashing assumption; show why expected chain length is α; compute expected position as (α + 1)/2.
  • Programs: implement hash table operations with chaining; demonstrate collisions and show table state. Full marks: correct indexing, update vs insert, proper deletion, and neat display.
  • Diagrams: array of buckets with linked lists; arrows from keys through h(k) to buckets. Full marks: labels for indices, chains, and (key, value) nodes.
  • Compare/contrast: division vs multiplication methods; when to choose which. Full marks: mention sensitivity to m, typical constants, and practical guidance.

Quick check

  1. Define load factor α and state its role in the expected time of operations with chaining.
  2. Why is choosing m = 14 a bad idea when keys are multiples of 7 under the division method? Suggest a better m.
  3. Write the index formula for the multiplication method and name one commonly used constant A.

Answers: 1) α = n/m, the average records per bucket; expected unsuccessful search examines ≈ α elements and successful ≈ 1 + α/2 under simple uniform hashing. 2) Because all keys k = 7t map to 0 or 7, causing heavy collisions; choose a prime like m = 13. 3) h(k) = floor(m · frac(k · A)); a common A ≈ 0.6180339887.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?