url去重策略：

1 保存到数据库 效率低

2  hashset 不放入重复的元素，键值对，查询只需要O（1） 太消耗内存

3前两种可以通过MD5或SHA -1    单向哈希在保存，节省内存

4 Bit-Map方法 建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。1 byte=8bit，用bit就更节省内存了

方法1~3都是将访问过的URL完整保存，方法4则只标记URL的一个映射位。

方法4如果只用一种哈希算法，冲突率太高

所以引入了 Bloom Filter，就采用多个哈希，对一个url分别进行多次哈希，下图，第一次哈希，算到8.就在第8位设置为1，依次类推

  　Bloom Filter算法如下：

  　 创建一个m位BitSet，先将所有位初始化为0，然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h（i，str），且h（i，str）的范围是0到m-1 。

所以，当URL经过哈希对应的位如果不全为1就肯定没有记录过，但是全为1也不一定被记录过，因为可能刚刚好恰巧，

这种错误叫false positive 

删除的话就不建议删除，但是要删除有一种叫Counting bloomfilter(CBF)，这是一种基本Bloom Filter的变体

补充：

scrapy的url去重原理：

需要将dont_filter设置为False开启去重，默认是True，没有开启去重；

.对于每一个url的请求，调度器都会根据请求得相关信息加密得到一个指纹信息，并且将指纹信息和set()集合中的指纹信息进行比对，如果set()集合中已经存在这个数据，就不在将这个Request放入队列中。如果set()集合中没有存在这个加密后的数据，就将这个Request对象放入队列中，等待被调度