Graphs, Hypergraphs and Hashing
Graphs, Hypergraphs and Hashing
复制标题
图、超图和散列
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Z. Czech
中科院分区：
文献类型：
--
作者：
G. Havas;B. Majewski;N. Wormald;Z. Czech
最小的完美哈希功能用于记忆有效存储和快速从静态集合中获取项目。我们提出了一个无限的高效和实用算法家族，用于产生最小的完美哈希功能，该功能允许为密钥指定任意命令。我们表明，几乎所有家庭成员都是空间和时间最佳的，我们确定具有最低常数的成员。家庭成员在两个步骤中产生了最小的完美哈希功能。首先，通过概率计算出一种特殊的功能。然后，该函数确定性地提高到最小的完美哈希函数。我们提供了强有力的实用和理论证据，即第一步使用线性随机时间。第二步以线性确定性时间运行。这个家庭不仅具有理论上的重要性，而且还提供了最快的已知方法来产生完美的哈希功能。
Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating minimal perfect hash functions which allow an arbitrary order to be specified for the keys. We show that almost all members of the family are space and time optimal, and we identify the one with minimum constants. Members of the family generate a minimal perfect hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect hash function. We give strong practical and theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known method for generating perfect hash functions.