论文标题
Sichash-小的不规则杜鹃桌，以完美哈希
SicHash -- Small Irregular Cuckoo Tables for Perfect Hashing
论文作者
论文摘要
完美的哈希功能（PHF）是一个哈希函数，在给定输入集上没有碰撞。 PHF可用于在数组中有效地存储数据，也可以用于确定集合中每个对象的紧凑代表。在本文中，我们介绍了PHF Construction算法Sichash-小型不规则的杜鹃桌，可完美哈希。 Sichash以其核心使用已知的技术：它将对象放在杜鹃屁股表中，然后将每个对象的最终哈希函数选择存储在检索数据结构中。我们将这个想法与不规则的杜鹃哈希相结合，每个对象都具有不同数量的哈希功能。此外，我们使用了许多小表，使我们超越了它们的渐近最大负载系数。最有效的竞争者通常使用蛮力方法来确定PHF。 Sichash提供了一种更直接的构造算法，仅需要重新计算零件。我们的实施在空间使用方面与构造时间相比，改善了最新配置的时间。同时，它提供了非常快速的查询。
A Perfect Hash Function (PHF) is a hash function that has no collisions on a given input set. PHFs can be used for space efficient storage of data in an array, or for determining a compact representative of each object in the set. In this paper, we present the PHF construction algorithm SicHash - Small Irregular Cuckoo Tables for Perfect Hashing. At its core, SicHash uses a known technique: It places objects in a cuckoo hash table and then stores the final hash function choice of each object in a retrieval data structure. We combine the idea with irregular cuckoo hashing, where each object has a different number of hash functions. Additionally, we use many small tables that we overload beyond their asymptotic maximum load factor. The most space efficient competitors often use brute force methods to determine the PHFs. SicHash provides a more direct construction algorithm that only rarely needs to recompute parts. Our implementation improves the state of the art in terms of space usage versus construction time for a wide range of configurations. At the same time, it provides very fast queries.
