Recent results on hash tables

Table of Contents

1 Types of hash tables

2 Metrics

3 Lower bounds

4 Iceberg hashing (2023)

5 IcebergHT (2023)

6 Tight Bounds for Classical Open Addressing (2024)

7 Optimal Non-oblivious Open Addressing (2025)

8 Optimal Bounds for Open Addressing Without Reordering

8.1 Funnel hashing

8.2 Elastic hashing

endtoc

[ \newcommand{\inv}{^{-1}} \newcommand{\di}{\delta\inv} \newcommand{\poly}{\mathrm{poly}} ]

This post summarizes some recent results and idea on various types hash tables. Collected together with Stefan Walzer.