In immutable open addressing, locality Ω(1/ε²) at some load is unavoidable, matching linear probing; with the final load known, Õ(1/ε) per-operation probes and locality are achievable.
Microscopic description of Log and Coulomb gases
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
These are the lecture notes of a course taught at the Park City Mathematics Institute in June 2017. They are intended to review some recent results, obtained in large part with Thomas Lebl\'e, on the statistical mechanics of systems of points with logarithmic or Coulomb interactions. After listing some motivations, we describe the "electric approach" which allows to get concentration results, Central Limit Theorems for fluctuations, and a Large Deviations Principle expressed in terms of the microscopic state of the system.
fields
cs.DS 1years
2026 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Locality in Open Addressing Hash Tables
In immutable open addressing, locality Ω(1/ε²) at some load is unavoidable, matching linear probing; with the final load known, Õ(1/ε) per-operation probes and locality are achievable.