ConcurrentHashMap utilizes a mechanism known as a thread probe to minimize contention among threads. When a thread adds an element to the map, it uses not only the key's hash but also a dedicated thread-specific probe value to select a bucket. This strategy helps distribute work across different buckets, reducing the likelihood of collisions.

Unlike a key's hash, which is fixed and essential for locating its value, the probe value can be dynamically altered. If multiple threads consistently collide on the same bucket, one of them can have its probe value changed, forcing it to attempt a different bucket. This functionality is provided by the ThreadLocalRandom class.

Let's examine how this is implemented. The ThreadLocalRandom.getProbe() method retrieves the probe value for the current thread. This value is stored in a special field within the Thread object.

// Retrieves the probe value for the current thread.
static final int getProbe() {
    return UNSAFE.getInt(Thread.currentThread(), PROBE_OFFSET);
}

This value is accessed via the memory offset of the threadLocalRandomProbe field in the Thread class. This offset is calculated during class iintialization.

// Unsafe mechanics for accessing thread-local fields
private static final sun.misc.Unsafe UNSAFE;
private static final long PROBE_OFFSET;

static {
    try {
        UNSAFE = sun.misc.Unsafe.getUnsafe();
        Class<?> threadClass = Thread.class;
        PROBE_OFFSET = UNSAFE.objectFieldOffset(
            threadClass.getDeclaredField("threadLocalRandomProbe")
        );
    } catch (Exception e) {
        throw new Error(e);
    }
}

The threadLocalRandomProbe field itself is defined in the Thread class but is initialized by ThreadLocalRandom.

// Probe hash value; initialized when the seed is set
@sun.misc.Contended("tlr")
int threadLocalRandomProbe;

Initialization occurs in the ThreadLocalRandom.localInit() method. This method sets both the initial probe value and a seed value for random number generation.

/**
 * Initializes thread-local fields for the current thread.
 * This is called when the probe value is zero, indicating
 * that a new seed and probe need to be generated.
 */
static final void localInit() {
    // probeSource is an AtomicInteger
    // PROBE_STEP is a static constant, value 0x9e3779b9
    int initialProbe = probeSource.addAndGet(PROBE_STEP);
    if (initialProbe == 0) {
        initialProbe = 1; // Avoid zero
    }
    long initialSeed = mix64(seedSource.getAndAdd(SEED_INCREMENT));
    Thread currentThread = Thread.currentThread();
    // Initialize the thread's threadLocalRandomSeed field
    UNSAFE.putLong(currentThread, SEED_OFFSET, initialSeed);
    // Initialize the thread's threadLocalRandomProbe field
    UNSAFE.putInt(currentThread, PROBE_OFFSET, initialProbe);
}

When contention is detected, the ThreadLocalRandom.advanceProbe() method generates a new probe value using a simple xorshift algorithm.

/**
 * Pseudo-randomly advances and records a new probe value for the current thread.
 */
static final int advanceProbe(int currentProbe) {
    currentProbe ^= (currentProbe << 13);
    currentProbe ^= (currentProbe >>> 17);
    currentProbe ^= (currentProbe << 5);
    UNSAFE.putInt(Thread.currentThread(), PROBE_OFFSET, currentProbe);
    return currentProbe;
}

In ConcurrentHashMap, the fullAddCount method orchestrates this process. If a thread lacks an initialized probe, it calls localInit(). If contention occurs, it calls advanceProbe() to try a different bucket.

private final void fullAddCount(long count, boolean uncontended) {
    int probeValue;
    if ((probeValue = ThreadLocalRandom.getProbe()) == 0) {
        ThreadLocalRandom.localInit(); // Force initialization
        probeValue = ThreadLocalRandom.getProbe();
        uncontended = true;
    }
    // ... further logic for handling collisions
    probeValue = ThreadLocalRandom.advanceProbe(probeValue);
    // ... use the new probeValue for bucket selection
}