目前写爬虫,网址入库过程中,需要判断新存入的 URL 在原 MySQL 中是否存在,有的 url 很长,只能将 URL 作为 text 类型字段存储在 MySQL 中,但貌似 text 类型字段检索唯一性效率很不高,想把 URL 压缩成 md5 再以定长 char 字段存储在 mysql 中,但是在千万级的 URL 条目下 md5 碰撞几率高么?个人没这方面经验,求好心 V 友推荐个算法
1
Mutoo 2017-07-13 10:32:36 +08:00
你要的这种算法叫 bloom filter
https://zh.wikipedia.org/wiki/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8 |
2
Morriaty 2017-07-13 10:35:51 +08:00
不存在不碰撞的 hash。
判重上 redis |
3
bukip 2017-07-13 10:35:51 +08:00
md5 碰撞几率是 1/2^256,千万级差的太远了。
|
5
rrfeng 2017-07-13 10:38:57 +08:00 via Android
sha256 强度更高一些。
要再高可以多几个 hash 一起存。 不过 md5 足够足够的了... |
6
batnss 2017-07-13 10:41:19 +08:00
目标网站 id + md5(url) ; 2 个字段判断
|
7
operafans 2017-07-13 10:44:08 +08:00
网站主域名 ➡️ 网站 ID,int 自增类型
网站具体页面地址 ➡️ 生成 hash 这样在不减少你的索引效率的前提下,能确保 hash 不撞 |
8
snail1988 2017-07-13 10:53:57 +08:00
MD5 现在确实不安全了,不过除非有人恶意构造,否则用来生成唯一标识,还是很够用的,楼主几千万数据太少了没有担心的必要
不喜欢可以用 SHA256 不存在永不碰撞的摘要,输出是有限的(长度一致),但是输入是无限的,这不存在 |
9
Mutoo 2017-07-13 11:00:21 +08:00
还没碰撞你的数据库估计先受不了了。千万级收录还做每次入库查询,Orz.
|
10
iyaozhen 2017-07-13 11:07:57 +08:00 via Android 1
没事,这概率,你想想碰撞了又没啥事,丢一条数据呗
|
11
grayon 2017-07-13 11:28:56 +08:00 1
索引不就是用的 hash 吗,hash 相同再比较原字符串
|
12
wdhwg001 2017-07-13 11:49:16 +08:00 via iPhone
我很好奇,什么 url 能超过 65535 字节…
|
13
bombless 2017-07-13 11:51:50 +08:00
让 MySQL 去确保唯一性就好了,233
|
15
oott123 2017-07-13 12:10:55 +08:00 2
不碰撞是不可能的,不过你可以建一个表,两列:
其中一列是完整的 url,text 类型,不用索引; 另一列是 url 的 hash,int 类型,就 CRC32(url) 或者其它的 hash 方法,不用管碰撞概率如何; 然后给 hash 列建非唯一的 index 索引 然后查的时候 where hash = crc32(url) and url = url 另外存 md5 这种东西,当成数字(二进制)存比十六进制字符串要好。 |
16
gdsing 2017-07-13 12:18:43 +08:00
接上面的说不碰撞是不可能的,个人的建议是同时采用 md5 和 sha1 存两个 hash 进行判断。这样都能碰撞上直接去买彩票好了。
|
18
imn1 2017-07-13 13:02:16 +08:00
其实任一种 hash+字节数就足够
|
19
woshixiaohao1982 2017-07-13 13:16:29 +08:00 via iPhone
hash 相同再判字符串不就好了 23333
|
20
undeflife 2017-07-13 13:24:40 +08:00
你存 url 的 md5 以后需要这个 url 的时候怎么弄?
|
21
zacard 2017-07-13 17:28:47 +08:00 1
1.理论上不存在不碰撞的 hash 算法
2.布隆过滤 |