給定一組完整的散列函數S,可以計算S中包含的整數,即如果整數不在S中,可以在不讀取散列表本身,如果一個整數是S,你能不告訴散列表嗎?假設我們有一個最小的完美散列函數。所以哈希表的大小是n,S的大小是m,n = m。我很抱歉,如果這是顯而易見的。給定了一個完美的散列函數,計算包含
0
A
回答
0
不,您不能,因爲完美的散列函數會將每個可能的整數映射到索引。
您可以做的是:對於每個密鑰,僅存儲一些附加信息,例如該密鑰的哈希碼的最後幾位。這樣,你可以說(以一個可配置的概率;它取決於你存儲多少數據)整數是否爲可能在集合中。這與bloom過濾器基本相同(您可以獲得誤報,但不會產生誤報)。
+0
我沒有考慮像bloom濾波器,在我特殊的GPU應用程序中bloom濾波器將適用於共享內存,所以這非常好。感謝您花時間回答,爲延誤道歉,從未收到通知。 – nexpert
相關問題
- 1. 完美散列函數的定義
- 2. 完美的散列函數和福利
- 3. 編寫一個計算數組中完美總和的函數?
- 4. 散列函數計算
- 5. 爲什麼給定的散列函數是一個糟糕的散列函數?
- 6. 通過固定長度輸入驗證完美散列函數
- 7. 從給定散列計算base64編碼的散列?
- 8. SHA散列函數給出了一個負面的輸出
- 9. 熊貓行計數給出了另一列包含一定的值
- 10. 大整數整數的完美散列函數[1..2^64-1]
- 11. 沒有這樣的東西作爲一個完美的散列函數?
- 12. 完美的散列函數是否保證沒有碰撞?
- 13. 保留最小完美散列函數的順序
- 14. 8乘8板的完美散列函數?
- 15. 如何檢查散列是否「完全」包含在另一個散列中?
- 16. 如果包含該散列的字符串可以計算散列嗎?
- 17. 我想找到一個散列函數生成散列與給定長度
- 18. 計算給定範圍內的完美平方,完美立方體等的數量?
- 19. Android實現包含另一個散列映射的包含散列映射的可包含對象
- 20. 如何計算這個散列函數中的衝突?
- 21. 如何計算這個散列函數的衝突?
- 22. 內存地址近完美或完美散列c
- 23. 做了一個弱命名的.NET程序集包含一個散列清單
- 24. 前一個函數(包含ajax)完成後調用函數
- 25. 散列碼計算
- 26. 計算給定列表中的偶數
- 27. 創建一個包含數組的散列
- 28. k-mer使用完美散列法計入R
- 29. 我定義了一個散列,但存在函數拋出一個錯誤,說它不是散列
- 30. 引用一個包含列方向計算值的行
如果散列函數是「超過一組整數S」,那麼如何確定「i」不在'S'中?你會期望哈希例程爲「不在S」中拋出異常嗎?返回一個特殊的標誌值? –
我想任何布爾返回值都可以工作,我只是不想讀哈希表。 – nexpert