映射函數

Question

我有一組128位數和集合的大小< 2^32 ...所以理論上我可以有一個映射函數，將所有的128位數映射到32位數....我怎麼構造映射函數

Answer 1

好像你正在尋找一個最小perfect hash它將n個鍵映射到n個連續的整數。

上述句子中的wiki頁面鏈接提到了兩個實現它的庫。

也看到更多的細節：http://burtleburtle.net/bob/hash/perfect.html

Answer 2

如果不知道輸入數據的性質，它不可能給最優的哈希算法。但是如果輸入是均勻分佈的，那麼你可以使用輸入的低32位。這意味着碰撞的可能性，所以你必須處理。

Answer 3

通用結構是將所有128位值保存在一個大數組中，按升序排列。然後，每個值被「映射」到數組中的索引。要「計算」地圖，您需要在數組中進行二分搜索，以獲取數組中值的精確索引。使用2 值，數組的大小爲64 GB，二進制搜索需要在數組中進行35次左右的查找。

在所有的普遍性，你不能做的比這更好。然而，如果你的128位數值具有相當均勻的分佈（取決於它們來自何處），那麼大型數組結構可以被大量壓縮，特別是如果你能保證所有地圖輸入總是成分128位值的集合;我敢打賭，你可以將其削減到幾千兆字節 - 但查找會更加昂貴。

對於更實用的解決方案，你將與結構中的128位值的工作：他們來自哪裏，他們代表着什麼......

Answer 4

設置你的電話號碼爲師的位置它的價值在2^32。