How does HashMap work internally and what is its time complexity?
TL;DR: HashMap stores key-value pairs in buckets indexed by key.hashCode % bucketCount. Lookup/insert/delete are O(1) average case. Collisions handled via chaining or open addressing. Worst case O(n) when all keys hash to the same bucket.
Full Answer
Internal Structure
A HashMap is an array of buckets. When you call map[key] = value: compute hashCode → map to bucket (hashCode % size) → store (key, value) in that bucket. Multiple keys can hash to the same bucket (collision).
Collision Handling
Dart's HashMap uses a combination of open addressing and chaining. When too many collisions occur (load factor > threshold), the map rehashes — doubles the bucket count and redistributes entries. Rehashing is O(n) but amortized O(1).
If you override == without overriding hashCode, HashMap breaks. Objects that are equal must have the same hashCode or they'll be stored in different buckets and never found.
Code Examples
Origin Set lookup: ~1µs List lookup: ~5000µs
Common Mistakes
- ✗Using mutable objects as Map keys — if the object changes after being inserted, hashCode changes and the entry is lost
- ✗Forgetting that null keys are allowed in HashMap but not in every Map implementation
Interview Tip
Explain the three rules: (1) equal objects must have equal hashCodes, (2) hashCode should be consistent for the same state, (3) good hashCode spreads values uniformly. Object.hash() handles rule 3 automatically.