# Explain Hash Map Collisions and Operation Complexity Explain how a hash map stores and retrieves key-value pairs. Then focus on collisions: what does it mean for two different keys to map to the same bucket, and how can an implementation preserve both values and still find the correct one? Compare at least two collision-resolution strategies and give the expected and worst-case time complexity of lookup, insertion, and deletion. Include the role of equality checks, load factor, and resizing. ### Constraints & Assumptions - Distinct keys may have the same hash value or bucket index. - Hash equality alone is not key equality; the original key must still be compared. - Discuss both a well-distributed normal case and a collision-heavy worst case. ### Clarifying Questions to Ask - Are keys immutable while stored in the map? - Does the implementation need stable iteration order? - Is deletion frequent enough to affect the choice between chaining and open addressing? ```hint Separate placement from identity The hash narrows the search to a bucket or probe sequence; an equality comparison identifies the actual key. ``` ```hint Complexity depends on occupancy Relate the number of entries to the number of buckets and explain how resizing keeps ordinary bucket or probe lengths short. ``` ### What a Strong Answer Covers - Hash computation, bucket selection, and equality-based key matching. - Separate chaining and open addressing, including deletion implications. - Expected constant-time operations under controlled load and a suitable hash distribution. - Linear worst-case operations when collisions concentrate many keys. - Resize cost and why it is usually analyzed amortized over many insertions rather than per insertion. ### Follow-up Questions - What can go wrong if a mutable key changes after insertion? - How do tombstones work in open addressing? - What defenses can reduce adversarial collision attacks?