Hash Functions

What a hash function does

A hash function receives a key and returns an integer value called a hash code. A hash does not have to be a unique identifier for the key. Its purpose is to quickly produce a number that can be used to distribute keys across the internal structure of a hash table.

Determinism is essential for correctness: as long as a key has not changed, the same key must produce the same hash. Otherwise, after inserting a record, the table would not know where to look for it on the next access.

Equal keys and the same hashCode

In Java, hash-based collections use equals() and hashCode(). If two objects are equal according to equals(), their hashCode() values must be the same. The reverse is not true: the same hash does not mean that the objects are equal.

String first = new String("java");
String second = new String("java");

System.out.println(first.equals(second));
System.out.println(first.hashCode() == second.hashCode());

Both checks print true. A table can therefore use the hash first to narrow the search area quickly, and then compare the keys for equality.

Good distribution matters more than uniqueness

The number of possible keys is usually much larger than the number of buckets, so it is impossible to reserve a separate bucket for every key. A good hash function tries to distribute typical input data reasonably evenly so that too many records do not accumulate in one bucket.

After obtaining a hash, the table still needs to convert it into a valid index. For a simple example, we can use Math.floorMod(hash, capacity): this method also works correctly with negative hashes.