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万，降低了性能 .
有些人建议使用数据库，在某些其他情况下绝对是明智的选择 . 但我真的在问一个数据结构和算法的问题，一个完整的数据库会比一个好的数据结构解决方案过度而且速度慢得多（毕竟数据库只是软件，但会有通信和可能的磁盘开销） .

25 回答

正如许多人指出的那样， 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是：

使用新方法给出：

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

回复于 2024-04-24T21:44:28+08:00

0
我在 hashCode() 方法中注意到的一件事是数组 a[] 和 b[] 中元素的顺序无关紧要 . 因此 (a[]={1,2,3}, b[]={99,100}) 将散列为与 (a[]={3,1,2}, b[]={100,99}) 相同的值 . 实际上所有键 k1 和 k2 ，其中 sum(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 和 c3 是不同的常量（如果需要，可以使用 b 的不同常量） . 这应该可以使事情变得更加平坦 .
回复于 2024-04-24T21:44:28+08:00
0
详细说明Pascal：你了解HashMap的工作原理吗？您的哈希表中有一些插槽 . 找到每个密钥的哈希值，然后映射到表中的条目 . 如果两个哈希值映射到同一条目 - “哈希冲突” - HashMap构建链接列表 .

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

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

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

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

但无论如何，这并不影响我试图制作的“整点”：当你有两个键 - 是的，不同的键，而不是同一个键再次显示 - 映射到表中的同一个插槽，HashMap构建一个链表 . 然后，因为它必须检查每个新密钥以查看它是否实际上是现有密钥的副本，所以每次尝试添加映射到同一个槽的新条目都必须追踪链接列表，检查每个现有条目以查看是否是先前看到的密钥的副本，或者它是否是新密钥 .

Update long after the original post

在发布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] ]），为了履行 Contract ，他们必须有相同的哈希码 . 好的 . 尽管如此，仍有超过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周期而不会完成任何有用的操作 . 这里的教训：增加哈希函数的复杂性不是目标 . 目标是获得广泛的不同 Value ，而不仅仅是为了复杂性而增加复杂性 .
回复于 2024-04-24T21:44:28+08:00
2

我的第一个想法是确保你正确地初始化你的HashMap . 来自JavaDocs for HashMap：

HashMap的一个实例有两个影响其性能的参数：初始容量和负载因子 . 容量是哈希表中的桶数，初始容量只是创建哈希表时的容量 . 加载因子是在自动增加容量之前允许哈希表获取的完整程度的度量 . 当哈希表中的条目数超过加载因子和当前容量的乘积时，哈希表将被重新哈希（即，重建内部数据结构），以便哈希表具有大约两倍的桶数 .

因此，如果您从一个太小的HashMap开始，那么每次需要调整大小时，都会重新计算哈希值......这可能是您在达到2-3百万个插入点时所感受到的 .

回复于 2024-04-24T21:44:28+08:00
15
我建议采取三管齐下的方法：
- 使用更多内存运行Java： java -Xmx256M 例如以256运行兆字节 . 如果需要，可以使用更多，并且有大量的RAM .
- 按照另一张海报的建议缓存计算的哈希值，因此每个对象只计算一次哈希值 .
- 使用更好的散列算法 . 您发布的那个将返回相同的散列，其中a = {0,1}，而a = {1,0}，其他所有相等 .
利用Java为您提供的免费服务 .
```
public int hashCode() {
    return 31 * Arrays.hashCode(a) + Arrays.hashCode(b);
}
```
我很确定这比现有的hashCode方法碰撞的可能性要小得多，尽管它取决于数据的确切性质 .
回复于 2024-04-24T21:44:28+08:00
5
进入“开/关主题”的灰色区域，但有必要消除有关Oscar Reyes建议更多哈希冲突是一件好事的混淆，因为它减少了HashMap中的元素数量 . 我可能会误解奥斯卡所说的话，但我似乎并不是唯一一个：kdgregory，delfuego，Nash0，我似乎都有同样的（错误的）理解 .

