Open Addressing & Linear Probing: Why Cache-Friendly Hash Tables Win

If you’ve written Java for any length of time, java.util.HashMap is probably your most-used data structure. It’s flexible, well-tested, and “fast enough” for almost everything. But “fast enough” has a ceiling, and that ceiling is shaped by something most Java developers never think about: CPU cache lines.

This post explains how HashMap works under the hood, why its memory layout fights against your CPU, and how the Mapish project takes a radically different approach—open addressing with linear probing in a single contiguous block of off-heap memory—to turn the hardware into an ally.

Think of HashMap’s chaining like a filing cabinet where each drawer has sticky notes pointing to other drawers across the room. Open addressing is like a single long shelf where you just slide to the next slot.

1. How java.util.HashMap Works (Separate Chaining)

HashMap uses a strategy called separate chaining. Internally it maintains an array of buckets (Node<K,V>[]). When you call put(key, value), the map hashes the key to find a bucket index. If two keys hash to the same bucket—a collision—the new entry is appended to a linked list hanging off that bucket.

Here’s what that looks like conceptually:

Bucket[0] → null
Bucket[1] → Node("key1") → Node("key5") → null
Bucket[2] → Node("key2") → null
Bucket[3] → null
Bucket[4] → Node("key3") → Node("key7") → Node("key9") → null
Bucket[5] → null
  ...

Each Node is a separate object on the Java heap, containing references to the key, the value, and the .next pointer. Since Java 8, if a single chain grows beyond 8 entries, it converts to a Red-Black Tree for $O(\log n)$ lookup instead of $O(n)$.

The problems

This design is correct and general-purpose, but it has four structural weaknesses that matter at scale:

1. Object explosion. Every entry creates a HashMap.Node object on the heap. One million entries means one million node objects, plus the key and value objects themselves. The GC must scan all of them.
2. Scattered memory. The JVM allocates objects wherever it finds space in the heap. Node objects for the same bucket are rarely adjacent in memory. They’re scattered across the heap like books left open in different rooms.
3. Pointer chasing. To traverse a chain, the CPU must follow .next references. Each reference is a pointer to a different heap location. If that location isn’t in the CPU cache, you pay a cache miss—and a main memory access is ~100× slower than an L1 cache hit.
4. Tree conversion overhead. At 8+ collisions, HashMap converts the linked list to a Red-Black Tree. This improves algorithmic complexity but adds significant memory overhead (TreeNode is larger than Node) and more pointer chasing per lookup.

2. Open Addressing: The Alternative

Open addressing is a collision resolution strategy where all entries live in the same contiguous array. There are no linked lists, no separate node objects, no pointers to chase. When a collision occurs, you simply look at the next slot in the array.

The most common flavors are:

• Linear probing: On collision, try slot $i+1$, then $i+2$, then $i+3$, …
• Quadratic probing: Try slot $i+1$, then $i+4$, then $i+9$, … (offsets grow quadratically)
• Double hashing: Use a second hash function to compute the probe step size.

All three avoid pointer chasing, but linear probing has a unique advantage that we’ll explore in the next section. First, let’s understand why the flat-array model is fundamentally better for memory access:

With open addressing, computing the address of any slot is just simple arithmetic:

address = base + (index * entrySize)

No dereferencing. No indirection. One multiplication and one addition.

3. Linear Probing and CPU Caches (The Key Insight)

Modern CPUs don’t access memory one byte at a time. When you read a single byte, the CPU fetches an entire cache line—typically 64 bytes—from main memory into the L1 cache. Every subsequent access within that 64-byte window is served from cache, which is roughly 100× faster than going to main memory.

This is where linear probing shines. Because probe slots are physically adjacent in memory, the next slot you check is usually on the same cache line as the current one. The CPU has already paid the memory access cost—the next probe is effectively free.

With separate chaining, the picture is the opposite. Each .next pointer leads to a different heap location. The CPU fetches a cache line for the first node, then follows the pointer and discovers the second node is in a completely different cache line—maybe even on a different memory page. That’s a cache miss every hop.

Here’s the punchline: linear probing often outperforms theoretically “better” collision strategies (like quadratic probing or double hashing) precisely because it maximizes cache locality. The constant factor of cache hits dominates the $O(1)$ amortized analysis in practice.

4. How Mapish Implements This

The Mapish project implements open addressing with linear probing on a single off-heap MemorySegment, allocated via Java’s Foreign Function & Memory API. The entire hash table—all entries, all metadata—lives in one contiguous block of native memory.

Allocation

A single call replaces what would be millions of new Node<>() allocations in a standard HashMap:

// The entire table is one allocation
this.memorySegment = arena.allocate((long) this.capacity * entrySize);

Entry layout

Each slot has a fixed binary layout, computed once at construction time:

// Status flags — one byte per slot
private static final byte EMPTY   = 0;
private static final byte FILLED  = 1;
private static final byte DELETED = 2;

// Offset calculations — computed once in the constructor
this.hashOffset  = 4;                                  // after 1-byte status + 3-byte pad
this.keyOffset   = 8;                                  // after the 4-byte hash
this.valueOffset = this.keyOffset + align(keySize, 8); // key size, 8-byte aligned
this.entrySize   = this.valueOffset + align(valueSize, 8);

The probe loop

The core of the lookup is findEntryIndex(). This is where linear probing happens:

