給出100億個URL，每個URL的平均長度爲100個字符，檢查重複

Question

假設我有1GB可用內存，如何在這些URL之間找到重複項？

我看到書上「破譯編碼訪談」一個解決方案，它建議使用哈希表在第一次掃描這些URL分割成4000個文件x.txt，X =散列（U）％4000。在第二次掃描中，我們可以檢查每個x.txt文件中的重複項。

但是我怎樣才能保證每個文件都能存儲大約1GB的url數據呢？我認爲有些文件可能會存儲比其他文件多得多的url數據。

我對這個問題的解決方案是迭代地實現文件分離技巧，直到文件足夠小，可用於我的內存。

有沒有其他方法可以做到這一點？

Answer 1

如果你不介意這需要一個更位代碼的解決方案，你可以做到以下幾點：

1. 只計算哈希碼。每個哈希碼恰好是4個字節，因此您可以完美控制每個哈希碼塊將佔用的內存量。你也可以在內存中包含比URL更多的hashcode，所以你的塊會更少。

2. 查找重複的哈希碼。據推測，他們將遠遠少於100億。他們甚至可能都適合記憶。

3. 再次遍歷URL，重新計算哈希碼，查看URL是否包含重複哈希碼之一，然後比較實際URL以排除由於哈希碼衝突導致的誤報。 （含10個十億網址，並與散列碼僅具有4個十億不同的值，將有大量的碰撞。）

Answer 2

這是有點長的評論。

事實是，您無法保證文件將小於1 GB。我不確定4,000來自哪裏。總數據量大約爲1,000GB，因此平均文件大小爲250Mbytes。

這是非常不可能的，你將永遠不會超過4倍的大小。當然，這是可能的。在這種情況下，只需將該文件再分成幾個其他文件即可。這增加了一個微不足道的複雜性。

這不是一個簡單的例子。如果其中一個網址的長度爲100，並且在數據中出現10,000,000次，該怎麼辦？哎喲!在這種情況下，您需要讀取一個文件並通過將每個值與一個計數相結合來「減少」它。

Answer 3

代替計算和存儲的哈希碼，一個應計算的散列碼直方圖。藉助10G不同的網址，您可以使8或2位飽和直方圖最小爲4，最大爲64個文件。

使用2位直方圖，可以在1GB的內存中容納4G不同的哈希碼。

第一遍將只存儲第一個2..6位爲零的哈希碼衝突，接下來哈希函數的第一位爲01（或000001）等等。

建議使用加密強散列代碼來防止衝突。

但即使這種方法很容易產生很多很多的步驟來處理不同的統計數據。 或者，人們可能能夠在葉子處生成具有直方圖計數的帕特里夏樹。可以添加一些標記/在線字典來節省內存。當1GB限制用完時，最大的條目將從樹中刪除，並添加更小的條目。下一個傳球將繼續以樹中最後一個網址爲起點。