Design Strategies for Minimal Perfect Hash Functions
Design Strategies for Minimal Perfect Hash Functions
复制标题
最小完美哈希函数的设计策略
DOI：
10.1007/978-3-540-74871-7_2
复制
发表时间：
2007
影响因子：
--
通讯作者：
Martin Dietzfelbinger
中科院分区：
文献类型：
--
作者：
Martin Dietzfelbinger
对于大小为n的集合S U，最小完美散列函数h是函数h：U → {0，. . ., n-1}，在S上是一对一的。感兴趣的复杂性度量是h的存储空间、求值时间（应该是常数）和构造时间。该演讲概述了最近几种最小完美哈希函数的随机构造，从而产生了在实践中快速的空间高效解决方案。一个核心问题是一种方法（“分割和共享”），它可以假设完全随机（散列）函数是可用的。
A minimal perfect hash function h for a set S ⊆ U of size n is a function h:U → {0,. . ., n-1} that is one-to-one on S. The complexity measures of interest are storage space for h, evaluation time (which should be constant), and construction time. The talk gives an overview of several recent randomized constructions of minimal perfect hash functions, leading to space-efficient solutions that are fast in practice. A central issue is a method ("split-and-share") that makes it possible to assume that fully random (hash) functions are available.