Hash Functions

A hash table is built on top of an array. The hash function is the bridge between the key you care about and the array index the implementation can access quickly. Given a key such as an integer, string, or object, the table computes a hash value, mixes it, and maps it to a bucket index.

The goal is not to sort keys or preserve their original meaning. The goal is to distribute keys across buckets so lookup can inspect a small local area instead of scanning the whole collection. That is why a HashMap can usually answer containsKey(x) or get(x) in expected O(1) time.

A good hash function is deterministic, uniform, and fast. Deterministic means the same key produces the same hash whenever the table asks for it. Uniform means common inputs spread broadly across buckets rather than clustering in a few locations. Fast means hashing is cheap enough that it does not dominate the cost of the operation.

Uniformity matters because a hash table is only as balanced as its buckets. If many unrelated keys map to the same bucket, lookup begins to look like a local search inside that bucket. In interviews, this is the reason hash-table operations are called expected O(1) rather than guaranteed O(1) for every possible input.

Java separates identity into two methods: hashCode() chooses the bucket family, and equals() confirms whether two keys are actually the same key. The required contract is: if a.equals(b) is true, then a.hashCode() == b.hashCode() must also be true. The reverse is not required, because different keys are allowed to collide.

This contract is a correctness rule, not a performance detail. If two equal objects produce different hashes, a HashMap may store them in different buckets and fail to find an existing key. If many unequal objects produce the same hash, the map can still be correct, but it becomes slower because collisions increase.

Many hash tables keep the internal array capacity as a power of two. That allows the bucket index to be computed with index = hash & (capacity - 1), which is a fast way to keep only the low bits that fit inside the current array. The implementation may also mix the hash first so information from high bits can affect the final bucket.

The number of filled entries compared with the number of buckets is the load factor. A load factor near zero wastes memory but makes collisions rare. A high load factor saves memory but increases bucket crowding. Java HashMap commonly resizes when the table grows past its threshold, trading occasional rehashing work for consistently low expected lookup cost.