V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Reign
V2EX  ›  程序员

有没有一种将长字符串压缩成定长且不碰撞重复的 hash id 算法?

  •  
  •   Reign · 2017-07-13 10:28:48 +08:00 · 6232 次点击
    这是一个创建于 2672 天前的主题,其中的信息可能已经有所发展或是发生改变。

    目前写爬虫,网址入库过程中,需要判断新存入的 URL 在原 MySQL 中是否存在,有的 url 很长,只能将 URL 作为 text 类型字段存储在 MySQL 中,但貌似 text 类型字段检索唯一性效率很不高,想把 URL 压缩成 md5 再以定长 char 字段存储在 mysql 中,但是在千万级的 URL 条目下 md5 碰撞几率高么?个人没这方面经验,求好心 V 友推荐个算法

    21 条回复    2017-07-13 17:28:47 +08:00
    Mutoo
        1
    Mutoo  
       2017-07-13 10:32:36 +08:00
    Morriaty
        2
    Morriaty  
       2017-07-13 10:35:51 +08:00
    不存在不碰撞的 hash。

    判重上 redis
    bukip
        3
    bukip  
       2017-07-13 10:35:51 +08:00
    md5 碰撞几率是 1/2^256,千万级差的太远了。
    Reign
        4
    Reign  
    OP
       2017-07-13 10:36:31 +08:00
    @bukip 那你的意思是我可以用 md5 来存 url 咯??
    rrfeng
        5
    rrfeng  
       2017-07-13 10:38:57 +08:00 via Android
    sha256 强度更高一些。
    要再高可以多几个 hash 一起存。

    不过 md5 足够足够的了...
    batnss
        6
    batnss  
       2017-07-13 10:41:19 +08:00
    目标网站 id + md5(url) ; 2 个字段判断
    operafans
        7
    operafans  
       2017-07-13 10:44:08 +08:00
    网站主域名 ➡️ 网站 ID,int 自增类型
    网站具体页面地址 ➡️ 生成 hash
    这样在不减少你的索引效率的前提下,能确保 hash 不撞
    snail1988
        8
    snail1988  
       2017-07-13 10:53:57 +08:00
    MD5 现在确实不安全了,不过除非有人恶意构造,否则用来生成唯一标识,还是很够用的,楼主几千万数据太少了没有担心的必要
    不喜欢可以用 SHA256

    不存在永不碰撞的摘要,输出是有限的(长度一致),但是输入是无限的,这不存在
    Mutoo
        9
    Mutoo  
       2017-07-13 11:00:21 +08:00
    还没碰撞你的数据库估计先受不了了。千万级收录还做每次入库查询,Orz.
    iyaozhen
        10
    iyaozhen  
       2017-07-13 11:07:57 +08:00 via Android   ❤️ 1
    没事,这概率,你想想碰撞了又没啥事,丢一条数据呗
    grayon
        11
    grayon  
       2017-07-13 11:28:56 +08:00   ❤️ 1
    索引不就是用的 hash 吗,hash 相同再比较原字符串
    wdhwg001
        12
    wdhwg001  
       2017-07-13 11:49:16 +08:00 via iPhone
    我很好奇,什么 url 能超过 65535 字节…
    bombless
        13
    bombless  
       2017-07-13 11:51:50 +08:00
    让 MySQL 去确保唯一性就好了,233
    ls2110609
        14
    ls2110609  
       2017-07-13 11:53:05 +08:00
    @Mutoo 优秀!
    oott123
        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 这种东西,当成数字(二进制)存比十六进制字符串要好。
    gdsing
        16
    gdsing  
       2017-07-13 12:18:43 +08:00
    接上面的说不碰撞是不可能的,个人的建议是同时采用 md5 和 sha1 存两个 hash 进行判断。这样都能碰撞上直接去买彩票好了。
    UnisandK
        17
    UnisandK  
       2017-07-13 12:24:36 +08:00
    @iyaozhen 老铁心态稳。。
    imn1
        18
    imn1  
       2017-07-13 13:02:16 +08:00
    其实任一种 hash+字节数就足够
    woshixiaohao1982
        19
    woshixiaohao1982  
       2017-07-13 13:16:29 +08:00 via iPhone
    hash 相同再判字符串不就好了 23333
    undeflife
        20
    undeflife  
       2017-07-13 13:24:40 +08:00
    你存 url 的 md5 以后需要这个 url 的时候怎么弄?
    zacard
        21
    zacard  
       2017-07-13 17:28:47 +08:00   ❤️ 1
    1.理论上不存在不碰撞的 hash 算法
    2.布隆过滤
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3410 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 04:54 · PVG 12:54 · LAX 20:54 · JFK 23:54
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.