Universal classes of hash functions (Extended Abstract)
Universal classes of hash functions (Extended Abstract)
复制标题
DOI：
10.1145/800105.803400
复制
发表时间：
1977-05
期刊：
影响因子：
--
通讯作者：
L. Carter;M. Wegman
中科院分区：
文献类型：
--
作者：
L. Carter;M. Wegman
本文给出了一种与输入无关的平均线性时间算法，用于密钥的存储和检索。该算法从合适的散列函数类别中随机选择散列函数。给定任何输入序列，存储和检索元素的预期时间（类中所有函数的平均值）与序列的长度呈线性关系。对于任何输入，算法所需的数据库引用数量都非常接近具有随机分布输入的任何可能的哈希函数的理论最小值。我们提出了三类合适的散列函数，它们也可以被快速评估。无需担心输入分布即可分析存储和检索成本的能力可以作为推论改进多种算法的边界。
This paper gives an input independent average 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.