Java HashMap

java.util.HashMap<K, V> is the collection that answers the question "given this key, what is the value?" in O(1) average time. Product catalogues, user session caches, configuration stores, word frequency counters — anything where you need to look up a value by a meaningful identifier rather than an array index uses HashMap. Understanding how it achieves O(1) lookup internally, and what breaks that guarantee, is one of the most frequently tested topics in Java interviews.

What Is Java HashMap?

HashMap<K, V> is a concrete class in java.util that implements the Map<K, V> interface. A Map stores key-value pairs where each key is unique. HashMap achieves near-constant time for put(), get(), and remove() by converting each key into a bucket index using a hash function, then storing the entry in that bucket.

The diagram below shows where HashMap fits in the Collections hierarchy.

java.util.Map<K, V>                    ← key-value contract
    ├── HashMap<K, V>                  ← THIS CLASS: hash table, no order
    │       └── LinkedHashMap<K, V>   ← extends HashMap, adds insertion order
    ├── java.util.SortedMap<K, V>
    │       └── NavigableMap<K, V>
    │               └── TreeMap<K,V>  ← Red-Black tree, sorted by key
    └── Hashtable<K, V>               ← legacy, synchronised, avoid in new code

KEY FACTS:
  Package        : java.util
  Since          : Java 1.2
  Implements     : Map<K,V>, Cloneable, Serializable
  Key ordering   : no guaranteed iteration order
  Null keys      : exactly ONE null key allowed
  Null values    : unlimited null values allowed
  Thread-safe    : NO — use ConcurrentHashMap for concurrent access
  Default capacity   : 16 buckets
  Default load factor: 0.75 (rehash when 75% of buckets are occupied)

Basic Overview — The Bucket Array and Entry Nodes

Every entry in a HashMap is stored as a Node<K, V> object inside a Node[] array called table. Each slot in the array is a bucket. Multiple entries can share a bucket — these are called collisions.

HASHMAP INTERNAL STRUCTURE (default capacity 16):

  table (Node[] of length 16):
    [0]:  null
    [1]:  null
    [2]:  Node("Mumbai"=2) → null
    [3]:  Node("Delhi"=1) → Node("Pune"=5) → null   ← collision chain
    [4]:  null
    [5]:  Node("null"=0) → null   ← null key always maps to bucket 0
    ...
    [15]: Node("Bengaluru"=3) → null

  Each Node holds:
    int  hash      — pre-computed hash of the key
    K    key       — the key object reference
    V    value     — the value object reference
    Node next      — pointer to next Node in chain (null if no collision)

  JAVA 8 TREEIFICATION:
    When a bucket chain grows beyond 8 nodes AND table length >= 64:
      The linked list converts to a Red-Black tree (TreeNode)
      Lookup improves from O(n) worst-case to O(log n)
    When the tree shrinks below 6 entries on removal:
      Converts back to a linked list

When to Use HashMap

USE HashMap WHEN:
  - Fast key-based lookup is the primary operation (O(1) average)
  - Insertion order does not matter
  - Sorted order does not matter
  - Keys are objects with well-implemented equals() and hashCode()

USE LinkedHashMap WHEN:
  - Iteration order must match insertion order
  - LRU cache implementation (LinkedHashMap with accessOrder=true)

USE TreeMap WHEN:
  - Keys must be in sorted order for iteration
  - Range queries are needed: headMap(), tailMap(), floor(), ceiling()
  - O(log n) per operation is acceptable

USE ConcurrentHashMap WHEN:
  - Multiple threads read and write the same map
  - HashMap is not thread-safe — concurrent puts can cause infinite loops
    in Java 6 and earlier (due to linked-list cycle during resize)

DO NOT USE Hashtable:
  - Synchronises every method, even in single-threaded use — legacy overhead
  - Does not allow null keys or values
  - ConcurrentHashMap is the correct thread-safe replacement

CHOOSE HashMap over List when:
  - You need to look up entries by a meaningful key (name, ID, code)
  - list.contains(element) is O(n); map.get(key) is O(1) average
  - A list of key-value pairs that you scan with a loop is usually a HashMap

How HashMap Works Internally

Step 1 — The Hash Function

When put(key, value) is called, HashMap first computes the bucket index in two steps.

