Module 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.