How do you design a Hash Table from scratch?
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.
- 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
Ensure key equality and hashing are consistent.
- 8
Define null-key behavior and duplicate-key semantics.
- 9
Consider iteration, memory overhead, concurrency, and security requirements.
- 10
Test collision-heavy, resize-heavy, empty, duplicate, and adversarial cases.
Follow-up Questions
- How would you implement resizing?
- How would you handle deletion with open addressing?
- How would you make the Hash Table thread-safe?