# Optimal Bounds for Open Addressing Without Reordering

**Authors:** Martin Farach-Colton, Andrew Krapivin, William Kuszmaul  
**arXiv:** [2501.02305](https://arxiv.org/abs/2501.02305)  
**Date:** 2025-01-04  
**Summary page:** https://www.summarizepaper.com/en/paper/2501.02305v1/

## Key points

- Authors: Martin Farach-Colton, Andrew Krapivin, William Kuszmaul
- Topic: Optimal bounds for open addressing without reordering
- Improved search complexities in open-addressed hash tables
- Challenge and disprove of Yao's central conjecture on hashing efficiency
- Concrete evidence and results surpassing existing boundaries
- Fresh perspective on optimizing open addressing techniques
- Accompanying lower bounds validating the proposed approach
- Valuable insights for enhancing search performance in hash tables without reorganization

## Summary

, , , , 

In their paper titled "Optimal Bounds for Open Addressing Without Reordering," authors Martin Farach-Colton, Andrew Krapivin, and William Kuszmaul delve into the fundamental problem of efficiently inserting elements into an open-addressed hash table for later retrieval with minimal probes. The authors demonstrate that it is possible to design a hash table that significantly improves expected search complexities, both in terms of amortized and worst-case scenarios, without the need to reorder elements over time. This challenges and disproves a central conjecture proposed by Yao in his influential work on hashing efficiency. By providing concrete evidence and results that surpass existing boundaries, the authors offer a fresh perspective on optimizing open addressing techniques. The findings presented in this paper come with accompanying lower bounds that further validate the effectiveness of the proposed approach. This study contributes valuable insights to the field of data structures by showcasing innovative strategies for enhancing search performance in hash tables without requiring costly reorganization processes.