首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
1oNflow
V2EX  ›  Java

如何设计一个可以降低哈希冲突可能的哈希函数?

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

    有必要重写 Java 基本类型的 hashcode 吗,比如 String 用到的 31,官方已经优化的很好了吧。

    如果是求对象的哈希,就递归调用成员的 hashcode,再把他们加在一起,还有比这个更好的方案吗?

    10 回复  |  直到 2019-12-04 08:31:32 +08:00
    OhYee
        1
    OhYee   53 天前
    先把对象成员的值转换成字节数组再对整个字节数组做哈希碰撞概率应该会更低一点(但是感觉不太必要)
    真的怕碰撞,可以换成别的哈希函数来实现哈希,比如 SHA3,或者自己魔改下 SHA,把输出长度拓展到更长
    reus
        2
    reus   53 天前
    sha256 够了,还怕就 sha512。

    就,如果你找到了一个冲突,可以出名那种。
    crclz
        3
    crclz   53 天前
    wangyzj
        4
    wangyzj   53 天前
    我看到了一个好大的轮子
    geelaw
        5
    geelaw   53 天前
    @reus #2 Java 的 hash code 是 32 位,但 SHA-256/512 的输出远远长于 32 位

    实际上一个很快速的策略是使用 AES + 固定 key + 截断,因为现代 CPU 有 AES 指令,所以这个可以非常非常快。此外,通常数据如果没有 adversarial behavior,那么 AES hash 的碰撞率比较低。

    把数个成员的 hash 加在一起是一个非常糟糕的方案,比如 class X { int a, b; /* details omitted */ } 那么 (1,0) 和 (0,1) 一定会有相同的 hash。
    xupefei
        6
    xupefei   53 天前 via iPhone
    用多级哈希。现成的实现是 bloom filter。
    zunceng
        7
    zunceng   53 天前
    当年听人吹过暴雪有个 hash 算法 从来没用上过
    Raymon111111
        8
    Raymon111111   53 天前
    楼主的意思是针对任意的槽大小, hash 结果可以均匀分布吧
    hzgit
        9
    hzgit   53 天前
    我看到了一个好大的轮子
    fluorinedog
        10
    fluorinedog   53 天前 via Android
    用 hash_combine 算法,别自己造轮子
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2043 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 22ms · UTC 05:43 · PVG 13:43 · LAX 21:43 · JFK 00:43
    ♥ Do have faith in what you're doing.