UNIVERSAL CLASSES OF HASH FUNCTIONS
UNIVERSAL CLASSES OF HASH FUNCTIONS
复制标题
DOI：
10.1016/0022-0000(79)90044-8
复制
发表时间：
1979-01-01
影响因子：
1.1
通讯作者：
WEGMAN, MN
中科院分区：
文献类型：
--
作者：
CARTER, JL;WEGMAN, MN
本文给出了一个与输入无关的线性时间密钥存取算法。该算法从合适的哈希函数类中随机选择哈希函数。给定任何输入序列，存储和检索元素的预期时间（类中所有函数的平均值）与序列的长度成线性关系。对于任何输入，该算法所需的数据库引用数都非常接近于具有随机分布输入的任何可能的散列函数的理论最小值。我们提出了三个合适的类的散列函数，也可以快速评估。分析存储和检索的成本而不用担心输入的分布的能力允许作为推论改进几个算法的边界。
This paper gives aninput independentaverage linear time algorithm for storage and retrieval on keys. The algorithm makes a random choice of hash function from a suitable class of hash functions. Given any sequence of inputs the expected time (averaging over all functions in the class) to store and retrieve elements is linear in the length of the sequence. The number of references to the data base required by the algorithm for any input is extremely close to the theoretical minimum for any possible hash function with randomly distributed inputs. We present three suitable classes of hash functions which also may be evaluated rapidly. The ability to analyze the cost of storage and retrieval without worrying about the distribution of the input allows as corollaries improvements on the bounds of several algorithms.