دوال التجزئة (Hash functions)

Written Explanation

What a hash function does

A hash function takes a key (a name, a number, an object) and returns an integer called the hash code. In Java the function is hashCode(), which returns an int: a number between about minus two billion and plus two billion.

"Ana".hashCode();   // 65972, and it is the same every time

The hash code is not a secret code and not an encryption. It is only a number computed from the key, cheap to calculate, and used to decide where the key belongs.

The rules

Every usable hash function follows two rules, and a good one has a third quality.

1. Deterministic. The same key gives the same number every time. If "Ana" gave 5 today and 9 a moment later, you could never find her letter again. (The Java documentation limits this slightly: the number must stay the same within one run of a program, as long as the data used by equals does not change. It need not be the same on the next run.)
2. Consistent with equals. If a.equals(b) is true, then a.hashCode() == b.hashCode() must be true. You met this in the equals/hashCode lesson. Two equal keys must land in the same mailbox, or the clerk would look in the wrong box.
3. Well spread (a quality, not a rule). Different keys should usually give different numbers, scattered widely, so they do not pile up.

The reverse of rule 2 is not a rule. Different keys may share a hash code. The Java documentation says this is allowed, while noting that distinct results for unequal objects can improve hash table performance. Two different keys with the same hash code is a collision.

Why collisions cannot be avoided

An int has about 4.3 billion possible values, but there are far more possible strings than that. By the pigeonhole idea (more pigeons than holes), some different keys must share a number. So a collision is not a bug in a hash function; it is a fact of life. What we want is for collisions to be rare and scattered, not common.

A hash function you can compute by hand

String.hashCode() is a polynomial hash. The Java documentation gives the formula

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the character at position i (as a number) and n is the length. The empty string gives 0. The same result comes from a simple loop: start with h = 0, and for each character do h = 31 * h + character.

For "Hi": H is 72 and i is 105, so 72 * 31 + 105 = 2337. For "Ana": A is 65, n is 110, a is 97:

• after A: 65
• after n: 65 * 31 + 110 = 2125
• after a: 2125 * 31 + 97 = 65972

That matches what Java prints. Two things to notice: each character changes the result, and the order matters, because earlier characters get multiplied again and again.

A bad hash function, and why

Suppose we add the characters instead of multiplying:

static int sumHash(String s) {
    int h = 0;
    for (int i = 0; i < s.length(); i++) h += s.charAt(i);
    return h;
}

This is deterministic, and equal strings give equal numbers, so it obeys both rules. But it ignores order: "listen" and "silent" use the same letters, so they get the same number. Worse, all words of similar length produce numbers in a narrow range. Many keys will collide. The function is valid but poorly spread, and in the next lessons you will see that a poor spread costs speed.

Multiplying by 31 fixes the order problem, because a letter in position 1 now counts differently from the same letter in position 5. The number 31 is an odd prime commonly used in this style of hash. Its choice is a convention more than a law, so do not worry about why not 30 or 33.

Hash codes can be negative and can overflow

The sum 31 * h + character is computed in int arithmetic, and int overflows silently, wrapping around instead of failing. So hash codes of longer strings are often negative, such as -2048738041. This is fine for a hash code. But a negative number cannot be an array index, so the next lesson must turn the hash code into a valid index. Do not use Math.abs for that: according to the Java documentation, Math.abs(Integer.MIN_VALUE) returns Integer.MIN_VALUE, which is still negative.

Hashing your own classes

For your own classes, you combine the fields that equals compares. Objects.hash(...) does this for you:

@Override public int hashCode() { return Objects.hash(suit, rank); }

Use exactly the fields used by equals, no more and no fewer. A record writes this pair for you, as you saw in the record preview.