Crate ptr_hash

PTRHash is a minimal perfect hash function.

Usage example:

use ptr_hash::{PtrHash, PtrHashParams};
let n = 1_000_000;
let keys = ptr_hash::util::generate_keys(n);
let mphf = <PtrHash>::new(&keys, PtrHashParams::default());
let sum = mphf.index_stream::<32, true>(&keys).sum::<usize>();
assert_eq!(sum, (n * (n - 1)) / 2);
// Get the minimal index of a key.
let key = 0;
let idx = mphf.index_minimal(&key);
assert!(idx < n);
// Get the non-minimal index of a key. Slightly faster.
let _idx = mphf.index(&key);
// An iterator over the indices of the keys.
// 32: number of iterations ahead to prefetch.
// true: remap to a minimal key in [0, n).
let indices = mphf.index_stream::<32, true>(&keys);
assert_eq!(indices.sum::<usize>(), (n * (n - 1)) / 2);
// Test that all items map to different indices
let mut taken = vec![false; n];
for key in keys {
    let idx = mphf.index_minimal(&key);
    assert!(!taken[idx]);
    taken[idx] = true;
}

Modules

• hash
  Customizable Hasher trait.
• pack
  Extendable backing storage trait and types.
• tiny_ef
  Reusable Tiny Elias-Fano implementation.
• 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. The recommended way to use PtrHash with default types.
• PtrHashParams
  Parameters for PtrHash construction.

Traits

• KeyT
  Trait that keys must satisfy.

Type Aliases

• DefaultPtrHash
  An alias for PtrHash with default generic arguments. Using this, you can write DefaultPtrHash::new() instead of <PtrHash>::new().
• EfPtrHash
  Using EliasFano for the remap is slower but uses slightly less memory.