| builder.rs |
|
7868 |
| cached_owned.rs |
|
1340 |
| mod.rs |
# 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));
``` |
17343 |