V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
watanuki
V2EX  ›  Node.js

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

  •  
  •   watanuki · 2020-06-15 12:38:24 +08:00 · 3848 次点击
    这是一个创建于 1621 天前的主题,其中的信息可能已经有所发展或是发生改变。
    我的需求:
    将一些 (5000 个以内) 较短 (长度 20 以内) 的字符串映射成整数,转换后的整数将用作数据库中的 id.

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

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

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

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

    因为数据量不大,再放一个反查,同塞一个 js 里面
    {
    "abc":1
    "def":2
    }
    Mistwave
        12
    Mistwave  
       2020-06-15 22:14:43 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4527 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 05:36 · PVG 13:36 · LAX 21:36 · JFK 00:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.