Underlying Data Structure of a Dictionary/HashMap

Problem What is the underlying data structure of a Dictionary / HashMap, and how does it achieve average O(1) lookup?

Be ready to discuss

• Core layout: an array of buckets, with a hash function mapping each key to an index, typically hash(key) % capacity (or a mask when capacity is a power of two).
• Hash quality: how a poor or adversarial hash function clusters keys into few buckets, and why languages mix/spread hash bits before indexing.
• Collision resolution by chaining: each bucket holds a linked list, treeified into a balanced tree in Java 8+ once a bucket exceeds a threshold, bounding worst case at O(log n).
• Collision resolution by open addressing: linear/quadratic probing or double hashing, plus the tombstone problem on deletion and why load factor matters more here.
• Complexity: average-case O(1) get/put, degrading to O(n) with chaining under heavy collisions; resizing rehashes into a larger array once the load-factor threshold is crossed, amortizing to O(1).
• Key requirements: equality and hash consistency, and why mutating a key after insertion strands the entry in the wrong bucket.