equals() and hashCode() Significance in Java Collections

Overview

equals() and hashCode() are defined in java.lang.Object and are critical for hash-based collections such as:

• HashMap
• HashSet
• LinkedHashMap
• Hashtable
• ConcurrentHashMap

Hash-based collections use:

hashCode() → to determine the bucket
equals() → to compare objects within the bucket

---

How HashMap Works Internally

When inserting:

map.put(key, value);

Step 1: hashCode() is called

int bucketIndex = hash(key.hashCode());

This determines the bucket.

Step 2: equals() is used

If multiple keys land in the same bucket:

existingKey.equals(newKey)

• If true → value overwritten\
• If false → new entry added

---

Example Without Overriding

class Employee {
    int id;

    Employee(int id) {
        this.id = id;
    }
}

Employee e1 = new Employee(1);
Employee e2 = new Employee(1);

HashSet<Employee> set = new HashSet<>();
set.add(e1);
set.add(e2);

System.out.println(set.size());

Output:

2

Because default equals() compares memory reference.

---

Correct Implementation

class Employee {
    int id;

    Employee(int id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Employee)) return false;
        Employee e = (Employee) o;
        return this.id == e.id;
    }

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

Now duplicates are prevented in HashSet.

---

Contract Between equals() and hashCode()

If:

a.equals(b) == true

Then:

a.hashCode() == b.hashCode()

Reverse is not mandatory.

---

Common Mistakes

1. Overriding equals() but not hashCode()

Leads to incorrect behavior in HashSet and HashMap.

2. Overriding hashCode() but not equals()

Equality still uses Object.equals().

3. Poor hashCode() implementation

@Override
public int hashCode() {
    return 1;
}

Causes all objects to go into one bucket → O(n) performance.

---

Performance Notes

Good hashCode → O(1) average
Poor hashCode → O(n)
After Java 8 → Buckets convert to Red-Black Tree after high collision → O(log n)

---

Immutability Warning

If key fields change after insertion:

Employee e = new Employee(1);
map.put(e, "data");
e.id = 2; // Dangerous

Object becomes unreachable in HashMap.

Keys should be immutable.

---

Collections Using equals() & hashCode()

Uses both: - HashMap - HashSet - ConcurrentHashMap

Does NOT use them: - TreeMap - TreeSet (uses compareTo or Comparator)

---

Summary

hashCode() → decides bucket
equals() → decides equality inside bucket

Both must be overridden together.