一个比较傻的问题

akai

这个问题是这样的，
关于url重复的判断.
打算采集一堆URL存到数据库中 类似如下

1. $url = http://www.freeoz.org/forum/post.php?action=newthread&fid=7048&extra=page%3D1

复制代码

我打算 把$url进行一次单向hash,　比如md5sum那样的。　存入hash这个字段中。
这样　如果我对于新的$url我只要进行hash对比就ok了。我想查询速度肯定比where url=$url 要快吧。
这个问题是。　md5sum太长了。　是否有短点的单向hash函数。
或者兄弟门是否又更nb的算法　作为check duplicated呢？

ritz

搜索一下 bloom filter

周星星1832

md5就行了

coredump

更短的hash算法很多，但是更短也就意味着hash冲突的可能更多

key

原帖由 akai 于 30-7-2009 14:05 发表

                               
登录/注册后可看大图

这个问题是这样的，
关于url重复的判断.
打算采集一堆URL存到数据库中 类似如下$url = http://www.freeoz.org/forum/post ... &extra=page%3D1我打算 把$url进行一次单向hash,　比如md5s ...

MD5是16bytes吧，你可以采用crc校检，32bits，但冲突就大了。
再看你的需求，如果是一锤子卖买，基本上怎样弄都行。
要用单向hash的问题是必须进行fully match；如果用md5，那冲突的机会并不会太大。
另外，采用MD5还有一个好处就是数据是定长的。定长存贮和比较从理论上都有着比不定长比较更大的优势。

然而，如果你考虑到系统的可扩展性，可能存贮完整的url会更好。而且，如果你采用rdbms，
存贮结构化的URL会比存贮单条URL记录更好，比如，你可以用下面的存贮方案：
hash code: 32 bits crc或16byte md5
protocol: 可以用描述性的，也可以用protocol code来代替
host：string
query string: string

这种存贮方案最大的drawback是你需要更多的存贮空间，但考虑到url及其hash都是很小的数据，
这种空间“浪费”还是可以接受的。但对于你的程序来说，无论从性能还是扩展性来说，
都可以得到兼顾了。

流浪的狗

本质是要找一个HASH函数吧。
又要短有要冲突少又要效率高。。。。
权衡一下，搜索看看

ubuntuhk

MD5是16bytes吧，你可以采用crc校检，32bits，但冲突就大了。....

MD5是32bytes的，碰撞的可能性很小，我觉得足够楼主用了，CRC不可靠。

akai

除了crc还有哪几个?核版?

[ 本帖最后由 akai 于 2-8-2009 21:12 编辑 ]

akai

对 我是想找个 短点的hash函数.
或者有更牛B的能检查 重复的办法.

鉴于md5有点长. 当然 碰撞啥对我没啥. 大不了重复了.

[ 本帖最后由 akai 于 2-8-2009 21:15 编辑 ]

yuba

我最近也在做类似的东西

在md5和sha1里选择了md5

主要是md5的速度比sha1快，且cpu占有率低

周星星1832

建议选择数据库内在的函数，减少IO

NoChoice

crc32差不多了，理论上0xffffffff才有碰撞,你如果收集的url远远少于4294967295个的话，crc32是个不错的选择，而且速度快储存小
还有checksum,crc16，md5,md4,sha1, sha256,sha384,sha512