skip to content

HashMap

HashMap end to end: a power-of-two table indexed by a bitmask, a hash-spreading function, separate chaining that treeifies a bucket into a red-black tree when it already holds eight entries and the table has at least 64 buckets, a 0.75 load factor, and a resize that splits each bucket on one hash bit. This is the deepest-probed class in Java interviews, and the treeify and resize details are what separate rote answers from real understanding.

part ofJavaread it →
on this pageshow

questions

6

How does a Java HashMap store key-value pairs internally, and how does it find a value by key?

level: juniorimportance: must knowfreq 90%

answer

  1. Array of buckets, each bucket = chain of Node<K,V>
  2. put = hash to index, store; get = same index, equals to match
  3. Collision = two keys, same bucket -> chained
  4. Amortized O(1); needs correct hashCode + equals
  5. Keys should be immutable

basics

~20 s

A 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 s

A 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 run in O(1) on average, assuming the hash function disperses keys evenly. 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

for a junior

Can describe buckets, hashing a key to an index, and using equals to find the value; knows custom keys need hashCode + equals.

for a middle

Explains collisions and chaining, amortized O(1) vs worst-case, and why mutable keys break lookups.

for a senior

Connects spreading/index math, the Node structure with cached hash, and reasons about when O(1) degrades.

for a principal

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 that stands in for the object: a class that overrides `hashCode()` usually derives it from its fields, while `Object`'s default gives distinct objects distinct numbers as far as is reasonably practical. 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 XORs the high 16 bits of the hash into the low 16). 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 for an equal key lands in the bucket holding 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). A `put` is also called **amortized** O(1), meaning "averaged over many operations": it stays constant 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. Since Java 8 a crowded bucket can become a tree, which keeps such a search at O(log n) only when the key's class declares `Comparable` of itself; otherwise lookups still degrade 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** (if its hash changes while it sits in the map, a lookup searches under the new hash and misses the entry, which is still stored).

  • What happens if you use a mutable object as a key and then change a field that affects its hashCode?
    The map filed it under the old hash and keeps that stored hash. After the mutation a lookup uses the new hash, so get and containsKey miss the entry even though it is still stored; on JDK 27 a lookup finds it again only after the field changes back. 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 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

context

open as a page

Explain capacity, load factor, and resizing in HashMap. What is the default load factor and why?

level: middleimportance: must knowfreq 80%

basics

~20 s

Capacity is the number of buckets (default 16). Load factor (default 0.75) is how full the map gets before it grows. When entries exceed capacity x load factor (the threshold), the map doubles its capacity and re-spreads entries so buckets stay short and lookups stay fast.

open as a page

How does HashMap handle null keys/values, what is its iteration order, and why is it not thread-safe?

level: middleimportance: must knowfreq 70%

basics

~20 s

HashMap allows one null key (in bucket 0) and any number of null values. Its iteration order is unspecified and can change after a resize. Concurrent structural modification can corrupt it or hang a thread, so use ConcurrentHashMap or external locking.

open as a page

What changed in Java 8's HashMap internals, and how did HashMap behave before that release?

level: middleimportance: should knowfreq 68%

basics

~20 s

Java 8 added tree bins: a crowded bucket becomes a red-black tree. put appends at a plain bin's tail, resize splits bins in order, and hash mixing is one XOR. Before, buckets stayed linked lists, O(n) under heavy collisions.

open as a page

How does HashMap compute a bucket index from a key, and why does it XOR the high bits of the hash?

level: seniorimportance: should knowfreq 50%

basics

~20 s

HashMap picks a bucket with (capacity - 1) & hash, a bitmask that works because capacity is a power of two. The mask reads only low bits, so hash() first XORs each hash with its own top 16 bits, which reduces collisions.

open as a page

What is bucket treeification in HashMap (Java 8+), and under what exact conditions does it happen?

level: seniorimportance: should knowfreq 55%

basics

~20 s

Since Java 8, HashMap can turn a crowded bucket's list into a red-black tree, to limit worst-case lookups. A put converts it when adding to a bucket already holding 8 entries, if the table has at least 64 buckets; otherwise it resizes.

open as a page