HashMap internals 2: What is a bucket?
Inside, a HashMap is an array (the "table"), and each slot of that array is a bucket. A bucket holds zero or more entries, each a small Node object with four fields: hash, key, value and next.
- The table starts with 16 buckets, created on the first
put. - A hash code can be any of billions of values, so HashMap turns it into an index:
index = hash & (n − 1). With 16 buckets that keeps only the lowest 4 bits, giving an index from 0 to 15. - This trick only works because the number of buckets is always a power of two: n − 1 is then all ones in binary (15 = 1111), so
&works like a very fast% n. - First, HashMap spreads the hash with
h ^ (h >>> 16), mixing the high 16 bits into the low 16. Otherwise keys that differ only in their high bits would all land in the same bucket.
Example
static int spread(Object key) {
int h = key.hashCode();
return h ^ (h >>> 16); // exactly what HashMap.hash() does
}
static int bucketOf(Object key, int buckets) {
return spread(key) & (buckets - 1); // buckets is always a power of two
}
System.out.println(bucketOf("java", 16)); // 3
System.out.println(bucketOf("mango", 16)); // 15
System.out.println(bucketOf("book", 16)); // 7
System.out.println(bucketOf("cat", 16)); // 7 same bucket as "book"Common mistake
Thinking a HashMap stores its entries in order. Where an entry goes depends only on its hash, so iteration order looks random and can change when the map grows.
Under the hood
A null key is allowed once: HashMap gives it hash 0, so it always lives in bucket 0. Each Node costs about 32 bytes on a typical 64-bit JVM, plus the key and value objects themselves, so a HashMap of a million small entries uses tens of megabytes.
Check yourself
With 16 buckets, which bits of the (spread) hash choose the bucket?
How this connects
Know these first
Where this leads
Part of HashMap internals, part by part.
Was this lesson helpful?
Finished reading? Mark it complete to track your progress.