Data Structures #2 — Hash Table

A hash table (hash map) is the data structure behind JavaScript's Map, objects, and Set. It provides O(1) average lookup by converting a key into an array index via a hash function. This article builds one with collision handling and dynamic resizing.

Prerequisites: Data Structures #1 — Linked List

1. The Hash Function — Key to Array Index

A hash function maps arbitrary keys to valid array indices:

2. Hash Table with Separate Chaining

When two keys hash to the same bucket (collision), chain them in a linked list:

3. Hash Collision Demonstration

Key Takeaways

• Hash table = hash function + array of buckets + collision handling.
• Load factor = size / capacity. Resize (usually double) when it exceeds 0.75.
• Resizing rehashes all entries — O(n) operation, but amortized over many inserts.
• Chaining (linked list per bucket) is simplest. Open addressing is an alternative (store collided entries in nearby empty slots).
• JavaScript's Map uses a hash table internally with deterministic iteration order.

Next: Data Structures #3 — LRU Cache — hash map + doubly linked list for O(1) get and put.