BUCKET INDEX CALCULATION for key "Delhi":

  Step 1: raw hash
    h = key.hashCode()
    h = "Delhi".hashCode()  = -2078581030  (example value)

  Step 2: hash spreading — mix high bits into low bits
    hash = h ^ (h >>> 16)
    This prevents poor hashCode() implementations that only vary in high bits
    from clustering all entries into the same few low-indexed buckets.

    h             = 1111 0000 0101 0100 ... (high bits matter for 16-bucket table)
    h >>> 16      = 0000 0000 1111 0000 ...
    hash = h ^ (h>>>16) = mixed result with both high and low bits represented

  Step 3: bucket index
    index = hash & (capacity - 1)
    index = hash & 15            (for default capacity 16, mask = 0b1111)

    Capacity is always a power of 2, so (capacity-1) is all-ones:
    16 - 1 = 15 = 0b00001111
    Any hash & 15 produces a value in [0, 15] — perfect bucket spread.
    Bitwise AND is faster than modulo (%) for this purpose.

Step 2 — put() Mechanics

put("Delhi", 1) into an empty HashMap:

  1. Compute hash for "Delhi" → hash = -2038...
  2. index = hash & 15 = 3
  3. table[3] is null → create new Node("Delhi", 1) and store at table[3]

put("Pune", 5) — assume also maps to bucket 3 (collision):

  1. hash("Pune") & 15 = 3
  2. table[3] is not null → traverse chain
  3. For each node: hash matches AND "Delhi".equals("Pune")? → false
  4. Reach end of chain → append new Node("Pune", 5) as next of "Delhi" node

  table[3]: Node("Delhi",1) → Node("Pune",5) → null

put("Delhi", 99) — update existing key:

  1. hash("Delhi") & 15 = 3
  2. table[3]: check Node("Delhi",1) — hash matches AND "Delhi".equals("Delhi") → true
  3. Replace value: node.value = 99
  4. Returns old value 1 — put() return value indicates previous value

get("Delhi") — two-step lookup:
  1. hash("Delhi") → bucket 3
  2. Walk chain: "Delhi".equals("Delhi") → found → return node.value
  O(1) average: typically one or two comparisons in a well-sized map.

Step 3 — Resize and Rehash

When size > capacity * loadFactor, HashMap doubles the table and redistributes all entries.

RESIZE TRIGGER at default settings:
  capacity = 16, loadFactor = 0.75
  threshold = 16 × 0.75 = 12
  When size reaches 13: resize fires

RESIZE PROCESS:
  1. New table of capacity 32 is allocated
  2. For every existing Node, recompute: index = hash & (32 - 1)
     — because the mask is now 31 (0b11111) instead of 15 (0b1111)
     — each entry either stays in its current slot OR moves to slot + 16
     — This is why capacity must always be a power of 2: the redistribution
       is a simple one-bit test, not a full re-hash
  3. All chains are redistributed into the new table
  4. O(n) resize — amortised O(1) per put() over the full lifetime

PRE-SIZING EXAMPLE:
  Loading 10,000 entries: each resize doubles capacity (16→32→64→...→16384)
  To avoid ~6 resize operations: new HashMap<>(16384)  or
  new HashMap<>(10000 / 0.75 + 1) ≈ new HashMap<>(13334)
  This allocates capacity ≥ 16384 and prevents all resizes.

Java 8 Treeification — The Collision Defense

Before Java 8, a bucket chain that degenerated to n entries caused O(n) lookups — attackers could craft keys with identical hashes to cause HashMap to perform at O(n) on every operation. Java 8 introduced treeification.

TREEIFICATION RULES:
  When a single bucket chain length exceeds 8 nodes
  AND the table length is >= 64:
    → Convert the linked list to a Red-Black tree (TreeNode)
    → Lookup improves from O(n) to O(log n)

  When table length < 64 and a bucket chain exceeds 8:
    → Resize instead of treeify (more buckets = better distribution)

  UNTREEIFY:
    When a tree bucket shrinks below 6 entries (through remove()):
    → Convert back to a linked list

WHY THIS MATTERS:
  String.hashCode() on carefully crafted strings can produce
  the same hash value deliberately. Without treeification, a
  HashMap<String, ...> is vulnerable to O(n) DoS attacks
  through hash flooding. With treeification, the worst case
  is O(log n) for any single bucket.

Core Operations with Examples

