boomphf: Scalable and Efficient Minimal Perfect Hash Functions

The boomphf library implements minimal perfect hash functions for massive key sets.

Key Characteristics:

• Efficiency: Generates hash functions that consume approximately 3-6 bits per item.
• Construction Memory: Memory usage during construction is typically less than 2x the size of the dataset plus the final MPHF size.
• Constraint: MPHFs only return valid, predictable hash values for objects that were part of the original set used to create the function. Hashing an object not in the original set will return an arbitrary hash value. If you need to distinguish between set members and non-members, you must implement an auxiliary detection scheme.
• Internal Implementation: The crate includes its own bit-vector implementation to support rank-select queries and multi-threaded read-write access.

Choosing the right BoomHashMap depends on your memory constraints and the guarantee that your queries only use known keys:

1. BoomHashMap<K, D>: Stores keys and values. Safest for general use. Valid keys always return Some. Unknown keys may return Some (random) or None.
2. BoomHashMap2<K, D1, D2>: Stores keys and two separate value arrays. Best for avoiding struct layout overhead when storing two values.
3. NoKeyBoomHashMap<K, D1>: Does not store keys. Lowest memory usage. Extremely unsafe if querying unknown keys, as it will return random values silently.

An Mphf (Minimal Perfect Hash Function) maps a specific set of $n$ keys to a unique set of integers in the range $[0, n)$.

Key Characteristics:

• Minimal: The output range is exactly the size of the input set.
• Perfect: There are no collisions for the keys used during construction.
• Constraint: It is only valid for the exact set of keys used to build it. Hashing a key that was not in the construction set is undefined behavior for .hash() (may panic) and returns None for .try_hash().

Construction Parameters:

• gamma: A float (must be $> 1.01$) that controls the tradeoff between construction speed, runtime speed, and memory usage. Increasing gamma increases the size of the data structure but improves performance.

If the parallel feature is enabled, you can use new_parallel to speed up the construction of the MPHF using multiple threads. This is available for BoomHashMap, BoomHashMap2, NoKeyBoomHashMap, and NoKeyBoomHashMap2.

// Requires 'parallel' feature
let map = BoomHashMap::new_parallel(keys, values);

You can iterate over the key-value pairs in a BoomHashMap using .iter() or by using the IntoIterator implementation.

for (key, value) in &map {
    println!("Key: {:?}, Value: {:?}", key, value);
}

Once an Mphf is constructed, you can retrieve hash values for items:

1. hash(&item): Use this when you are certain the item was part of the original construction set. If the item was not in the set, this function may panic.
2. try_hash(&item): Use this when you cannot guarantee the item was in the construction set. If the item was not present, it returns None. If it was present, it returns Some(hash_value).

// Guaranteed to be in set
let h = phf.hash(&item);

// Safe for unknown items
if let Some(h) = phf.try_hash(&unknown_item) { 
    // ...
}

Use Mphf::new to generate a minimal perfect hash function (MPHF) for a slice of objects. The objects must not contain any duplicate items.

gamma controls the tradeoff between construction-time/run-time speed and the size of the resulting data structure. A higher gamma typically results in a larger data structure but faster operations.

Note: An MPHF can only be used with the set of objects used during its construction. Hashing a new object will return an arbitrary hash value.

use boomphf::*;

// Generate MPHF
let possible_objects = vec![1, 10, 1000, 23, 457, 856, 845, 124, 912];
let phf = Mphf::new(1.7, &possible_objects);

// Get hash value of an object
let h = phf.hash(&10);

If you need to map a single key to two distinct value types without the memory overhead of a tuple or struct, use BoomHashMap2<K, D1, D2>. This stores values in two separate dense arrays (values and aux_values).

let keys = vec![k1, k2];
let values = vec![v1, v2];
let aux_values = vec![a1, a2];
let map = BoomHashMap2::new(keys, values, aux_values);

// Returns a tuple of references (&D1, &D2)
if let Some((v, a)) = map.get(&k1) {
    println!("Value: {:?}, Aux: {:?}", v, a);
}

A BoomHashMap<K, D> stores keys and values in dense arrays, using a Minimal Perfect Hash Function (MPHF) to encode the mapping. This results in approximately 3 bits/item overhead for the MPHF.

Important Behavior: You must only query with keys that were used during creation. Querying with a key not in the original set may return Some with a random value or None. Valid keys will always return Some.

// Create a new map from vectors of keys and values
let keys = vec![k1, k2, k3];
let values = vec![v1, v2, v3];
let map = BoomHashMap::new(keys, values);

// Retrieve a value
if let Some(value) = map.get(&k1) {
    println!("Found: {:?}", value);
}

// Get the index/position of a key
if let Some(id) = map.get_key_id(&k1) {
    println!("Key ID: {}", id);
}

If the parallel feature is enabled, you can use Mphf::new_parallel to speed up the construction of the MPHF using the Rayon threadpool. This is useful for large datasets where CPU-bound construction is a bottleneck.

// Requires 'parallel' feature
#[cfg(feature = "parallel")]
let phf = Mphf::new_parallel(1.7, &possible_objects, None);

A NoKeyBoomHashMap<K, D1> (or NoKeyBoomHashMap2) does not store the keys themselves, significantly reducing memory consumption.

Warning: This can only be used if you can guarantee that you will only query for keys that were in the original set. Querying for a new key will return a random value silently or None.

To use this, your key type K must implement the ConstructibleKey trait.

// Keys are consumed and not stored in the map
let keys = vec![k1, k2];
let values = vec![v1, v2];
let map = NoKeyBoomHashMap::new(keys, values);

// Querying works, but is unsafe for unknown keys
let val = map.get(&k1);