這個散列函數是唯一的嗎？

假設散列整數永遠不會溢出，以下生成的散列對於不同的鍵是否總會不同？該鍵應該包含ascii編碼的字符。這個散列函數是唯一的嗎？

我認爲是這樣，因爲我想不出一個例外情況。

char[] arr = "abcd" 
int hash = 0 
for (int i=0; i<arr.size; i++) { 
    hash += (i+1) * arr[i] 
}

EDIT1：雖然下面是技術上是正確的答案，我原來的問題，我應該提到的是，按鍵的域是有效的電子郵件id的。所以，一些ascii字符不包括在內。不過，我會進行一些測試並報告。列舉所有燙髮的唯一問題是可能的，只有很短的一段時間。

無論如何，我的要求是根據email-id製作唯一的ID，並將它們用作數據庫中的主鍵。只是不想使用郵件ID本身。

編輯2：好的，顯然，有大量的碰撞。例如，散列[email protected] ==散列[email protected]

... 
040 == 012 
041 == 013 
042 == 014 
043 == 015 
044 == 016 
045 == 017 
046 == 018 
047 == 019 
048 == 01: 
...

我需要不同的哈希算法。你能建議嗎？例如：

來源

2016-08-04 DebD

「以下生成的散列對於不同的密鑰總是不同的？」根據「散列函數」的定義，答案是「否」。如果答案是「是」 - 不要稱之爲散列函數。 –

您正在佔用一個大的空間並將其「壓縮」到一個較小的空間。根據定義，至少會有2個映射到相同輸出的輸入值。 –

應該至少有一次碰撞 – xdevs23

否：1 * 2 + 2 * 2 = 1 * 4 + 2 * 1。

（char[] arr = {'\u0002','\u0002'}和char[] arr = {'\u0004','\u0001'}）

來源

2016-08-04 15:26:15

這兩個串會產生相同的哈希值：

"~ " 
"@?"

上面完全由可打印的ASCII字符。

測試你的算法的一種蠻力的方法是簡單地嘗試2個字符的所有組合，然後可能是3或4個字符的所有組合，以獲得唯一性的想法。

char key[5] = {0}; 
bool used[65536] = {0}; 
for (key[0] = " "; key[0] < 128; key[0]++) 
    for (key[1] = " "; key[1] < 128; key[1]++) { 
     if (used[hashcode(key)]) { 
      printf("failed %s", key); 
     else 
      used[hashcode(key) = true; 
     }

來源

2016-08-04 15:33:31

你提到的兩個值分別爲190和253。 – DebD

哎呀，對不起@DebD。我認爲它應該是 –

好抓，@DebD。在打字之前我沒有仔細檢查ASCII表格，我的錯誤是必須讀取八進制值或其他值。我會嘗試將第二個更正爲「@？」而不是錯誤的「{A」 –

回答你的問題，另外在你的編輯約尋求改善你的哈希函數，你可以做一個小的變化將是一個素數加總之前乘以每個字符。這不會保證沒有碰撞，但應該減少它們，因爲你添加的每個新術語將間隔更多，並且是素數的倍數。我會跳過前幾個質數來獲得更好的間距，所以也許可以將第一個字符乘以11，第二個乘以13，第三乘17，第四乘19，等等。如果你的琴絃不是太長，你不需要一張非常大的素數表。

如果你真的想要得到幻想，你可以考慮生成一個CRC，或使用線性反饋移位寄存器技術來生成簽名。在後者中，您需要將新字符（或新字符的選定位）XOR到運行總數的最低8位，然後將整個總數旋轉若干位。

來源

2016-08-05 04:09:11

這個散列函數是唯一的嗎？

回答

相關問題