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.17109409.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.84337268.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