Modern Hashing Made Simple

Michael A. Bender, Martín Farach-Colton, John Kuszmaul, William Kuszmaul

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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.

    Original languageEnglish (US)
    Title of host publication2024 Symposium on Simplicity in Algorithms, SOSA 2024
    EditorsMerav Parter, Seth Pettie
    PublisherSociety for Industrial and Applied Mathematics Publications
    Number of pages11
    ISBN (Electronic)9781713887171
    StatePublished - 2024
    Event7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024 - Alexandria, United States
    Duration: Jan 8 2024Jan 10 2024

    Publication series

    Name2024 Symposium on Simplicity in Algorithms, SOSA 2024


    Conference7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024
    Country/TerritoryUnited States

    ASJC Scopus subject areas

    • Mathematics (miscellaneous)


    Dive into the research topics of 'Modern Hashing Made Simple'. Together they form a unique fingerprint.

    Cite this