Module zerotrie::byte_phf

Byte Perfect Hash Function Internals

This module contains a perfect hash function (PHF) designed for a fast, compact perfect hash over 1 to 256 nodes (bytes).

The PHF uses the following variables:

1. A single parameter p, which is 0 in about 98% of cases.
2. A list of N parameters q_t, one per bucket
3. The N keys in an arbitrary order determined by the PHF

Reading a key from the PHF uses the following algorithm:

1. Let t, the bucket index, be f1(key, p).
2. Let i, the key index, be f2(key, q_t).
3. If key == k_i, return Some(i); else return None.

The functions f1 and f2 are internal to the PHF but should remain stable across serialization versions of ZeroTrie. They are very fast, constant-time operations as long as p <= P_FAST_MAX and q <= Q_FAST_MAX. In practice, nearly 100% of parameter values are in the fast range.

use zerotrie::_internal::PerfectByteHashMap;

let phf_example_bytes = [
    // `p` parameter
    1, // `q` parameters, one for each of the N buckets
    0, 0, 1, 1, // Exact keys to be compared with the input
    b'e', b'a', b'c', b'g',
];

let phf = PerfectByteHashMap::from_bytes(&phf_example_bytes);

// The PHF returns the index of the key or `None` if not found.
assert_eq!(phf.get(b'a'), Some(1));
assert_eq!(phf.get(b'b'), None);
assert_eq!(phf.get(b'c'), Some(2));
assert_eq!(phf.get(b'd'), None);
assert_eq!(phf.get(b'e'), Some(0));
assert_eq!(phf.get(b'f'), None);
assert_eq!(phf.get(b'g'), Some(3));

Re-exports

• pub use cached_owned::PerfectByteHashMapCacheOwned;

Modules

• builder 🔒
• cached_owned 🔒

Structs

• PerfectByteHashMap
  A constant-time map from bytes to unique indices.

Constants

• P_FAST_MAX 🔒
  The cutoff for the fast version of f1.
• P_REAL_MAX 🔒
  The maximum allowable value of p. This could be raised if found to be necessary. Values exceeding P_FAST_MAX could use a different p algorithm by modifying f1.
• Q_FAST_MAX 🔒
  The cutoff for the fast version of f2.
• Q_REAL_MAX 🔒
  The maximum allowable value of q. This could be raised if found to be necessary.

Functions

• f1
  Calculates the function f1 for the PHF. For the exact formula, please read the code.
• f2
  Calculates the function f2 for the PHF. For the exact formula, please read the code.