结合布隆过滤器按位存储的思想，和暴雪字符串哈希算法的三次确认是否存在方法，练手写出适合所写程序的哈希。（这里我并没有测试布隆过滤器在1000W数据量的误差，也并没有诸如暴雪哈希等一大批优秀的算法，提供一种思路仅此而已。）

思路如下（注：结合测试搞出来的。如有纰漏，非常感谢指出）：

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

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

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

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

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

30W，无任何碰撞！

100W，无任何碰撞！

500W，无任何碰撞！

1000W，（这时候txt文件大小已经接近1GB），测试结果无任何碰撞，也就是数据量为1000W的时候，碰撞为0，不过这里有次数据，6次哈希碰撞为16，7次哈希碰撞为1，8次依然为0。

总结：1000W数据量的大小程序使用该方法不产生任何冲突（测试3次1000W数据），所用哈希算法为最常见的字符串哈希算法，如果结合优秀的哈希，碰撞次数更小。

Copyright：www.cplusplus.me Share、Open- C/C++程序员之家