Uniform Hashing in Constant Time and Optimal Space

Anna Östlin Pagh, Rasmus Pagh

    Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

    Abstract

    Many algorithms and data structures employing hashing have been analyzed under the uniform hashing assumption, i.e., the assumption that hash functions behave like truly random functions. Starting with the discovery of universal hash functions, many researchers have studied to what extent this theoretical ideal can be realized by hash functions that do not take up too much space and can be evaluated quickly. In this paper we present an almost ideal solution to this problem: a hash function $h: U\rightarrow V$ that, on any set of $n$ inputs, behaves like a truly random function with high probability, can be evaluated in constant time on a RAM and can be stored in $(1+\epsilon)n\log |V| + O(n+\log\log |U|)$ bits. Here $\epsilon$ can be chosen to be any positive constant, so this essentially matches the entropy lower bound. For many hashing schemes this is the first hash function that makes their uniform hashing analysis come true, with high probability, without incurring overhead in time or space.
    Original languageEnglish
    JournalSIAM Journal on Computing
    Volume38
    Issue number1
    Pages (from-to)85-96
    Number of pages12
    ISSN0097-5397
    DOIs
    Publication statusPublished - 2008

    Keywords

    • hash function
    • uniform hashing
    • randomized algorithms

    Fingerprint

    Dive into the research topics of 'Uniform Hashing in Constant Time and Optimal Space'. Together they form a unique fingerprint.

    Cite this