Underlying Data Structure of a Dictionary/HashMap

Q: What is the underlying data structure of a Dictionary (HashMap)? A: A Dictionary/HashMap is backed by an array of buckets, where a hash function maps each key to a bucket index (typically hash(key) % capacity). Collisions (two keys hashing to the same bucket) are resolved either via chaining (each bucket holds a linked list or, in Java 8+, a balanced tree once a bucket gets large) or open addressing (probing for the next free slot). Average-case get/put is O(1), degrading to O(n) (or O(log n) with treeified buckets) under heavy collisions. The structure resizes (rehashes into a larger array) once a load-factor threshold is crossed to keep operations close to O(1).