給定了一個完美的散列函數，計算包含

Question

給定一組完整的散列函數S，可以計算S中包含的整數，即如果整數不在S中，可以在不讀取散列表本身，如果一個整數是S，你能不告訴散列表嗎？假設我們有一個最小的完美散列函數。所以哈希表的大小是n，S的大小是m，n = m。我很抱歉，如果這是顯而易見的。

Answer 1

不，您不能，因爲完美的散列函數會將每個可能的整數映射到索引。

您可以做的是：對於每個密鑰，僅存儲一些附加信息，例如該密鑰的哈希碼的最後幾位。這樣，你可以說（以一個可配置的概率;它取決於你存儲多少數據）整數是否爲可能在集合中。這與bloom過濾器基本相同（您可以獲得誤報，但不會產生誤報）。