具有已知最大項數和固定密鑰大小的高效固定大小「有損」哈希表

鑑於我將始終有一個128位整數作爲關鍵字和最大數量的元素，是否有可能做一個完美的哈希函數？具有已知最大項數和固定密鑰大小的高效固定大小「有損」哈希表

我想存儲GUID作爲鍵，我想要一個固定大小的無鏈表解決方案。那就是如果有碰撞，我會失去第二個元素。

有人可以推薦一個哈希函數來做到這一點嗎？

這些GUID是在本地生成的嗎？在這種情況下，實際上每個GUID只有一小部分會有所不同 - 我忘記了詳細信息，但您可能需要查看由哪些GUID組成的部分，並且只使用最可能不同的部分。 –

事實證明，已經討論過GUID上的散列[這裏]（http://stackoverflow.com/questions/7326593/guid-gethashcode-uniqueness）。 –

@ 500-InternalServerError實際上，大多數現代GUID算法幾乎都是隨機位，而不是舊的機制，其中大約一半是基於硬件密鑰，一半是時間戳。 – Servy

鑑於我將始終有一個128位整數作爲一個關鍵和最大數量的元素，是否有可能做出完美的散列函數？

如果熵關鍵的（預期的信息包含在變量值）是比散列的結果可以容納更大的 - 答案是否定的。如果密鑰的熵等於或低於散列結果可以容納的值 - 答案是肯定的。

意思是說，如果你的散列函數例如產生了一個16位的結果（65536個可能的值），而你的128個關鍵變量可以假設至多有65536個或更少的不同值（所以128位密鑰的熵最多10位）比存在這種散列函數。另一方面，如果您的密鑰可以承擔超過65535個不同值，那麼您無法將其散列到65535或更少的存儲桶中。

有人可以推薦一個哈希函數來做到這一點嗎？

不知道什麼樣的可能的值可以假設沒有人可以給你一個哈希函數，即使你知道關鍵熵太低以至於它可以完成，也可以做到這一點。

2013-01-23 10:38:43 RoBiK

回答