On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications
On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications
复制标题
通用类快速高性能哈希函数、时空权衡及其应用
DOI：
10.1109/sfcs.1989.63450
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
A. Siegel
中科院分区：
文献类型：
--
作者：
A. Siegel
提供了一种用于构造可在O(1)时间内求值的对数n向独立散列函数的机制。一个概率论证表明，对于固定的ε1，一个小的O(1)时间程序可以访问一个包含n/超/随机字的表来计算一个重要的散列函数族。文中还给出了这一族的一个显式算法，该算法在所有的实际应用中都能达到相当的性能。一个下界表明这样的程序必须花费Omega(k/epsilon)时间，而一个概率参数表明程序可以在O(k/sup 2//epsilon/sup 2/)时间内运行。这些构造的直接结果是，对于适当适度的负载，使用这些通用函数的双重散列在时间上具有(恒定系数)最优性能。另一个结果是，针对n个logn处理器(和n/sup k/存储器)的T时间PRAM算法可以在由n*logn欧米茄网络互连的n处理器机器上进行仿真，总工作量的乘性代价很高，仅为O(1)。
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 epsilon <1, a table of n/sup epsilon / 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 Omega (k/ epsilon ) time, and a probabilistic arguments shows that programs can run in O(k/sup 2// epsilon /sup 2/) 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 algorithm for n log n processors (and n/sup 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).<<ETX>>