Card 09/ 09
Recap: Maps and HashMap Internals
Hashing to a bucket, collisions, tree buckets, resizing, and null keys, with where each was.
Maps come down to the five ideas below, each listed with the card that covers it.
| The idea | Where |
|---|---|
| A lookup hashes, picks one bucket, and searches only that bucket | How a HashMap Finds a Value: Hashing and Buckets |
| A collision keeps both entries; only an equal key replaces a value | Hash Collisions: Two Keys in the Same Bucket |
| An overloaded bucket becomes a tree at eight entries | HashMap Example: A Crowded Bucket Turns Into a Tree |
| Sixteen buckets, a load factor of 0.75, and a rebuild that moves everything | HashMap Resizing: The Load Factor and the Rebuild |
A TreeMap refuses null keys because it has to compare them | Null Keys: Allowed in HashMap, Refused by TreeMap |
A map's speed is borrowed from the key's hashCode, and nearly every map problem is that loan going bad.
← → move through sections and cards