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

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

  •  
  •   1oNflow · 6 天前 · 1342 次点击

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

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

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

    就,如果你找到了一个冲突,可以出名那种。
        3
    crclz   6 天前
        4
    wangyzj   6 天前
    我看到了一个好大的轮子
        5
    geelaw   6 天前
    @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。
        6
    xupefei   6 天前 via iPhone
    用多级哈希。现成的实现是 bloom filter。
        7
    zunceng   6 天前
    当年听人吹过暴雪有个 hash 算法 从来没用上过
        8
    Raymon111111   6 天前
    楼主的意思是针对任意的槽大小, hash 结果可以均匀分布吧
        9
    hzgit   6 天前
    我看到了一个好大的轮子
        10
    fluorinedog   6 天前 via Android
    用 hash_combine 算法,别自己造轮子
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4492 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 28ms · UTC 02:15 · PVG 10:15 · LAX 18:15 · JFK 21:15
    ♥ Do have faith in what you're doing.