hash - 如何计算此哈希函数上的冲突？

Question

我做了一个简单的散列函数（如果它可以被称为一个），它将一个字符串转换为一个双精度。

它的工作原理是取第一个字符的值并将其转换为双倍，然后将其与下一个字符的余弦相乘，然后与下一个字符的余弦相乘，依此类推......

这是功能：

double hash (string str) {
    double hash = (double)str[0];

    for (int i = 1; i < str.length(); i++) {
        hash *= cos((double)str[i]);
    }

    return hash;
}

那么如何计算这个函数中的碰撞概率呢？

我找到了一个公式，它是 1 - e^(k(k-1)/(2k))，但从我读到的内容，它只有在哈希函数是一个好的函数时才有效（它均匀地分布哈希值，就像一个好的 RNG ， 或类似的东西）。

Answer 1

使用浮点数学计算字符串的哈希似乎有点过头了。您的公式至少有一个问题是同一字符串的排列会导致冲突，因为乘法是可交换的。

在您的情况下hash('abc') = (cos('a') * cos('b')) * cos('c')，等于hash('cab') = (cos('c') * cos('a')) * cos('b')，除了可能存在一些小的浮点错误。