Java HashMap性能优化/替代

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

回答:

正如许多人指出的那样,这种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

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

以上是 Java HashMap性能优化/替代 的全部内容, 来源链接: utcz.com/qa/397819.html

回到顶部