Build challenges · 4 steps · javascript · python

Hash Map

Construct a high-performance hash map with bucket arrays, modular hashing, collision chaining, and dynamic rehashing.

How do hash tables achieve average $O(1)$ lookups and insertions across millions of items?

In this build, you will construct a Hash Map from raw bucket arrays. You will:

  1. Implement bucket indexing and polynomial string hashing.
  2. Resolve hash collisions using separate chaining.
  3. Implement $O(1)$ key deletion and iteration.
  4. Add dynamic load-factor rehashing to prevent performance degradation as the table fills up.

The workspace

These files carry across every step. What you write in one step is what you start the next with.

Steps · 0 of 4 done

  1. Bucket Storage & Basic Hashing
  2. Collision Chaining & Deletion
  3. Size Tracking & Key Listing
  4. Dynamic Load-Factor Rehashing

Start anywhere. Open step 3 first and you are handed the reference build of steps 1 and 2, so every step stands on its own. Nothing here is locked behind anything else.

This build applies Hash Maps, Arrays & Traversal and Caching. Read the lesson first if it is unfamiliar — a recommendation, not a prerequisite.

Shorter practice on the same ideas