1 unstable release

0.1.0 Feb 16, 2024

#1973 in Algorithms

Custom license

35KB
685 lines

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 Platinum 8375C CPU @ 2.9GHz.

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

Dependencies

~26KB