從稀疏鍵空間映射到密鑰空間

我有一個事件列表，它有一個標識瀏覽器的UUID。鑑於這個稀疏的關鍵空間，我想映射到一個密鑰空間。從稀疏鍵空間映射到密鑰空間

除了布魯姆過濾器，我還有什麼其他的選擇？

如果我可以有一些映射到64位值的東西，它會是完美的，特別是如果它是算法而不是查找表。

我看不到如何使用Bloom Filters來做映射。布盧姆過濾器旨在通過`no`或`maybe`來回答'是成員'問題。 – 2011-01-12 16:31:10

如果事件列表是固定的而不是動態的，那麼可以使用Minimal Perfect Hashing函數。

2011-01-12 14:31:22 Tim

UUID是一個真正的UUID，因此2 ** 128種可能性。這是很多項目。 – 2011-01-12 15:33:39

爲了保證零衝突，使用任何標準字典/符號表算法。這就是他們所做的。

對於最小的碰撞，有各種散列函數可用。鮑勃詹金斯的lookup3.c相當受歡迎。然後你必須問自己一個問題，如果你將受到惡意選擇的UUID。如果是這樣，你需要一個更好的散列函數和一個安全的隨機鹽。（如果你可以容忍這個速度，鍵控HMAC是完美的選擇。）

2011-01-13 03:02:33 Anonymous

回答