FlipHash

FlipHash是一个一致性范围哈希函数，它将整数key哈希到参数化的值..=range_end，其中range_end是参数化的。它是

• 规则的（即均匀的，平衡的）：它将键均匀分布在范围的哈希值上，
• 单调的（即稳定的）：当改变范围时，键的哈希值不会在保持在该范围内的值之间打乱，并且键只能从现在位于范围之外的哈希值（如果范围缩小）重新映射，或者映射到之前位于范围之外的哈希值（如果范围扩大），
• 快速的：它具有低计算成本，并且具有常数时间复杂度。

使用方法

use fliphash::fliphash_64;
let hash = fliphash_64(10427592028180905159, ..=17);
assert!((..=17).contains(&hash));

规则性

以下代码片段说明了FlipHash的规则性。

对于足够多的不同键，range的哈希值出现的次数相对接近。

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);

单调性

以下代码片段说明了FlipHash的单调性，即稳定性。

给定一个键，当扩大范围时，要么键的哈希值保持不变，要么它得到一个新值，而之前的范围不包含该值。

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;
}

性能

FlipHash具有常数平均和最坏情况时间复杂度。

相比之下，Jump Consistent Hash的时间复杂度是对范围宽度的对数。

评估墙时间

在Intel Xeon Platinum 8375C CPU @ 2.9GHz上。