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: tree bin past 8 entries, 64+ buckets
- 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 hashes spread keys across buckets. Collisions degrade them to O(n), or O(log n) in a tree bin (since Java 8) when keys have distinct hashes or are Comparable.
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 worst case is O(n) (e.g. bad or adversarial hashCodes). Since Java 8, a bucket that grows past 8 entries, in a table of at least 64 buckets, converts to a red-black tree, giving O(log n) lookups when keys have distinct hash codes or are mutually Comparable; keys that share one hash and have no order stay O(n). HashMap also doubles and rehashes when size exceeds capacity * load factor (default 0.75), which is O(n) at that moment but keeps buckets short on average.
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 when Java 8 treeification gives O(log n).
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 (`MIN_TREEIFY_CAPACITY`; a smaller table resizes instead), converts from a linked list into a **red-black tree** (a self-balancing binary search tree). The tree is ordered by hash code first, then by `compareTo` when keys of the same class are `Comparable`, so lookups in that bucket cost **O(log n)** when keys have distinct hash codes or are orderable. Keys that share one hash code and have no order leave the tree nothing to navigate by, so a lookup can still visit every entry: **O(n)**. A tree bin goes back to a list when a resize splits it down to 6 entries or fewer (`UNTREEIFY_THRESHOLD`), or when removals leave the tree too small, a test on the tree's shape rather than a count. ## 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)** in a tree bin with distinct hashes or Comparable keys, **O(n)** when keys share one hash and have no order. A `put` that triggers a resize is also O(n). - 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 keys share one full hash code and are not mutually Comparable, as with a constant hashCode(): the tree bin has nothing to navigate by, so a miss can visit every entry. With distinct hash codes or Comparable keys, treeification since Java 8 bounds it at O(log n).
- 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).
- 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)
- HashMap tree bins
- Java 1.8
Assumes JDK 27. Tree bins date from Java 8, and the thresholds (8, 6 and 64) are the same at JDK 25.
context
- HashMap (Java SE 27 & JDK 27)docs.oracle.com
- HashMap.java at jdk-27-gagithub.com