How does a Java HashMap store key-value pairs internally, and how does it find a value by key?
- Array of buckets, each bucket = chain of Node<K,V>
- put = hash to index, store; get = same index, equals to match
- Collision = two keys, same bucket -> chained
- Amortized O(1); needs correct hashCode + equals
- Keys should be immutable
A HashMap keeps an array of buckets. It turns each key into a number (a hash), uses that number to pick a bucket, and stores the key and value there. To get a value it hashes the key again, jumps to the same bucket, and compares keys with equals to find the match.
solid answer ~40 slevel notes 4 levelsdeep dive ~3 mincommon follow-ups 2 questionsred flags 4 flagsrelated questions 9 questionsrelated topics 3 topicsreferences 3 links