put(), get(), containsKey(), remove()

Output:
=== put() ===
put(Mumbai, 2069)   : null
put(Delhi, 1679)    : null
put(Bengaluru, 961) : null
put(Mumbai, 2100)   : 2069
Map: {Bengaluru=961, Delhi=1679, Mumbai=2100}

=== get() ===
get(Delhi)    : 1679
get(Chennai)  : null

getOrDefault(Chennai, 0): 0

=== containsKey() and containsValue() ===
containsKey(Delhi)      : true
containsKey(Hyderabad)  : false
containsValue(961)      : true

=== remove() ===
remove(Bengaluru)       : 961
remove(Hyderabad)       : null
remove(Delhi, 999)      : false
remove(Delhi, 1679)     : true
Map after removes: {Mumbai=2100}

=== Null key ===
get(null)   : 0
Map: {null=0, Mumbai=2100}

Iterating a HashMap

Output:
=== entrySet() — key + value ===
  Webcam       Rs.  3499.00
  Laptop       Rs. 49999.00
  Monitor      Rs. 18999.00
  Keyboard     Rs.  2499.00
  Mouse        Rs.   999.00

=== keySet() — keys only ===
Webcam Laptop Monitor Keyboard Mouse

=== values() — values only ===
Total inventory value: Rs.75995.00

=== forEach (Java 8+) — apply discount ===
  Webcam       Rs.  3499.00 → Rs.  3149.10 (10% off)
  Laptop       Rs. 49999.00 → Rs. 44999.10 (10% off)
  Monitor      Rs. 18999.00 → Rs. 17099.10 (10% off)
  Keyboard     Rs.  2499.00 → Rs.  2249.10 (10% off)
  Mouse        Rs.   999.00 → Rs.   899.10 (10% off)

Java 8 Map Methods — compute, merge, getOrDefault

These methods eliminate boilerplate null-check patterns that appear constantly in production code.

Output:
=== Word frequency with getOrDefault ===
Frequencies: {hibernate=1, java=3, spring=2, hashmap=1}

=== computeIfAbsent — group by category ===
  Veg: [Onion, Tomato]
  Dairy: [Milk]
  Fruits: [Mango, Banana, Apple]

=== merge — safe aggregation ===
Sales by city: {Pune=1, Delhi=2, Mumbai=3}

=== compute — apply discount to specific key ===
After compute: {Laptop=44999.1, Mouse=999.0}

=== putIfAbsent — idempotent registration ===
putIfAbsent(user-001): session-A
putIfAbsent(user-002): null
Sessions: {user-001=session-A, user-002=session-C}

Real-World Example — Meesho Seller Session Cache

A session cache at Meesho stores active seller sessions for the API gateway. Incoming requests carry a session token. The gateway looks up the session in O(1) to verify the seller's identity and permissions before forwarding to downstream services. Sessions expire after inactivity and must be evicted. HashMap provides the O(1) lookup; a timestamp field inside the session handles expiry.

Output:
--- Registering seller sessions ---
  REGISTERED: Session[seller=FashionHub, token=...abc123]
  REGISTERED: Session[seller=ElectroWorld, token=...def456]
  REGISTERED: Session[seller=KitchenKing, token=...ghi789]

--- Incoming requests ---
  AUTH OK : Session[seller=FashionHub, token=...abc123]  permissions=[READ, WRITE, PUBLISH]
  AUTH OK : Session[seller=ElectroWorld, token=...def456]  permissions=[READ, WRITE]
  AUTH FAILED  : unknown token ...z999

--- After inactivity period ---
  SESSION EXPIRED: Session[seller=KitchenKing, token=...ghi789]
  SESSION EXPIRED: Session[seller=FashionHub, token=...abc123]

--- Eviction sweep ---
  EVICTED: Session[seller=ElectroWorld, token=...def456]
  Eviction sweep complete. Evicted: 1  Remaining: 0

Active sessions: 0

Performance Considerations

O(1) average vs worst case: The O(1) average degrades to O(n) if all keys hash to the same bucket. Java 8 treeification caps this at O(log n) for long chains. A well-distributed hashCode() prevents degradation entirely.

Iteration cost O(n + capacity): HashMap iteration scans all buckets including empty ones. A HashMap with capacity 16,384 but only 5 entries iterates 16,389 slots. LinkedHashMap iterates only the live entries via its linked list — O(n). For sparse maps where iteration is frequent, LinkedHashMap is preferable.

