Crate fliphash

FlipHash is a consistent range-hashing function that hashes an integer key into a value of ..=range_end, where range_end is parameterized.

It is:

• regular (i.e., uniform, balanced): it distributes the keys evenly over the hash values of the range,
• monotone (i.e., stable): when varying the range, key hashes are not shuffled across the values that stay within the range, and keys can only be remapped from a hash value now outside of the range (if the range is narrowed), or to a hash value previously outside of the range (if the range is enlarged),
• fast: it has a low computational cost, and constant-time complexity.

Usage

use fliphash::fliphash_64;

let hash = fliphash_64(10427592028180905159, ..=17);

assert!((..=17).contains(&hash));

Regularity

The following code snippet illustrates the regularity of FlipHash.

With a large enough number of distinct keys, the numbers of occurrences of the hash values of range are relatively close to one another.

use fliphash::fliphash_64;

let mut hash_counts = [0_u64; 18];
// Hash a lot of keys; they could be picked randomly.
for key in 0_u64..2_000_000_u64 {
    let hash = fliphash_64(key, ..=17);
    hash_counts[hash as usize] += 1;
}

let (min_count, max_count) = (
    *hash_counts.iter().min().unwrap() as f64,
    *hash_counts.iter().max().unwrap() as f64,
);
let relative_difference = (max_count - min_count) / min_count;
assert!(relative_difference < 0.01);

Monotonicity

The following code snippet illustrates the monotonicity, i.e., the stability, of FlipHash.

Given a key, when making the range larger, either the hash of the key is unchanged or it gets a new value that the previous range does not contain.

use fliphash::fliphash_64;

let key = 10427592028180905159;

let mut previous_hash = 0;
for range_end in 1..1000 {
    let hash = fliphash_64(key, ..=range_end);
    assert!(hash == previous_hash || hash == range_end);
    previous_hash = hash;
}

Performance

FlipHash has constant average and worst-case time complexity.

As a comparison, Jump Consistent Hash has a time complexity that is logarithmic in the width of the range.

Evaluation wall times

On an Intel Xeon 8375C CPU.

Range	FlipHash	JumpHash
..=10	5.9 ns	8.2 ns
..=1000	4.7 ns	25 ns
..=1000000	5.5 ns	45 ns
..=1000000000	6.4 ns	69 ns

Functions

• fliphash_64
  Hashes key to a value of range, uniformly and with stability.
• fliphash_64_with_seed