如何设计大量数据查重

 

至少在现阶段内存和CPU的执行效率在固定时间内是有限的，大量的数据的查重和去重处理不可能同时在内存中进行。就像外部排序算法和内部排序算法差别很大，遇到此类大量数据查重问题对算法进行设计是有必要的。

ConcurrentHashMap

数据量不大的时候可以采用concurrentHashMap来操作，在内存中对数据进行同步的CRUD操作。

这种做法的好处是很明显的，逻辑处理很简单易懂。但是会产生大量的小对象，小对象会存放在新生代，新生代一般采用复制算法，大量不消亡的小对象在每次GC的时候都对JVM的性能产生灾难性的影响。这是我们不能接受的。

布隆过滤器

布隆过滤器是一种采用hash法进行查重的工具。它将每一条数据进行n次独立的hash处理，每次处理得到一个整数，总共得到n个整数。使用一个很长的数组表示不同的整数，每一次插入操作把这n个整数对应的位置的0设置为1（如果已经被设置为1则不变）。下次查找的时候经过同样的计算，如果这几个位置都是1则说明已经存在。

布隆过滤器的优点是使用方便，因为并不将key存放进内存所以十分节省空间，多个hash算法无关，可以并发执行效率高。缺点也是显而易见的，这种算法是可能出现错误，有误判率这种概念。通过hash的次数我们可以降低误判率，但是不能保证没有误判的情况。

BitMap　

比如有2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，我们只需要2bits就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为00，存在一次01，存在两次及其以上为11。那我们大概需要存储空间几十兆左右。接下来的任务就是遍历一次这2.5亿个数字，如果对应的状态位为00，则将其变为01；如果对应的状态位为01，则将其变为11；如果为11，,对应的转态位保持不变。

最后，我们将状态位为01的进行统计，就得到了不重复的数字个数，时间复杂度为O(n)。

hash分组

如果有两份50G的数据，要查重，内存4G，怎么查？

想法是先将50G的数据分别做hash%1000，分成1000个文件，理论上hash做得好那么这1000个文件的大小是差不多接近的。如果有重复，那么A和B的重复数据一定在相对同一个文件内，因为hash结果是一样的。将1000个文件分别加载进来，一一比对是否有hash重复。这种想法是先把所有数据按照相关性进行分组，相关的数据会处于同样或者接近的位置中，再将小文件进行对比。

有1千万条短信，找出重复出现最多的前10条？

可以用哈希表的方法对1千万条分成若干组进行边扫描边建散列表。第一次扫描，取首字节，尾字节，中间随便两字节作为Hash Code，插入到hash table中。并记录其地址和信息长度和重复次数，1千万条信息，记录这几个信息还放得下。同Hash Code且等长就疑似相同，比较一下。相同记录只加1次进hash table，但将重复次数加1。一次扫描以后，已经记录各自的重复次数，进行第二次hash table的处理。用线性时间选择可在O（n）的级别上完成前10条的寻找。分组后每份中的top10必须保证各不相同，可hash来保证，也可直接按hash值的大小来分类。