Walk through exactly how HashMap uses hashCode() and equals() during a get(), and pinpoint where a broken hashCode causes the lookup to fail.

## What a HashMap is A `HashMap` stores key→value pairs and promises *average* O(1) `get`/`put`. It achieves this with a **hash table**: an internal **array** (call its length `n`, the *capacity*) whose slots are called **buckets**. Each bucket holds the entries (key+value) that "belong" there — in modern OpenJDK a bucket is a linked list of `Node`s (and converts to a balanced tree once it grows past ~8 entries, but the list mental model is enough here). ## Step-by-step: `map.get(key)` 1. **Compute the raw hash.** Call `key.hashCode()`. This returns an `int`. 2. **Spread the bits.** HashMap mixes the hash with `h ^ (h >>> 16)` so that high-order bits also influence the low-order bucket index. (This is an implementation detail, not part of your contract — but it explains why even a poor hashCode still distributes somewhat.) 3. **Pick the bucket index.** Capacity `n` is always a power of two, so HashMap maps the spread hash to a slot with `index = (n - 1) & hash`. That `&` is a fast equivalent of `hash mod n`. The result is **one** bucket — the only bucket that will be searched. 4. **Search that one bucket.** Walk its entries. For each stored node, HashMap does a cheap check first: compare the **stored hash** to the query hash, and try `==` (same reference). Only if the hashes match does it call `storedKey.equals(queryKey)`. The first node whose key `equals()` the query key wins, and its value is returned. 5. **Miss.** If the bucket runs out with no `equals()` match, `get` returns `null`. ## The crucial division of labor - **`hashCode()` decides *which bucket* is searched** (steps 1–3). - **`equals()` decides *which entry inside that bucket* is the answer** (step 4). Because step 4 only ever examines **one** bucket, `equals()` is **never** called on entries living in *other* buckets. That is the entire performance trick — and the entire trap. ## Where a broken hashCode kills the lookup Suppose `equals()` says `Key("A")` and another `Key("A")` are equal, but `hashCode()` was left as the inherited identity hash, so the two instances return different ints. You do `map.put(new Key("A"), 1)` then `map.get(new Key("A"))`: - `put` hashed the first instance to bucket **5** (say) and stored it there. - `get` hashes the second instance — a *different* int — to bucket **11**. - Step 4 scans bucket **11**, which does not contain the stored entry. `equals()` is never run against the entry in bucket 5. - `get` returns **null**, even though a key that `.equals()` the query is sitting in the map. No exception, no warning — just a wrong answer. `put` uses the same probe to detect duplicates, so you can even insert what should be the "same" key twice; and `remove` can't find the entry to delete it. ## The narrow vs. wide failure modes - **hashCode too *fine* (equal objects hash differently):** the contract-violating case above — entries become unreachable. - **hashCode too *coarse* (everything returns the same constant, e.g. `return 1;`):** this does **not** violate the contract, so lookups still *work* — but every key piles into one bucket, degrading get/put to O(n) (or O(log n) after treeification). Correct, just slow. ## The fix Derive `hashCode()` from **exactly** the fields `equals()` compares: `return Objects.hash(field1, field2);`. Then equal keys always produce equal hashes, land in the same bucket, and step 4 finds them.