private long findEntryIndex(Object key) {
    int h = hash(key);
    int index = h;
    for (int i = 0; i < capacity; i++) {
        long offset = ((long) index) * entrySize;
        byte status = memorySegment.get(ValueLayout.JAVA_BYTE, offset);

        if (status == EMPTY) {
            return -1;
        } else if (status == FILLED) {
            int storedHash = memorySegment.get(ValueLayout.JAVA_INT, offset + hashOffset);
            if (storedHash == h) {
                if (keySerializer.equals((K) key, memorySegment, offset + keyOffset))
                    return index;
            }
        }
        index = (index + 1) % capacity; // linear probing
    }
    return -1;
}

Walk through what happens, step by step:

1. Hash the key to get a starting index.
2. Read the status byte at that slot. If EMPTY, the key doesn’t exist—return immediately.
3. If FILLED, compare the stored hash first. This is a fast rejection filter: a 4-byte integer comparison is far cheaper than a full key comparison. Most non-matching entries are eliminated here.
4. If the hashes match, compare the actual key bytes using keySerializer.equals()—which can use hardware-accelerated MemorySegment.mismatch().
5. If no match, advance to the next slot: index = (index + 1) % capacity. This is the linear probe. The next slot is physically adjacent in the MemorySegment, so it’s likely already in the CPU cache.

5. The Tombstone Problem

With separate chaining, removing an entry is simple: unlink the node from the list. The chain remains intact. With open addressing, deletion is trickier because it can break probe chains.

Imagine three keys—A, B, and C—all hash to slot 5. They end up in slots 5, 6, and 7 via linear probing. Now you delete B (slot 6). If you simply mark slot 6 as EMPTY, a later lookup for C will start at slot 5, see A, probe to slot 6, see EMPTY—and conclude that C doesn’t exist. But C is sitting right there in slot 7.

The solution is a tombstone—a special status byte that means “this slot was occupied; skip over it and keep probing.” In Mapish, the three status values are:

The removal code is straightforward—find the entry, then flip one byte:

// From OffHeapMap.remove() — tombstone deletion
memorySegment.set(ValueLayout.JAVA_BYTE, offset, DELETED);
size--;

The trade-off is that tombstones can accumulate. If you insert and delete millions of entries without resizing, the table fills with DELETED markers, and probe chains get longer even though the logical size hasn’t grown. This is one reason Mapish uses an aggressive load factor, which we’ll cover next.

6. Load Factor and Resizing

The load factor determines when the table resizes. HashMap uses a default of 0.75 (resize when 75% full). Mapish uses 0.5 (resize when 50% full). Why the difference?

With separate chaining, high load factors are tolerable because collisions just make chains longer. Performance degrades gracefully—you’re adding one more node to a linked list.

With open addressing, high load factors are dangerous. As the table fills up, probe chains grow exponentially. At 90% load, a lookup might need to scan dozens of slots before finding the target or an empty slot. The expected number of probes for an unsuccessful search in linear probing is approximately:

At $\alpha = 0.5$, that’s about 2.5 probes. At $\alpha = 0.75$, it’s 8.5. At $\alpha = 0.9$, it’s 50.5. The 0.5 load factor keeps Mapish in the sweet spot: short probe chains, high cache hit rates, and plenty of room for tombstones.

The cost of resizing

When the threshold is reached, Mapish allocates a new segment at double the capacity, then rehashes every FILLED entry into the new segment:

private void resize() {
    int newCapacity = capacity * 2;
    MemorySegment newSegment = arena.allocate((long) newCapacity * entrySize);

    for (int i = 0; i < capacity; i++) {
        long offset = ((long) i) * entrySize;
        byte status = memorySegment.get(ValueLayout.JAVA_BYTE, offset);
        if (status == FILLED) {
            K key = keySerializer.deserialize(memorySegment, offset + keyOffset);
            V value = valueSerializer.deserialize(memorySegment, offset + valueOffset);
            insert(newSegment, newCapacity, key, value, true);
        }
    }

    this.capacity = newCapacity;
    this.memorySegment = newSegment;
    this.threshold = (int) (capacity * LOAD_FACTOR);
}

Resizing is expensive: it touches every live entry, deserializes keys and values, and re-serializes them into the new segment. The tombstones are naturally cleaned up because only FILLED entries are copied.

// Pre-allocate for 2 million entries — no resizes needed
var map = new OffHeapMap<>(keySerializer, valueSerializer, 2_000_000);

7. Summary: Why This Matters

The difference between HashMap and Mapish isn’t just an implementation detail—it’s a fundamental rethinking of how a hash table interacts with hardware. Here’s the comparison at a glance:

Three properties make Mapish fast where it counts:

1. Cache-friendly probing. Linear probing through a contiguous memory segment turns CPU caches into an advantage. Adjacent probes are free.
2. Zero allocations per lookup. No node objects created, no garbage generated. Every get() is a read-only scan of existing native memory.
3. Off-heap storage. The entire data set is invisible to the GC. No scanning, no compacting, no safepoint pauses caused by your hash table. Latency becomes predictable.

HashMap is an excellent general-purpose data structure and remains the right choice for most applications. But when you’re pushing millions of entries, need predictable tail latency, or simply can’t afford GC pauses—the combination of open addressing, linear probing, and off-heap memory offers a fundamentally better contract with your hardware.