如果我理解Oscar对同一个具有相同哈希码的类的说法，他建议只有一个具有给定哈希码的类的实例将插入到HashMap中 . 例如，如果我有一个哈希码为1的SomeClass实例和一个哈希码为1的SomeClass的第二个实例，则只插入一个SomeClass实例 .

http://pastebin.com/f20af40b9处的Java pastebin示例似乎表明以上正确总结了Oscar提出的建议 .

无论有任何理解或误解，如果相同类的不同实例具有相同的哈希码，则不会仅将其插入HashMap中 - 直到它需要不等对象具有不同的哈希码（尽管这可能是可取的）由于其他原因）[1] .

下面是pastebin.com/f20af40b9示例（Oscar至少引用两次），但略微修改以使用JUnit断言而不是printlines . 此示例用于支持相同哈希码导致冲突的提议，并且当类相同时，仅创建一个条目（例如，在此特定情况下仅一个字符串）：
```
@Test
public void shouldOverwriteWhenEqualAndHashcodeSame() {
    String s = new String("ese");
    String ese = new String("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // AND equal
    assertTrue(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(2, map.size());

    assertEquals(2, map.get("ese"));
    assertEquals(3, map.get(some));

    assertTrue(s.equals(ese) && s.equals("ese"));
}

class SomeClass {
    public int hashCode() {
        return 100727;
    }
}
```
但是，哈希码并不是完整的故事 . pastebin示例忽略的是 s 和 ese 都相等：它们都是字符串"ese" . 因此，使用 s 或 ese 或 "ese" 作为键插入或获取 Map 的内容都是等效的，因为 s.equals(ese) && s.equals("ese") .

第二个测试表明，当在测试1中调用 map.put(ese, 2) 时，在同一个类上使用相同的哈希码是错误的原因 - > s -> 1 被 ese -> 2 覆盖的原因是错误的 . 在测试2中， s 和 ese 仍然具有相同的哈希码（由 assertEquals(s.hashCode(), ese.hashCode()); 验证）并且它们是同一个类 . 但是， s 和 ese 在此测试中是 MyString 实例，而不是Java String 实例 - 此测试的唯一差异是等于： String s equals String ese 在上面的测试1中，而 MyStrings s does not equal MyString ese 在测试2中：
```
@Test
public void shouldInsertWhenNotEqualAndHashcodeSame() {
    MyString s = new MyString("ese");
    MyString ese = new MyString("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // BUT not equal
    assertFalse(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(3, map.size());

    assertEquals(1, map.get(s));
    assertEquals(2, map.get(ese));
    assertEquals(3, map.get(some));
}

/**
 * NOTE: equals is not overridden so the default implementation is used
 * which means objects are only equal if they're the same instance, whereas
 * the actual Java String class compares the value of its contents.
 */
class MyString {
    String i;

    MyString(String i) {
        this.i = i;
    }

    @Override
    public int hashCode() {
        return 100727;
    }
}
```
根据后来的评论，奥斯卡似乎扭转了他早先所说的话，并承认平等的重要性 . 然而，似乎仍然认为平等是重要的，而不是“同一类”，不清楚（强调我的）：

