Crate tab_hash 

This crate offers Rust implementations of simple, twisted, and mixed tabulation hashing for 32-bit and 64-bit integer values.

Instantiating Tab32Simple, Tab32Twisted, or Tab32Mixed will initialize tables and create a random hash function from the respective hash family. The hash value of a 32-bit integer can be computed by calling its hash method.

Example:

use tab_hash::Tab32Simple;

let keys = vec![0, 8, 15, 47, 11];
let simple = Tab32Simple::new();
for k in keys {
    println!("{}", simple.hash(k));
}

To reprocude hashes, save the table used by the hash function and save it. The function can be recreated using the with_table constructor.

use tab_hash::Tab32Twisted;

let key = 42;
let twisted_1 = Tab32Twisted::new();
let twisted_2 = Tab32Twisted::with_table(twisted_1.get_table());
let twisted_3 = Tab32Twisted::new();
assert_eq!(twisted_1.hash(key), twisted_2.hash(key));
assert_ne!(twisted_1.hash(key), twisted_3.hash(key));

Note:

These hash functions do not implement the std::hash::Hasher trait, since they do not work on arbitrary length byte streams.

Literature:

This implementation is based on the articles of Mihai Patrascu and Mikkel Thorup:

• Simple Tabulation Hashing
• Twisted Tabulation Hashing
• Hashing for Statistics over k-Partitions
• Fast and Powerful Hashing Using Tabulation

Structs

Tab32Mixed

A hash function for 32-bit integers using mixed tabulation.

Tab32Simple

A universal hash function for 32-bit integers using simple tabulation.

Tab32Twisted

A universal hash function for 32-bit integers using twisted tabulation.

Tab64Mixed

A hash function for 64-bit integers using mixed tabulation. see paper:Dahlgaard, S., Knudsen, M. and Thorup, M., 2017. Practical hash functions for similarity estimation and dimensionality reduction. Advances in neural information processing systems, 30. The first stage uses eight input-byte lookups to produce a 64-bit intermediate hash value and eight derived bytes. Eight more lookups hash the derived bytes. This implementation uses c = d = 8, where c is the number of input characters and d is the number of derived characters.

Tab64Simple

A universal hash function for 64-bit integers using simple tabulation.

Tab64Twisted

A universal hash function for 64-bit integers using twisted tabulation.