Thread safety: HashMap is not thread-safe. Two threads calling put() simultaneously can corrupt the table — in Java 6 and earlier, concurrent resizing could create a circular linked-list cycle, causing infinite loops. In Java 8+, the resize mechanism is safer but data corruption is still possible. Use ConcurrentHashMap for concurrent access — it uses segment-level locking and provides atomic computeIfAbsent, putIfAbsent, and merge operations.

Best Practices

Pre-size the map when the expected entry count is known. Each resize doubles the table and rehashes all entries — O(n) per resize. For a map that will hold 10,000 entries, use new HashMap<>(10000 / 0.75 + 1) — approximately new HashMap<>(13334). This allocates a table of capacity 16,384 and prevents all resizes during loading. The formula is expectedSize / loadFactor + 1.

Always override both equals() and hashCode() together on custom key classes. HashMap uses hashCode() to find the bucket and equals() to confirm the exact match. Overriding only equals() causes two logically equal keys to land in different buckets — get() returns null for a key that was clearly put(). IDEs generate both methods from the same fields in one action. Use Objects.hash(field1, field2) and Objects.equals(field1, other.field1) for null-safety.

Use entrySet() for iteration, not keySet() followed by get(). for (Entry<K,V> e : map.entrySet()) retrieves both key and value in one step. for (K key : map.keySet()) { V value = map.get(key); } performs a second hash lookup for every key — O(n) extra hash computations. In a map with 100,000 entries, this doubles the iteration cost.

Use Java 8 methods to eliminate null-check boilerplate. getOrDefault(key, default) replaces value = map.get(key); if (value == null) value = default. computeIfAbsent(key, k -> new ArrayList<>()) is cleaner than checking containsKey before creating a new list. merge(key, 1, Integer::sum) is the cleanest word-count pattern — no null check required.

Common Mistakes

Mistake 1 — Using a Mutable Key Whose hashCode Changes After Insertion

Mistake 2 — Calling get() Inside keySet() Loop Instead of Using entrySet()

Mistake 3 — Modifying the Map Directly Inside entrySet() For-Each

Mistake 4 — Using HashMap in Multi-threaded Code Without Synchronisation

Interview Questions

Q1. How does HashMap work internally in Java?

HashMap stores entries in a Node[] array called table. When put(key, value) is called, it computes an index as hash(key.hashCode()) & (capacity - 1) and stores the entry at that index. If two keys produce the same index (a collision), they are chained as a linked list at that bucket. In Java 8+, when a chain exceeds 8 entries and the table has at least 64 buckets, the chain is converted to a Red-Black tree — improving worst-case lookup from O(n) to O(log n). get(key) uses the same hash to find the bucket, then walks the chain comparing equals() until the matching key is found.

Q2. What is the role of hashCode() and equals() in HashMap?

hashCode() determines which bucket the key maps to — it is the first step in locating an entry. equals() confirms the exact match within the bucket — multiple keys can share a bucket (collisions), so equality checking is needed to find the right one. The contract: if a.equals(b) is true, then a.hashCode() must equal b.hashCode(). If hashCode() is overridden but equals() is not, two logically equal keys land in the same bucket but equals() returns false — get() finds the bucket but not the entry. If equals() is overridden but hashCode() is not, equal keys land in different buckets — get() looks in the wrong bucket entirely.

Q3. What is the default load factor of HashMap and why is 0.75 the default?

The default load factor is 0.75, meaning HashMap resizes when 75% of its buckets are occupied. The value 0.75 is a balance between two competing costs: a lower load factor (e.g., 0.5) keeps buckets sparse — fewer collisions, faster lookup — but wastes more memory. A higher load factor (e.g., 0.9) uses memory more efficiently but increases collision chains, degrading average lookup time. 0.75 was empirically shown to provide good throughput and acceptable space overhead under typical key distribution patterns.

Q4. What is treeification in HashMap and why was it introduced in Java 8?

Treeification converts a bucket's linked list into a Red-Black tree when the chain length exceeds 8 entries and the table size is at least 64. Before Java 8, an attacker could craft a set of keys with identical hashCode() values, forcing all entries into one bucket and degrading every get() and put() to O(n). With treeification, even adversarial hash distributions produce O(log n) per operation. The tree reverts to a linked list when it shrinks below 6 entries. This change made HashMap resistant to hash-flooding denial-of-service attacks without sacrificing average-case O(1) performance.

