无碰撞的哈希函数

Question

基本上我使用的是rabin karp中的哈希函数。

和在 快速实现滚动散列 但我不是对一个字符串进行散列，而是对一个整数向量进行散列。

const unsigned PRIME_BASE = 257;
const unsigned PRIME_MOD = 1000000007;
unsigned hash(const std::vector< unsigned int >& Line)
{
    unsigned long long ret = 0;
    for (int i = 0; i < Line.size(); i++)
    {
        ret = ret*PRIME_BASE + Line[i];
        ret %= PRIME_MOD;
    }
    return ret;
}

问题是，我得到了很多碰撞。改变质数可以使碰撞最小化或最大化，但我不能避免它。

有什么办法可以避免这种函数的碰撞，或者有更好的办法吗？

Answer 1

你不需要。

散列的全部意义在于从一个大域中获取一个输入，并在一个小域中产生一个输出。

从这个过程的本质来看，碰撞是不可避免的。

你可以 尽量降低其可能性对于某些特定类别的数据集，但你已经探索过这样做了，你可以做得更好一些（减少碰撞的机会），增加更多的哈希函数。

Answer 2

你可以通过添加更多的哈希函数来改善（减少碰撞的几率），比如：创建两个哈希函数，用不同的PRIME BASE和PRIME MOD来存储一对长长的数据。例如:创建2个哈希函数，用不同的PRIME BASE和PRIME MOD来存储一对长长的数据。

另一个问题是，如果Line存储了很多0，那么最好在数值中加入一些随机的（初始化后固定的）移位。例如，在Robin-Karb中，如果你想计算'A'和'AA'的哈希值，最好加上shift值，否则这两个字符串的哈希值都会是0。 (我的意思是，如果你转换字符，比如：f(char c){return c-'A';}。

另一个有趣的问题是，我认为如果你选择了一个好的哈希函数(从随机方面来看)，并且你的输入也是随机的，那么当Line向量中不同项的数量小于sqrt(哈希函数的范围)时，就不应该发生碰撞，这就是生日悖论。你目前的范围是1e9+7，所以这个范围的平方是3e4左右。如果你使用了两个哈希函数，那么合并范围就是它们的范围的乘法。