关于去重的问题

Question

在写个爬虫程序，需要在抓取前与抓过的url比较去重。
目前想了两个解决办法，一个是bloom filter,但是没找到java下现成的，最主要的是有误差的可能。
另外就是把url用md5一类的算法生成一个摘要，放到hashset里去比了。。想问下有必要先生成md5再放到hashset里么？java自己用的算法是什么样的？
另外就是md5有多少位的？128和256么？有没短点的？长度和碰撞概率有什么关系么？

Answer 1

md5一般是32位的
但你的需求似乎没必要生成md5摘要摘要长度在算法相同的情况下和碰撞概率当然有联系了

Answer 2

答:用url本身的string做KEY,不行吗?

Answer 3

你们说的是16位还是16位字节还是16个字符啊？url比较长另外据说java的string的hashcode算法很容易碰撞？

Answer 4

推荐不哈希化，直接使url本身的string做KEY

Answer 5

同一串字符，返回的hash是一样的，可以看看String类的源码：）

Answer 6

同一串字符，返回的hash码是一样的，可以看看String类的源码：）

Answer 7

同一个string当然hash code肯定是一样的啊
我的意思是如果出现hash碰撞以后hashset是怎么处理的？

Answer 8

这种需求应该不需要那么麻烦，一般url又不会很长，不就几十个字符吗，直接用url做key比你用hashcode还方便准确，虽然效率比用hashcode肯定要低一点，但是这种效率对于网络获取url内容以及存取数据库内容所花的时间来说完全可以忽略不计。

Answer 9

Key值出现重复，put方法会把原来的value替换掉，并且返回原来的value，若原来没有，则返回null。

Answer 10

key?你是说hashcode么？
hashset的话应该是不能有重复的元素。
我记得我看有人说过java的hashset在加入新元素的时候是先用hashcode找到有没有同样的hashcode在hashset里，有的话再看那个元素是不是和新加入的元素equals.不知道是不是如果碰撞了的话也就是hashcode相同但是元素不equals的时候hashset会不会有一些特殊的处理。因为hashcode这东西本来就不是很靠谱，据说java自己的string的hashcode的算法的碰撞概率是很高的，如果放任不管的话hashset也太不可靠了吧。。

Answer 11

hashcode是有重复的问题的概率方面，倒未必大。
自己写hashcode？

Answer 12

答:出现hash碰撞后,其实是线性表的依次逐一进行测试的.这时是性能差的.因此,要尽可能不能碰撞.hashCode应该在整个HashSet的长度内尽可能均匀分布才行啊.Has函数是不大好设计的,弄不好,弄巧成拙了.

Answer 13

不用一次逐一测试吧？插入的时候看下hashcode对应的值是多少，如果对应的值不同，就把这个新插入的标记出来，然后再插入。。难道你的意思是java实现的时候是把所有碰撞的都放到一个链表里，然后如果以后再有碰撞的就从链表的里去找？...

Answer 14

答:难道你的意思是java实现的时候是把所有碰撞的都放到一个链表里，然后如果以后再有碰撞的就从链表的里去找？...
是把HASHCODE相同的那些对象放到一个链表里,然后从链表的里去找.而不是:把所有碰撞的都放到一个链表里.

Answer 15

个人比较推荐使用md5进行hash,我也写过类似的程序，一开始的时候，没有使用hash,
把获取到的URL全部放到内存中的一个hashset,结果网页到100W的时候，就OutOfMemory了，
后来的想法是使用MD5 hash,使用128bit的，效果好一点，后来觉得还是不行，因为网页太多了，就想在文件中保存MD5,使用外搜索的方法，二分查找。然后过一段时间后，再外排序一下，而且MD5并不是总保存在一个文件中
而是分很多文件，这样能大致满足需要了

Answer 16

采用BitSet,自个再提供了一个防止碰撞的处理函数