“不是真的 . 只有当哈希值相同但密钥不同时才创建列表 . 例如，如果String给出哈希码2345并且Integer给出相同的哈希码2345，则整数被插入到列表中，因为String . equals（Integer）为false . 但 if you have the same class ( or at least .equals returns true ) 然后使用相同的条目 . 例如new String（"one"）和`new String（"one"）用作键，将使用相同的条目 . 实际上这是HashMap的第一个点自己看看：pastebin.com/f20af40b9 - Oscar Reyes“

与之前的注释明确地解决了相同类和相同哈希码的重要性，没有提到equals：

"@delfuego: See for yourself: pastebin.com/f20af40b9 So, in this question the same class is being used ( wait a minute, the same class is being used right? ) Which implies that when the same hash is used the same entry is used and there is not " list " of entries. – Oscar Reyes"

要么

"Actually this would increase the performance. The more collisions eq less entries in the hashtable eq. less work to do. Is not the hash ( which looks fine ) nor the hashtable ( which works great ) I'd bet it is on the object creation where the performance is degrading. – Oscar Reyes"

要么

"@kdgregory: Yes, but only if the collision happens with different classes, for the same class ( which is the case ) the same entry is used. – Oscar Reyes"

我可能会误解奥斯卡实际上想说的话 . 然而，他最初的评论引起了足够的混淆，通过一些明确的测试清除所有内容似乎是谨慎的，因此没有挥之不去的疑虑 .

[1] - 来自Effective Java，第二版由Joshua Bloch撰写：
- 每当在执行应用程序期间多次在同一对象上调用它时，hashCode方法必须始终返回相同的整数，前提是不修改在对象的相等比较中使用的信息 . 这个整数从一个应用程序的执行到同一个应用程序的另一个执行，不需要保持一致 .
- 如果两个对象根据等于s（Obj ect）方法相等，则对两个对象中的每一个调用hashCode方法必须产生相同的整数结果 .
- 如果两个对象根据相等的s（Object）方法不相等，则不需要在两个对象中的每一个上调用hashCode方法必须产生不同的整数结果 . 但是，程序员应该知道为不等对象生成不同的整数结果可能会提高哈希表的性能 .
回复于 2024-04-24T21:44:28+08:00
7

如果发布的hashCode中的数组是字节，那么最终可能会出现大量重复数据 .

a [0] a [1]将始终介于0和512之间 . 添加b将始终生成介于0和768之间的数字 . 将这些数字相乘并获得400,000个唯一组合的上限，假设您的数据完全分布在每个字节的每个可能值 . 如果您的数据完全正常，则此方法的唯一输出可能要少得多 .

回复于 2024-04-24T21:44:28+08:00
4

HashMap具有初始容量，HashMap的性能非常依赖于生成底层对象的hashCode .

尝试调整两者 .

回复于 2024-04-24T21:44:28+08:00
1

如果键具有任何图案，则可以将 Map 拆分为较小的 Map 并具有索引图 .

示例：密钥：1,2,3，.... n 28个 Map ，每个100万 . 索引 Map ：1-1,000,000 - > Map1 1,000,000-2,000,000 - > Map2

因此，您将进行两次查找，但密钥集将为1,000,000与28,000,000 . 您也可以使用刺痛模式轻松完成此操作 .

如果密钥是完全随机的，那么这将不起作用

回复于 2024-04-24T21:44:28+08:00
1

如果您提到的两个字节数组是您的整个键，则值在0-51范围内，唯一且a和b数组中的顺序无关紧要，我的数学告诉我，只有大约2600万个可能的排列和您可能正在尝试使用所有可能键的值填充 Map .

在这种情况下，如果使用数组而不是HashMap并将其从0到25989599索引，那么从数据存储中填充和检索值当然会快得多 .

回复于 2024-04-24T21:44:28+08:00
7
我迟到了，但有几条关于大 Map 的评论：
- 正如其他帖子中详细讨论的那样，使用一个好的hashCode（），Map中的26M条目没什么大不了的 .
- 但是，这里潜在的隐藏问题是巨型 Map 对GC的影响 .
我假设这些 Map 是长寿的 . 即你填充它们并在应用程序的持续时间内保持不变 . 我也假设应用程序本身很长寿 - 就像某种服务器一样 .

Java HashMap中的每个条目都需要三个对象：键，值和将它们连接在一起的Entry . 因此， Map 中的26M条目意味着26M * 3 == 78M对象 . 这很好，直到你达到一个完整的GC . 然后你有一个暂停世界的问题 . GC将查看每个78M对象并确定它们都是活着的 . 78M对象只是很多要查看的对象 . 如果您的应用程序可以忍受偶尔的长时间（可能是几秒钟）暂停，那就没有问题 . 如果您正在尝试实现任何延迟保证，那么您可能会遇到一个重大问题（当然，如果您想要延迟保证，Java不是选择的平台:)）如果 Map 中的值快速流失，您最终可能会频繁完全收集这大大加剧了这个问题 .

我不知道这个问题有很好的解决方案 . 思路：
- 有时可以将GC和堆大小调整为"mostly"以防止完整的GC .
- 如果您的 Map 内容流失很多，您可以尝试Javolution's FastMap - 它可以汇集Entry对象，这可以降低完全收集的频率
- 您可以创建自己的映射impl并在byte []上进行显式内存管理（即通过将数百万个对象序列化为单个字节来交换更可预测的延迟[] - 呃！）
- 不要在这部分使用Java - 通过套接字与某种可预测的内存数据库通信
- 希望新的G1收藏家能够提供帮助（主要适用于高流失案例）
只是花了很多时间在Java中使用巨型 Map 的人的一些想法 .
回复于 2024-04-24T21:44:28+08:00
4

您可以尝试使用内存数据库，如HSQLDB .

回复于 2024-04-24T21:44:28+08:00
2
在我的情况下，我想创建一个包含2600万条目的 Map . 使用标准Java HashMap，在2-3百万次插入后，放置速率变得无法忍受 .

从我的实验（2009年的学生项目）：
- 我为100.000 Build 了一个红黑树节点从1到100.000 . 花了785.68秒（13分钟） . 而且我没有为100万个节点构建RBTree（就像使用HashMap的结果一样） .
- 使用"Prime Tree"，我的算法数据结构 . 我可以在21.29秒内为一千万个节点 Build 树/ Map （RAM：1.97Gb） . 搜索键值成本为O（1） .
注意：“Prime Tree”在“连续键”上的效果最好，从1到10百万 . 要使用像HashMap这样的键，我们需要调整一些未成年人 .

那么，什么是#PrimeTree？简而言之，它是像二叉树一样的树数据结构，分支数是素数（而不是“2” - 二进制） .
回复于 2024-04-24T21:44:28+08:00
1

SQLite允许您在内存中使用它 .

回复于 2024-04-24T21:44:28+08:00
0

您是否考虑过使用嵌入式数据库来执行此操作 . 看看Berkeley DB . 它是开源的，现在由Oracle拥有 .

它将所有内容存储为Key-> Value对，它不是RDBMS . 它的目标是快速 .

回复于 2024-04-24T21:44:28+08:00
1

首先，您应该检查您是否正确使用Map，键的好hashCode（）方法，Map的初始容量，正确的Map实现等等许多其他答案描述 .

然后我会建议使用分析器来查看实际发生的情况以及执行时间的花费 . 例如，hashCode（）方法执行了数十亿次？

如果这没有帮助，那么如何使用EHCache或memcached这样的东西呢？是的，它们是用于缓存的产品，但您可以对它们进行配置，以便它们具有足够的容量，并且永远不会从缓存存储中逐出任何值 .

另一种选择是某些数据库引擎，它比完整的SQL RDBMS重量更轻 . 也许是Berkeley DB之类的东西 .

请注意，我个人没有这些产品的性能经验，但它们值得一试 .

回复于 2024-04-24T21:44:28+08:00
17
您可以尝试将计算的哈希代码缓存到密钥对象 .

像这样的东西：
```
public int hashCode() {
  if(this.hashCode == null) {
     this.hashCode = computeHashCode();
  }
  return this.hashCode;
}

