尋找一箇中等強度的散列函數

我有一個從20到60個字節的〜35000個唯一的ASCII文本字符串。我想在他們中引入一個獨特的索引。簡單編號會因各種原因而不受歡迎。尋找一箇中等強度的散列函數

像MD5這樣的加密級函數可以正常工作，但我覺得這是一種矯枉過正。這最終是爲了一個移動項目，所以我對存儲和CPU週期都很貪婪。另一方面，我嘗試了32位Adler32併發生衝突。

任何人都可以想到一個好的散列函數，產生一個64位值？

2011-08-30 Seva Alekseyev

你能詳細說明爲什麼給它們編號是不可取的，但是像64位散列一樣簡單的方法是可取的嗎？ – corsiKa

我希望密鑰值（即散列）在設置的小修改下不變 - 添加額外的字符串或刪除。字符集集會偶爾更新（而不是我），我想要存儲的哈希值保留其含義。 –

嗯。難道你不能只在最後添加新的，並「刪除」已刪除的索引嗎？對於帶有遞增主鍵的數據庫表，它工作得非常好。我看到的問題是從字符串值到索引的查找的代價（您希望Trie，BST或具有諷刺意味的哈希表，其中任何一個可能會佔用比您想要的更多的內存），而不是任何更改難度集合。 –

建立在64位MurmurHash64B。 purry冠冕堂皇的名字的額外點。

來源

2014-01-31 18:29:36

由於集你已經是固定的字符串，你應該嘗試尋找一個perfect hash function，散列函數專門對一組數據，以保證發生沒有衝突設計。有很多工具可以創建像這樣的哈希函數，其中之一，gperf（不要與gprof混淆）我知道是免費提供的。我強烈建議這一點。

如果您以後最終需要更改字符串集並希望獲得輕量級的簡單哈希函數，則可能需要考慮使用Rabin-Karp rolling hash function。可以使用O（n）加法，乘法和模數計算長度爲n的字符串，並確保每兩個字符串具有成對獨立的散列值。而且，你大概可以在大約半個小時內對它進行編碼，以測試它是否比Adler校驗和更好。

也就是說，如果您不想實現加密安全性，那麼使用像MD5這樣衆所周知的散列函數仍然可能是一個好主意。在這種情況下，即使是一個簡單的CRC32也是足夠的。

來源

2011-08-30 23:05:39 templatetypedef

MD4在密碼上破碎，但比MD5快。 Fowler-Noll-Vo是一個很好的非加密哈希函數。 – rossum

鑑於碰撞的可能性從64位降低到128位的事實減少了很多，我會強烈考慮使用MD5128。

 Max entries before X chance of collision 
Bits 10e−18 10e−15 10e−12 10e−9 10e−6 0.1%  1%  25%  50%  75% 
---------------------------------------------------------------------------------------------- 
16 2  2  2  2  2  11  36  1.9e2 3.0e2 4.3e2 
32 2  2  2  2.9  93  2.9e3 9.3e3 5.0e4 7.7e4 1.1e5 
64 6.1  1.9e2 6.1e3 1.9e5 6.1e6 1.9e8 6.1e8 3.3e9 5.1e9 7.2e9 
128 2.6e10 8.2e11 2.6e13 8.2e14 2.6e16 8.3e17 2.6e18 1.4e19 2.2e19 3.1e19 
256 4.8e29 1.5e31 4.8e32 1.5e34 4.8e35 1.5e37 4.8e37 2.6e38 4.0e38 5.7e38 
384 8.9e48 2.8e50 8.9e51 2.8e53 8.9e54 2.8e56 8.9e56 4.8e57 7.4e57 1.0e58 
512 1.6e68 5.2e69 1.6e71 5.2e72 1.6e74 5.2e75 1.6e76 8.8e76 1.4e77 1.9e77

因此，與35000（3.5e4）字符串，用64位的哈希，這給你一個10E^-12和10E^-9機會，有碰撞之間的事情。這似乎不是很高，但是當涉及到哈希時，十億分之一的數字很容易被打破。

通過增加到128位，你可以下降到遠低於1億（億億）億。

來源

2011-08-30 23:13:52 corsiKa

當然，由於字符串集合是靜態的，因此提問者可以運行64位散列。如果有十億分之一的機會存在數據集中的碰撞，請添加鹽並再試一次。第二次嘗試將延伸到十億分之一的可能性增加到1，而不必延長到128位。嘗試第二種鹽的能力將達到十億立方英寸，所以即使採用非加密哈希的體面分佈，除非攻擊者選擇35k字符串，否則我們聽起來很健全。 –

史蒂夫說什麼。 –

@Steve如果你走得那麼遠，那麼你也可以把它減少到32位散列。這隻會有20％的碰撞機會。這很大程度上取決於哈希將如何使用。 – corsiKa

我想你可以連接兩個不同的32位散列函數的值來獲得64位散列。

要獲得四個不同的散列函數，我將使用預處理步驟，以某種方式將散列函數的輸入更改爲不與散列函數中的值交換。一種方法是使用一個256字節的查找表重新編號字節。另一個可能是將每個字節乘以X mod 257，用-X mod 257替換產生256 = -1 mod 257的任何內容，否則將不會發生。請注意，（a * 256 + b）mod 257是a + b mod 257.

來源

2011-08-31 04:18:00 mcdowella

FWIW存在非安全散列函數，具有相當好的保證。作爲一個例子，選擇一個素數，並按照該數字進行所有計算，這給了你一個數學領域。將你的數據切換成一個模數序列，並將它們當作多項式的係數。除了爲你的散列函數選取模數之外，你還可以選擇一個數字x mod作爲素數，然後在該x處計算多項式。理論上x是隨機挑選的。

如果兩個消息的多項式差爲零，則映射到相同的值，這意味着所選的x是該多項式的根。一個N次多項式至多有N個根，所以在你的情況下 - 如果你有很短的弦並選擇一個大的模數 - 這不是一個不好的保證。如果你加密這個計算的結果，我想我認爲這是一個更快的方法來獲得一個安全的散列函數。我認爲它應該比MD5更快，因爲即使做算術模128位素數是昂貴的，有人認爲它比做MD5便宜。

來源

2011-08-31 18:14:40 mcdowella

尋找一箇中等強度的散列函數

回答

相關問題