字符串哈希为 Long 型整数算法有推荐的吗

[yanshenxian]

用来标记一个字符串, 可以忍受一定的碰撞概率

有两部分数据（字符串形式）
一部分自身带有唯一的 id
一部分纯数据
现在想要把这两部分数据整合到同一张表中
我考虑设置一个 基数 比如 1000000000000000000 、5000000000000000000
第一部分 id 直接用 1000000000000000000 + 自身 id 生成
第二部分字符串需要生成一个 id， 最后生成的主键是 5000000000000000000 + hash(xxx)

被限制回复了，在这里 append 一下
@msg7086 Reply#22 数据不是一次性拿到，所以没法顺序写入
需要数据的唯一 id 来关联其他地方，如果直接固定主键的话可以省去一些步骤

@livid 这是为何

[ThirdFlame]

哈希值 截取部分 转回 long ？

[ipwx]

ret: unsigned long long = 0
for c in s:
ret = ret * 131 + (uint8)c;

[ipwx]

这是当年我刷算法题，对付 char 字符串的手写哈希算法常用的方式。虽然不一定是最好的，但是胜在写起来快。如果是 unicode 你可以网上找找，131 替换成什么。（提示：一定要是素数）

[yanshenxian]

@ThirdFlame 这个想法不错.. 截 15 位 这个概率应该挺低的

[ipwx]

@yanshenxian 这个想法一点都不好。。。。 前 15 位相同的字符串算出来的哈希值一模一样。。。。

[yanshenxian]

@ipwx 这个碰撞概率怎么看? 是不是只要不溢出就不会碰撞 😂

[yanshenxian]

@ipwx 这个应该可以先用 md5 哈希下, 然后截取 8-23 位的转成 long

[ipwx]

@yanshenxian 溢出也没关系的。。。你乘以 256 溢出就消失了，但是乘以一个素数（比如 131 这个数字是传统，从 NOI 银牌选手那里继承来的习惯）信息是不会完全消失的。

[ipwx]

@yanshenxian MD5 当然可以，但是更慢。

[qwerthhusn]

MURMUR3

[yanshenxian]

@qwerthhusn 这个如果生成 64 位以及以上的话，很容易得到一个负值. 不太好用作数据库主键

[zjyl1994]

fnv1a ？这个是一个很成熟的字符串哈希算法，我记得输出是 32bit 的整数，好像也有 64bit 的变体

[CEBBCAT]

问题发出 24 分钟后，楼主在第 11 个回复中指出是想用作数据库主键
---
根据 XY 问题，反正我个人建议楼主开门见山地托出自己遇到的业务问题

[chendy]

原来楼主是要做数据库主键？
和内容相关的主键不合适吧

[p2pCoder]

64 位 一般都很难碰撞
机器学习 深度学习里面用的最多是 mumurhash3
存过线性模型，32 位，三千万的模型碰撞位七八万
64 位，75 亿的模型，碰撞为 0

[yanshenxian]

@CEBBCAT append 了

[yanshenxian]

@chendy 主要是想用 insert ignore 直接插入，不想先需要判断是否存在，再得到主键

[yanshenxian]

@p2pCoder 嗯 64 位确实好。。

[msg7086]

主键与业务无关。整个问题的大前提就错了……

[exch4nge]

BLAKE2 算法，支持生成长度 1 ～ 64 字节的结果

[yanshenxian]

@msg7086 是有这个顾虑，之所以这么做还是考虑实现的简易程度，而且这些数据都是一次写入，读>>>写, 感觉也还行

[msg7086]

@yanshenxian 我想问的是为什么不直接按顺序写入表中呢？一定要 hash 成特殊的主键是有什么用途么？

（话说这个帖子实在是太 XY 问题了……

[allenhu]

你就是要把字符串变成整数吧，试试 crc32 ？

[liuhan907]

@yanshenxian

[liuhan907]

手机点快了，直接发出去了…试试 murmur3，自定义 seed，应该刚好解决

[QingchuanZhang]

@ipwx 溢出取模是 114514 年前就退出历史舞台的做法，无论你的 base 是什么 https://codeforces.com/blog/entry/60442

[ysc3839]

fnv hash?

[xupefei]

邪道玩法：aes256 加密后取若干位（前若干位和中间若干位均可）转成 long 。
这种邪道玩法的随机性有论文证明过，懒得找了。

[ipwx]

@QingchuanZhang 嘛嘛，毕竟 OI 要扣时间常量的。一般 OI 的题目不会去针对 hash 函数做针对性的攻击，所以 * 31, *131 这种简单而且只是“可以构造出攻击的例子”的方法在刷题的时候很好用，毕竟简单的 hash 函数快嘛。所以这就看楼主了，如果楼主的场景不需要那么强的防御攻击性，而且被哈希的字符串真的很随机（比如是序列化以后的神经网络参数），我觉得快一点更重要。

[QingchuanZhang]

@ipwx 现在良心出题人默认卡自然溢出 hash 了，不卡说明不太负责

[QingchuanZhang]

@ipwx 再说一次“与底数无关，只要是溢出取模，任意底数都可被同一组数据 hack”

[qwertyegg]

https://en.wikipedia.org/wiki/List_of_hash_functions

ctrl + f("64")

[lovewell]

标记,如果你是 java 的，使用 guava 吧。。
https://guava.dev/releases/29.0-jre/api/docs/com/google/common/hash/Hashing.html