什麼散列函數應該散列一個有序的數字列表？

Question

考慮一個類型，它是int鍵到int值的映射。這些鍵的排序不及地圖，並且地圖可以被認爲是扁平列表{key1，val1，key2，val2等}

我生成這些地圖的列表，並希望能夠識別相同的地圖在小於O（n^2）的時間內。我打算散列每個地圖一次來實現這一點。

我不確定散列函數最適合這個用途。我的密鑰可以是非常大的數字（但仍然是int32），值往往很小，但我認爲這樣的考慮是不相關的，希望有一個我可以使用的散列函數，它適用於一般數字序列。

任何想法？謝謝。

Answer 1

大多數散列函數，特別是加密散列函數，都是在二進制數據上工作，所以任何可以表示爲字節序列的東西都可以被處理。你只需要決定你將使用什麼編碼作爲你的鍵值。

至於散列函數，由於您的問題與安全性無關，您可以選擇任何您希望的功能。加密哈希函數提供了非常好的「混合」，有些非常快（與衆所周知的非加密哈希函數如CRC32相比）。例如MD4。但是很可能你的編程語言（你沒有說你使用哪種語言）已經提供了一個MD5的實現，這個實現還是相當快的。