如何計算這個散列函數的衝突？

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')，除了可能的一些小浮點錯誤。