这是一个创建于 1605 天前的主题，其中的信息可能已经有所发展或是发生改变。
用来标记一个字符串, 可以忍受一定的碰撞概率
第 1 条附言 · 2020-06-30 19:21:09 +08:00
有两部分数据（字符串形式）
一部分自身带有唯一的 id
一部分纯数据
现在想要把这两部分数据整合到同一张表中
我考虑设置一个 基数 比如 1000000000000000000 、5000000000000000000
第一部分 id 直接用 1000000000000000000 + 自身 id 生成
第二部分字符串需要生成一个 id， 最后生成的主键是 5000000000000000000 + hash(xxx)
一部分自身带有唯一的 id
一部分纯数据
现在想要把这两部分数据整合到同一张表中
我考虑设置一个 基数 比如 1000000000000000000 、5000000000000000000
第一部分 id 直接用 1000000000000000000 + 自身 id 生成
第二部分字符串需要生成一个 id， 最后生成的主键是 5000000000000000000 + hash(xxx)
第 2 条附言 · 2020-06-30 19:58:16 +08:00
第 3 条附言 · 2020-06-30 20:00:38 +08:00
 |
1
ThirdFlame 2020-06-30 18:38:31 +08:00  1
哈希值 截取部分 转回 long ？
|
 |
2
ipwx 2020-06-30 18:43:41 +08:00 2
ret: unsigned long long = 0
for c in s: ret = ret * 131 + (uint8)c; |
|
3
ipwx 2020-06-30 18:44:37 +08:00
这是当年我刷算法题，对付 char 字符串的手写哈希算法常用的方式。虽然不一定是最好的，但是胜在写起来快。如果是 unicode 你可以网上找找，131 替换成什么。（提示：一定要是素数）
|
 |
4
yanshenxian OP @ThirdFlame 这个想法不错.. 截 15 位 这个概率应该挺低的
|
|
5
ipwx 2020-06-30 18:46:41 +08:00
@yanshenxian 这个想法一点都不好。。。。 前 15 位相同的字符串算出来的哈希值一模一样。。。。
|
|
6
yanshenxian OP @ipwx 这个碰撞概率怎么看? 是不是只要不溢出就不会碰撞 😂
|
|
7
yanshenxian OP @ipwx 这个应该可以先用 md5 哈希下, 然后截取 8-23 位的转成 long
|
|
8
ipwx 2020-06-30 18:47:59 +08:00 1
@yanshenxian 溢出也没关系的。。。你乘以 256 溢出就消失了，但是乘以一个素数（比如 131 这个数字是传统，从 NOI 银牌选手那里继承来的习惯）信息是不会完全消失的。
|
|
9
ipwx 2020-06-30 18:48:13 +08:00
@yanshenxian MD5 当然可以，但是更慢。
|
 |
10
qwerthhusn 2020-06-30 18:53:13 +08:00 1
MURMUR3
|
|
11
yanshenxian OP @qwerthhusn 这个如果生成 64 位以及以上的话，很容易得到一个负值. 不太好用作数据库主键
|
 |
12
zjyl1994 2020-06-30 19:03:55 +08:00 via Android 1
fnv1a ？这个是一个很成熟的字符串哈希算法，我记得输出是 32bit 的整数，好像也有 64bit 的变体
|
 |
13
CEBBCAT 2020-06-30 19:06:20 +08:00 via Android
问题发出 24 分钟后，楼主在第 11 个回复中指出是想用作数据库主键
--- 根据 XY 问题，反正我个人建议楼主开门见山地托出自己遇到的业务问题 |
 |
14
chendy 2020-06-30 19:15:52 +08:00
原来楼主是要做数据库主键？
和内容相关的主键不合适吧 |
 |
15
p2pCoder 2020-06-30 19:15:58 +08:00
64 位 一般都很难碰撞
机器学习 深度学习里面用的最多是 mumurhash3 存过线性模型，32 位，三千万的模型碰撞位七八万 64 位，75 亿的模型，碰撞为 0 |
|
16
yanshenxian OP @CEBBCAT append 了
|
|
17
yanshenxian OP @chendy 主要是想用 insert ignore 直接插入，不想先需要判断是否存在，再得到主键
|
|
18
yanshenxian OP @p2pCoder 嗯 64 位确实好。。
|
 |
19
msg7086 2020-06-30 19:35:08 +08:00
主键与业务无关。整个问题的大前提就错了……
|
 |
20
exch4nge 2020-06-30 19:38:38 +08:00
BLAKE2 算法，支持生成长度 1 ～ 64 字节的结果
|
|
21
yanshenxian OP @msg7086 是有这个顾虑，之所以这么做还是考虑实现的简易程度，而且这些数据都是一次写入，读>>>写, 感觉也还行
|
|
22
msg7086 2020-06-30 19:45:38 +08:00
|
 |
23
allenhu 2020-06-30 20:12:55 +08:00 via Android 1
你就是要把字符串变成整数吧，试试 crc32 ？
|
 |
24
liuhan907 2020-06-30 23:34:42 +08:00 via Android
|
|
25
liuhan907 2020-06-30 23:35:56 +08:00 via Android 1
手机点快了，直接发出去了…试试 murmur3，自定义 seed，应该刚好解决
|
 |
26
QingchuanZhang 2020-06-30 23:46:08 +08:00 1
@ipwx 溢出取模是 114514 年前就退出历史舞台的做法，无论你的 base 是什么 https://codeforces.com/blog/entry/60442
|
 |
27
ysc3839 2020-07-01 00:46:51 +08:00
fnv hash?
|
 |
28
xupefei 2020-07-01 01:21:27 +08:00 via iPhone 1
邪道玩法：aes256 加密后取若干位（前若干位和中间若干位均可）转成 long 。
这种邪道玩法的随机性有论文证明过，懒得找了。 |
|
29
ipwx 2020-07-01 09:35:51 +08:00
@QingchuanZhang 嘛嘛，毕竟 OI 要扣时间常量的。一般 OI 的题目不会去针对 hash 函数做针对性的攻击，所以 * 31, *131 这种简单而且只是“可以构造出攻击的例子”的方法在刷题的时候很好用，毕竟简单的 hash 函数快嘛。所以这就看楼主了，如果楼主的场景不需要那么强的防御攻击性，而且被哈希的字符串真的很随机（比如是序列化以后的神经网络参数），我觉得快一点更重要。
|
|
30
QingchuanZhang 2020-07-01 12:26:33 +08:00 via Android
@ipwx 现在良心出题人默认卡自然溢出 hash 了，不卡说明不太负责
|
|
31
QingchuanZhang 2020-07-01 12:27:41 +08:00 via Android
@ipwx 再说一次“与底数无关，只要是溢出取模，任意底数都可被同一组数据 hack”
|
 |
32
qwertyegg 2020-07-01 13:28:30 +08:00 1
|
 |
33
lovewell 2020-11-19 18:12:33 +08:00
标记,如果你是 java 的，使用 guava 吧。。
https://guava.dev/releases/29.0-jre/api/docs/com/google/common/hash/Hashing.html |
Select Language