Skip to main content

5.5 Map Hierarchy & HashMap Internals Architecture

← Back to Chapter 5: Collections Framework

Map<K, V> maps unique keys to values. HashMap is Java's quintessential hash table implementation.

1. Internal Architecture: Buckets & Treeification (Java 8+)​

  HashMap Table: Node<K, V>[] table (Array of power-of-two size)
  ┌────┬────────────────────────────────────────────────────────┐
  │ 0  │ null                                                   │
  ├────┼────────────────────────────────────────────────────────┤
  │ 1  │ [Node A] ──► [Node B] ──► [Node C] (Singly-Linked List)│
  ├────┼────────────────────────────────────────────────────────┤
  │ 2  │ null                                                   │
  ├────┼────────────────────────────────────────────────────────┤
  │ 3  │ [TreeNode Root] (Red-Black BST: TreeBin, depth <= 8)   │
  └────┴────────────────────────────────────────────────────────┘

Key Internal Parameters​

  1. Default Initial Capacity: 16 (always a power of 2: 2^n).
  2. Default Load Factor: 0.75 (balance between space efficiency and collision probability).
  3. Threshold: capacity * loadFactor (e.g., 16 * 0.75 = 12).
  4. TREEIFY_THRESHOLD: 8 (when a bucket reaches 8 elements, it converts to Red-Black Tree).
  5. UNTREEIFY_THRESHOLD: 6 (when tree shrinks to 6, it reverts to linked list).
  6. MIN_TREEIFY_CAPACITY: 64 (table will resize rather than treeify if table capacity is less than 64).

2. Hash Calculation & Index Bitmasking​

Instead of costly division / modulo (hash % length), Java calculates bucket index with bitwise AND:

// 1. Bit Spreading (Perturbation Function)
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 2. Index Calculation (Requires length to be power of 2)
int index = (n - 1) & hash;

3. LinkedHashMap & TreeMap​

  • LinkedHashMap: Extends HashMap with a doubly-linked list running through all nodes. Can be ordered by insertion order or access order (used to build LRU Caches via removeEldestEntry()).
  • TreeMap: Red-Black Tree implementation guaranteeing O(log n) key search, insertion, and deletion while maintaining keys sorted by natural ordering or custom Comparator.