private int computeHashCode() {
   int hash = 503;
   hash = hash * 5381 + (a[0] + a[1]);
   hash = hash * 5381 + (b[0] + b[1] + b[2]);
   return hash;
}
```
当然，在第一次计算hashCode之后，您必须小心不要更改密钥的内容 .

编辑：当您将每个键只添加一次到 Map 时，似乎缓存的代码值是不值得的 . 在其他一些情况下，这可能很有用 .
回复于 2024-04-24T21:44:28+08:00
7
另一张海报已经指出，由于您将值一起添加的方式，您的哈希码实现将导致大量冲突 . 我愿意这样做，如果你在调试器中查看HashMap对象，你会发现你有200个不同的哈希值，具有极长的存储桶链 .

如果总是具有0..51范围内的值，则每个值将需要6位来表示 . 如果您总是有5个值，则可以使用左移和添加创建一个30位哈希码：
```
int code = a[0];
    code = (code << 6) + a[1];
    code = (code << 6) + b[0];
    code = (code << 6) + b[1];
    code = (code << 6) + b[2];
    return code;
```
左移是快速的，但会留下不均匀分布的哈希码（因为6位意味着范围为0..63） . 另一种方法是将散列乘以51并添加每个值 . 这仍然不会完美分布（例如，{2,0}和{1,52}将发生碰撞），并且将比移位慢 .
```
int code = a[0];
    code *= 51 + a[1];
    code *= 51 + b[0];
    code *= 51 + b[1];
    code *= 51 + b[2];
    return code;
