c++ - 单机海量哈希去重算法

Question

单机环境，有大约1TB硬盘装满了md5哈希，里边有重复的，怎样才可能最快速度踢出重复的。内存大小限定为512MB吧

我实际遇到的一个问题，我去知乎提问了。居然被管理员封了，说我“代为解决个人问题”
https://www.zhihu.com/questio...

我把我知乎的回复抄过来

居然有人投诉说"代为完成个人任务",也是醉了。这个问题不是面试题，也不是啥个人问题。是我实实在在遇到的问题。我有个思路，实现也简单，但是预估计跑完得个把星期了。

现在有两T，1TB是数据，另外1TB用来存放结果。

我现在没有啥特别好的思路。只有最简单的优化。
分文件

A分区存1TB数据，B分区空闲

MD5hash 特点0~9a-f 总共16种情况 总共32个字符。

第一步分级
分两级

第一级 0·f 总公16个目录
第二级 0-f 总共16 个文件

那么这样下来我们总共会有256个文件

从A分区中顺序读取哈希，哈希的第一个字母情况根据目录进行分类；
哈希的第二个字母进行文件分类；对于任意一个A分区中的数据，会通过前两个字母定位
到这256个文件中的某一个；

顺序遍历A分区数据，完成全部操作之后会生成256个文件。

第二步
此时就转化成为将256个小一点的文件进行去重；

对于小一点的文件去重；

1. 分块读入内存进行堆排序，进行一次顺序遍历则可以剔除重复数据；

2. 对于两个已经分块的顺序数据合并去重；这种情况相当于“”有序单链表合并问题“”
   很容易做到；

3. 依次重复1.2两步可以将这256个小文件去重；此时得到结果

这是我想的一个简单办法，但是估算了一下时间可能要个把星期。。。好久

Answer 1

之前做過去除幾百G的DNA序列中的重複序列，感覺和這個問題類似（假設你的文件一行一個hash），buffsize給的是30G（在集群上跑了一天），不知道你這512M要跑多久...

sort -u -S buffsize -o unique_file file

Answer 2

不知我是否對那1TB資料真正理解，我按你的方法算出來的空間要求遠大於你的空間限制，但時間遠小於你的估計。
考慮MD5為最佳儲存方案，則每個MD5所佔用的硬碟空間為$$frac{log_{2}1632}{8}=16$$，如此，整個1TB硬碟中約有$$610^{10}$$個MD5。
依你的方法，在平均情況下，空間佔用為1TB/256(4GB)，超過了256MB的限制。何況MD5首兩個字母的分佈不一定是平均的，所以這個值可能會更大。
但是計算時間，我得到的答案約為16h，算上IO的開銷及分類準備，怎麼也不可能超過兩天。
當然，理論上分類沒必要這麼麻煩，直接外部排序並線性去重來的更方便。而你的方法複雜度為$$O(nklog_{2}frac{n}{k})(k=256)$$，直接方法為$$O(nlog_{2}n)$$，所以在理論複雜度上後者也更低。但是加上磁碟IO等因素，孰優孰劣我可不能妄加定論了。
所謂

Answer 3

直接用Hadoop行不行~

---

雜湊值是128位元的，只要其中1位元不同，就不是重複的。
所以，不用太複雜的比較演算法，只要抽取其中一部分進行比對就行了。
例如，只比較每個雜湊值的低64位元。這樣能過濾掉大部分值。

硬碟最好是2個，避免讀寫衝突。
第二個空硬碟當作平坦空間用，用來標示重複值，而不是把雜湊值從A碟複製出來。

Answer 4

1.我覺得這類問題出現頻率很高的，例如面試，筆試題中，所以一般Google一把，都能找到比較詳細的答案的。
2.hash去重應該可以用這個演算法Bloom Filter

Answer 5

這個得用布隆過濾器

Answer 6

我來一個暫且忽略IO速度的演算法：

1. 把資料平均分成1024 2或 1024 2.5個；O(N)

2. 對每個資料檔案的hash值進行排序，快排就可以了; O(NlogN)

3. 建立一個小根堆，然後建立1024 * 2.5個檔案讀取連接，一個檔案對應一個；

4. 第一次先從檔案中讀取1024 * 2.5個md5，依序放到堆中，得標記一下每個md5是來自哪一個檔案；

5. 將堆頂取出，輸出到檔案中儲存（這個md5代表算完了），但這個堆頂先留著；

6. 根據4記錄的文件，從那個文件（有可能一個md5對應了多個文件，如果有多個，隨便一個文件就行）再讀1個放進堆中，並更新一下新的md5是來著哪個文件；

7. 將堆頂取出，與5記錄的前堆頂進行比較，如果相同的則拋棄；如果不同，則存入文件，並更新堆頂的記錄，轉到6。直到所有字元都搞完了。 O(NlogN)

總平均複雜度：O(NlogN)。

現在有這樣幾個問題，一，我不清楚0.5個G的資料能不能在記憶體中一次排完，因為我沒開過那麼大的數組；二，如果會用字典樹來解第4部的記錄那速度會更快；三，能不能建立幾千個文件流來讀我也不清楚，沒試過，如果建立不了，可以建1個也行；四，IO輸入輸出會不會很慢，例如每次讀1條md5，要讀1TB的，會不會慢到無法接受。

IO太慢的話，這個方法跑上好幾天也是可能的。