Implement a Hash Map 1

Implementing an open-addressing hash map in C++

This medium-difficulty coding problem tests your ability to build a cache-friendly hash table from scratch using linear probing for collision resolution. Quant firms value custom data structure implementations because standard library containers can be tuned to specific access patterns and latency requirements. Your task is to implement core hash-map operations—insert, retrieve, contains, and erase—while managing automatic resizing and handling the subtle correctness issues that arise from open addressing.

The main challenges are: correctly implementing linear probing to find both insertion slots and existing keys; managing deletion without breaking the probing chains that subsequent lookups depend on; and triggering resizes at the right load factor threshold while rehashing all elements into the new capacity. Strong solutions explicitly track which slots are occupied versus tombstoned, handle the boundary cases around wraparound and full tables, and reason carefully about when resizes must occur.

• Hash function design and modular arithmetic for slot mapping
• Linear probing and collision chain integrity
• Load factor thresholds and dynamic resizing with full rehashing
• Tombstone marking versus physical deletion
• Template class design and exception safety