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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2690 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

url

MySQL

定长

md5

21 条回复 • 2017-07-13 17:28:47 +08:00

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

Morriaty

2017-07-13 10:35:51 +08:00

不存在不碰撞的 hash。

判重上 redis

bukip

2017-07-13 10:35:51 +08:00

md5 碰撞几率是 1/2^256，千万级差的太远了。

Reign

2017-07-13 10:36:31 +08:00

@bukip 那你的意思是我可以用 md5 来存 url 咯？？

rrfeng

2017-07-13 10:38:57 +08:00 via Android

sha256 强度更高一些。
要再高可以多几个 hash 一起存。

不过 md5 足够足够的了...

batnss

2017-07-13 10:41:19 +08:00

目标网站 id + md5(url) ; 2 个字段判断

operafans

2017-07-13 10:44:08 +08:00

网站主域名 ➡️ 网站 ID，int 自增类型
网站具体页面地址 ➡️ 生成 hash
这样在不减少你的索引效率的前提下，能确保 hash 不撞

snail1988

2017-07-13 10:53:57 +08:00

MD5 现在确实不安全了，不过除非有人恶意构造，否则用来生成唯一标识，还是很够用的，楼主几千万数据太少了没有担心的必要
不喜欢可以用 SHA256

不存在永不碰撞的摘要，输出是有限的(长度一致)，但是输入是无限的，这不存在

Mutoo

2017-07-13 11:00:21 +08:00

还没碰撞你的数据库估计先受不了了。千万级收录还做每次入库查询，Orz.

iyaozhen

2017-07-13 11:07:57 +08:00 via Android

没事，这概率，你想想碰撞了又没啥事，丢一条数据呗

grayon

2017-07-13 11:28:56 +08:00

索引不就是用的 hash 吗，hash 相同再比较原字符串

wdhwg001

2017-07-13 11:49:16 +08:00 via iPhone

我很好奇，什么 url 能超过 65535 字节…

bombless

2017-07-13 11:51:50 +08:00

让 MySQL 去确保唯一性就好了，233

ls2110609

2017-07-13 11:53:05 +08:00

@Mutoo 优秀!

oott123

2017-07-13 12:10:55 +08:00

不碰撞是不可能的，不过你可以建一个表，两列：
其中一列是完整的 url，text 类型，不用索引；
另一列是 url 的 hash，int 类型，就 CRC32(url) 或者其它的 hash 方法，不用管碰撞概率如何；
然后给 hash 列建非唯一的 index 索引
然后查的时候 where hash = crc32(url) and url = url

另外存 md5 这种东西，当成数字（二进制）存比十六进制字符串要好。