On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications

A mechanism is provided for constructing log-n--wise-independent hash functions that can be evaluated in O(1) time. A probabilistic argument shows that for fixed ε < 1, a table of n^ε random words can be accessed by a small O(1)-time program to compute one important family of hash functions. An explicit algorithm for such a family, which achieves comparable performance for all practical purposes, is also given. A lower bound shows that such a program must take Ω(k/ε) time, and a probabilistic argument shows that programs can run in O(k²/ε²) time. An immediate consequence of these constructions is that double hashing using these universal functions has (constant factor) optimal performance in time, for suitably moderate loads. Another consequence is that a T-time PRAM (parallel random-access machine) algorithm for n log n processors (and n^k memory) can be emulated on an n-processor machine interconnected by an n × log n Omega network with a multiplicative penalty for total work that, with high probability, is only O(1).