equals() Method and Object Comparison

hashCode() is defined in the Object class, returns an int, and every Java object has one.

Programming

Starting From the Fingerprint Assumption

Many beginners arrive at their first hash table project with a tidy assumption: every object gets its own number, and no two different objects ever share that number. If that were true, a hash code would work like a fingerprint, and finding a key in a table would be simple. This article starts from that assumption, tests it, and then builds the correct picture. The method at the center of the discussion is hashCode(), which every Java object has.

What do you think happens?

Suppose a class Person redefines equals() so that two Person objects are equal when they have the same name. The programmer does not redefine hashCode(). Two equal Person objects are stored as keys in a hash table. What does the table do when it searches for one of those keys?

It finds the stored Person and returns it
It usually fails to find the stored Person and returns nothing
It throws an error before searching

Reveal answer

Answer:

It usually fails to find the stored Person and returns nothing.

A hash table uses the hash code to decide where to search and equals() to confirm that the stored key is the one being sought. Here the two Person objects are equal under equals(), but because hashCode() was not redefined, they can have different hash codes. The search then goes to a slot that may not contain the stored key, so the lookup fails unless the two hash codes happen to land in the same slot.

Where hashCode() Lives and What It Returns

Definition

hashCode() is a method defined in the Object class. It returns a value of type int, and every Java object has one. A user-defined class gets this method by inheriting it from Object, so the programmer does not have to write it in order for the object to have a hash code.

The return type matters. An int can be negative as well as positive, so a raw hash code is not automatically a usable position in an array. The next section explains how a hash table converts that raw value into a slot number.

The source does not promise that hashCode() is unique. It establishes only three things: every object in Java has a hash code, hashCode() is defined in the Object class, and it returns an int. Uniqueness is not part of that promise, and the rest of this article explains why it cannot be.

Turning a Hash Code Into a Slot

A hash table with N locations has N places to put things, numbered from 0 to N-1. When an object obj is stored, the table needs a valid index for it. The source gives the computation directly: take the absolute value of obj.hashCode(), then compute the remainder when that value is divided by N.

Pattern

index = Math.abs(obj.hashCode()) % N, which always falls in the range 0 to N-1

java

int n = 8;
int hash = key.hashCode();
int index = Math.abs(hash) % n;

int n = 8;
int hash = key.hashCode();
int index = Math.abs(hash) % n;

Notes on the code

n is the number of locations in the table
hashCode() supplies a raw int, which may be negative
Math.abs makes the value non-negative before the remainder is taken
The % operator keeps the result between 0 and n-1

The source explains why the absolute value is needed. A hash code can be a negative integer, but an array index must be non-negative. Without Math.abs, the remainder operation could produce a negative index, and a negative index cannot be used to address an array element.

Worked example

Finding Slots in an 8-Location Table

A table has N = 8 locations. Three keys have hash codes 42, -17, and 26. Which slot does each key use, and do any keys share a slot?

1
Key with hash code 42
Math.abs(42) is 42. The remainder of 42 divided by 8 is 2, so the key goes to slot 2.
2
Key with hash code -17
Math.abs(-17) is 17. The remainder of 17 divided by 8 is 1, so the key goes to slot 1. Without the absolute value, -17 % 8 would be a negative index in many languages, which cannot address an array.
3
Key with hash code 26
Math.abs(26) is 26. The remainder of 26 divided by 8 is 2, so the key goes to slot 2.
4
Checking for sharing
The first and third keys both map to slot 2. Two different hash codes landed in the same location, which the fixed-size table makes possible.

Result

Slot 1 holds the key with hash code -17. Slot 2 is shared by the keys with hash codes 42 and 26.

Which slot does each key land in, and which keys share a slot?

The diagram shows the central mechanism. Each raw hash code is reduced to a slot number, and two keys whose hash codes differ can still be sent to the same slot. The table has only 8 places, so some sharing is unavoidable.

Why Different Objects Can Share a Hash Code

Any scheme that maps many possible keys into a fixed set of N locations must place some different keys into the same location. The number of possible keys is far larger than the number of slots, so two different objects sharing a hash code is an expected consequence of mapping keys into a limited table. It is not a defect in the language.

This shifts the question a programmer should ask. It is not whether two objects can share a hash code, because they can. The question is whether the hash function distributes keys well enough that sharing rarely happens.

The equals() and hashCode() Rule

Definition

For hashing to work properly, two objects that are equal according to the equals() method must have the same hash code.

Notice the direction of this requirement. It does not say that objects with the same hash code must be equal. Two unequal objects may share a hash code, as the previous section showed. The requirement runs in one direction only: equal objects must agree on their hash code.

