How do you design a Hash Table from scratch?

Difficulty: 8/10

collision resolution, hash functions, rehashing

Hash Table Design

I would first define the API and requirements, then choose a collision strategy, hash function, resizing policy, and key equality semantics. A practical implementation needs to correctly handle collisions, updates, deletion, resizing, empty states, and pathological input distributions.

javascript

1
Choose a bucket array and entry representation.
2
Implement deterministic hashing and bucket-index calculation.
3
Use separate chaining or open addressing for collisions.
4
Implement get, put, contains, and remove.
5
Use a load-factor threshold to trigger resizing.
6
Rehash all entries after resizing.
7

Scenario Questions

0-2 years experience

2-5 years experience

1We have a feature that caches recent API responses using a hash table. After a deployment, lookups are suddenly much slower. What could have gone wrong in your hash table implementation?

Follow-up Questions