Java哈希冲突概率

 郑谊099_448 发布于 2023-02-08 17:59

我在散列图(约280万个对象)中存储大量对象(具有存储在对象中的字节数组中的值的唯一组合),并且在检查我是否有任何哈希码冲突时(32位哈希) ),我很惊讶地看到在统计上没有任何东西,我有近100%的机会至少有一次碰撞(参见http://preshing.com/20110504/hash-collision-probabilities/).

因此,我想知道我检测碰撞的方法是否被窃听,或者我是否非常幸运......

以下是我尝试从地图中存储的280万个值中检测碰撞的方法:

HashMap values;
(...fill with 2.8 mlns unique values...)
HashSet hashes = new HashSet<>();
for (ShowdownFreqKeysVO key:values.keySet()){
    if (hashes.contains(key.hashCode())) throw new RuntimeException("Duplicate hash for:"+key);
    hashes.add(key.hashCode());
}

这是对象创建哈希值的方法:

public class ShowdownFreqKeysVO {
    //Values for the different parameters
    public byte[] values = new byte[12];

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + Arrays.hashCode(values);
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        ShowdownFreqKeysVO other = (ShowdownFreqKeysVO) obj;
        if (!Arrays.equals(values, other.values))
            return false;
        return true;
    }
}

任何关于我做错的想法/暗示都将不胜感激!

谢谢,托马斯

1 个回答
  • 我不相信运气

    这是Arrays.hashCode您使用的实现

    public static int hashCode(int a[]) {
        if (a == null)
            return 0;
    
        int result = 1;
        for (int element : a)
            result = 31 * result + element;
    
        return result;
    }
    

    如果你的值恰好小于31,则它们被视为基数31中的不同数字,因此每个结果都有不同的数字(如果我们现在忽略溢出).让我们称之为纯粹的哈希

    现在当然31^11比Java中的整数数量大,所以我们会得到大量的溢出.但由于31的幂和最大整数是"非常不同",你不会得到几乎随机的分布,而是一个非常规则的均匀分布.

    让我们考虑一个较小的例子.我假设你的数组中只有2个元素,范围从0到5.我尝试通过取"纯哈希"的模38来创建0到37之间的"hashCode".结果是我得到5个整数的条纹,中间有小间隙,而不是单个碰撞.

    val hashes = for {
      i <- 0 to 4
      j <- 0 to 4
    } yield (i * 31 + j) % 38
    
    println(hashes.size) // prints 25
    println(hashes.toSet.size) // prints 25
    

    要验证这是否是您的数字所发生的情况,您可以创建一个图形,如下所示:对于每个哈希,取x的前16位和y的第二个16位,点黑色.我打赌你会看到一个非常规律​​的模式.

    2023-02-08 18:01 回答
撰写答案
今天,你开发时遇到什么问题呢?
立即提问
热门标签
PHP1.CN | 中国最专业的PHP中文社区 | PNG素材下载 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有