Java HashMap性能优化/替代

Question

我想创建一个大型HashMap，但put()性能不够好。有任何想法吗？

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

map.get(key)

就我而言，我想创建一个包含2600万个条目的地图。使用标准的Java HashMap，插入2到3百万次后，放置速度会变得异常缓慢。

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

我的哈希码方法：

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;
}

我正在使用adding的关联属性来确保相等的对象具有相同的哈希码。数组是字节，值的范围是0-51。在两个数组中，值只能使用一次。如果a数组包含相同的值（任一顺序）且b数组的对象相同，则对象相等。因此a
= {0,1} b = {45,12,33}和a = {1,0} b = {33,45,12}是相等的。

编辑，一些注意事项：

• 少数人批评使用哈希图或其他数据结构来存储2600万个条目。我不明白为什么这看起来很奇怪。在我看来，这似乎是经典的数据结构和算法问题。我有2600万个项目，我希望能够快速将其插入数据结构并从数据结构中查找它们：给我数据结构和算法。

• 将默认Java HashMap的初始容量设置为2600万会 降低 性能。

• 有人建议在其他情况下使用数据库，这绝对是明智的选择。但是我确实是在问一个数据结构和算法问题，一个完整的数据库会比一个好的数据结构解决方案矫kill过正，而且速度慢得多（毕竟，所有数据库只是软件，但可能会有通信和磁盘开销）。

Answer 1

正如许多人指出的那样，这种hashCode()方法应该受到指责。它仅为2600万个不同的对象生成大约20,000个代码。每个哈希存储桶平均有1300个对象=非常非常糟糕。但是，如果我将两个数组转换为以52为底的数字，则可以确保为每个对象获取唯一的哈希码：

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;
}

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

168350.17
109409.195
81344.91
64319.023
53780.79
45931.258
39680.29
34972.676
31354.514
28343.062
25562.371
23850.695
22299.22
20998.006
19797.799
18702.951
17702.434
16832.182
16084.52
15353.083

使用新方法可以得出：

337837.84
337268.12
337078.66
336983.97
313873.2
317460.3
317748.5
320000.0
309704.06
310752.03
312944.5
265780.75
275540.5
264350.44
273522.97
270910.94
279008.7
276285.5
283455.16
289603.25

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