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

字符串映射成数字,有什么好的算法嘛

  •  
  •   leebs · 153 天前 · 2661 次点击
    这是一个创建于 153 天前的主题,其中的信息可能已经有所发展或是发生改变。

    用 bitmap 存储数据,需要对数据做 offset 映射,有什么好的算法嘛。

    21 条回复    2022-03-09 15:30:54 +08:00
    kilasuelika
        1
    kilasuelika  
       153 天前 via Android   ❤️ 1
    啥叫 offset 映射
    liprais
        2
    liprais  
       153 天前
    murmurhash3
    CEBBCAT
        3
    CEBBCAT  
       153 天前 via iPhone
    你……是要做布隆过滤器吗?
    murmur
        4
    murmur  
       152 天前
    offset 映射是啥意思,记住用户看书看到的地方?
    dangyuluo
        5
    dangyuluo  
       152 天前
    leebs
        6
    leebs  
    OP
       152 天前
    @kilasuelika offset 是偏移量,bitmap 里面的概念,相当于数组下标。
    leebs
        7
    leebs  
    OP
       152 天前
    @dangyuluo 任意字符串,不是数字字符串,需要编码成数字。
    dangyuluo
        8
    dangyuluo  
       152 天前
    那就 md5 然后取前 64bit 做 uint64_t?
    gwbw
        9
    gwbw  
       152 天前
    参考 base64 的算法,映射成 base10 ,用 0~9 表示,这种么;要求纯数字的话可能要 base9 ,留一个数字专门补位
    Yi23
        10
    Yi23  
       152 天前
    如果单纯的字符串转数字的话,是否可以考虑 36 进制( 26 个英文+10 个数字)转换?但这样子可能会导致转出来的数字会非常大
    hu8245
        11
    hu8245  
       152 天前 via Android
    面腾讯就问的这个,蹲一个方案💬
    X0ray
        12
    X0ray  
       152 天前
    这?直接 hash 不行吗
    also24
        13
    also24  
       152 天前   ❤️ 1
    直觉上是一个 X-Y Problem

    如果是构建布隆过滤器的话,那二进制数据无需转换,直接就能塞进 bitmap ,不需要特殊处理。


    如果是想用 bitmap 的下标来表示一个数据的话,那除非特定场景,效率是极低的,基本不存在实际的可行性,用下来还不如直接 hashmap 好用。
    labulaka521
        14
    labulaka521  
       152 天前 via iPhone   ❤️ 1
    @also24 我也觉得是
    前提: https://v2ex.com/t/838798#reply14
    zhongchaowade
        15
    zhongchaowade  
       152 天前
    所以需要同时支持正负数,8 ,10 ,16 进制吗?
    lniwn
        16
    lniwn  
       152 天前 via iPhone
    难道在说 ascii 码?
    EminemW
        17
    EminemW  
       152 天前
    hash 然后 mod ?
    WhereverYouGo
        18
    WhereverYouGo  
       152 天前
    md5? sha256?
    3dwelcome
        19
    3dwelcome  
       152 天前
    有个叫 perfect hash 的算法,可以满足楼主的需求。

    举个例子,有 10 万个字符串需要查重,那么在 redis 里创建一个大小为 10 万的 bitmap 数据结构,用 0 和 1 来表示,当前字符串是否已被占用。

    先对 10 万个字符串做预处理,便可以得到一个不冲突,又刚好完美 1:1 匹配进 bitmap ,自定义 hash 映射表。
    littlewing
        20
    littlewing  
       152 天前
    楼上说 hash 的,冲突怎么解决?
    3dwelcome
        21
    3dwelcome  
       152 天前
    @littlewing “楼上说 hash 的,冲突怎么解决?”

    完美 hash 没冲突。否则就不叫完美了。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1163 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 21ms · UTC 20:30 · PVG 04:30 · LAX 13:30 · JFK 16:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.