🔑 Section 10 · Question #9

If Two Objects Have the Same hashCode(), Are They Necessarily Equal by equals()

A situation where two logically distinct objects (a.equals(b) == false) return the exact same hashCode() value is known as a Hash Collision. This is normal, expected behavior wh...

🔑 HashMap equals hashCode 📄 Source Markdown

🟢 Junior Level

Short Interview Answer (30 Seconds)

NO, ABSOLUTELY NOT!

A situation where two logically distinct objects (a.equals(b) == false) return the exact same hashCode() value is known as a Hash Collision. This is normal, expected behavior when working with hash tables in Java.

Under the Java Language Specification (java.lang.Object), the contract enforces a strict one-way implication:

  • equals() == true $\implies$ hashCode() == true (MANDATORY invariant);
  • hashCode() == true $\not\implies$ equals() == true (Equality is NOT guaranteed).

Collisions are mathematically unavoidable due to the Pigeonhole Principle: the hashCode() method returns a 32-bit signed int (roughly $4.29 \times 10^9$ possible values), while the number of distinct object states and string combinations in memory is infinite.

Examples of Deterministic Collisions in Standard JDK Classes

public class StandardJdkCollisionsDemo {
    public static void main(String[] args) {
        // 1. String Collision: "Aa" and "BB"
        // String.hashCode() formula: 31 * char[0] + char[1]
        // "Aa": 31 * 65 + 97 = 2015 + 97 = 2112
        // "BB": 31 * 66 + 66 = 2046 + 66 = 2112
        String s1 = "Aa";
        String s2 = "BB";

        System.out.println("s1 hash: " + s1.hashCode()); // 2112
        System.out.println("s2 hash: " + s2.hashCode()); // 2112
        System.out.println("Strings equal by equals()? " + s1.equals(s2)); // false!

        // 2. Long String Collisions: "Siblings" and "Teheran"
        System.out.println("Siblings hash: " + "Siblings".hashCode()); // 231609873
        System.out.println("Teheran hash: " + "Teheran".hashCode());   // 231609873

        // 3. Long Primitive Bit Folding: 1L and 4294967297L (1 + 2^32)
        // Long.hashCode() folds 64 bits into 32 bits: (int)(v ^ (v >>> 32))
        Long l1 = 1L;
        Long l2 = 4294967297L;
        System.out.println("l1 hash: " + l1.hashCode()); // 1
        System.out.println("l2 hash: " + l2.hashCode()); // 1
        System.out.println("Longs equal by equals()? " + l1.equals(l2)); // false!
    }
}

🟡 Middle Level

The Two-Tier Search Pipeline in HashMap

The architecture of HashMap and HashSet is purpose-built to handle collisions gracefully:

                           Incoming map.get(key)
                                    │
                                    ▼
           [ Tier 1: hashCode() — Fast Coarse Filter ]
          Computes bucket index: index = (n - 1) & hash
                 Instantly discards 99.9% of unrelated buckets!
                                    │
                                    ▼
            [ Tier 2: equals() — Exact Precision Matcher ]
                Traverses only nodes inside targeted bucket:
           Evaluates p.hash == hash && (p.key == key || key.equals(p.key))
           Unambiguously identifies matching key among collisions

Value Update vs. Collision Insertion

When put(key, value) is invoked and the key’s hash matches an existing node in that bucket, HashMap evaluates equals() to decide between updating or appending:

  1. If k.equals(existingKey) == true:
    HashMap treats this as the exact same key. The existing node’s value is overwritten (e.value = value), and put() returns the old value. The size of the map (size) remains unchanged.
  2. If k.equals(existingKey) == false:
    HashMap records a collision. A new Node<K,V> is instantiated and appended to the tail of the bucket’s linked list (Tail Insertion). Both entries are preserved in the map, and size increments (size++).

🔴 Senior Level

Conflict Resolution in TreeNode Red-Black Trees

What occurs when a single bucket accumulates $\ge 8$ entries that share the exact same hashCode()?

A Red-Black binary search tree requires strict ordering ($<$ or $>$). If hash codes are identical, comparing hashes yields zero direction. HotSpot resolves this dilemma using an escalating cascade:

// OpenJDK HotSpot TreeNode insertion logic:
int dir;
Class<?> kc;
// 1. Attempt comparison via Comparable
if ((kc = comparableClassFor(k)) != null &&
    (dir = compareComparables(kc, k, pk)) != 0) {
    // Branch direction (left/right) determined via compareTo()!
} 
// 2. If Comparable is absent or compareTo() returned 0 (while equals == false)
else {
    // Recursive search across both subtrees (find)
    // If key not found, break tie deterministically via System.identityHashCode:
    dir = tieBreakOrder(k, pk);
}
  1. comparableClassFor: Checks if the key implements Comparable<Self>. If so, invokes k.compareTo(pk).
  2. Fallback via tieBreakOrder: If the key is not Comparable, HotSpot compares class names (getClass().getName()), and if identical, invokes System.identityHashCode(k) (the native memory hash from the object’s Mark Word), establishing total deterministic tree ordering.

