大数据查重

大数据去重复/查重

经常会有大量的数据比如100G，要在内存为4G的处理器上进行查重和去重操作。

ConcurrentHashMap

数据量不大的时候可以采用concurrentHashMap来操作。

布隆过滤器

布隆过滤器是一种采用hash法进行查重的工具，它不是简单的做hash操作，而是将数据进行n次hash处理得到n个整数，将一个很长的数组的这n位从0设置为1。下次查找的时候经过同样的计算，如果这几个位置都是1则说明已经重复。

优点是使用方便，不需要存储k节省空间，多个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个文件，如果有重复，那么A和B的重复数据一定在相对同一个文件内，因为hash结果是一样的。将1000个文件分别加载进来，一一比对。