什麼哈希算法考慮了可變長度數據

Question

爲了避免對哈希算法

問題陳述 我有一個包含可變長度的數據記錄多個文本文件我重新取景根據我的研究，我的問題的任何混淆。我需要找到輸入中是否有重複的記錄。每個文本文件都可以有數百萬的數據記錄。

由於無法一次加載內存中的所有數據，我計劃在處理記錄時在記錄中創建關鍵字段的散列。處理記錄意味着驗證，過濾和轉換它。處理完所有文本文件中的所有記錄後，它們將被合併，以創建整個輸入（文本文件或數據庫表）的一個視圖。

如果爲所有記錄生成散列值，則查找重複項會快得多。如果存在散列值衝突，則只能檢查這些記錄是否相等（假設散列算法是確定性的）

問題 - 對於這種輸入（即可變長度數據），我應該考慮哪些散列算法？

Answer 1

簡答

不要這樣做。使用Java地圖。你可以在這裏找到細節： http://docs.oracle.com/javase/6/docs/api/java/util/Map.html

長的答案

您可以通過將您的字符串作爲基礎-N的數，其中N是所有可能的值的任何字符可以創造一個完美的散列函數上。這裏的問題是內存。散列函數意味着與數組一起使用，這意味着您需要一個足夠大的數組來處理散列結果，這是不切實際的。

例如，以10個字符的鍵爲例。讓我們更謙虛，並假設他們保證只包含小寫字母。這給你26個可能性，每個角色和10個字符。這意味着可能的組合有：

26^10 = 141,167,095,653,376 

如果你看看散列算法，它們包括第一件事就是碰撞檢測，因爲他們認識到，衝突是生活中的事實。

現在你說你沒有在內存中加載密鑰，但你爲什麼要使用哈希呢？散列的一點是給你一個映射到數組索引。也許你最好使用另一種機制。

可能的解決方案

如果您擔心內存，得到重複的一些統計數據在您的文件。如果您只存儲一個標誌來指示哈希中某個特定鍵的出現，並且您有很多重複項，那麼您可以使用Java的地圖。 Java的映射處理衝突，所以不會阻止你檢測唯一的密鑰。您可以放心，如果找到A [x]，那就意味着x在A中，即使x的散列與先前的散列相沖突。

接下來，您可以嘗試一些實用程序來提取重複項。由於它們是專門爲此目的而編寫的，因此它們應該能夠處理大量的數據。

最後，您可以嘗試將條目放入數據庫並使用它處理重複項。這可能看起來像是矯枉過正，但數據庫針對處理大量記錄進行了優化。

Answer 2

這是地圖創意的擴展。在訴諸這個之前，我會檢查它不能通過簡單地建立一個代表所有字符串的HashSet來完成。請記住，您可以使用64位JVM並設置較大的堆大小。

定義一個類StringLocation，它包含您需要對磁盤上的字符串進行隨機訪問的數據 - 例如，對RandomAcessFile的引用和文件內的偏移量。如果無法一次打開所有文件，請根據需要打開和關閉，爲RandomAcessFile緩存最常用的文件。

創建一個HashMap<Integer,List<StringLocation>>。

開始閱讀字符串。對於每個字符串，轉換爲小寫並以Integer形式獲取其hashCode（），hash。如果在Map中有一個以hash作爲關鍵字的條目，則將新字符串與現有值中表示的每個字符串進行比較，執行隨機文件訪問以獲取已處理的字符串。使用字符串equalsIgnoreCase。如果有匹配，你有一個副本。如果不匹配，則將表示當前字符串的新StringLocation附加到列表中。

這需要一次最多有兩個字符串在內存中，一個是當前正在處理的字符串，另一個是之前處理過的字符串，它與您正在比較的hashCode（）結果相同。

通過使用MessageDigest爲小寫字符串生成一個低衝突風險的寬校驗和並將其保存在等式檢查中，您可以進一步減少重新讀取等值檢查字符串的次數StringLocation對象。在比較期間，如果校驗和不匹配，則返回false，而不重新讀取字符串。