Crate ptr_hash 

PtrHash: Minimal Perfect Hashing at RAM Throughput

PtrHash builds a minimal perfect hash function, that is, a hash function that maps a fixed set of keys to {0, ..., n-1}.

PtrHash was developed for large key sets of at least 1 million keys, and has been tested up to 10^11 keys. In the default configuration, it uses 3.0 bits per key. Nevertheless, it can also be used for arbitrary small sets.

See the GitHub readme or paper (arXiv, blog version) for details on the algorithm and performance.

Usage example:

use ptr_hash::PtrHashParams;

// Enable logging.
env_logger::init();

// Generate some random keys.
let n = 1_000_000;
let keys = ptr_hash::util::generate_keys(n);

// Build the default variant of the datastructure.
// See `FastPtrHash` and `CompactPtrHash` below as alternatives.
let mphf = <ptr_hash::DefaultPtrHash>::new(&keys, PtrHashParams::default());

// Get the index of a key.
let key = 0;
let idx = mphf.index(&key);
assert!(idx < n);

// An iterator over the indices of the keys.
// 32: number of iterations ahead to prefetch.
// _: placeholder to infer the type of keys being iterated.
let indices = mphf.index_stream::<32, _>(&keys);
assert_eq!(indices.sum::<usize>(), (n * (n - 1)) / 2);

// Query a batch of keys.
let query_keys = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
let mut indices = mphf.index_batch::<16, _>(query_keys);
indices.sort();
for i in 0..indices.len()-1 {
    assert!(indices[i] != indices[i+1]);
}

// Test that all items map to different indices
let mut taken = vec![false; n];
for key in &keys {
    let idx = mphf.index(&key);
    assert!(!taken[idx]);
    taken[idx] = true;
}

// `FastPtrHash` skips remapping and returns values up to `PtrHash::max_index()`,
// which is around 1.01*n.
let phf = <ptr_hash::FastPtrHash>::new(&keys, PtrHashParams::default());

for key in &keys {
    let idx = mphf.index(&key);
    // NOTE: Not `n` but `phf.max_index()` here!
    assert!(idx < phf.max_index());
}

// `CompactPtrHash` uses multi-threaded construction and is more space-efficient,
// but slightly slower to query.
let phf = <ptr_hash::CompactPtrHash>::new(&keys, PtrHashParams::default_compact());

for key in &keys {
    let idx = mphf.index(&key);
    assert!(idx < n);
}

Default configurations

• For fastest query throughput, use FastPtrHash (2.67 bits/key), which is a non-minimal PHF that skips remapping values into [0, n).67 bits/key.
• If you want a minimal PHF that returns values in [0, n), use DefaultPtrHash (3.0 bits/key).
• If you have many keys, use CompactPtrHash (2.15 bits/key), which allows for multi-threaded construction by splitting the input into multiple parts and uses a more space-efficient bucket function. Queries will be a bit slower because the part and index inside the part are computed separately. PtrHashParams::default_balanced() is smaller and still fast to construct, while PtrHashParams::default_compact() is even smaller and around 2x slower to construct.

Hash functions

PtrHash benefits from using an as-fast-as-possible hash function.

• If your keys are already random integers, use hash::NoHash.
• For integers, use hash::FastIntHash, which aliases the fast-but-weak hash::FxHash. Otherwise, try hash::StrongerIntHash.
• For strings, use [hash::StringHash] when the number of keys is at most 10^9, and use [hash::StringHash128] for more keys. These alias [hash::Gx] and [hash::Gx128].

See the hash module documentation for better hashes in case these cause hash collisions.

// Hashing strings
use ptr_hash::{DefaultPtrHash, PtrHashParams, hash::StringHash};

let keys = vec!["abc", "def"];
let mphf = <DefaultPtrHash<StringHash, _>>::new(&keys, PtrHashParams::default());

let idx = mphf.index(&"def");

Partitioning

By default, PtrHash builds all keys as a single part.

Faster multi-threaded construction is possible using SINGLE_PART=false (via CompactPtrHash), which splits the keys over multiple parts. Additionally, having fewer keys per part improves the cache-locality of the construction. Query time is slightly slower though, since computing the part and index inside the part are two separate steps.

Sharding

When the keys and/or their hashes do not all fit in memory at once, use sharding. This requires SINGLE_PART=false, e.g. via CompactPtrHash. See shard::Sharding for details of different sharding methods.

use ptr_hash::{CompactPtrHash, PtrHashParams, Sharding};

let mut params = PtrHashParams::default_compact();
// The default value. For ~16GB of u64 hashes or ~32GB of u128 hashes.
// Make sure to also leave space for the data structure itself.
params.keys_per_shard = 1<<31;
params.sharding = Sharding::Disk;

let keys = vec![1,2,3]; // 10^12 or who knows how many keys.
let mphf = <CompactPtrHash>::new(&keys, params);

Reducing space usage

The default parameters are chosen for reliability, construction speed, and query speed, and give around 3 bits per keys. To achieve smaller sizes, consider using cacheline_ef::CachelineEfVec or pack::EliasFano as ‘remap’ structure, instead of Vec<u32>.

Additionally, one can use CompactPtrHash with PtrHashParams::default_balanced() parameters, which use the CubicEps bucket function instead of Linear, and increase lambda from the default of 3.0 to 3.5. PtrHashParams::default_compact() is even smaller, but slower to construct, and generally slightly less reliable.

use ptr_hash::{PtrHash, PtrHashParams};

let params = PtrHashParams::default_balanced();
let keys = vec![1u64, 2, 3];
let mphf = <PtrHash<_, _, ptr_hash::pack::EliasFano>>::new(&keys, params);

Modules

bucket_fn

Various “bucket functions” are implemented here.

hash

Customizable Hasher trait. Implementations of various hashers to use with PtrHash.

pack

Extendable backing storage trait and types. The Packed and MutPacked traits are used for the underlying storage of the remap vector.

util

Some internal logging and testing utilities. Internal utilities that are only exposed for testing/benchmarking purposes. Do not use externally.

Structs

PtrHash

PtrHash datastructure. It is recommended to use PtrHash with default type aliases:

PtrHashParams

Parameters for PtrHash construction.

Enums

Sharding

The sharding method to use.

Traits

KeyT

Trait that keys must satisfy.

Type Aliases

CompactPtrHash

Variant for large data sets with multi-threaded construction. 2.15 bits/key.

DefaultPtrHash

Default variant: a minimal PHF that returns values in [0, n). 3.0 bits/key.

FastPtrHash

Fastest variant: a non-minimal PHF that may return values slightly larger than n. 2.67 bits/key.