Crate boomphf

source ·
Expand description

boomphf - Fast and scalable minimal perfect hashing for massive key sets

A Rust implementation of the BBHash method for constructing minimal perfect hash functions, as described in “Fast and scalable minimal perfect hashing for massive key sets” https://arxiv.org/abs/1702.03154. The library generates a minimal perfect hash function (MPHF) for a collection of hashable objects. Note: minimal perfect hash functions can only be used with the set of objects used when hash function was created. Hashing a new object will return an arbitrary hash value. If your use case may result in hashing new values, you will need an auxiliary scheme to detect this condition.

use boomphf::*;
// Generate MPHF
let possible_objects = vec![1, 10, 1000, 23, 457, 856, 845, 124, 912];
let n = possible_objects.len();
let phf = Mphf::new(1.7, &possible_objects);
// Get hash value of all objects
let mut hashes = Vec::new();
for v in possible_objects {
    hashes.push(phf.hash(&v));
}
hashes.sort();

// Expected hash output is set of all integers from 0..n
let expected_hashes: Vec<u64> = (0 .. n as u64).collect();
assert!(hashes == expected_hashes)

Modules

  • HashMap data structures, using MPHFs to encode the position of each key in a dense array.

Structs

  • A minimal perfect hash function over a set of objects of type T.