爲數百萬項創建完美哈希 - 結果只需要「是否存在」

Question

有誰知道一個好的庫（窗口），可以讓我創建一個靜態（不是運行時）完美的哈希數百萬個項目大概約10米）？

我基本上擁有數百萬套字符串，我想知道最小O（1）字符串是否在我的集合中 - 就是這樣。我不需要它來查找字符串 - 它背後沒有任何價值（除了存在）。

Answer 1

嘗試：

• 鮑勃·詹金斯的perfect。
• CMPH
• gperf

完美的gperf和產生的C代碼形式的表，這應該工作在Windows的罰款。我不知道CMPH的輸出是什麼。

CMPH有評論說：

的gperf是有點不同，因爲它的構想是創造小套鑰匙和CMPH圖書館非常快捷完善的散列函數的構想是打造最小完美哈希函數非常大的鑰匙組。

如果這是正確的，那麼在你的百萬密鑰的情況下，你應該更喜歡CMPH。我不知道他們與詹金斯的完美比較。它應該很簡單，嘗試所有三個，並針對彼此進行基準測試。

Answer 2

布盧姆過濾器將做你想做的，我會環顧四周有圖書館，或者你可以嘗試自己寫一個。