JDK Bug Analysis

This article discusses a subtle issue discovered in JDK 8 related to the computeIfAbsent method within ConcurrentHashMap.

Discovery Process

The issue came to light while reviewing changes in Apache Dubbo 2.7.7. A specific bug fix was noted:

JDK-8062841: Deadlock in ConcurrentHashMap.computeIfAbsent when keys have identical hash codes.

This bug was resolved in JDK 9 by Doug Lea himself.

Reproduction Case

The problem manifests when two keys with the same hash code attempt to use computeIfAbsent concurrently. Consider this minimal test case:

import java.util.concurrent.ConcurrentHashMap;

class Test {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
        
        // These keys produce identical hash codes
        String key1 = "AaAa";
        String key2 = "BBBB";
        
        // This will cause an infinite loop in JDK 8
        map.computeIfAbsent(key1, k -> {
            // Recursive call to computeIfAbsent with another key
            return map.computeIfAbsent(key2, k -> 42);
        });
    }
}

In JDK 8, this code enters an infinite loop because both keys map to the same internal slot.

Root Cause Analysis

When keys share the same hash code:

1. Both attempts target the same array index
2. The first operation places a ReservationNode to reserve space
3. During processing, the second operation encounters the reservation node
4. It cannot proceed due to lack of proper exit conditions in the loop

The critical issue occurs in the computeIfAbsent implementation where:

• Key "AaAa" reserves position with a ReservationNode
• Key "BBBB" tries to access the same slot
• The algorithm gets stuck in a loop because it doesn't properly handle the reservation state

Solution in JDK 9

The fix introduced in JDK 9 adds explicit checks for ReservationNode:

if (f instanceof ReservationNode)
    throw new IllegalStateException("Recursive update");

This prevents the deadlock by detecting recursive operations early.

Practical Workaround for JDK 8

Avoid nested computeIfAbsent calls:

// Instead of nested calls
map.computeIfAbsent(key1, k -> map.computeIfAbsent(key2, k2 -> 42));

// Use separate operations
if (map.get(key1) == null) {
    map.putIfAbsent(key1, map.computeIfAbsent(key2, k -> 42));
}

Thread Safety Considerations

While ConcurrentHashMap provides thread safety for individual operations, combining multiple operations requires care:

// Not safe without external synchronization
map.put(key, value);
Integer result = map.get(key);

// Safe approach
synchronized(map) {
    map.put(key, value);
    Integer result = map.get(key);
}

Conclusion

This behavior highlights the importance of understanding implementation details and the need for careful testing of concurrent data structures.