Crate hash_iter 

hash-iter

Implementation of the enhanced double hashing technique based on the Bloom Filters in Probabilistic Verification paper (Dillinger and Manolios, 2004).

Motivation

Given a key key, instead of hashing it to a single value, one can hash it to a sequence of k hashes [hash_1, hash_2, .., hash_k].

See use cases below for details.

Quick Start

use hash_iter::{DoubleHashHasher, HashIterHasher};

let hasher = DoubleHashHasher::new();
let hashes: Vec<u64> = hasher.hash_iter(&"key", 10).collect();

Usage

Basic Usage

Hash a key to generate a sequence of hash values:

use hash_iter::{DoubleHashHasher, HashIterHasher};

let hasher = DoubleHashHasher::new();

// Generate 3 hash values for each key
let hashes = hasher.hash_iter(&"foo", 3).collect::<Vec<_>>();
let hashes = hasher.hash_iter(&"bar", 3).collect::<Vec<_>>();

Configuration

Customize the hasher with seeds, modulus, and output type:

use hash_iter::{BuildHashIterHasher, DoubleHashBuilder, HashIterHasher};

// Configure for u32 with custom parameters
let hasher = DoubleHashBuilder::<u32>::new()
    .with_seed1(12345)
    .with_seed2(67890)
    .with_n(10000)  // Maximum hash value
    .build_hash_iter_hasher();

let hashes: Vec<u32> = hasher.hash_iter(&"key", 5).collect();

Default configuration:

• Seeds: 12345, 67890
• Modulus n: T::MAX for the chosen type
• Hash function: XXH3

Custom Hash Functions

Use any hash function implementing std::hash::BuildHasher:

use hash_iter::{DoubleHashHasher, HashIterHasher};
use xxhash_rust::xxh3::Xxh3Builder;

let hasher = DoubleHashHasher::<u64, _, _>::with_hash_builders(
    Xxh3Builder::new().with_seed(111),
    Xxh3Builder::new().with_seed(222),
    u64::MAX,
);

let hashes = hasher.hash_iter(&"hello", 3).collect::<Vec<_>>();

Use Cases

This crate enables efficient implementations of hash-based algorithms:

• Bloom filters - Generate multiple filter positions from a single key (Kirsch and Mitzenmacher, 2006)
• Hash tables - Double hashing for collision resolution in open addressing
• Consistent hashing - Map keys to server rings (e.g., mpchash)

Instead of computing k independent hashes, double hashing produces k hash values from just two base hashes using the formula:

h(i) = h₁(key) + i·h₂(key) + (i³-i)/6 (mod n)

The implementation uses forward differencing for O(1) computation per iteration.

License

MIT

Structs

DoubleHashBuilder

Holds the state for the hasher that implements enhanced double hashing.

DoubleHashHasher

Enhanced double hashing hasher.

Hashes

Iterator over hash values generated using enhanced double hashing technique.

Traits

BuildHashIterHasher

Builds hash iterator hasher – a hasher capable of generating multiple hash values.

HashIterHasher

Provides an iterator over multiple hash values for a given key.