DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2026.28

Bounded Linear Probing Hashing

Authors: Ahmed Alharbi, Cyril Banderier, and Charles Bouillaguet

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract

We introduce a process that inserts elements into a hash table with a bounded number of probes, motivated by an application in cryptography. The cost of this algorithm is the number of insertion trials, whether successful or failed, until the table gets completely filled. This gives an interpolation between linear probing hashing and the coupon collector problem. We show that the process is related to a non-linear differential equation, which allows us to obtain the generating function of full tables. The proofs involve a full algebra of operators, which are themselves of independent interest. Then, we obtain the asymptotic behaviour of the expected number of insertion trials to get a full table.

Cite as

Ahmed Alharbi, Cyril Banderier, and Charles Bouillaguet. Bounded Linear Probing Hashing. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alharbi_et_al:LIPIcs.AofA.2026.28,
  author =	{Alharbi, Ahmed and Banderier, Cyril and Bouillaguet, Charles},
  title =	{{Bounded Linear Probing Hashing}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.28},
  URN =		{urn:nbn:de:0030-drops-262995},
  doi =		{10.4230/LIPIcs.AofA.2026.28},
  annote =	{Keywords: Linear probing hashing, analytic combinatorics, cryptography}
}

Search Results

Documents authored by Alharbi, Ahmed

Bounded Linear Probing Hashing

Abstract

Cite as

Thanks for your feedback!

Could not send message