```
回复于 2024-04-24T21:44:28+08:00
0
正如所指出的，您的哈希码实现有太多的冲突，修复它应该会产生不错的性能 . 此外，缓存hashCodes和有效实现equals将有所帮助 .

如果您需要进一步优化：

根据您的描述，只有（52 * 51/2）*（52 * 51 * 50/6）= 29304600个不同的密钥（其中26000000，即约90％将存在） . 因此，您可以设计没有任何冲突的哈希函数，并使用简单数组而不是哈希映射来保存数据，从而减少内存消耗并提高查找速度：
```
T[] array = new T[Key.maxHashCode];

void put(Key k, T value) {
    array[k.hashCode()] = value;

T get(Key k) {
    return array[k.hashCode()];
}
```
（一般来说，设计一个高效，无碰撞的散列函数是不可能很好地聚类，这就是为什么HashMap会容忍碰撞，这会产生一些开销）

假设 a 和 b 已排序，您可以使用以下哈希函数：
```
public int hashCode() {
    assert a[0] < a[1]; 
    int ahash = a[1] * a[1] / 2 
              + a[0];

    assert b[0] < b[1] && b[1] < b[2];

    int bhash = b[2] * b[2] * b[2] / 6
              + b[1] * b[1] / 2
              + b[0];
    return bhash * 52 * 52 / 2 + ahash;
}

static final int maxHashCode = 52 * 52 / 2 * 52 * 52 * 52 / 6;
```
我认为这是无碰撞的 . 证明这是留给数学倾向读者的练习 .
回复于 2024-04-24T21:44:28+08:00
0

在Effective Java: Programming Language Guide (Java Series)

第3章，您可以在计算hashCode（）时找到要遵循的良好规则 .

特别：

如果该字段是数组，则将其视为每个元素都是单独的字段 . 也就是说，通过递归地应用这些规则来计算每个重要元素的哈希码，并且每步骤2.b组合这些值 . 如果数组字段中的每个元素都很重要，则可以使用版本1.5中添加的Arrays.hashCode方法之一 .

回复于 2024-04-24T21:44:28+08:00
1

在开头分配一张大 Map . 如果你知道它将有2600万条和你有记忆，做一个 new HashMap(30000000) .

你确定，你有足够的内存用于2600万个条目，拥有2600万个密钥和值吗？这对我来说听起来像是很多记忆 . 你确定垃圾收集在200到300万的标记下还能正常吗？我可以想象这是一个瓶颈 .

回复于 2024-04-24T21:44:28+08:00
1
你可以尝试两件事：
使您的hashCode方法返回更简单和更有效的内容，例如连续的int将 Map 初始化为：Map map = new HashMap（30000000，.95f）;
这两个动作将大大减少结构重复的数量，并且我认为很容易测试 . 如果这不起作用，请考虑使用不同的存储，例如RDBMS . 编辑奇怪的是，设置初始容量会降低您的性能 . 从javadocs看：如果初始容量大于最大条目数除以加载因子，则不会发生任何重新连接操作 . 我做了一个microbeachmark（这不是任何权威，但至少证明了这一点）$ cat Huge * java
import java.util . *;
公共阶层巨大的{
public static void main（String [] args）{
Map map = new HashMap（30000000,0.95f）;
for（int i = 0; i <26000000; i）{
map.put（i，i）;
}
}
}
import java.util . *;
公共课Huge2 {
public static void main（String [] args）{
Map map = new HashMap（）;
for（int i = 0; i <26000000; i）{
map.put（i，i）;
}
}
}
$ time java -Xms2g -Xmx2g巨大的

真实0m16.207s
用户0m14.761s
sys 0m1.377s
$ time java -Xms2g -Xmx2g Huge2

真正的0m21.781s
用户0m20.045s
sys 0m1.656s
$
因此，由于重新使用，初始容量从21s降至16s . 这使我们将您的hashCode方法作为“机会区域”;）
EDIT

不是HashMap

按照你上一版的说法 .

我认为你应该真正剖析你的应用程序，看看内存/ cpu的消耗位置 .

我创建了一个实现相同的类 hashCode

该哈希代码会产生数百万次冲突，然后HashMap中的条目会显着减少 .

我在之前的考试中从21s，16s传到10s和8s . 原因是hashCode会引发大量的冲突，你不会存储你认为的26M对象，但是数量要少得多（我会说约20k）所以：

问题 IS NOT THE HASHMAP 在您的代码中的其他位置 .

现在是时候找到一个分析器并找出它的位置 . 我认为这是在项目的创建或可能你正在写入磁盘或从网络接收数据 .

这是我的课程实施 .

note 我没有't use a 0-51 range as you did but -126 to 127 for my values and admits repeated, that'，因为我在更新你的问题之前做了这个测试

唯一的区别是您的 class 将有更多的碰撞，因此存储在 Map 中的项目更少 .
```
import java.util.*;
public class Item {

    private static byte w = Byte.MIN_VALUE;
    private static byte x = Byte.MIN_VALUE;
    private static byte y = Byte.MIN_VALUE;
    private static byte z = Byte.MIN_VALUE;

    // Just to avoid typing :) 
    private static final byte M = Byte.MAX_VALUE;
    private static final byte m = Byte.MIN_VALUE;


    private byte [] a = new byte[2];
    private byte [] b = new byte[3];

    public Item () {
        // make a different value for the bytes
        increment();
        a[0] = z;        a[1] = y;    
        b[0] = x;        b[1] = w;   b[2] = z;
    }

    private static void increment() {
        z++;
        if( z == M ) {
            z = m;
            y++;
        }
        if( y == M ) {
            y = m;
            x++;
        }
        if( x == M ) {
            x = m;
            w++;
        }
    }
    public String toString() {
        return "" + this.hashCode();
    }



    public int hashCode() {
        int hash = 503;
        hash = hash * 5381 + (a[0] + a[1]);
        hash = hash * 5381 + (b[0] + b[1] + b[2]);
        return hash;
    }
    // I don't realy care about this right now. 
    public boolean equals( Object other ) {
        return this.hashCode() == other.hashCode();
    }

    // print how many collisions do we have in 26M items.
    public static void main( String [] args ) {
        Set set = new HashSet();
        int collisions = 0;
        for ( int i = 0 ; i < 26000000 ; i++ ) {
            if( ! set.add( new Item() ) ) {
                collisions++;
            }
        }
        System.out.println( collisions );
    }
}
```
使用此类具有以前程序的Key
```
map.put( new Item() , i );
```
给我：
```
real     0m11.188s
user     0m10.784s
sys 0m0.261s


real     0m9.348s
user     0m9.071s
sys  0m0.161s
```
回复于 2024-04-24T21:44:28+08:00
4

也许尝试使用，如果你需要它同步

http://commons.apache.org/collections/api/org/apache/commons/collections/FastHashMap.html

回复于 2024-04-24T21:44:28+08:00
4

我用一个列表与一个hashmap做了一个小小的测试，有趣的是在列表中迭代，发现对象花费的时间与毫秒相同，就像使用hashmaps获取函数一样...只是一个fyi . 哦，使用大小的哈希映射时，内存是一个大问题 .

回复于 2024-04-24T21:44:28+08:00
54

使用的流行散列方法对于大型集合并不是非常好，并且如上所述，使用的散列特别糟糕 . 更好的是使用具有高混合和覆盖的散列算法，例如BuzHash（样本实现在http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm）

回复于 2024-04-24T21:44:28+08:00

Java HashMap性能优化/替代方案

25 回答

不是HashMap

相关问题