How does a Java HashMap store key-value pairs internally, and how does it find a value by key?
answer
- Array of buckets, each bucket = chain of Node<K,V>
- put = hash to index, store; get = same index, equals to match
- Collision = two keys, same bucket -> chained
- Amortized O(1); needs correct hashCode + equals
- Keys should be immutable
basics
~20 sA HashMap keeps an array of buckets. It turns each key into a number (a hash), uses that number to pick a bucket, and stores the key and value there. To get a value it hashes the key again, jumps to the same bucket, and compares keys with equals to find the match.
solid answer
~40 sA HashMap is backed by an array (the table) of buckets. On put(k,v) it computes the key's hashCode, spreads it, and maps it to a bucket index. The key-value pair is stored as a Node in that bucket. On get(k) it repeats the index calculation, walks the bucket, and uses equals() to find the entry whose key matches, returning its value. When two different keys land in the same bucket (a collision), they are chained together in that bucket, so get still works by scanning the short chain. Because most lookups touch only one bucket, get and put are amortized O(1). This is why a key's class must implement hashCode() and equals() consistently: a broken hashCode scatters equal keys, and a broken equals breaks matching.
go deeper
Can describe buckets, hashing a key to an index, and using equals to find the value; knows custom keys need hashCode + equals.
Explains collisions and chaining, amortized O(1) vs worst-case, and why mutable keys break lookups.
Connects spreading/index math, the Node structure with cached hash, and reasons about when O(1) degrades.
Discusses key-design implications across a codebase (immutability, equals/hashCode contracts, value-based key types) and failure modes at scale.
## What a HashMap is A **HashMap** stores **key-value pairs** (called *entries* or *mappings*) and lets you look up a value by its key very fast. It implements the `Map` interface. A *key* is the thing you search by (e.g. a username); a *value* is the data attached to it (e.g. a user object). ## The core data structure: a table of buckets Internally a HashMap holds an array called the **table**. Each slot of that array is a **bucket**. A bucket can hold zero, one, or several entries. Each stored entry is a small object Java calls a `Node<K,V>` holding four things: the key, the value, the key's cached hash, and a `next` pointer to the following entry in the same bucket (forming a linked list). ## What a hash code is Every Java object has a `hashCode()` method returning an `int`. A **hash code** is just a number derived from the object's contents. The contract: if two objects are `equals()`, they MUST return the same `hashCode()`. The reverse is not required — two unequal objects may share a hash code (that is allowed and is called a *collision*). ## How put works (storing) 1. Compute `key.hashCode()`. 2. *Spread* it (HashMap mixes the high bits down — explained in the spreading question). 3. Map the spread hash to a bucket **index** in the table. 4. Go to that bucket. If empty, place the new Node there. If it already has entries, walk them: if a key already `equals()` the new key, overwrite its value (a key is unique); otherwise append the new Node to the chain. ## How get works (retrieving) 1. Compute and spread the key's hash exactly as in put. 2. Map to the same bucket index. 3. Walk that bucket's entries; for each, first compare cached hashes (cheap), then compare keys with `equals()`. Return the value of the entry whose key matches, or `null` if none matches. Because put and get use the *same* index math, a get always lands in the bucket where put placed the entry. ## Why it is fast If entries are spread evenly, each bucket holds roughly one entry, so a lookup does one index calculation plus one or two comparisons — constant time, written **O(1)** (cost does not grow with map size). The word **amortized** means "averaged over many operations": individual operations are O(1) on average even though an occasional resize is more expensive. ## Why hashCode and equals matter - A correct `hashCode()` spreads keys across buckets. A bad one (e.g. always returning `0`) dumps every key into one bucket, degrading lookups toward O(n) (a linear scan). - A correct `equals()` is how the map confirms a real match inside a bucket. If `equals()` is wrong, get may miss an entry that is actually present. This is why you must override BOTH together whenever you use a custom class as a key, and the key should be **immutable** (its hash must not change while it sits in the map, or the map can never find it again).
- What happens if you use a mutable object as a key and then change a field that affects its hashCode?The map indexed it under the old hash. After mutation its new hash maps to a different bucket, so get/contains usually fail to find it even though it is still stored. Use immutable keys.
- Why must hashCode() and equals() be overridden together?The contract requires equal objects to have equal hash codes. If you override only equals(), two equal keys can land in different buckets and the map treats them as distinct; if you override only hashCode(), the map can't confirm a match. Both are needed for correct lookups.
saying these in an interview costs you the question
- Saying HashMap stores entries in sorted or insertion order
- Claiming equal hash codes mean equal objects (collisions are normal)
- Forgetting that equals() is still needed even with a good hashCode
- Thinking get is always O(1) regardless of hashCode quality