Sha256: 7f21c124e58286bf5239bba064c3f1bdd76ba95f27c2f6c82ffff1ec54f46274
Contents?: true
Size: 1.69 KB
Versions: 25
Compression:
Stored size: 1.69 KB
Contents
//! Build support for precomputed constant hash tables.
//!
//! This module can generate constant hash tables using open addressing and quadratic probing.
//!
//! The hash tables are arrays that are guaranteed to:
//!
//! - Have a power-of-two size.
//! - Contain at least one empty slot.
use std::iter;
/// Compute an open addressed, quadratically probed hash table containing
/// `items`. The returned table is a list containing the elements of the
/// iterable `items` and `None` in unused slots.
pub fn generate_table<'cont, T, I: iter::Iterator<Item = &'cont T>, H: Fn(&T) -> usize>(
items: I,
num_items: usize,
hash_function: H,
) -> Vec<Option<&'cont T>> {
let size = (1.20 * num_items as f64) as usize;
// Probing code's stop condition relies on the table having one vacant entry at least.
let size = if size.is_power_of_two() {
size * 2
} else {
size.next_power_of_two()
};
let mut table = vec![None; size];
for i in items {
let mut h = hash_function(i) % size;
let mut s = 0;
while table[h].is_some() {
s += 1;
h = (h + s) % size;
}
table[h] = Some(i);
}
table
}
#[cfg(test)]
mod tests {
use super::generate_table;
use cranelift_codegen_shared::constant_hash::simple_hash;
#[test]
fn test_generate_table() {
let v = vec!["Hello".to_string(), "world".to_string()];
let table = generate_table(v.iter(), v.len(), |s| simple_hash(&s));
assert_eq!(
table,
vec![
None,
Some(&"Hello".to_string()),
Some(&"world".to_string()),
None
]
);
}
}
Version data entries
25 entries across 25 versions & 1 rubygems