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

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

  •  1
     
  •   yanshenxian · 2020-06-30 18:35:45 +08:00 · 3068 次点击
    这是一个创建于 1367 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    第 1 条附言  ·  2020-06-30 19:21:09 +08:00
    有两部分数据(字符串形式)
    一部分自身带有唯一的 id
    一部分纯数据
    现在想要把这两部分数据整合到同一张表中
    我考虑设置一个 基数 比如 1000000000000000000 、5000000000000000000
    第一部分 id 直接用 1000000000000000000 + 自身 id 生成
    第二部分字符串需要生成一个 id, 最后生成的主键是 5000000000000000000 + hash(xxx)
    第 2 条附言  ·  2020-06-30 19:58:16 +08:00
    被限制回复了,在这里 append 一下
    @msg7086 Reply#22 数据不是一次性拿到,所以没法顺序写入
    需要数据的唯一 id 来关联其他地方,如果直接固定主键的话可以省去一些步骤
    第 3 条附言  ·  2020-06-30 20:00:38 +08:00
    @livid 这是为何
    33 条回复    2020-11-19 18:12:33 +08:00
    ThirdFlame
        1
    ThirdFlame  
       2020-06-30 18:38:31 +08:00   ❤️ 1
    哈希值 截取部分 转回 long ?
    ipwx
        2
    ipwx  
       2020-06-30 18:43:41 +08:00   ❤️ 1
    ret: unsigned long long = 0
    for c in s:
    ret = ret * 131 + (uint8)c;
    ipwx
        3
    ipwx  
       2020-06-30 18:44:37 +08:00
    这是当年我刷算法题,对付 char 字符串的手写哈希算法常用的方式。虽然不一定是最好的,但是胜在写起来快。如果是 unicode 你可以网上找找,131 替换成什么。(提示:一定要是素数)
    yanshenxian
        4
    yanshenxian  
    OP
       2020-06-30 18:45:09 +08:00
    @ThirdFlame 这个想法不错.. 截 15 位 这个概率应该挺低的
    ipwx
        5
    ipwx  
       2020-06-30 18:46:41 +08:00
    @yanshenxian 这个想法一点都不好。。。。 前 15 位相同的字符串算出来的哈希值一模一样。。。。
    yanshenxian
        6
    yanshenxian  
    OP
       2020-06-30 18:46:41 +08:00
    @ipwx 这个碰撞概率怎么看? 是不是只要不溢出就不会碰撞 😂
    yanshenxian
        7
    yanshenxian  
    OP
       2020-06-30 18:47:52 +08:00
    @ipwx 这个应该可以先用 md5 哈希下, 然后截取 8-23 位的转成 long
    ipwx
        8
    ipwx  
       2020-06-30 18:47:59 +08:00   ❤️ 1
    @yanshenxian 溢出也没关系的。。。你乘以 256 溢出就消失了,但是乘以一个素数(比如 131 这个数字是传统,从 NOI 银牌选手那里继承来的习惯)信息是不会完全消失的。
    ipwx
        9
    ipwx  
       2020-06-30 18:48:13 +08:00
    @yanshenxian MD5 当然可以,但是更慢。
    qwerthhusn
        10
    qwerthhusn  
       2020-06-30 18:53:13 +08:00   ❤️ 1
    MURMUR3
    yanshenxian
        11
    yanshenxian  
    OP
       2020-06-30 18:59:54 +08:00
    @qwerthhusn 这个如果生成 64 位以及以上的话,很容易得到一个负值. 不太好用作数据库主键
    zjyl1994
        12
    zjyl1994  
       2020-06-30 19:03:55 +08:00 via Android   ❤️ 1
    fnv1a ?这个是一个很成熟的字符串哈希算法,我记得输出是 32bit 的整数,好像也有 64bit 的变体
    CEBBCAT
        13
    CEBBCAT  
       2020-06-30 19:06:20 +08:00 via Android
    问题发出 24 分钟后,楼主在第 11 个回复中指出是想用作数据库主键
    ---
    根据 XY 问题,反正我个人建议楼主开门见山地托出自己遇到的业务问题
    chendy
        14
    chendy  
       2020-06-30 19:15:52 +08:00
    原来楼主是要做数据库主键?
    和内容相关的主键不合适吧
    p2pCoder
        15
    p2pCoder  
       2020-06-30 19:15:58 +08:00
    64 位 一般都很难碰撞
    机器学习 深度学习里面用的最多是 mumurhash3
    存过线性模型,32 位,三千万的模型碰撞位七八万
    64 位,75 亿的模型,碰撞为 0
    yanshenxian
        16
    yanshenxian  
    OP
       2020-06-30 19:21:26 +08:00
    @CEBBCAT append 了
    yanshenxian
        17
    yanshenxian  
    OP
       2020-06-30 19:23:21 +08:00
    @chendy 主要是想用 insert ignore 直接插入,不想先需要判断是否存在,再得到主键
    yanshenxian
        18
    yanshenxian  
    OP
       2020-06-30 19:24:11 +08:00
    @p2pCoder 嗯 64 位确实好。。
    msg7086
        19
    msg7086  
       2020-06-30 19:35:08 +08:00
    主键与业务无关。整个问题的大前提就错了……
    exch4nge
        20
    exch4nge  
       2020-06-30 19:38:38 +08:00
    BLAKE2 算法,支持生成长度 1 ~ 64 字节的结果
    yanshenxian
        21
    yanshenxian  
    OP
       2020-06-30 19:40:31 +08:00
    @msg7086 是有这个顾虑,之所以这么做还是考虑实现的简易程度,而且这些数据都是一次写入,读>>>写, 感觉也还行
    msg7086
        22
    msg7086  
       2020-06-30 19:45:38 +08:00
    @yanshenxian 我想问的是为什么不直接按顺序写入表中呢?一定要 hash 成特殊的主键是有什么用途么?

    (话说这个帖子实在是太 XY 问题了……
    allenhu
        23
    allenhu  
       2020-06-30 20:12:55 +08:00 via Android   ❤️ 1
    你就是要把字符串变成整数吧,试试 crc32 ?
    liuhan907
        24
    liuhan907  
       2020-06-30 23:34:42 +08:00 via Android
    liuhan907
        25
    liuhan907  
       2020-06-30 23:35:56 +08:00 via Android   ❤️ 1
    手机点快了,直接发出去了…试试 murmur3,自定义 seed,应该刚好解决
    QingchuanZhang
        26
    QingchuanZhang  
       2020-06-30 23:46:08 +08:00   ❤️ 1
    @ipwx 溢出取模是 114514 年前就退出历史舞台的做法,无论你的 base 是什么 https://codeforces.com/blog/entry/60442
    ysc3839
        27
    ysc3839  
       2020-07-01 00:46:51 +08:00
    fnv hash?
    xupefei
        28
    xupefei  
       2020-07-01 01:21:27 +08:00 via iPhone   ❤️ 1
    邪道玩法:aes256 加密后取若干位(前若干位和中间若干位均可)转成 long 。
    这种邪道玩法的随机性有论文证明过,懒得找了。
    ipwx
        29
    ipwx  
       2020-07-01 09:35:51 +08:00
    @QingchuanZhang 嘛嘛,毕竟 OI 要扣时间常量的。一般 OI 的题目不会去针对 hash 函数做针对性的攻击,所以 * 31, *131 这种简单而且只是“可以构造出攻击的例子”的方法在刷题的时候很好用,毕竟简单的 hash 函数快嘛。所以这就看楼主了,如果楼主的场景不需要那么强的防御攻击性,而且被哈希的字符串真的很随机(比如是序列化以后的神经网络参数),我觉得快一点更重要。
    QingchuanZhang
        30
    QingchuanZhang  
       2020-07-01 12:26:33 +08:00 via Android
    @ipwx 现在良心出题人默认卡自然溢出 hash 了,不卡说明不太负责
    QingchuanZhang
        31
    QingchuanZhang  
       2020-07-01 12:27:41 +08:00 via Android
    @ipwx 再说一次“与底数无关,只要是溢出取模,任意底数都可被同一组数据 hack”
    qwertyegg
        32
    qwertyegg  
       2020-07-01 13:28:30 +08:00   ❤️ 1
    lovewell
        33
    lovewell  
       2020-11-19 18:12:33 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1035 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 22:37 · PVG 06:37 · LAX 15:37 · JFK 18:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.