算法2粗糙版:基于布隆过滤器,扫一遍,找出那些可能是重复的。看完这个数据结构你就懂了。
算法2精确版:使用布隆过滤器,扫一遍,找出那些可能是重复的。再扫一遍,计算它们的出现次数,超过1的就是精确的答案。
---
算法1:基本思路是对n个信息进行相对比较平均的分组(使用 hash(info) % m 分成m组),使得每组构成的哈希表可以放在内存中,且保证相同的两个信息进入同一组,然后再对每一组中的数据建立哈希表进行匹配即可。
4GB内存大约可以存下8000w+个50Bytes,考虑到hash表的空间利用率,假设以5000w为一组,则需要1000组(这个数字可以适当增加,并且使用质数的话通常效果更好)。
时间复杂度和空间复杂度都是O(n)。
p.s. 由于涉及到了外存,所以时间和空间复杂度其实就是扯淡。这个算法需要将所有数据先扫描一次(读取),分组(写入硬盘),再对每组进行查找(再读取),也就是要读2次写1次。