Java HashMap Deep Dive — Internals and Performance

5 minute read

HashMap is Java’s most-used Map implementation. Understanding its internals — hash functions, buckets, collisions, and load factor — helps you write faster code and avoid subtle bugs.

How HashMap Works

put("Alice", 30):
  1. hashCode("Alice") → 92668751
  2. bucketIndex = hash & (capacity - 1) → e.g., 3
  3. Store in bucket[3]

  Buckets (internal Node[] array):
  ┌─────┬─────┬─────┬─────────────────┬─────┬─────┐
  │  0  │  1  │  2  │      3          │  4  │ ... │
  │null │null │null │ Alice→30        │null │     │
  └─────┴─────┴─────┴─────────────────┴─────┴─────┘

put("Bob", 25):   hash → bucket 7
put("Eve", 28):   hash → bucket 3 (collision!)

  ┌─────┬─────┬─────┬─────────────────────────┬─────┬─────┬─────┬─────┐
  │  0  │  1  │  2  │          3              │  4  │  5  │  6  │  7  │
  │null │null │null │ Alice→30 → Eve→28       │null │null │null │Bob→25│
  └─────┴─────┴─────┴─────────────────────────┴─────┴─────┴─────┴─────┘
                     └── linked list for collisions

The Hash Function

Java’s HashMap applies an additional spread to avoid clustering:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

This XORs the upper 16 bits with the lower 16 bits, spreading hash values more evenly across buckets.

Bucket Index

int index = hash & (capacity - 1);  // equivalent to hash % capacity
                                     // when capacity is a power of 2

This is why HashMap capacity is always a power of 2.

Collisions

When two keys land in the same bucket, HashMap handles it with:

1. Linked List (Default)

Bucket 3: Alice→30 → Eve→28 → Charlie→35
           (linked list chain)

With many collisions, get() degrades from O(1) to O(n).

2. Red-Black Tree (Java 8+ — Treeification)

When a bucket has ≥ 8 entries (and capacity ≥ 64), the linked list is converted to a red-black tree:

Bucket 3: [Red-Black Tree]
           O(log n) instead of O(n)

When the count drops below 6, it converts back to a linked list.

TREEIFY_THRESHOLD  = 8   (list → tree)
UNTREEIFY_THRESHOLD = 6  (tree → list)
MIN_TREEIFY_CAPACITY = 64 (table must be this big to treeify)

Capacity and Load Factor

Parameter Default Meaning
Initial capacity 16 Number of buckets
Load factor 0.75 Ratio of entries to capacity before resize
Resize threshold capacity × loadFactor = 12 When rehashing happens

Resizing (Rehashing)

When size > capacity × loadFactor:

  1. Create new array with 2× capacity.
  2. Rehash every entry into the new array.
  3. This is O(n) — expensive.
Entries: 0......12 → resize! → 0...................24 → resize! → ...
Capacity:    16                        32

Pre-sizing to Avoid Resizing

// If you know you'll have ~100 entries:
// threshold = capacity * 0.75
// capacity needed = 100 / 0.75 = 134 → round up to 256 (power of 2)
Map<String, Integer> map = new HashMap<>(134); // rounds to next power of 2

The hashCode() Contract

For HashMap to work correctly:

  1. Consistent: hashCode() must return the same value for the same object (unless mutated).
  2. Equal objects → equal hashCodes: If a.equals(b), then a.hashCode() == b.hashCode().
  3. Unequal objects → different hashCodes (recommended, not required). Better distribution = fewer collisions.
public class Employee {
    private final int id;
    private final String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Employee e)) return false;
        return id == e.id && Objects.equals(name, e.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);  // uses both fields
    }
}

What Happens with Bad hashCode()?

// TERRIBLE — all objects in same bucket → O(n) everything
@Override public int hashCode() { return 42; }

// BAD — only uses one field → more collisions
@Override public int hashCode() { return id; }

// GOOD — uses all equality fields
@Override public int hashCode() { return Objects.hash(id, name, department); }

null Key Handling

HashMap allows one null key — it’s always stored in bucket 0:

Map<String, String> map = new HashMap<>();
map.put(null, "no key");
map.get(null);  // "no key"

TreeMap, ConcurrentHashMap, and Hashtable do not allow null keys.

Big-O Complexity

Operation Average Worst (all collisions) With Treeification
get(key) O(1) O(n) O(log n)
put(key, value) O(1) O(n) O(log n)
remove(key) O(1) O(n) O(log n)
containsKey(key) O(1) O(n) O(log n)
containsValue(value) O(n) O(n) O(n)

LinkedHashMap

Maintains insertion order (or optionally access order):

Map<String, Integer> ordered = new LinkedHashMap<>();
ordered.put("C", 3);
ordered.put("A", 1);
ordered.put("B", 2);
System.out.println(ordered);  // {C=3, A=1, B=2} — insertion order

LRU Cache with Access Order

Map<String, String> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 100;  // evict when exceeding 100 entries
    }
};

Setting the third constructor parameter to true switches to access order — the most recently accessed entry moves to the end.

WeakHashMap

Keys are held by weak references — entries are automatically removed when the key is garbage collected:

Map<Object, String> cache = new WeakHashMap<>();
Object key = new Object();
cache.put(key, "cached data");

key = null;  // remove strong reference
System.gc(); // suggest GC (not guaranteed)
// cache may now be empty — entry was collected

Use for memory-sensitive caches where entries should be evictable.

HashMap vs TreeMap vs LinkedHashMap

Feature HashMap TreeMap LinkedHashMap
Order None Sorted by key Insertion order
get/put O(1) O(log n) O(1)
Null keys ✅ (one) ❌ ✅ (one)
Thread-safe ❌ ❌ ❌
Memory Low Moderate Moderate
Use case General purpose Sorted data, range queries Ordered iteration, LRU cache

Common Mistakes

Mistake Problem Fix
Mutable keys Key’s hash changes → entry lost Use immutable keys (String, Integer)
Missing hashCode() Equal objects in different buckets Override equals() + hashCode()
Not pre-sizing Multiple expensive resizes new HashMap<>(expectedSize)
containsKey() + get() Two lookups instead of one Use getOrDefault() or computeIfAbsent()
HashMap in multithreaded code Data corruption, infinite loop (pre-Java 8) Use ConcurrentHashMap

Key Takeaways

  1. HashMap uses a hash table with buckets, O(1) average for get/put.
  2. Collisions are handled by linked lists (→ red-black trees at 8+ entries).
  3. Default load factor 0.75 balances time vs space; rehashing is O(n).
  4. Always override equals() + hashCode() — the contract is non-negotiable.
  5. Pre-size HashMap when you know the entry count.
  6. Use LinkedHashMap for ordered iteration, TreeMap for sorted keys.

What’s Next?

Next: Deque and ArrayDeque — double-ended queue internals, circular array, and performance.

Updated:

You may also enjoy