Introduction to Hash Tables

Mechanism

A hash table gets O(1) average lookup by never searching at all: a hash function H(key) computes an array index directly from the key's bits, so insert/search/delete jump straight to a bucket instead of scanning or comparing keys one by one. The table trades the O(log n) comparison-based bound of balanced trees for O(1) expected time by spending memory on a sparsely-filled array and accepting that different keys can collide on the same index — handled by chaining (a linked list/bucket per slot) or open addressing (probe to another slot).

Recognize the pattern

• Need "have I seen this before?" / membership checks faster than O(n) scan → use a Set.
• Need to map arbitrary keys (strings, tuples, objects) to values with fast lookup, no ordering required → use a Map/HashTable.
• Counting frequencies, grouping by key, detecting duplicates, caching computed results (memoization) → hash table is the default tool.
• Tell-tale phrasing in problems: "find pairs that sum to X", "first repeating element", "group anagrams", "has this appeared already".

Brute force → optimal

Brute force: keep records in an unsorted array/list; Search(key) scans every element comparing keys → O(n) per lookup, O(1) extra space.

Optimal (hash table): Insert/Search/Delete compute index = H(key) and jump to that bucket → O(1) expected time per operation, O(n) extra space for the bucket array plus chain nodes. The cost moves from CPU time (scanning) to memory (a larger, sparser array) and to occasional rehashing when the array fills up.

Complexity, derived

Let n = number of stored entries, m = number of buckets, load factor α = n/m.

• Search/Insert/Delete (chaining): H(key) is O(1) (fixed number of arithmetic/bit ops regardless of n). Once at the bucket, we walk its chain. Under a uniform hash function, keys distribute evenly, so expected chain length = n/m = α. Total expected cost = O(1) hash + O(α) chain walk = O(1 + α). Keeping α bounded by a constant (resize when α exceeds ~0.75) makes this O(1) amortized.
• Worst case: if all n keys collide into one bucket (bad hash function or adversarial input), the chain degenerates to a list → O(n) per operation.
• Resizing (amortized): doubling the array forces a full rehash because each key's bucket index depends on m (or the bit mask) — changing m changes the home bucket of nearly every key. That rehash of all n entries costs O(n), but happens only every O(n) insertions (once α crosses the threshold again), so amortized cost per insert stays O(1) — the same argument used for dynamic array (ArrayList) growth.
• Space: O(n + m) — m is kept proportional to n (m = n/α), so this is O(n).

Traced example (toy model)

This is a simplified pedagogical model, not a trace of any real library. Table size m = 5, hash H(key) = key mod 5. Insert keys 12, 7, 17, 3 in order (chaining on collision):

Search(17): H(17)=2 → jump to bucket2 → walk chain [12, 7, 17] comparing keys → found after 3 comparisons (worst-case within this bucket), instead of scanning all 4 entries in the whole table. Note: this m=5 layout is a hand-traced toy model built to make chaining and collisions visible. A real production hash table (see the java.util.HashMap example below) uses a different table size and hash-spreading strategy, so it will not necessarily produce the same collisions for the same keys.

Pitfalls

• Mutable keys: mutating an object after inserting it changes its hashCode, so it becomes unfindable — its bucket location no longer matches. Use immutable keys (String, boxed numbers, custom classes overriding hashCode/equals consistently and never mutated post-insert).
• hashCode/equals contract violation: in Java, if you override equals() you must override hashCode() consistently, or logically-equal keys land in different buckets and lookups silently miss.
• Poor hash function / clustering: a bad H(x) (e.g., always returning the same bucket, or correlated with input patterns) collapses average O(1) into worst-case O(n).
• Ignoring load factor: never resizing lets chains grow unbounded, degrading toward O(n) per op.
• Assuming ordering: hash tables give no iteration order guarantee (plain HashMap) — don't rely on insertion or sorted order.
• Conflating toy models with real implementations: a hand-traced example with a small table size (e.g., m=5, key mod 5) is built to demonstrate the chaining mechanism, not to predict the exact bucket layout of a real library's hash table, which uses a different capacity and hash-spreading function.
• Unsalted hashing in public APIs (Hash Collision DoS): Neglecting randomized hashing allows attackers to craft colliding string payloads, forcing maps into linear scans (O(n)) and browning out CPU cores. (See details in Hashing, Collisions, Overflow, and Resizing).

When to use / when not

Use a hash table when you need fast key-based lookup/insert/delete and don't care about ordering — frequency counts, caches, deduplication, index lookups. Not when you need sorted iteration or range queries (min/max/floor/ceiling) — use a balanced BST/TreeMap instead, which gives O(log n) for all ops but supports ordered traversal and range queries that a hash table cannot do faster than O(n log n) (sorting first). Also avoid when keys are small dense integers with a known bound — a plain array indexed directly is simpler and guarantees true O(1) worst case with no hashing/collision overhead. And for tiny n (a handful of keys), a plain linear scan can beat the hash table on constant factors.

From toy model to real java.util.HashMap

The mod-5 trace above is a simplification for teaching chaining, not how java.util.HashMap actually indexes. In the real JDK implementation: Integer.hashCode() returns the raw int value; HashMap.hash() only XORs in the high 16 bits of the hashCode with the low 16 bits (a spreading step that matters for large or poorly-distributed hashCodes, but is a no-op for small ints); and with the default initial capacity of 16, the bucket index is hash & 15 (a bitmask, not mod 5). Under that real scheme: 12 & 15 = 12, 7 & 15 = 7, 17 & 15 = 1, 3 & 15 = 3 — four different buckets, so none of these four keys actually collide in a default-capacity HashMap. The code below reflects that real behavior; treat the earlier trace purely as a mechanism illustration.

import java.util.*;

class QuickDemo {
    public static void main(String[] args) {
        Map<Integer, String> ht = new HashMap<>();
        ht.put(12, "Book-A");
        ht.put(7, "Book-B");   // default capacity 16: 12&15=12, 7&15=7 -> different buckets, no collision here
        ht.put(17, "Book-C");  // 17&15=1 -> also a distinct bucket
        ht.put(3, "Book-D");   // 3&15=3 -> also distinct

        System.out.println(ht.get(17));   // O(1) expected -> "Book-C"
        ht.remove(7);                      // O(1) expected
        System.out.println(ht.containsKey(7)); // false
    }
}

Takeaways

• O(1) expected time comes from computing an index instead of comparing keys; it degrades to O(n) if the hash function clusters or the load factor is left unbounded.
• Chaining trades a little memory (list nodes) for graceful collision handling; capacity/resizing keeps α bounded so cost stays amortized O(1).
• A hand-traced toy model (small m, mod hashing) is for building intuition about the collision mechanism — it is not a prediction of how a real library's hash table will lay out the same keys, since real capacity and hash-spreading differ.
• Pick hash tables for unordered fast lookup; pick a balanced BST when you need sorted order or range queries.

Recall: Why does doubling-and-rehashing keep insertion at amortized O(1) instead of making it O(n) per insert?

Synthesized from standard hash table theory (CLRS-style analysis of chaining/load factor), the source notes on naive Hash Table implementation (Insert/Search/Delete, modular hashing), and java.util.HashMap's documented default capacity (16) and hash-spreading behavior.