Algorithmic Complexity / Hash Flooding DoS Attacks

Because String.hashCode() is a polynomial rolling hash: \(h = s[0] \cdot 31^{n-1} + s[1] \cdot 31^{n-2} + \dots + s[n-1]\) and because $31 \times 65 + 97 = 31 \times 66 + 66 = 2112$, the two-character pairs "Aa" and "BB" produce identical hash values.

An attacker can generate $2^{16} = 65,536$ unique strings by combining pairs of "Aa" and "BB": "AaAaAaAa", "AaAaAaBB", "AaAaBBAa", "AaAaBBBB"…
All 65,536 strings possess the identical 32-bit hash code!

  • In Java 7: Submitting an HTTP POST payload with these 65,536 parameters forced the web server (Tomcat/Jetty) to build a 65,536-element linked list in a single bucket. Inserting each parameter required $O(n)$ comparisons, resulting in $O(n^2)$ total work that pinned server CPU cores at 100% for minutes (Denial of Service).
  • In Java 8+: At 8 elements, the bucket converts into a Red-Black Tree, dropping processing time to $O(n \log n)$ and neutralizing the vulnerability.

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

Equal hash codes DO NOT guarantee equality by equals(). Identical hashes for non-equal objects represent a hash collision. This is mathematically inevitable due to the Pigeonhole Principle (4.29 billion 32-bit int values vs. infinite object states). In HashMap, identical hash codes simply direct entries to the same bucket, where they coexist as a linked list or Red-Black Tree and are distinguished via equals(). Value overwrite occurs ONLY when equals() == true.

2. 4 Tricky Questions with Deep Answers

Question 1: Why does Java’s hashCode() return a 32-bit int rather than a 64-bit long, which would vastly reduce collision probabilities?

Answer:

  1. Memory Overhead: Every node in HashMap stores final int hash. A 64-bit long would increase node size by 8 bytes (accounting for 8-byte object alignment), consuming massive extra RAM across millions of entries.
  2. CPU Architecture: 32-bit arithmetic operations are universally fast and power-efficient across all CPU architectures.
  3. Table Size Reality: Practical hash tables rarely hold more than a few million entries. Bucket indices are extracted using the lowest 4–20 bits of the hash ((n - 1) & hash); a 64-bit hash would not reduce bucket index collisions on typical table capacities.

Question 2: How can you generate an arbitrary number of distinct strings that all have identical hashCode() values in Java?

Answer: Use pairs of characters with equal polynomial sums under multiplier 31, such as "Aa" and "BB" (both hash to 2112). Because String.hashCode() is linear with respect to character positions, any concatenation of $N$ blocks of "Aa" or "BB" produces identical hashes. By taking Cartesian products across $K$ blocks, you can generate $2^K$ unique strings (e.g., "AaAa", "AaBB", "BBAa", "BBBB") that all produce the exact same 32-bit hash.

Question 3: What happens inside HashMap if every key inserted into the map returns a constant hashCode() (e.g., return 42;)?

Answer: All entries are directed to a single bucket index: (table.length - 1) & 42. Up to 7 entries, they form a singly linked list with $O(n)$ search complexity. When the 8th entry arrives (and capacity is at least 64), the bucket treeifies into a Red-Black Tree, stabilizing search and insertion complexity at $O(\log n)$. HashMap will function correctly and will not lose data, but lookup performance degrades significantly compared to $O(1)$.

Question 4: How does HashMap distinguish between inserting a new entry and updating an existing key when hash codes match?

Answer: HashMap executes a two-tier verification: upon matching hashes, it evaluates key.equals(existingKey). If equals() returns true, HashMap treats the key as an existing entry, updates its value, and returns the old value without altering size. If equals() returns false, HashMap treats the entry as a new colliding key, appends a new Node to the chain, and increments size.

3. Common Pitfalls and Red Flags

❌ “If two objects have the same hashCode, they are equal by equals().”
Correction: False. Equal hash codes are merely a collision. equals() must be evaluated to confirm true equivalence.

❌ “A good hash function must guarantee zero collisions.”
Correction: General-purpose hash functions cannot eliminate collisions due to the Pigeonhole Principle; their goal is uniform pseudo-random distribution.

❌ “When a collision occurs, the previous key is evicted from the map.”
Correction: Both keys are stored together in the bucket unless equals() returns true.