Q5. What is the difference between HashMap and ConcurrentHashMap?

HashMap is not thread-safe. Concurrent puts from two threads can corrupt the internal table — in Java 6, concurrent resizing could create a circular reference in the linked list, causing an infinite loop. ConcurrentHashMap divides the map into segments (Java 7) or uses CAS and bucket-level synchronisation (Java 8+), allowing multiple threads to read and write without blocking each other unnecessarily. ConcurrentHashMap also provides atomic compound operations: putIfAbsent(), computeIfAbsent(), and merge() — essential for race-condition-free patterns like counters and caches. It does not allow null keys or values. Collections.synchronizedMap(new HashMap<>()) exists but synchronises on the entire map object — much slower under concurrent load.

Q6. Why should HashMap keys be immutable?

HashMap computes the bucket index from key.hashCode() at the time of put(). If the key is mutable and a field used in hashCode() changes after insertion, the entry is now stored in bucket A but its new hash points to bucket B. Any subsequent get() with the same key lands in bucket B, finds nothing, and returns null. The entry is effectively lost — size() still counts it but it can never be retrieved or removed through normal operations. Using immutable keys — String, Integer, UUID, or a custom immutable record — eliminates this bug entirely.

FAQs

What is the default initial capacity of HashMap in Java?

The default initial capacity is 16 buckets with a load factor of 0.75. The first resize fires when size exceeds 12 (16 × 0.75). The constructor new HashMap<>(initialCapacity) lets you specify a different starting capacity, which is rounded up to the next power of 2. For known sizes, pre-sizing avoids resize overhead: new HashMap<>(expectedSize / 0.75 + 1).

Can HashMap have duplicate keys?

No. If you put() a key that already exists, the new value replaces the old one. The old value is returned by put(). HashMap can have duplicate values — multiple keys can map to the same value — but each key appears exactly once.

What is the difference between HashMap and Hashtable?

Hashtable is the legacy synchronised map from Java 1.0. Every method acquires a mutex, even in single-threaded code. It does not allow null keys or values. HashMap is faster (no synchronisation), allows one null key and unlimited null values, and was introduced in Java 1.2 as the non-synchronised replacement. For concurrent use, ConcurrentHashMap is the correct modern choice — not Hashtable.

How does HashMap handle a null key?

HashMap places the null key in bucket 0, bypassing the hashCode() call entirely (which would throw NullPointerException for a null object). There can be at most one null key. get(null) looks specifically in bucket 0. TreeMap and Hashtable do not support null keys — TreeMap calls compareTo(null), which throws, and Hashtable has an explicit null check.

What happens when two keys have the same hashCode but are not equal?

This is a hash collision. Both entries are stored in the same bucket as a linked list (or tree, if the chain is long enough to trigger treeification). get() walks the chain, calling equals() on each entry until the correct key is found. Collisions are normal and expected — they degrade O(1) average to O(k) where k is the chain length for that bucket. Good hashCode() implementations spread keys evenly across buckets to keep chains short.

Does HashMap maintain insertion order?

No. HashMap makes no guarantee about iteration order — entries may appear in any order, and the order can change after a resize. If insertion order is required, use LinkedHashMap, which maintains a doubly-linked list through all entries in insertion sequence. If sorted key order is required, use TreeMap.

Summary

HashMap<K, V> achieves O(1) average put(), get(), and remove() by converting each key to a bucket index via hash(key.hashCode()) & (capacity - 1). Collisions are handled by separate chaining — linked lists that treeify to Red-Black trees when a bucket exceeds 8 entries in Java 8+. Resize fires at 75% capacity and doubles the table.

Two rules govern correctness: override both equals() and hashCode() on key classes using the same fields, and never mutate those fields after insertion. Violating either produces lost entries that size() counts but get() cannot retrieve.

For interviews: explain the two-step lookup (hashCode → bucket, equals → node), describe the load factor and resize trigger, know the difference between HashMap and ConcurrentHashMap for thread safety, and describe treeification and why it was introduced. These questions cover everything from TCS fresher rounds through Flipkart and Razorpay senior rounds.

What to Read Next