128位密钥的高速通用哈希函数

Question

128位密钥的高速通用哈希函数

3

我需要一个非常快速的通用哈希函数，用于128位密钥。返回值需要约为32位（16位足够；实际上，大多数情况下我只需要1-4位）。通用哈希意味着有两个参数：密钥（128位）和索引（64位）。对于两个密钥，如果使用不同的索引调用通用哈希函数，它需要最终返回不同的结果。因此，使用不同的索引，通用哈希应该像不同的哈希函数一样运行。对于x = universalHash(k, i)和y = universalHash(k, i + 1)，最好平均50％的所有位在x和y之间不同（随机）。对于使用不同密钥调用方法的情况也是如此。在实践中，5%的误差对我来说还可以接受。

它需要非常快速（最多一两次乘法）。它被调用数百万次。请不要说：不，你不需要它很快。它还需要最终返回不同的值。

到目前为止我所拥有的（Java代码，但由于缺少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项目，特别是RecSplit算法和这篇文章。为了支持大小为10^12的集合（例如BBHash），我尝试在内部使用128位签名，这将简化算法。

- Thomas Mueller

2

那问题是什么？ - Jabberwocky

2

{btsdaf} - Eugene Sh.

这里也需要知道索引的宽度很重要。 - Ajay Brahmakshatriya

1

一个重要的方面是，哈希函数是否需要具有密码学安全性，还是只需要等分布即可。 - Ctx

你真的需要64位索引吗？类似于所有四个4B块的XOR是否有用？ - Peter Cordes

显示剩余9条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ajay Brahmakshatriya · Answer 1

你需要一个哈希函数，将128位的输入输出32位。

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

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

对于键0，您选择最低的32位
对于键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));
}