Hash Table Operations Under Load

Context

You’re joining a fintech team that serves 5–10 million daily active users and must keep P99 API latency under 50ms for balance checks and fraud rules. Many hot paths rely on in-memory key/value lookups (e.g., mapping user_id -> risk_profile, card_token -> account_id). Choosing and tuning the right data structure directly impacts latency, CPU cost, and tail behavior under traffic spikes.

Core Question

Explain the concept of a hash table (hash map/dictionary) and how its core operations work:

1. Operations & expected performance

   • How do insert/put, lookup/get, and delete/remove work at a high level?
   • What are the average-case and worst-case time complexities, and what conditions cause the worst case?

2. Under-the-hood mechanics

   • What is a hash function, and how does it map a key to an index in a backing array?
   • What is a collision, why is it unavoidable, and how do collision resolution strategies work?

3. Maintaining performance at scale

   • Define load factor. Why do implementations resize/rehash, and what does “amortized O(1)” mean in this context?
   • Discuss trade-offs between separate chaining and open addressing (probing) in terms of memory, cache locality, and behavior at high load.

Scope Guidance

Answer at the level expected of a mid-level engineer: describe the backing array + hashing, collision handling, resizing strategy, and complexity. You don’t need to reproduce a production-grade implementation, but you should be able to sketch how you’d build a basic one and explain the trade-offs clearly.