Hash Tables and Collision Handling

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

Programming

Interactive lab

Try it: How a dict Stores Keys

How a dictionary turns a key into a slot with a hash, what happens on a collision, why deleted keys leave a marker, and why the table grows.

How it works

hash(key) gives a number; hash % table size gives the key's home slot.
If that slot is taken by another key (a collision), probe the next slot.
Deleting leaves a DELETED marker so lookups keep probing past it.
When more than 2/3 of the slots are used, the table doubles and every key is re-inserted.

Default run (5 steps): A dict with 3 keys in 8 slots. Choose an operation. Example: d["mango"] = 5. … Done. 4 keys in 8 slots.

Simplified: Uses a small educational hash (Python's real string hash is randomised per run) and simple linear probing; CPython's probe order is more elaborate.

Educational simulation

Loading the simulation…

Why a Hash Code Is Not a Fingerprint

Many beginners who build their first hash table start 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 against what the source actually establishes, and then builds the correct picture.

What do you think happens?

Suppose a class Person redefines equals() so that two Person objects are equal when they have the same name, but the programmer never redefines hashCode(). Two equal Person objects are stored as keys in a hash table. What do you expect the table to do when it searches for one of those keys?

It finds the stored key, because the two objects are equal
It may fail to find the key, because the search may begin in the wrong place

Make your prediction before reading on. The rest of this article explains what the hash table actually does, and the answer depends on a rule about how equals() and hashCode() must agree.

Where hashCode() Lives and What It Returns

hashCode() is a method defined in the Object class in Java. Every Java object has one, because every class inherits from Object. The method returns a value of type int. Because it is inherited, a class that does nothing special still has a hashCode() method available to call.

The source does not promise that hashCode() returns a unique value for each object. What it establishes is narrower: every object has a hash code, the method is defined in Object, and the result is an int. Whether two objects share a hash code is a separate question, and the answer is that they sometimes do. The next sections explain why that is expected rather than a flaw in the language.

Turning a Hash Code Into a Slot Index

A raw hash code can be any int, including negative values. An array index, however, must be a non-negative number inside the table's range. A hash table with N locations therefore converts the hash code into a valid location. The source gives the computation directly: when an object obj is stored in a hash table with N locations, the location is found by taking the absolute value of obj.hashCode() and computing the remainder when that value is divided by N. The result always falls in the range 0 to N-1.

Pattern

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

With N equal to 5, which slot does each hash code map to, and what happens when two hash codes land in the same slot?

Worked example

Computing the slot for a negative hash code

A hash table has N equal to 5 locations. An object returns the hash code -7 from hashCode(). Which slot does the object go to?

1
Take the absolute value
Math.abs(-7) gives 7. This removes the negative sign so the value can be used safely in the next step.
2
Compute the remainder
Divide 7 by N, which is 5. The remainder is 2, because 5 goes into 7 once with 2 left over.
3
Check the range
The result 2 lies between 0 and N-1, which is 0 to 4, so it is a legal array index.

Result

The object is placed in slot 2. The hash code 12 also gives 12 % 5 = 2, so it lands in the same slot. This is the sharing of a location described in the next sections.

The source explains the role of Math.abs. Without it, a negative hash code could produce a negative remainder, and a negative number cannot be used to address an array element. Taking the absolute value first ensures the value passed to the remainder operation is non-negative, so the final index is always usable.

The equals() and hashCode() Rule

The central rule of this topic is stated in the source: for hashing to work properly, two objects that are equal according to the equals() method must have the same hash code. Pay attention to the direction of this requirement. It does not say that objects with the same hash code must be equal. It says that equal objects must agree on their hash code.

The reason this matters is how a hash table searches. It uses the hash code to decide where to look, and it uses equals() to confirm that the stored key is the one being sought. If the two methods disagree, the search goes to the wrong place and never reaches the matching entry, even though the matching entry is in the table.

What steps does the table take when it searches for an equal key, and at which step does the search fail?

In this trace, the stored Person sits in slot 2, but the lookup key produces a different hash code and therefore points at slot 4. The table never examines slot 2, so equals() is never asked whether the two objects match. The failure happens at step 2, where the search picks the wrong location, not at the equality check itself.

Redefining equals() Without hashCode()

The following class follows the mistake the source warns about. It redefines equals() so that two Person objects are equal when their names match, but it does not redefine hashCode(). The class therefore inherits the default hashCode() from Object.

java

class Person {
    private String name;

    Person(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object other) {
        if (!(other instanceof Person)) {
            return false;
        }
        return this.name.equals(((Person) other).name);
    }

    // hashCode() is not redefined, so the inherited Object version is used
}

class Person {
    private String name;

    Person(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object other) {
        if (!(other instanceof Person)) {
            return false;
        }
        return this.name.equals(((Person) other).name);
    }

    // hashCode() is not redefined, so the inherited Object version is used
}

Notes on the code

equals() compares the name field, so two Person objects with the same name are equal
hashCode() is missing, so the default version from Object is used
The default hash code is not based on the name, so equal Person objects may get different hash codes

The source describes the default behavior of Object. In Object, equals() and hashCode() are both based on where the object is stored in memory. Under this default, two references are equal only when they refer to the same object, so they agree on the hash code. The problem begins when a class changes equals() to compare contents. The default hashCode() no longer matches the new notion of equality, and the class must supply its own hashCode() to restore the rule.

java

@Override
public int hashCode() {
    return name.hashCode();
}

@Override
public int hashCode() {
    return name.hashCode();
}

Notes on the code

The hash code is computed from name, the same field equals() compares
Two Person objects with equal names now produce equal hash codes, which satisfies the rule

Collisions and Why Sharing Is Expected

A hash table with N locations has only N places to put things. Many possible keys must therefore be mapped into a fixed set of locations, and some different keys must land in the same one. A hash code that is the same for two different objects is not a bug in the language. It is an expected consequence of mapping keys into a limited table.

This is why the source focuses on distribution rather than uniqueness. The question a programmer should ask 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 such sharing stays uncommon. In the five-slot example above, slot 2 holds two hash codes, 12 and -7, and the table must still use equals() to tell the stored keys apart when searching that slot.

Keeping Keys Spread Evenly

Once the equals() and hashCode() rule is satisfied, the remaining question is how evenly the hash code spreads keys across the table. The source says writing a good hash function is something of an art. A good hash function must spread the possible keys fairly evenly over the table. When it fails to do so, items cluster in a few locations, the linked lists at those locations grow large, and the efficiency that justifies using a hash table disappears.

How does a well-spread hash function place the same keys across slots differently from a poor one that clusters them?

The two columns hold the same four keys. In the well-spread case, each slot holds one key and a lookup checks a single entry. In the clustered case, one slot holds every key, so the lookup must work through a long list there and the table gains little over a simple list. Correctness and distribution are separate goals. A hash function can satisfy the equals() rule and still perform badly.

Practice: Trace a Lookup

MEDIUM

A hash table has N equal to 5 locations. A key whose hashCode() returns -12 is stored in the table. Work out which slot it goes to, using Math.abs and the remainder operation. Then explain what would happen if a lookup used an equal key whose hashCode() returned 3 instead.

Hints

Start by taking the absolute value of -12
Then divide by 5 and keep the remainder
For the second part, compare the slot the new hash code points to with the slot where the stored key sits

Your attempt (not saved)

Mistakes Beginners Make With Keys

Common mistake
Assuming every object has a unique hash code
Why it fails
The source does not promise uniqueness, and a table with N locations must place some different keys into the same location.
Do this instead
Treat shared hash codes as normal and rely on equals() to tell the keys apart within a slot.
Common mistake
Redefining equals() without redefining hashCode()
What it looks like
Person objects compare equal by name, but hashCode() is inherited from Object and depends on memory location.
Why it fails
Equal keys can end up with different hash codes, so a search starts at the wrong slot and misses the stored key.
Do this instead
Redefine hashCode() using the same fields that equals() compares, as in name.hashCode().
Common mistake
Reading the rule backwards
Why it fails
The rule requires that equal objects share a hash code. It does not require that objects sharing a hash code be equal.
Do this instead
Check that equal objects always agree on the hash code, and accept that unequal objects may also agree.
Common mistake
Using a negative hash code directly as an index
Why it fails
A raw hash code can be negative, and a negative value cannot address an array element.
Do this instead
Apply Math.abs before taking the remainder by N, so the index falls in the range 0 to N-1.

Key Takeaways

hashCode() is defined in the Object class, returns an int, and every Java object has one.
A hash table with N locations converts a hash code into a valid index with Math.abs(obj.hashCode()) % N, which always lies from 0 to N-1.
Two objects equal according to equals() must have the same hash code, so a class that redefines equals() for use as keys must also redefine hashCode().
Different objects may share a hash code, so the goal is a hash function that spreads keys fairly evenly rather than one that guarantees uniqueness.
Correctness (the equals() and hashCode() rule) and distribution (even spread) are separate goals, and a good hash function must satisfy both.