C++爬虫原理(七):布隆过滤器和暴雪字符串哈希的思考

2015/11/23

结合布隆过滤器按位存储的思想，和暴雪字符串哈希算法的思想，写出适合所写程序的哈希。（主要参考，布隆过滤器）

如下：

一、首先申请约为1亿比特位的空间 = 1亿/8 字节 = 13MB，8次哈希，所以需要 8*13MB = 100MB的内存。

这里我为什么要取接近1亿的质数为哈希表大小呢？大约测试了8-9个垂直行业站点，数据量随机（几十万到千万），URL相似度存在高度相似等情况，这里有个奇怪的现象，在哈希表大小为1亿左右的时候，哈希冲突递减的最强。哈希表长度大于1亿的时候，冲突递减衰弱，而付出的内存代价得不偿失。反而8次哈希，同时碰撞，几乎可以避免这种极小的冲突。

二、按位存取哈希结果，8个哈希表，分别存取8个哈希算法的结果。取同时碰撞（都为1）才为真（相等字符串），否则假。首先根据哈希值，计算出索引位，也就是在那个字节号存储，然后计算出哈希在8字节中，所占的位置，置1。

三、读一个URL串，哈希计算。当所有的哈希位都为1的时候，也就是已经抓取（有可能碰撞产生），否则就是没有被抓取，继续任务。

四、存在极小情况的漏抓，但是不会出现重抓的情况。

测试结果：
测试数据均为：随机URL串，存在高度相似（规律站内翻页）、高度散列、最大长度256或者更高、中文串交叉等真实URL串，非构造出。

例如：

https://www.baidu.com/123213/344444/453453/657657/786786/1_1.html

https://www.baidu.com/123213/344444/453453/657657/786786/1_2.html

https://www.baidu.com/123213/344444/453453/657657/786786/1_3.html

30W，无任何碰撞！

100W，无任何碰撞！

500W，无任何碰撞！

1000W，（这时候txt文件大小已经接近1GB+），测试结果无任何碰撞

总结：千万级数据量的大小程序使用该方法不产生任何冲突（测试3次1000W随机站点数据），适用于垂直爬虫的抓取！所用哈希算法为最常见的字符串哈希算法，如果结合优秀的哈希，碰撞次数更小。

Blogroll