HashMap Bucket Indexing

Java HashMap maps a key's hash value to a table bucket by combining the hash with a bit-spreading step and then masking against a power-of-two table size. This makes bucket selection efficient while helping distribute keys across the table.

A HashMap stores entries in an internal array often called the table, where each array position represents a bucket. To select a bucket, Java derives an integer hash from the key and transforms it before using the table length.

For a table whose length is a power of two, the bucket position can be calculated as `(n - 1) & hash`, where `n` is the table length. This bitwise AND is equivalent to taking the hash modulo `n` for nonnegative values, but it is especially efficient for a power-of-two size.

Java HashMap also mixes bits from the key's hash before bucket selection. In the commonly used implementation pattern, the transformed value is `h ^ (h >>> 16)`. The purpose is to let higher-order hash bits influence lower-order bits, because the mask uses only the low bits.

If multiple keys map to the same bucket, HashMap handles the collision using entries associated with that bucket. In modern Java implementations, heavily populated buckets can be converted from a linked structure into a tree structure under specified conditions, improving worst-case lookup behavior.

Key points

• Bucket selection uses `(n - 1) & hash` when the table length `n` is a power of two.
• HashMap mixes high hash bits into low bits before masking.
• The mask uses low-order bits, so poor low-bit distribution can cause collisions.
• Different keys can produce the same bucket index; this is a collision, not necessarily a duplicate key.
• HashMap table sizes are maintained as powers of two during resizing.

Interview questions

How does Java HashMap determine which bucket a key belongs to?

HashMap obtains a hash value from the key and mixes some higher-order bits into the lower-order bits. It then uses the table length to select an array position. With a power-of-two table length `n`, the bucket index is calculated using `(n - 1) & hash`. The resulting integer is the bucket position used to locate candidate entries.

Why does HashMap use bit masking instead of ordinary modulo?

For a power-of-two table size, masking with `n - 1` selects the same low-order bits that determine the remainder modulo `n` for the relevant integer representation. This can be implemented as a simple bitwise operation. It also fits naturally with HashMap's resizing strategy, where table lengths double. The design therefore provides efficient indexing while maintaining a predictable relationship between capacity and bucket selection.

Why does HashMap spread the hash before calculating the bucket?

The bucket mask primarily examines low-order bits of the hash. If a key set has similar or poorly distributed low bits, many keys could therefore land in the same buckets even when their full hash values differ substantially. HashMap mixes higher bits into lower bits so more information from the original hash affects bucket selection. This can reduce avoidable clustering for imperfect hash functions.

What happens when two different keys map to the same bucket?

The two entries form a hash collision because their bucket indices are equal. HashMap then examines the entries stored in that bucket, comparing hash information and ultimately using `equals` to identify the matching key. If the keys are not equal, both mappings can coexist in the same bucket. In sufficiently large collision chains, modern Java implementations can use a tree-based structure under defined conditions.

Why is a power-of-two HashMap capacity important for bucket indexing?

A power-of-two capacity makes `n - 1` a contiguous low-bit mask, allowing bucket selection through bitwise AND. It also makes doubling the table size straightforward during resizing. When the table grows, the new capacity is twice the old capacity, and an entry's destination can be determined from an additional hash bit rather than recomputing a general modulo operation. This supports efficient resizing and indexing.