V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
LeeReamond
V2EX  ›  问与答

为用户生成唯一标识有什么比较简短的哈希算法吗?

  •  
  •   LeeReamond · 2022-03-05 19:29:24 +08:00 · 2808 次点击
    这是一个创建于 771 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如题,业务要求需要标记用户,目前对于未登录用户是使用 IP 和浏览器信息对用户进行唯一标识(然后再 hash 一下,变成统一长度),发现一个问题是储存比较占用空间,目前用最短的 sha1 来做,单个用户也需要 40 个字节才能储存的下来,十万个用户这种数量级的话占用内存感觉有点大了。有什么合适一些的更简短的哈希吗?比如 10 个字节或者 20 个字节就能表示的,最好使用广泛一些的,不用自己实现,我这个需求是不太在意碰撞。

    谢谢大家。

    第 1 条附言  ·  2022-03-06 01:23:53 +08:00
    贴个条,最后用 google 的 cityhash64 了,足够短,容量和碰撞都满足需求,且使用较广泛,可以别人的代码开箱即用,谢谢大家。
    27 条回复    2022-03-06 18:41:17 +08:00
    misdake
        1
    misdake  
       2022-03-05 19:33:15 +08:00
    那就只用 sha1 前 20 个字节?
    popok
        2
    popok  
       2022-03-05 19:41:09 +08:00
    就 10 万规模而已,需要考虑内存占用了吗?
    那你参考一楼的说法,想取几位取几位呗。
    LeeReamond
        3
    LeeReamond  
    OP
       2022-03-05 19:49:09 +08:00
    @misdake 我不太了解哈希算法,所以来问问万能的 v 友有没有合适的,单纯截取前 20 字节的话好像,我印象里 sha1 是有通道啥的,似乎单纯截取会导致有些通道被完全弃用,感觉不太优雅所以没这么干。

    @popok 也许以后更多也说不定,其实主要是想折腾一下搞个合理一点的。。
    ruixue
        4
    ruixue  
       2022-03-05 19:53:08 +08:00
    Zy143L
        5
    Zy143L  
       2022-03-05 19:57:30 +08:00 via Android
    Sha 中间取 16 位或者 8 位
    westoy
        6
    westoy  
       2022-03-05 20:07:05 +08:00
    第一、sha1 是 byte 20 啊, 你没必要存 hex 40 啊

    第二、IP+UA 这个很明显不科学啊。 学校、网吧、普通企业都一样了, 小区宽带走 VLAN+国产浏览器重合率也蛮高的.......
    xiaopc
        7
    xiaopc  
       2022-03-05 20:13:56 +08:00
    @westoy 浏览器信息不止 UA ,参考下 fingerprintjs
    3dwelcome
        8
    3dwelcome  
       2022-03-05 20:13:59 +08:00
    @westoy SHA1 是 20 个字节,我还以为自己记错了,又想了一下,应该没错。

    我们对于未登录用户的识别,是先服务器请求生成一个 UUID ,然后存在浏览器本地。
    victor
        9
    victor  
       2022-03-05 20:55:23 +08:00
    SHA1 算法得出的 SHA1 值长度为 20 个 Byte 。10 万个用户就是 200 万 Byte 。1MB = 1048576 Byte ,约 100 万 Byte 。也就是说 10 万个用户,占用了 2 MB 内存。

    兄弟们我哪算错了吗?
    mousewolf
        10
    mousewolf  
       2022-03-05 21:14:48 +08:00   ❤️ 1
    snowflake id
    LeeReamond
        11
    LeeReamond  
    OP
       2022-03-05 22:05:38 +08:00
    @westoy 确实有这个问题,不过还能怎么区分唯一用户呢?登录以后当然是有身份区分了,未登录的难道用网卡区分,但是网卡不在 http 信息里
    3dwelcome
        12
    3dwelcome  
       2022-03-05 22:13:25 +08:00   ❤️ 2
    @xiaopc "浏览器信息不止 UA ,参考下 fingerprintjs"

    我前一阵发过一个关于浏览器指纹的帖子。( https://browserleaks.com/canvas

    测试的时候,用防指纹浏览器,每次都能给出不同的随机结果。

    如果用于未登录用户识别,只会把用户数据源给污染,还不如不用。
    CEBBCAT
        13
    CEBBCAT  
       2022-03-05 22:15:36 +08:00
    见过一种做法,给游客也注册一个账号,只不过这种账号限制了权限,前台也看不到登录状态
    LeeReamond
        14
    LeeReamond  
    OP
       2022-03-05 22:27:21 +08:00
    @CEBBCAT 感觉没啥意义,模拟存在账号的话,因为真实账号使用本质上还是依赖类似于 cookie 记录这些类似服务。


    @3dwelcome 非常有趣,学习了,但是感觉区分度一般,我自己试了一下区分度是 280 个人里就有一个跟我一样的。所以使用这个 hash 加上 IP 可能是一个不错的方法。不过这个需要运行 js 才行,我想在后端获得请求的时候就区分用户。。
    LeeReamond
        15
    LeeReamond  
    OP
       2022-03-05 22:59:08 +08:00
    @3dwelcome 我在那个网站的获取结果是

    Your Fingerprint
    Signature ✔9D5F1ADC
    Uniqueness 99.64% (3035 of 850373 user agents have the same signature)
    Image File Details
    PNG Hash 193F91E186C48FF3317CBDAC67C612CC

    倒是他这个 9D5F1ADC 的短 hash 非常符合我的需求
    Inn0Vat10n
        16
    Inn0Vat10n  
       2022-03-05 23:51:12 +08:00
    10 万*40Byte 不算大,真到大的受不了的规模也不会全放内存里
    3dwelcome
        17
    3dwelcome  
       2022-03-06 00:05:50 +08:00
    @LeeReamond "倒是他这个 9D5F1ADC 的短 hash 非常符合我的需求"

    看网站下面的说明,好像就是 MD5 截断。

    以前我做过一点 hash 的每单位 bit 随机概率测试,有些算法产生的每个 bit 概率不一样,没那么散列。把 MD5 截断后,用 birthday 算法测试冲撞率,基本上没太多变化。

    为了缩短空间,该砍就砍吧,这些经典算法设计的都挺好。
    JamesR
        18
    JamesR  
       2022-03-06 00:19:34 +08:00
    雪花算法( Snowflake )是一种生成分布式全局唯一 ID 的算法,生成的 ID 称为 Snowflake IDs 或 snowflakes 。这种算法由 Twitter 创建,并用于推文的 ID 。
    我项目用过,还行,实现简单,也比 UUID 短多了。
    2NUT
        19
    2NUT  
       2022-03-06 00:26:10 +08:00
    @LeeReamond #15 太扯了,我的

    Your Fingerprint
    Signature ✔9D5F1ADC
    Uniqueness 99.64% (3035 of 850373 user agents have the same signature)
    JamesR
        20
    JamesR  
       2022-03-06 00:26:29 +08:00
    要么就 Canvas 指纹吧,也用过,还行。
    LeeReamond
        21
    LeeReamond  
    OP
       2022-03-06 01:22:38 +08:00
    @2NUT 很正常,差不多时间装的差不多的系统,软件环境相似很正常,我找了几个朋友试了试,4 个朋友其中一个跟我结果相同,区分度还是有的
    lysS
        22
    lysS  
       2022-03-06 04:12:51 +08:00
    10 万个 sha1 才 4MB 。。。。
    zachlhb
        23
    zachlhb  
       2022-03-06 12:14:37 +08:00 via iPhone
    短 uuid 比较合适
    sampeng
        24
    sampeng  
       2022-03-06 13:51:54 +08:00
    问题来了。。。现在 web 应用很少很少把数据全部放内存里,通常都是数据库一把梭
    2NUT
        25
    2NUT  
       2022-03-06 15:33:23 +08:00
    @LeeReamond #21 不正常, 因为数量统计都没有增加
    3035 of 850373 user
    Thiece
        26
    Thiece  
       2022-03-06 17:31:13 +08:00
    @LeeReamond
    其实用 SHAKE128 或者 SHAKE256 就好
    documentzhangx66
        27
    documentzhangx66  
       2022-03-06 18:41:17 +08:00
    我就好奇,10 万用户,为啥要 hash ?直接 int 32 自增主键 ID 作为唯一标志,不就完事了,最大能给 21 亿个用户进行唯一标志。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2967 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 14:32 · PVG 22:32 · LAX 07:32 · JFK 10:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.