Academic Origins | Off-Heap Mapish

None of the techniques in Mapish were invented here. Open addressing, linear probing, region-based memory, and SIMD-accelerated comparison all have deep roots in computer science and systems research. Understanding where these ideas came from adds context to why they work—and helps you evaluate when to reach for them.

This page collects the key academic papers and references behind each of Mapish’s three deep-dive topics: Open Addressing & Linear Probing, Why Off-Heap?, and Zero-Deserialization Lookups.

1. Open Addressing & Linear Probing

The most historically rich technique in the project. Linear probing is one of the oldest algorithms in computer science—predating most programming languages—and its interaction with CPU caches has been a subject of active research for decades.

Paper / Source	Year	Relevance to Mapish
W.W. Peterson, “Addressing for Random-Access Storage”, IBM J. Res. Dev. 1(2)	1957	The original paper introducing open addressing as a collision resolution strategy for hash tables. This is where the concept of probing forward through slots was first formalized.
Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, §6.4	1973	The definitive mathematical analysis of linear probing. Knuth proved that the expected number of probes for a successful search is approximately $\frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)$ for load factor $\alpha$. His analysis actually dates to 1963 notes, making it one of the earliest rigorous results in computer science. Mapish’s choice of a 0.5 load factor is directly informed by this formula.
Pagh, Pagh & Ružić, “Linear Probing with Constant Independence”, SIAM J. Comput. 39(3)	2009	Proves that 5-independent hash functions are sufficient for linear probing to achieve $O(1)$ expected time—resolving a long-standing theoretical question about what hash quality linear probing actually requires.
Heileman & Luo, “How Caching Affects Hashing”, ALENEX ’05	2005	Directly relevant to Mapish’s thesis. Empirically demonstrates that linear probing outperforms chaining and other open addressing schemes specifically because of CPU cache effects. The deep dive’s “cache lines as an ally” argument originates here.
Richter, Alvarez & Dittrich, “A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing”, VLDB Endowment 9(3)	2015	Comprehensive modern survey comparing hashing strategies across multiple dimensions including cache behavior. Confirms linear probing’s superiority for cache-resident workloads.

Timeline: Peterson’s 1957 paper introduced the idea. Knuth’s 1963/1973 analysis proved it worked mathematically. Heileman & Luo (2005) showed it works even better in practice because of hardware. Pagh et al. (2009) settled the theoretical hash-quality question. Richter et al. (2015) confirmed everything in a modern systems context.

2. Off-Heap & Region-Based Memory

The idea of managing memory in bulk by scoping lifetimes—rather than relying on per-object garbage collection—has roots in both programming language theory and systems engineering.

Paper / Source	Year	Relevance to Mapish
Tofte & Talpin, “Region-Based Memory Management”, Information and Computation 132(2)	1997	The foundational theory behind arena/region allocation—the idea that memory can be managed in bulk by scoping lifetimes rather than per-object GC. Mapish’s `Arena`-scoped `MemorySegment` is a direct application of this concept.
Gay & Aiken, “Language Support for Regions”, PLDI ’01	2001	Extends region-based management into practical language design—shows how region annotations can eliminate GC for data-intensive workloads.
Thompson, Farley, Barker & Gee (LMAX), “The LMAX Disruptor”, white paper & mechanical-sympathy.blogspot.com	2011	While not a traditional academic paper, Martin Thompson’s work on mechanical sympathy—designing software that works with hardware—is the philosophical foundation of Mapish’s approach to avoiding GC for latency-critical Java systems. Hugely influential in the off-heap and low-latency Java community.
Perlman, Biboudis, Venneri et al., JEP 454: Foreign Function & Memory API	2023	The Java Enhancement Proposal that standardized the FFM API used by Mapish. Builds on lessons from `Unsafe` and `ByteBuffer` to provide safe, bounded native memory access with arena-scoped lifecycle management.

Key connection: Tofte & Talpin (1997) proved that region-based memory management could be safe and efficient. Two decades later, Java’s FFM API (JEP 454) brought that same model to the JVM with Arena—the exact API Mapish builds on.

3. Zero-Deserialization Lookups & SIMD Comparison

The idea of using vectorized hardware instructions to compare raw data—bypassing object materialization entirely—originates in the database systems research community.

Paper / Source	Year	Relevance to Mapish
Zhou & Ross, “Implementing Database Operations Using SIMD Instructions”, ACM SIGMOD ’02	2002	One of the earliest papers applying SIMD vector instructions to data processing operations—the intellectual ancestor of Mapish’s vectorized key comparison via `MemorySegment.mismatch()`.
Neumann, T., “Efficiently Compiling Efficient Query Plans for Modern Hardware”, VLDB Endowment 4(9)	2011	Argues for data-centric processing that keeps data in registers and caches, avoiding materialization (deserialization). Mapish’s “compare bytes, not objects” philosophy directly mirrors this principle.
Lemire & Boytsov, “Decoding Billions of Integers in Milliseconds Through Vectorization”, Software: Practice and Experience 45(1)	2015	Demonstrates how SIMD intrinsics can process data at memory-bandwidth speed. The same principle underlies HotSpot’s `vectorizedMismatch` stub used by `MemorySegment.mismatch()`.
Polychroniou, Raghavan & Ross, “Rethinking SIMD Vectorization for In-Memory Databases”, ACM SIGMOD ’15	2015	Demonstrates that SIMD vector instructions (the same AVX2/AVX-512 that backs `mismatch()`) can dramatically accelerate in-memory data operations. The paper’s key finding—that vectorized comparison dominates scalar comparison—is exactly why Mapish’s `mismatch()` trick works.

The thread: Zhou & Ross (2002) pioneered SIMD for data processing. Neumann (2011) argued for keeping data in native form to avoid materialization overhead. Polychroniou et al. (2015) proved vectorized comparison dominates. Mapish combines these insights via MemorySegment.mismatch()—a JVM intrinsic that maps directly to AVX2/AVX-512 instructions.

4. Hash Caching (Two-Layer Defense)

Storing hash codes alongside entries to enable fast rejection before full key comparison is a well-established optimization in hash table literature.

Paper / Source	Year	Relevance to Mapish
Donald E. Knuth, TAOCP Vol. 3, §6.4 “Hashing”	1973	Discusses storing hash values alongside entries to enable fast rejection before full key comparison. Java’s own `HashMap` stores the hash in each `Node` for the same reason. Mapish stores it at a fixed offset in native memory.
Celis, P., “Robin Hood Hashing”, PhD thesis, U. Waterloo	1986	While Mapish does not use Robin Hood hashing, Celis’s work formalized the idea of using stored metadata (including hashes) to optimize probe chains in open-addressing tables—a principle Mapish applies directly.

Summary

The techniques in Mapish are not novel individually—they draw from 60+ years of hashing theory (Peterson 1957, Knuth 1963), region-based memory research (Tofte & Talpin 1997), and modern SIMD database processing (Zhou & Ross 2002, Polychroniou et al. 2015).

Mapish’s contribution is combining them in a single java.util.Map implementation using the modern FFM API—something that only became practical with JDK 22.

The most directly citable papers for each technique are:

Cache-Friendly Hashing

Heileman & Luo (2005), “How Caching Affects Hashing”, ALENEX

Region / Arena Memory

Tofte & Talpin (1997), “Region-Based Memory Management”, Information and Computation

SIMD Vectorized Comparison

Polychroniou, Raghavan & Ross (2015), “Rethinking SIMD Vectorization for In-Memory Databases”, ACM SIGMOD