Java HashMap 性能优化/替代方案

performance optimization hashmap java map

2022-08-31 09:48:37

我想创建一个大的HashMap，但性能不够好。有什么想法吗？put()

欢迎其他数据结构建议，但我需要Java Map的查找功能：

map.get(key)

在我的情况下，我想创建一个包含2600万个条目的地图。使用标准的Java HashMap，在200-300万次插入后，放置速率变得难以忍受的缓慢。

另外，有谁知道对密钥使用不同的哈希代码分布是否会有所帮助？

我的哈希码方法：

byte[] a = new byte[2];
byte[] b = new byte[3];
...

public int hashCode() {
    int hash = 503;
    hash = hash * 5381 + (a[0] + a[1]);
    hash = hash * 5381 + (b[0] + b[1] + b[2]);
    return hash;
}

我正在使用加法的关联属性来确保相等的对象具有相同的哈希码。数组是值在 0 - 51 范围内的字节。值在任一数组中仅使用一次。如果 a 数组包含相同的值（按任一顺序），则对象相等，而 b 数组也是如此。所以 a = {0，1} b = {45，12，33} 和 a = {1，0} b = {33，45，12} 是相等的。

编辑，一些注意事项：

一些人批评使用哈希映射或其他数据结构来存储2600万个条目。我不明白为什么这看起来很奇怪。对我来说，这看起来像是一个经典的数据结构和算法问题。我有2600万个项目，我希望能够快速将它们插入数据结构并从中查找它们：给我数据结构和算法。
将默认 Java HashMap 的初始容量设置为 2600 万会降低性能。
有些人建议使用数据库，在其他一些情况下，这绝对是明智的选择。但我实际上是在问一个数据结构和算法问题，一个完整的数据库会过分，而且比一个好的数据结构解决方案慢得多（毕竟数据库只是软件，但会有通信和可能的磁盘开销）。

答案 1

正如许多人所指出的那样，这种方法是罪魁祸首。它只为2600万个不同的对象生成了大约20，000个代码。这是每个哈希桶平均1，300个对象=非常非常糟糕。但是，如果我将两个数组转换为以52为基数的数字，我可以保证为每个对象获得唯一的哈希代码：hashCode()

public int hashCode() {       
    // assume that both a and b are sorted       
    return a[0] + powerOf52(a[1], 1) + powerOf52(b[0], 2) + powerOf52(b[1], 3) + powerOf52(b[2], 4);
}

public static int powerOf52(byte b, int power) {
    int result = b;
    for (int i = 0; i < power; i++) {
        result *= 52;
    }
    return result;
}

对数组进行排序以确保此方法满足相等对象具有相同哈希代码的协定。使用旧方法，在 100，000 个看跌区块（100，000 到 2，000，000）的区块上，每秒的平均看跌期权数量为：hashCode()

使用新方法可以得到：

好多了。旧方法很快就消失了，而新方法则保持了良好的吞吐量。

答案 2

我注意到您的方法中的一件事是数组中元素的顺序并不重要。因此，将哈希值与相同。实际上，所有键和位置都会导致冲突。我建议为数组的每个位置分配一个权重：hashCode()a[]b[](a[]={1,2,3}, b[]={99,100})(a[]={3,1,2}, b[]={100,99})k1k2sum(k1.a)==sum(k2.a)sum(k1.b)=sum(k2.b)

hash = hash * 5381 + (c0*a[0] + c1*a[1]);
hash = hash * 5381 + (c0*b[0] + c1*b[1] + c3*b[2]);

其中，和是不同的常量（如有必要，可以使用不同的常量）。这应该会让事情更加平衡。c0c1c3b