HashMap Core Characteristics

HashMap implements key-value storage using hash tables, offering non-thread-safe operations. Both keys and values can be null, and entries are unordered. Pre-JDK 1.8, HashMap used array-chaining (linked lists) to resolve collisions. Since JDK 1.8, when bucket chains exceed 8 elements and the array size surpasses 64, chains convert to red-black trees for optimized search performance. Below threshold 6, trees revert to linked lists.

Internal Data Structure

Storage Process

Map<String, Integer> userAges = new HashMap<>();
userAges.put("Alice", 30);
userAges.put("Bob", 25);
userAges.put("Charlie", 40);
userAges.put("Alice", 32);  // Update existing key

Output: {Bob=25, Alice=32, Charlie=40}. Storage mechanics:

1. Initial array creation (size=16) occurs on first insertion
2. Index calculation: (array_length - 1) & hash(key)
3. Hash collisions resolved via chaining or tree convertion
4. Identical keys trigger value updates via equals()
5. Resizing doubles capacity when exceeding threshold = capacity * loadFactor

Common Intevriew Questions

1. Hash function: Computes (hashCode ^ (hashCode >>> 16)) for optimal bit distribution
2. Hash collisions: Identical hashcodes trigger chaining or tree cnoversion
3. Key storage: When hashcodes match, equals() determines key uniqueness

Class Inheritance

HashMap extends AbstractMap and implements Map, Cloneable, and Serializable. The redundant Map interface implementation is a historical artifact retained for compatibility.

Key Components

Critical Variables

• DEFAULT_INITIAL_CAPACITY = 16: Initial size (power-of-two for bitmask efficiency)
• DEFAULT_LOAD_FACTOR = 0.75f: Capacity expansion trigger point
• TREEIFY_THRESHOLD = 8: Minimum chain length for tree conversion
• UNTREEIFY_THRESHOLD = 6: Tree-to-chain reversion threshold
• MIN_TREEIFY_CAPACITY = 64: Minimum array size for tree conversion
• threshold = capacity * loadFactor: Size limit before resizing

Capacity Initialization

static int calculateCapacity(int target) {
    int adjusted = target - 1;
    adjusted |= adjusted >>> 1;
    adjusted |= adjusted >>> 2;
    adjusted |= adjusted >>> 4;
    adjusted |= adjusted >>> 8;
    adjusted |= adjusted >>> 16;
    return (adjusted < 0) ? 1 : 
        (adjusted >= MAX_CAPACITY) ? MAX_CAPACITY : adjusted + 1;
}

Ensures capacities are powers-of-two via bitwise operations. The 0.75 load factor balances memory efficiency and collision probability, derived from Poisson distribution statistics where tree conversion probability at length 8 is ~0.00000006.

Constructors

// Default: 16 capacity, 0.75 load factor
HashMap() 

// Custom initial capacity
HashMap(int initialCapacity)

// Full parameter control
HashMap(int initialCapacity, float loadFactor)

Core Functionality

Insertion Mechanism

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // Index calculation and collision handling
    // Tree conversion when thresholds exceeded
}

Hash computation: (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16). Handles collisions via chaining or tree conversion after checking key equality.

Tree Conversion

final void convertToTree(Node<K,V>[] table, int hash) {
    if (table == null || table.length < MIN_TREEIFY_CAPACITY) 
        resize();
    else if ((e = table[index]) != null) {
        // Replace chain with balanced tree
    }
}

Converts chains to red-black trees only when both chain length and array size exceed thresholds.

Dynamic Resizing

final Node<K,V>[] resize() {
    // Double capacity, redistribute entries
    // Preserve order: entries stay in original bucket or shift by oldCapacity
}

Resizing occurs when size > threshold. Elements redistribute using (hash & oldCapacity) == 0 to determine new bucket locations, exploiting power-of-two capacity for efficient rehashing.

Element Retrieval

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    // Check bucket head first
    // Traverse chain/tree if needed
}

Uses tree searches (O(log n)) or chain traversal (O(n)) based on bucket structure.

Efficient Traversal

// Recommended approach
map.forEach((k, v) -> System.out.println(k + ": " + v));

// EntrySet iteration
for (Map.Entry<K, V> entry : map.entrySet()) {
    // Process entry
}

Initial Capacity Optimization

Set initial capacity to expectedEntries / 0.75 + 1 to minimize resizing. For example, 12 expected entries requires (12 / 0.75) + 1 = 17 → 32 (nearest power-of-two). This prevents redundant rehashing while avoiding excessive memory allocation.