Reproduce “Incremental Open Addressing Has No Time-Space Tradeoff” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Martín Farach-Colton, Andrew Krapivin, William Kuszmaul

The authors construct a fixed-capacity, insert-only open-addressed hash table that supports insertions and positive and negative queries in O(1) worst-case expected time, even when full. It uses reordering, fixed nonadaptive probe sequences, and only a counter as external metadata. The bound is over random hash functions, not a measured latency; it does not cover deletions or resizing.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.