Java HashMap性能优化/替代

2018-06-04 16:58:45

我想创建一个大的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;
}

我正在使用addition的associative属性来确保相等的对象具有相同的哈希码。这些数组是字节值在0-51范围内的值。数值仅在任一数组中使用一次。如果a数组包含相同的值（以任意顺序）并且b数组也是相同的，则这些对象是相等的。所以a = {0,1} b = {45,12,33}和a = {1,0} b = {33,45,12}是相等的。

编辑，一些笔记：

一些人批评使用哈希映射或其他数据结构来存储2600万个条目。我看不出为什么这看起来很奇怪。它看起来像我经典的数据结构和算法问题。我有2600万个项目，我希望能够快速插入并从数据结构中查找它们：给我数据结构和算法。

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

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

许多人指出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()合约。使用旧的方法，平均每秒投放100,000个投币组的投放数量为10万到2,000,000个：

使用新方法给出：

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

我在你的hashCode()方法中注意到的一件事是数组a[]和b[]元素的顺序无关紧要。因此(a[]={1,2,3}, b[]={99,100})将散列为与(a[]={3,1,2}, b[]={100,99}) 。实际上，所有其中sum(k1.a)==sum(k2.a)和sum(k1.b)=sum(k2.b)密钥k1和k2将导致冲突。我建议为阵列的每个位置分配一个权重：

hash = hash * 5381 + (c0*a[0] + c1*a[1]);
hash = hash * 5381 + (c0*b[0] + c1*b[1] + c3*b[2]);

其中， c0 ， c1和c3是不同的常量（如果需要，可以对b使用不同的常量）。这应该让事情多一点。

详细阐述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]]。equals（[[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个静态常量。

另外，哈希函数的第一份草案有几个计算，它们不会添加到输出范围中。请注意，他甚至在考虑来自班级的数值之前，先将散列值设置为503，然后再乘以5381。所以......实际上他为每个值增加了503 * 5381。这完成了什么？为每个哈希值添加一个常量只会烧毁cpu周期，而不会完成任何有用的操作。这里的教训：增加散列函数的复杂性不是目标。我们的目标是获得广泛的不同价值观，而不仅仅是为了复杂性而增加复杂性。

链接地址: http://www.djcxy.com/p/15215.html

上一篇: Java HashMap performance optimization / alternative

下一篇: Is there a performance difference between i++ and ++i in C?