Java HashMap性能优化/替代方案-Java 学习之路

问题

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

其他数据结构建议是受欢迎的，但我需要Java Map的查找功能：
map.get(key)
在我的情况下，我想创建一个包含2600万条目的 Map 。使用标准的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;
}

我使用add的associative属性来确保相等的对象具有相同的哈希码。数组是字节，其值在0到51之间。值只在一个数组中使用一次。如果a数组包含相同的值(按任意顺序)，则对象相等，而b数组则相同。所以a = {0,1} b = {45,12,33}和a = {1,0} b = {33,45,12}是相等的。

编辑，一些笔记：

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

#1 热门回答(54 赞)

正如许多人指出的那样，hashCode()的方法应该受到指责。它只为2600万个不同的对象生成大约20,000个代码。这是每个哈希桶平均1,300个对象=非常非常糟糕。但是，如果我将两个数组转换为基数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()contract，即相等的对象具有相同的哈希代码。使用旧方法，每秒平均放置次数超过100,000次放置，100,000到2,000,000是：

使用新方法给出：

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

#2 热门回答(17 赞)

我在你的hashCode()方法中注意到的一件事是，数组a[]和b[]中元素的顺序无关紧要。因此(a[]={1,2,3}, b[]={99,100})将哈希值与(a[]={3,1,2}, b[]={100,99})相同。实际上所有键k1和k2wheresum(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]);

其中，c0,c1和c3aredistinctconstants(如果需要，可以使用不同的常量b)。这应该甚至更多的东西。

#3 热门回答(15 赞)

详细说明Pascal：你了解HashMap的工作原理吗？你的哈希表中有一些插槽。找到每个密钥的哈希值，然后映射到表中的条目。如果两个哈希值映射到同一条目 - "哈希冲突" - HashMap构建链接列表。

散列冲突可能会破坏哈希映射的性能。在极端情况下，如果所有密钥都具有相同的哈希码，或者如果它们具有不同的哈希码，但它们都映射到同一个槽，则哈希映射将变为链接列表。

因此，如果你看到性能问题，我首先要检查的是：我是否获得了随机分布的哈希码？如果没有，你需要更好的哈希函数。那么，在这种情况下"更好"可能意味着"更好地为我的特定数据集"。比如，假设你正在使用字符串，并且你将字符串的长度用于哈希值。 (不是Java的String.hashCode如何工作，但我只是编写一个简单的例子。)如果你的字符串有很多不同的长度，从1到10,000，并且相当均匀地分布在这个范围内，这可能是一个非常好的哈希函数。但是如果你的字符串都是1或2个字符，那么这将是一个非常糟糕的哈希函数。

编辑：我应该添加：每次添加新条目时，HashMap都会检查这是否重复。当存在哈希冲突时，它必须将传入密钥与映射到该槽的每个密钥进行比较。因此，在最糟糕的情况下，所有内容都散列到一个插槽，第二个键与第一个键进行比较，第三个键与#1和#2进行比较，第四个键与#1，#2和#3进行比较当你获得关键#100万时，你已经完成了超过一万亿的比较。

@Oscar：嗯，我不知道那是怎么回事。它更像是"让我澄清"。但是，是的，如果你使用与现有条目相同的密钥创建新条目，则会覆盖第一个条目。当我谈到在最后一段中查找重复项时，这就是我的意思：每当一个键哈希到同一个槽时，HashMap必须检查它是否是现有键的副本，或者它们是否恰好位于同一个槽中哈希函数。我不知道那是HashMap的"重点"：我会说"整点"是你可以快速按键检索元素。

但无论如何，这并不影响我试图制作的"整点"：当你有两个键 - 是的，不同的键，而不是同一个键再次显示 - 映射到表中的同一个插槽，HashMap构建一个链表。然后，因为它必须检查每个新密钥以查看它是否实际上是现有密钥的副本，所以每次尝试添加映射到同一个槽的新条目都必须追踪链接列表，检查每个现有条目以查看是否是先前看到的密钥的副本，或者它是否是新密钥。
在原始帖子之后更新很久
在发布6年后，我刚刚对这个答案进行了投票，这让我重新阅读了这个问题。

问题中给出的散列函数对于2600万个条目来说不是一个好的散列。

它将[0] a [1]和b [0] b [1] b [2]加在一起。他说每个字节的值范围从0到51，因此只给出(51 * 2 1)*(51 * 3 1)= 15,862个可能的哈希值。有2600万个条目，这意味着每个哈希值平均大约有1639个条目。这是很多很多的冲突，需要通过链表进行大量的连续搜索。

OP表示阵列a和阵列b中的不同顺序应该被认为是相等的，即[[1,2]，[3,4,5]]。等于([[2,1]，[5,3,4] ])，为了履行合同，他们必须具有相同的哈希码。好的。尽管如此，仍有超过15,000个可能的值。他的第二个提议哈希函数要好得多，给出了更广泛的范围。

虽然正如其他人所评论的那样，哈希函数似乎不适合更改其他数据。在创建对象时"标准化"对象或使对象的副本使用散列函数更有意义。此外，每次通过函数使用循环来计算常量是低效的。由于这里只有四个值，我会写

return a[0]+a[1]*52+b[0]*52*52+b[1]*52*52*52+b[2]*52*52*52*52;

这会导致编译器在编译时执行一次计算;或者在类中定义4个静态常量。

此外，散列函数的初稿有几个计算，它们不会添加到输出范围。注意，在考虑类中的值之前，他首先设置hash = 503而不是乘以5381。所以...实际上他为每个值增加了503 * 5381。这完成了什么？为每个哈希值添加一个常量只会烧掉cpu周期而不会完成任何有用的操作。这里的教训：增加哈希函数的复杂性不是目标。目标是获得广泛的不同价值，而不仅仅是为了复杂性而增加复杂性。

原文链接

Java HashMap性能优化/替代方案

问题

#1 热门回答(54 赞)

#2 热门回答(17 赞)

#3 热门回答(15 赞)

相关问题