单机海量哈希去重算法？

单机环境，有大约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两步可以将这256个小文件去重；此时得到结果

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

---

360U3058061266优艾设计网_设计圈 9小时前

硬盘最好是2个，避免读写冲突。 第二个空硬盘当作平坦空间用，用来标记重复值，而不是把哈希值从A盘复制出来。

---

a397460849 优艾设计网_在线设计 9小时前

直接用Hadoop行不行~

---

kulongdo 9小时前

优艾设计网_设计

哈希值是128位的，只要其中1位不同，就不是重复的。所以，不用太复杂的比较算法，只要抽取其中一部分进行比对就行了。比如，只比较每个哈希值的低64位。这样能过滤掉大部分值。

---

大龙猫家 优艾设计网_设计模板 9小时前

之前做过去除几百G的DNA序列中的重复序列，感觉和这个问题类似（假设你的文件一行一个hash），buffsize给的是30G（在集群上跑了一天），不知道你这个512M要跑多久...

---

萌叔之吻 优艾设计网_Photoshop交流 9小时前

这个得用布隆过滤器

---

柳栋 9小时前

优艾设计网_Photoshop交流

1.我觉得这类问题出现频率很高的，比如面试，笔试题中，所以一般Google一把，都能找到比较详细的答案的。2.hash去重应该可以用这个算法Bloom Filter

---