java - 适用于 128 位 key 的非常快速的通用哈希函数

Question

我需要一个非常快的通用哈希函数来处理 128 位 key 。返回的值需要大约 32 位(嗯，16 位就足够了；在大多数情况下，我实际上只需要 1-4 位)。

通用哈希意味着，有两个参数:key(128位)和index(64位)。对于两个键，如果使用不同的索引调用通用哈希函数，最终需要返回不同的结果。因此，对于不同的索引，通用哈希的行为应该类似于不同的哈希函数。对于 x = universalHash(k, i) 和 y = universalHash(k, i + 1)，最好是所有位中平均有 50% 是不同的x 和 y(随机)。如果使用不同的键调用该方法，情况也是如此。实际上，5% 的折扣对我来说还可以。

它需要非常快(最多一到两次乘法)。它被调用了数百万次。请不要说:不，您不需要它太快。它最终也需要返回不同的值。

到目前为止我所拥有的(Java代码，但C是(由于缺乏128位数据类型，关键是a和b的组合，它们都是64位):

int universalHash(long a, long b, long index) {
    long x = a ^ Long.rotateLeft(b, (int) index) ^ index;
    int y = (int) ((x >>> 32) ^ x);
    y = ((y >>> 16) ^ y) * 0x45d9f3b;
    y = ((y >>> 16) ^ y) * 0x45d9f3b;
    y = (y >>> 16) ^ y;
    return y;
}

int universalHash2(long a, long b, long index) {
    long x = Long.rotateLeft(a, (int) index) ^ 
            Long.rotateRight(b, (int) index) ^ index;
    x = (x ^ (x >>> 32)) * 0xbf58476d1ce4e5b9L;
    return (int) ((x >>> 32) ^ x);
}

(第二种方法实际上对于某些值来说是错误的。)

我希望有一个比上面的散列函数更快的散列函数，并且保证在所有情况下都能工作(如果可能的话可以证明是正确的，即使这不是一个严格的要求；但是它不需要是加密安全的) )。

我将为相同的键调用带有递增索引(第一个索引 0，然后索引 1，依此类推)的 universalHash 方法。如果可以根据前一个结果更快地计算出下一个结果(例如，无需相乘)，那就最好了。但如果索引是某个值(如示例代码中所示)，我还需要快速“直接访问”。

背景

我试图解决的问题是为相对较小的一组键(通过直接映射最多 16 个键，通过分成更小的子集最多约 1024 个键)找到 MPHF(最小完美哈希函数)。算法详情参见我的MinPerf project ，特别是 RecSplit algorithm 。为了支持大小为 10^12 的集合(例如 BBHash )，我尝试在内部使用 128 位签名，这将简化算法。

Answer 1

您需要一个为 128 位输入输出 32 位的哈希函数。

一种简单的方法是只返回原始 128 位中的“一些”32 位。选择32位的方法有很多种，每种选择都会产生冲突。但索引可以决定选择哪一个32位。

128/32 = 4，因此 4 个索引足以找到至少一个不同的位。

• 对于 key 0，您选择最低的 32 位
• 对于 key 1，您选择接下来的 32 位
• 等等..

C 实现是

uint32_t universal_hash(uint64_t key_higher, uint64_t key_lower, int index) {
    // For a lack of portable 128 bit datatype we take the key in parts.
    return 0xFFFFFFFF & ( index >=2 ? key_higher >> ((index - 2)*32) : key_lower >> (index*32));
}