请教一下,我该选择哪一种 hash 算法?

2020-06-15 12:38:24 +08:00
 watanuki
我的需求:
将一些 (5000 个以内) 较短 (长度 20 以内) 的字符串映射成整数,转换后的整数将用作数据库中的 id.

我这个数据量应该算小的吧,显然用 md5 太浪费了,但是 hash 算法有好多种,我不知道按照我的需求该选择哪种算法?
要是 npm 上有现成的库就更好了。
3877 次点击
所在节点    Node.js
12 条回复
imn1
2020-06-15 13:05:21 +08:00
CRC32 啰,而且本身就是整数,短一些
binux
2020-06-15 13:14:07 +08:00
md5 截短呗,反正除非你特别设计,该碰撞还是要碰撞的,用什么都差不多。
takemeaway
2020-06-15 13:42:44 +08:00
这么简单的,直接手写个算法就行了。
LennieChoi
2020-06-15 15:01:48 +08:00
不就是要生成个唯一 id,用作表的索引么,直接附上去一个 uuid
Mithril
2020-06-15 15:05:16 +08:00
随便找个算法就行,反正该冲突就还是要冲突。
怕冲突就查重然后 UUID
flyingghost
2020-06-15 15:22:30 +08:00
既然用作 id,那肯定不希望冲突。
如果源字符串集固定,不会有新的不确定的字符串加入,那么完美哈希可能是你想要的东西。

如果源字符串集不固定,可以考虑某种可逆的映射,比如各种编码算法 /加密算法。

如果只是为了查找,数据库里 5000 条记录有索引的情况下怎么查差别都不会太大。。。说不定大头在请求吧。
realpg
2020-06-15 17:58:07 +08:00
5000……自制映射表吧……
id 自增 id,str
insert into hashes str values ('xxxx');
然后需要数字时候去 select 一下
liberty1900
2020-06-15 20:17:16 +08:00
我记着当初上学老师为了说明哈希的概念用的是一种质数算法,然后笑了起来说,大概这就是计算机科学吧
ztcaoll222
2020-06-15 21:50:22 +08:00
qwerthhusn
2020-06-15 22:05:24 +08:00
https://www.npmjs.com/package/murmur3hash-wasm
考虑一下 MURMUR3,这玩意比 MD,SHA 系列要快的多,但是相比 CRC32 这种碰撞率要低得多

npm 有现成的实现,有 wasm 的也有 pure-js 的
xiangyuecn
2020-06-15 22:07:07 +08:00
查表, 数据量不大,完全放一个 js 里面也放得下:
{
1:"abc"
2:"def"
}

因为数据量不大,再放一个反查,同塞一个 js 里面
{
"abc":1
"def":2
}
Mistwave
2020-06-15 22:14:43 +08:00

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/681655

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX