TY - GEN

T1 - Modern Hashing Made Simple

AU - Bender, Michael A.

AU - Farach-Colton, Martín

AU - Kuszmaul, John

AU - Kuszmaul, William

N1 - Publisher Copyright:
Copyright © 2024 by SIAM.

PY - 2024

Y1 - 2024

N2 - Modern work on hashing has led to hash tables with extraordinary guarantees. However, these data structures are too complex to be taught in (even an advanced) data structures course. In this paper, we show that this need not be the case: using standard machinery that we already teach, one can construct a simple hash table that offers guarantees much stronger than what are classically taught: Operations are O(1)-time with high probability; The hash table stores n k-bit items in nk + O(n log log n) bits of space; The hash table is dynamically resized, so the space bound holds with respect to the current size n at each time step.

AB - Modern work on hashing has led to hash tables with extraordinary guarantees. However, these data structures are too complex to be taught in (even an advanced) data structures course. In this paper, we show that this need not be the case: using standard machinery that we already teach, one can construct a simple hash table that offers guarantees much stronger than what are classically taught: Operations are O(1)-time with high probability; The hash table stores n k-bit items in nk + O(n log log n) bits of space; The hash table is dynamically resized, so the space bound holds with respect to the current size n at each time step.

UR - http://www.scopus.com/inward/record.url?scp=85194149899&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85194149899&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85194149899

T3 - 2024 Symposium on Simplicity in Algorithms, SOSA 2024

SP - 363

EP - 373

BT - 2024 Symposium on Simplicity in Algorithms, SOSA 2024

A2 - Parter, Merav

A2 - Pettie, Seth

PB - Society for Industrial and Applied Mathematics Publications

T2 - 7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024

Y2 - 8 January 2024 through 10 January 2024

ER -