2026-07-24T11:54:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20246 2024-07-02T07:52:53Z ddc:004 open_access

Towards an Analysis of Quadratic Probing Kuszmaul, William Xi, Zoe quadratic probing hashing open addressing witness trees Since 1968, one of the simplest open questions in the theory of hash tables has been to prove anything nontrivial about the correctness of quadratic probing. We make the first tangible progress towards this goal, showing that there exists a positive-constant load factor at which quadratic probing is a constant-expected-time hash table. Our analysis applies more generally to any fixed-offset open-addressing hash table, and extends to higher load factors in the case where the hash table examines blocks of some size B = ω(1). Schloss Dagstuhl – Leibniz-Zentrum für Informatik William Kuszmaul and Zoe Xi 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.103 urn:nbn:de:0030-drops-202463 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.103 eng https://creativecommons.org/licenses/by/4.0/legalcode