What are Hash Tables? Basics Explained

Scenario context

A hash table gives you near-O(1) lookups, inserts, and deletes by using a hash function to map keys to array indices. The tradeoff: collisions (when two keys hash to the same slot) must be handled, and a full hash table must be resized.

Python dict uses open addressing with compact arrays (since Python 3.6). Entries are stored in an incrementally-growing compact array indexed by insertion order, with…

This walkthrough focuses on Why Python Dicts Are Fast.

Before making a design choice, clarify:

• Python dict uses open addressing with compact arrays (since Python 3.6).
• Entries are stored in an incrementally-growing compact array indexed by insertion order, with a separate hash table of indices pointing into it.
• This gives: - Fast iteration (compact memory, no pointer chasing).

Concepts in play: hash-tables-and-bloom-filters, database-indexing, api-gateway, jvm-internals-and-garbage-collection

Stage 1 — The Magic Mailroom Stamp

• Imagine a mailroom with 100 drawers.
• A magic stamp converts any employee name to a number 1–100.
• Stamp "John" → you get 42 → open Drawer 42.
• That stamp is a hash function .

Observable outcome: That stamp is a hash function .

Stage 2 — Hash Table Fundamentals

• A hash table combines two simple ideas into a data structure with near-constant-time performance: 1.
• An array provides O(1) access by index: array[42] is instant.
• A hash function converts any key (string, integer, object) to an index: h("john") → 42 .
• Together: given any key, compute its index in one step, then access the array slot directly.

Observable outcome: Together: given any key, compute its index in one step, then access the array slot directly.

Stage 3 — Deep Dive: Array + Hash Function

• Deterministic: Same input always produces the same output.
• Uniform: Keys distribute evenly to minimize collisions.
• Simple hash function (NOT production-quality): Python's built-in hash() uses SipHash (cryptographically secure version) to prevent hash flooding attacks.

flowchart LR
    Key[Key: 'cat'] --> HashFn["Hash Function h('cat') = 2"]
    HashFn --> Array[Array [0][1][2: 'catmeow'][3]...]
    Array --> Value[Value: 'meow']

def simple_hash(key: str, size: int) -> int:
    return sum(ord(c) for c in key) % size

Observable outcome: Simple hash function (NOT production-quality): Python's built-in hash() uses SipHash (cryptographically secure version) to prevent hash flooding attacks.

Stage 4 — How a Hash Table Handles a Lookup

• The lookup flow for key "alice" in a hash table with separate chaining: Three scenarios during lookup: 1.
• Direct hit: array[index] contains exactly the target key → O(1).
• Collision chain: array[index] has multiple entries → scan the short chain → O(k) where k = bucket length (typically 1–2 with good load factor).
• Miss: The slot is empty → key not in table → O(1).

flowchart TD
    K[Key: 'alice'] --> HF["Hash Function: h('alice') = 7"]
    HF --> IDX[Array index 7]
    IDX --> BK[Bucket 7: [('alice', 25), ('charlie', 30)]]
    BK --> SCAN{Scan bucket: key == 'alice'?}
    SCAN -->|Match found| RET[Return value: 25]
    SCAN -->|No match| MISS[Return None / KeyError]
    style RET fill:#90EE90
    style MISS fill:#FFB6C1

Observable outcome: Miss: The slot is empty → key not in table → O(1).

Stage 5 — Collisions: When Two Keys Land in the Same Slot

• Given a finite array, two different keys will eventually map to the same slot.
• Example: - hash('cat') = 2 → Stored at index 2.
• • hash('bird') = 2 → Collision at index 2!
• Two collision resolution strategies: Separate Chaining Each slot holds a linked list of key-value pairs.

index 2: [('cat', 'meow') → ('bird', 'tweet')]

hash('cat') = 2 → store at 2
hash('bird') = 2 (full) → probe 3 → store at 3

Observable outcome: Two collision resolution strategies: Separate Chaining Each slot holds a linked list of key-value pairs.

Stage 6 — Deep Dive: Load Factor and Rehashing

• Load factor = (number of entries) / (array capacity).
• As the table fills up (load factor → 1.0), collisions increase and performance degrades.
• Standard practice: rehash when load factor exceeds 0.75 .
• Create a new array 2× the size.

flowchart TD
    A[Insert new key] --> B{Load factor > 0.75?}
    B -- No --> C[Insert into current array]
    C --> D["O(1) average"]
    B -- Yes --> E[Allocate 2x array]
    E --> F[Re-hash all existing keys]
    F --> G[Insert new key]
    G --> H[Old array GC'd]
    H --> I["Amortized O(1) per insert"]

Observable outcome: Create a new array 2× the size.

End-to-end outcome

Python dict uses open addressing with compact arrays (since Python 3.6).

Alternatives considered

The source focuses on one primary design. A second architecture is not compared, so no alternative is invented here.

Failure and degraded modes

Trade-offs & Failure Modes: Trade-offs, Failure Modes & Decision Guide: Hash Tables vs Others

• Detection: Choose hash table when: You need fast key-value lookup and don't need ordering or range queries.
• User or operator impact: Choose hash table when: You need fast key-value lookup and don't need ordering or range queries.

What Hash Tables Teach You About Trade-offs

• Detection: - O(1) average is not O(1) guaranteed.
• User or operator impact: - O(1) average is not O(1) guaranteed.