PHast -- Perfect Hashing made fast
Piotr Beling Peter Sanders
作者信息
Abstract
Perfect hash functions give unique "names" to arbitrary keys requiring only a few bits per key. This is an essential building block in applications like static hash tables, databases, or bioinformatics. This paper introduces the PHast approach that combines the fastest available queries, very fast construction, and good space consumption (below 2 bits per key). PHast improves bucket-placement which first hashes each key k to a bucket, and then looks for the bucket seed s such that a placement function maps pairs (s,k) in a collision-free way. PHast can use small-range hash functions with linear mapping, fixed-width encoding of seeds, and parallel construction. This is achieved using small overlapping slices of allowed values and bumping to handle unsuccessful seed assignment. A variant we called PHast+ uses additive placement, which enables bit-parallel seed searching, speeding up the construction by an order of magnitude.引用本文复制引用
Piotr Beling,Peter Sanders.PHast -- Perfect Hashing made fast[EB/OL].(2025-10-22)[2025-12-31].https://arxiv.org/abs/2504.17918.学科分类
计算技术、计算机技术
|国家预印本平台
评论