miniphf/
lib.rs

1use quickdiv::DivisorU64;
2use std::fmt;
3
4/// Sentinel value indicating slot is not occupied.
5const EMPTY: u32 = u32::MAX;
6
7pub fn build_phf_map<V>(entries: Vec<(u64, V)>, c: f64, alpha: f64) -> CodeWriter<V> {
8    let lg = (usize::BITS - entries.len().leading_zeros() - 1) as f64;
9    let n = entries.len() as f64;
10    let buckets_len = (c * n / lg).ceil() as u64;
11    let codomain_len = {
12        let candidate = (n / alpha).ceil() as u64;
13        if candidate % 2 == 0 {
14            candidate + 1
15        } else {
16            candidate
17        }
18    };
19
20    let keys = entries.iter().map(|(k, _)| k);
21    let phf = generate_phf(keys, codomain_len, buckets_len);
22    CodeWriter { phf, entries }
23}
24
25pub struct CodeWriter<V> {
26    phf: Phf,
27    entries: Vec<(u64, V)>,
28}
29
30impl<V: fmt::Debug> fmt::Display for CodeWriter<V> {
31    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
32        write!(f, "crate::MiniPhf::new(")?;
33
34        write!(f, "&[")?;
35        for &idx in &self.phf.map {
36            if idx == EMPTY {
37                write!(f, "0,")?;
38                continue;
39            }
40            write!(f, "{:?},", self.entries[idx as usize].1)?;
41        }
42        write!(f, "    ],")?;
43
44        write!(f, "&[")?;
45        for &pilot in &self.phf.pilots_table {
46            write!(f, "{:?},", pilot)?;
47        }
48        write!(f, "])")
49    }
50}
51
52fn hash_pilot_value(pilot_value: u64) -> u32 {
53    /// Multiplicative constant from `fxhash`.
54    const K: u64 = 0x517cc1b727220a95;
55    pilot_value.wrapping_mul(K) as u32
56}
57
58/// Parameters for a PTHash perfect hash function.
59#[derive(Debug)]
60struct Phf {
61    pilots_table: Vec<u32>,
62    map: Vec<u32>,
63}
64
65/// Generate a perfect hash function using PTHash for the given collection of keys.
66fn generate_phf<'a>(keys: impl Iterator<Item = &'a u64>, n_prime: u64, m: u64) -> Phf {
67    let buckets_len = DivisorU64::new(m);
68    let codomain_len = DivisorU64::new(n_prime);
69
70    // We begin by hashing the entries, assigning them to buckets, and checking for collisions.
71    struct HashedEntry {
72        idx: usize,
73        hash: u64,
74        bucket: usize,
75    }
76
77    let mut hashed_entries: Vec<_> = keys
78        .enumerate()
79        .map(|(idx, &key)| {
80            let hash = key;
81            let bucket = (hash % buckets_len) as usize;
82
83            HashedEntry { idx, hash, bucket }
84        })
85        .collect();
86
87    hashed_entries.sort_unstable_by_key(|e| (e.bucket, e.hash));
88
89    //
90    struct BucketData {
91        idx: usize,
92        start_idx: usize,
93        size: usize,
94    }
95
96    let mut buckets = Vec::with_capacity(buckets_len.get() as usize);
97
98    let mut start_idx = 0;
99    for idx in 0..buckets_len.get() as usize {
100        let size = hashed_entries[start_idx..]
101            .iter()
102            .take_while(|entry| entry.bucket == idx)
103            .count();
104
105        buckets.push(BucketData {
106            idx,
107            start_idx,
108            size,
109        });
110        start_idx += size;
111    }
112
113    buckets.sort_unstable_by(|b1, b2| b1.size.cmp(&b2.size).reverse());
114
115    let mut pilots_table = vec![0; buckets_len.get() as usize];
116    // Using a sentinel value instead of an Option here allows us to avoid an expensive
117    // reallocation. This is fine since the compiler cannot handle a static map with more than
118    // a few million entries anyway.
119    let mut map = vec![EMPTY; codomain_len.get() as usize];
120
121    let mut values_to_add = Vec::new();
122    for bucket in buckets {
123        let bucket_start = bucket.start_idx;
124        let bucket_end = bucket_start + bucket.size;
125        let bucket_entries = &hashed_entries[bucket_start..bucket_end];
126
127        'pilots: for pilot in 0u64.. {
128            values_to_add.clear();
129            let pilot_hash = hash_pilot_value(pilot);
130
131            // Check for collisions with items from previous buckets.
132            for entry in bucket_entries.iter() {
133                let destination = (entry.hash ^ pilot_hash as u64) % codomain_len;
134
135                if map[destination as usize] != EMPTY {
136                    continue 'pilots;
137                }
138
139                values_to_add.push((entry.idx, destination));
140            }
141
142            // Check for collisions within this bucket.
143            values_to_add.sort_unstable_by_key(|k| k.1);
144            for window in values_to_add.as_slice().windows(2) {
145                if window[0].1 == window[1].1 {
146                    continue 'pilots;
147                }
148            }
149
150            for &(idx, destination) in &values_to_add {
151                map[destination as usize] = idx as u32;
152            }
153            pilots_table[bucket.idx] = pilot_hash;
154            break;
155        }
156    }
157
158    Phf { pilots_table, map }
159}
miniphf/lib.rs

miniphf/
lib.rs
