Crate tab_hash

This crate offers rust implementations of simple and twisted tabulation hashing for 32-bit integer values.

Instatiating Tab32Simple or Tab32Twisted will initialize a table 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;

fn main() {
    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;

fn main() {
    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

Structs

Tab32Simple

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

Tab32Twisted

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

Tab64Simple

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

Tab64Twisted

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