数据去重方法

根据原理主要可以分为两类：循环和哈希。

循环

以python为例，比如可以用for循环、也可以利用python的内置函数reduce特性实现去重。
python的内置函数reduce能对序列中的数据实现累积。reduce的参数有两个，一个是一个函数，一个序列，reduce函数首先是对元素中的第一个元素、第二个元素利用传入的函数进行操作，再将获得的结果与第三个元素进行操作，以此类推，最后，获得结果。

image

哈希

哈希函数是指可以将任意大小的数据转换成特定大小的数据的函数，转换后的数据成为哈希值或哈希编码。
由于哈希表消耗的内存很大，当数据量非常大的时候就无法使用它来去重。因此就出现了布隆过滤器（bloom filter）。

• 布隆过滤器原理
  布隆过滤器的核心就是利用位数组和几个哈希函数来表示一个集合。假设位数组的长度为m，哈希函数有k个。当给布隆过滤器中添加元素的时候，首先利用几个哈希函数计算当前元素的编码，得到位数组的k个位置，然后在数组中将这k个位置置1。需要查询某个元素是否存在的时候，同样也是先计算当前元素在位数组中的k个位置，然后依次比较这k个位置的值是否都为1，如果有一个不为1，那么当前元素一定不在布隆过滤器里面，如果都为1，元素可能在。因此布隆过滤器具有一定的误判率，
• 由于哈希表是精确匹配，适用于数据量小的时候，或者内存足够的时候，以及一些不能接受误判的场景。而布隆过滤器，适合海量数据去重，并且能容忍错误率的情况，比如：爬虫中网页去重、垃圾邮件的过滤、字处理软件中检查单词是否拼写正确。