需要一个低冲突哈希函数。输入都是相同 72 位的排列

Question

对于关联数组，我将 72 位散列为 26 位并且需要极低的冲突率。速度也是一个主要因素。我从 https://en.wikipedia.org/wiki/Hash_function#Hashing_By_Nonlinear_Table_Lookup 开始，这已经足够快了，但在测试中，我在前 100 个输入中发生了碰撞！

    for(=0; k<9; k++)
            hash ^= randombits[byteptr[k]];
    hash &= (1<<HASHBITS)-1

问题是我所有的输入都是相互派生的——有一个初始的 72 位，后续输入是通过相互交换 2 个位对（在偶数位边界上对齐）从前一个输入派生的。上面的简单 XOR 循环失败得很惨。一个明显的方法是使用字节索引 "k"，以某种方式在每次迭代中修改散列。除了代码建议，我还在寻找理论基础——我想知道碰撞率是多少。阅读论文我没有发现任何关于排列的哈希有效性的信息。我确信加密哈希会很好，但它们看起来很慢。欢迎对我的研究提出建议和指点，谢谢。 FWIW 我使用 ARC4 生成 "randombits"，一个 256 u_int32_t.

的数组

为清楚起见编辑：输入中的位转换如下所示：对于偶数 N 和小于 72 的 X，位 (N:N+1) 与位 (X:X+1) 交换，对于随机 X 和 N。所有此类交换实际上会改变状态 - 永远不会交换相同的位。

Answer 1

Appliyng birthday paradox 你可以看到，统计上你将在散列 (2**13 = 8000) 个输入后获得超过 0.5 的碰撞概率。

Bast 尝试是使用加密散列或一些基于快速 PRNG 的散列函数（我想到了 Xorshift）。你可以试试 MurmurHash3（作者声称它通过了一些统计测试并且非常快）

https://code.google.com/p/smhasher/source/browse/branches/chandlerc_dev/MurmurHash3.cpp

Answer 2

这是解决我问题的解决方案：在我发布的循环中，在每个 XOR 之间我将散列旋转 k 位，其中 k 是循环索引。在我的测试中，输入排列的碰撞现在和单个位翻转一样不常见。似乎 "birthday paradox" 是阻止我进一步降低冲突率的原因，但我只能负担 26 位 - 散列 table 已经很大了。

需要一个低冲突哈希函数。输入都是相同 72 位的排列

Need a low collision hash function. Inputs are all a permutation of the same 72 bits

algorithm

hash

associative-array

hashtable

hash-collision