What is the average and worst-case time complexity of HashMap get and put, and what makes the average case constant?
answer
- Hash → spread → bucket index → equals check
- Average O(1), collisions degrade it
- Java 8: bucket treeifies at 8 entries → O(log n)
- Load factor 0.75 triggers O(n) resize/rehash
- equals/hashCode contract must hold or entries get lost
basics
~20 sHashMap get and put are O(1) on average because keys are spread across buckets by their hash. In the worst case (many collisions) they can degrade to O(n), or O(log n) since Java 8 when a bucket converts to a balanced tree.
solid answer
~50 sA HashMap stores entries in an array of buckets; a key's hashCode (after Java's spreading function) picks the bucket index, so get and put are O(1) on average — you jump straight to one bucket and check a few entries. The catch is collisions: keys landing in the same bucket form a list that must be scanned, so the true worst case is O(n) when everything collides (e.g. bad or adversarial hashCodes). Since Java 8, a bucket that grows past a threshold (8 entries, with table size >= 64) converts from a linked list to a red-black tree, bounding that bucket's lookup at O(log n). HashMap also resizes (rehashes, doubling capacity) when load factor (default 0.75) is exceeded, which is O(n) at that moment but keeps buckets short on average. So: average O(1), worst case O(log n) with good comparable keys, O(n) in pathological cases.
go deeper
Knows get/put are 'O(1) on average' and that it relies on hashCode spreading keys across buckets.
Explains collisions, the O(n) worst case, load-factor resizing, and the Java 8 O(log n) treeification threshold.
Discusses the equals/hashCode contract, pre-sizing to avoid rehashes, immutable keys, and how poor hash functions cause real degradation.
Frames hash-collision DoS, choice of capacity/load-factor for throughput vs memory, and alternatives (ConcurrentHashMap, open addressing) at scale.
## What a HashMap is A `HashMap` stores **key→value** pairs and lets you look a value up by its key. The goal is to find any key in roughly constant time regardless of how many entries exist. ## How it works internally A HashMap holds an **array of 'buckets'** (slots). To place a key: 1. Compute the key's **hash code** (`key.hashCode()`), an integer derived from the key. 2. Java applies a **spreading function** (XORs the high bits down) to mix the bits, reducing clustering. 3. Take that value **modulo the array length** (done with a bit-mask since the length is a power of two) to get a **bucket index**. 4. Store the entry in that bucket. To `get(key)`, it repeats steps 1–3 to find the bucket, then checks the entries in that bucket using `equals()` to find the exact key. ## Why average cost is O(1) If hash codes are well distributed, each key lands in its own bucket or shares with very few others. So `get`/`put` do a constant amount of work: hash, index, compare a handful of entries. That is the **O(1) average** case. 'O(1)' (constant) means the cost does not grow with the number of entries `n`. ## Collisions and the worst case A **collision** is when two different keys map to the same bucket. Colliding entries are chained together. To find your key you scan the chain, comparing with `equals()`. If *every* key collided into one bucket — for example because `hashCode()` always returns the same number, or an attacker crafted keys to collide — the scan becomes **O(n)**, linear in the number of entries. This is the worst case. ## Java 8 treeification To blunt the worst case, since Java 8 a bucket that grows beyond **8 entries** (the `TREEIFY_THRESHOLD`), *and* when the table has at least 64 buckets, converts from a linked list into a **red-black tree** (a self-balancing binary search tree). Lookups within that bucket then cost **O(log n)** instead of O(n) — *provided the keys are mutually `Comparable`* (otherwise it falls back to comparing hash codes / identity, still tree-ordered). If the bucket shrinks back below 6 entries it 'untreeifies'. So with reasonable keys the realistic worst case is O(log n) per bucket, not O(n). ## Load factor and resizing The **load factor** (default **0.75**) is the fullness threshold: when `size > capacity * loadFactor`, the HashMap **resizes** — it doubles the bucket array and **rehashes** every entry into the new, larger array. That single resize is **O(n)**, but it happens rarely and keeps the average bucket short, preserving amortized O(1) inserts. Pre-sizing the map (constructor capacity hint) avoids repeated resizes when you know the size. ## The equals/hashCode contract For any of this to work, keys must obey the contract: equal objects (`a.equals(b)`) must have equal hash codes, and `hashCode()`/`equals()` must be stable while the key is in the map. Breaking it causes 'lost' entries you can never retrieve. ## Summary table - get / put: **O(1) average**, **O(log n)** worst with Comparable keys (treeified), **O(n)** pathological. - resize/rehash: **O(n)** but amortized away. - containsKey: same as get. containsValue: **O(n)** (no value index — must scan all buckets).
- What is the worst-case complexity of HashMap.get and when does it actually happen?O(n) when all keys collide into one bucket and it cannot treeify (or keys aren't comparable). With Java 8 treeification and Comparable keys it is bounded at O(log n). The classic trigger is a constant or attacker-crafted hashCode.
- What does the load factor control and what happens when it is exceeded?It is the fullness threshold (default 0.75). When size exceeds capacity * loadFactor, the map doubles capacity and rehashes all entries (an O(n) operation), keeping buckets short and average lookups O(1).
saying these in an interview costs you the question
- Stating HashMap is always O(1) with no mention of the collision worst case
- Confusing load factor (0.75) with the treeify threshold (8 entries)
- Claiming containsValue is O(1) (it is O(n) — no value index)
- Saying treeification makes the whole map a tree (only an over-full bucket converts)