Open AccessSimulating Uniform Hashing in Constant Time and Optimal Space
Author(s) -
Anna Östlin,
Rasmus Pagh
Publication year - 2002
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v9i27.21743
Subject(s) - dynamic perfect hashing , k independent hashing , hash function , universal hashing , linear hashing , constant (computer programming) , perfect hash function , double hashing , hash table , mathematics , computer science , theoretical computer science , set (abstract data type) , discrete mathematics , algorithm , computer security , programming language
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. In this paper it is shown how to implement hash functions that can be evaluated on a RAM in constant time, and behave like truly random functions on any set of n inputs, with high probability. The space needed to represent a function is O(n) words, which is the best possible (and a polynomial improvement compared to previous fast hash functions). As a consequence, a broad class of hashing schemes can be implemented to meet, with high probability, the performance guarantees of their uniform hashing analysis.