Java HashMap性能优化/替代

一尘不染

Java HashMap性能优化/替代

java

我想创建一个大型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过正，而且速度慢得多（毕竟，所有数据库只是软件，但可能会有通信和磁盘开销）。

阅读 331

2020-09-08

共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）的平均每秒看跌次数为：

使用新方法可以得出：

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

2020-09-08