hashers 1.0.1

A collection of non-cryptographic hashing algorithms for Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

// **WARNING:** This program must be compiled in --release mode, with optimizations, or it will
// take a very, very long time.

extern crate hashers;

use std::collections::{HashMap, HashSet};
use std::hash::{BuildHasher, BuildHasherDefault, Hasher};
use std::io::{BufRead, BufReader};
use std::{fs, time};

use hashers::{builtin, fnv, fx_hash, jenkins, oz, pigeon};

pub mod combinations;

/// Convert a word to a vector of sorted bytes.
fn get_letters(s: &str) -> Vec<u8> {
    let mut t: Vec<char> = s.chars().collect();
    t.sort();
    return t.iter().map(|&ch| ch as u8).collect();
}

/// Split a line into a vector of space-separated words.
fn split_words(s: &str) -> Vec<String> {
    s.split(" ").map(|w| w.to_string()).collect()
}

/// A HashMap using the Hasher provided by BuildHasher BH.
type Dictionary<BH> = HashMap<Vec<u8>, Vec<String>, BH>;
/// A HashSet of strings using the Hasher provided by BuildHasher BH.
/// 
/// Not to be confused with a swing set.
type StringSet<BH> = HashSet<String, BH>;

/// Read the anagram dictionary into a HashMap.
fn load_dictionary<H: Default + Hasher>() -> Dictionary<BuildHasherDefault<H>> {
    let file = match fs::File::open("./data/anadict.txt") {
        Ok(f) => f,
        Err(e) => panic!(e),
    };
    let buffered_file = BufReader::new(file);
    let mut map = HashMap::default();
    for line in buffered_file.lines() {
        let line = line.unwrap();
        let mut words = split_words(&line);
        let key: Vec<u8> = words.remove(0).chars().map(|ch| ch as u8).collect();
        map.insert(key, words);
    }
    return map;
}

/// Search all combinations of letters, returning a set of the matching words.
fn search<H: Default + Hasher, BH: BuildHasher>(
    letters: &[u8],
    dictionary: &Dictionary<BH>,
) -> StringSet<BuildHasherDefault<H>> {
    let mut set = HashSet::default();
    for i in 0..letters.len() + 1 {
        let mut key: Vec<u8> = vec![0; i];
        // note the internal iterator
        combinations::each_combination(letters, i, |combo| {
            for j in 0..combo.len() {
                key[j] = combo[j];
            }
            match dictionary.get(&key) {
                Some(val) => {
                    for word in val.iter() {
                        set.insert(word.clone());
                    }
                }
                None => {}
            }
        });
    }
    return set;
}

/// Return the number of words found using a particular string.
fn do_search<H: Default + Hasher>() -> usize {
    let letters = get_letters("asdwtribnowplfglewhqagnbe");
    let dictionary = load_dictionary::<H>();
    let set = search::<H, BuildHasherDefault<H>>(&letters, &dictionary);
    set.len()
}

/// Measure and print the time used by a search, using Hasher H.
///
/// Also returns the duration, to be used as a baseline for later searchs.
fn time<H: Default + Hasher>(title: &str, baseline: f64) -> f64 {
    let start = time::Instant::now();
    assert_eq!(do_search::<H>(), 7440);
    let duration = time::Instant::now().duration_since(start);
    let secs = duration.as_secs();
    let micros = duration.subsec_micros();
    let time = (secs as f64) + ((micros as f64) / 1_000_000.0);
    if baseline > 0.0 {
        let percent = ((time / baseline) * 1000.0).round() / 10.0;
        println!("{:10} {: >8.3}s ({}%)", title, time, percent);
    } else {
        println!("{:10} {: >8.3}s", title, time);
    }
    time
}

fn main() {
    let baseline = time::<builtin::DefaultHasher>("default", 0.0);
    time::<oz::DJB2Hasher>("djb2", baseline);
    time::<oz::SDBMHasher>("sdbm", baseline);
    time::<jenkins::OAATHasher>("oaat", baseline);
    time::<jenkins::Lookup3Hasher>("lookup3", baseline);
    time::<fnv::FNV1aHasher32>("fnv-1a 32", baseline);
    time::<fnv::FNV1aHasher64>("fnv-1a 64", baseline);
    time::<fx_hash::FxHasher>("fxhash", baseline);
    time::<fx_hash::FxHasher32>("fxhash32", baseline);
    time::<fx_hash::FxHasher64>("fxhash64", baseline);
    time::<jenkins::spooky_hash::SpookyHasher>("spooky", baseline);
    time::<pigeon::Bricolage>("bricolage", baseline);
}