Buckets and the index

Definition

A HashMap keeps its entries in an array of buckets. To pick a bucket it takes the key's hashCode, mixes the high bits into the low bits, and keeps only the low bits with a bit mask. That is how it jumps straight to the right place without searching.

Example code

How a key becomes a bucket number (simplified from the JDK source)

class Demo {
    static int bucketIndex(Object key, int tableLength) {
        int h = key.hashCode();
        int hash = h ^ (h >>> 16);              // spread the high bits into the low bits
        return (tableLength - 1) & hash;        // same as hash % tableLength, because the length is a power of two
    }

    public static void main(String[] args) {
        int tableLength = 16;                    // the default number of buckets
        for (String key : new String[] {"apple", "banana", "cherry", "date"}) {
            System.out.println(key + " -> bucket " + bucketIndex(key, tableLength));
        }
    }
}

// Output:
// apple -> bucket 1
// banana -> bucket 0
// cherry -> bucket 1
// date -> bucket 0