The rule matters because a hash table uses the two methods for two different jobs. It uses the hash code to decide where to search, and it uses equals() to confirm that the stored key is the one being sought. If the two methods disagree about which objects are the same, the search goes to the wrong place.

Why Redefining equals() Breaks Key Lookup

In the Object class, equals() and hashCode() are both based on the address of the memory location where the object is stored. Under this default equals(), two references are equal only when they refer to the same object, so they agree on the hash code. The default pairing is therefore safe.

The trouble begins when a class changes equals() to compare contents. At that point the default hashCode() no longer matches the new notion of equality. Two objects can be equal under the new equals() while still having different hash codes. The class must then supply its own hashCode() to restore the rule.

The sequence below traces what happens when two equal Person objects are used as keys and only equals() has been redefined. The first object is stored, and the second is looked up.

p1 and p2 are equal under equals(), but hashCode() was not redefined, so they have different hash codes. What happens during put and get?

Worked example

Tracing the Failed Lookup

A table has N = 10 locations. p1 has hash code 101 and p2 has hash code 230. The two are equal under equals(), but hashCode() was not redefined. Trace put(p1) followed by get(p2).

1
Store p1
The table computes Math.abs(101) % 10, which is 1. Wait, the table has N = 10, so the slot is 1, and p1 is stored there.
2
Look up p2
The table computes Math.abs(230) % 10, which is 0. It searches slot 0 to find a key equal to p2.
3
Compare
Slot 0 does not hold p1, so equals() is never asked about p1. The equal object is in slot 1, where the search never looks.

Result

The lookup returns nothing, even though p1 and p2 are equal under equals().

The same trace also shows the sequence diagram's logic. In the diagram the two hash codes sent the equal objects to different slots, which is what the source means when it says that the search goes to the wrong place. The fix is not a better equals(). It is a hashCode() that agrees with the new equals().

How the String Class Gets It Right

In the real world

The String class is the source's main example of doing this correctly. Its equals() method is redefined so that two String objects are equal when they contain the same sequence of characters. Its hashCode() is also redefined, so the hash code is computed from the characters in the string rather than from where the string sits in memory.

Because the two methods are changed together, two strings with the same characters are equal and also share a hash code. That agreement is what keeps hash tables working when strings are used as keys. Changing only one of the two methods would reproduce the Person problem.

Mistakes With equals() and hashCode()

Common mistake
Redefining equals() for keys and leaving hashCode() alone
What it looks like
A Person class compares names in equals(), and its objects are used as keys in a hash table, but hashCode() is inherited unchanged from Object.
Why it fails
Equal objects can end up with different hash codes, so the table searches the wrong slot and misses the stored key.
Do this instead
Redefine hashCode() in the same class so that objects equal under equals() produce the same hash code.
Common mistake
Assuming that equal hash codes mean the objects are equal
What it looks like
Two different keys with hash codes 42 and 26 both map to slot 2 in an 8-location table, and a programmer concludes they must be the same key.
Why it fails
The rule runs in one direction only. Different objects may share a hash code, and a fixed table forces some sharing.
Do this instead
Use equals() to decide whether two keys are the same. The hash code only narrows the search to a location.
Common mistake
Using a raw hash code directly as an array index
What it looks like
Writing table[key.hashCode() % n] when the hash code is -17.
Why it fails
A negative remainder cannot address an array element.
Do this instead
Take Math.abs(key.hashCode()) % n so the index is always between 0 and n-1.
Common mistake
Believing every object gets a unique hash code, which the source does not promise

Why Distribution Still Matters

Once the equals() and hashCode() rule is satisfied, the remaining question is how well the hash code spreads keys across the table. The source says that writing a good hash function is something of an art. A good hash function must spread the possible keys fairly evenly over the table.

Feature	Poor hash function	Good hash function
Where keys land	Keys cluster in a few slots	Keys spread across most slots
Linked lists at occupied slots	Grow large	Stay short
Effect on lookup	Search through long lists, losing the efficiency that justifies the table	Search stays close to direct access
Satisfies the equals() rule	Can still satisfy it	Can still satisfy it

Correctness and distribution are separate goals. A hash function can satisfy the equals() rule and still perform badly.

Practice: Predict the Slots

EASY

A hash table has N = 10 locations. Compute the slot for a key with hash code -73 and for a key with hash code 58. Then say whether the two keys share a slot.

Hints

Start with Math.abs(-73), which is 73.
Then take the remainder of 73 divided by 10.
Repeat the same steps for 58, and compare the two remainders.

Your attempt (not saved)

MEDIUM

Explain, in your own words, why a class that redefines equals() for use as hash table keys must also redefine hashCode(). Use the phrase equal objects must agree on their hash code in your answer.