Java HashMap性能优化/替代
我想创build一个大的HashMap，但put()性能不够好。 有任何想法吗？
其他数据结构的build议是受欢迎的，但我需要Java Map的查找function：
map.get(key)
在我的情况下，我想创build一个有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; }
我正在使用添加的关联属性来确保相等的对象具有相同的哈希码。 这些数组是字节，其值在0 – 51之间。值只在数组中使用一次。 如果a数组包含相同的值（以任意顺序）并且对于b数组也是相同的，则这些对象是相等的。 所以a = {0,1} b = {45,12,33}和a = {1,0} b = {33,45,12}是相等的。
编辑，一些笔记：
-
有less数人批评使用哈希映射或其他数据结构来存储2600万个条目。 我不明白为什么这看起来很奇怪。 它看起来像一个经典的数据结构和algorithm问题给我。 我有2600万个项目，我希望能够快速插入到数据结构中并查找它们：给我数据结构和algorithm。
-
将默认Java HashMap的初始容量设置为2600万降低了性能。
-
有人build议使用数据库，在其他一些情况下，这绝对是明智的select。 但是我真的在问一个数据结构和algorithm的问题，一个完整的数据库会比一个好的数据结构解决scheme（毕竟数据库只是软件，但会有通信和可能的磁盘开销）慢得多。
许多人指出hashCode()方法是怪罪。 仅为2千6百万个不同的对象生成大约2万个代码。 那就是每个散列桶平均有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; }
数组被sorting以确保这个方法满足hashCode()约定，即相等的对象具有相同的散列码。 使用旧的方法，平均每秒投放100,000个投币，10万到200万投币的数量是：
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
好多了。 旧的方法很快就褪去了，而新的方法保持了很好的吞吐量。
在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将导致冲突。 我build议给数组的每个位置分配一个权重：
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是如何工作的吗？ 你的散列表中有一定数量的插槽。 find每个键的哈希值，然后映射到表中的一个条目。 如果两个哈希值映射到相同的条目 – “散列冲突” – HashMap生成一个链表。
哈希碰撞可能会破坏哈希映射的性能。 在极端情况下，如果所有密钥都具有相同的哈希码，或者它们具有不同的哈希码，但它们都映射到相同的位置，则哈希映射会变成链接列表。
所以，如果你看到性能问题，我会检查的第一件事是：我得到一个随机分布的散列码？ 如果没有，你需要一个更好的散列函数。 那么，在这种情况下，“更好”可能意味着“对我的特定数据更好”。 就像，假设你正在使用string，并且你把string的长度作为散列值。 （并不是Java的String.hashCode是如何工作的，但是我只是一个简单的例子。）如果你的string长度范围很广（从1到10,000），并且在这个范围内是相当均匀分布的，这可能是一个很好的散列函数。 但是，如果你的string都是1或2个字符，这将是一个非常糟糕的散列函数。
编辑：我应该添加：每次你添加一个新的条目，HashMap检查，如果这是重复的。 当发生散列冲突时，必须将传入的密钥与映射到该插槽的每个密钥进行比较。 因此，在最糟糕的情况下，所有东西都散列到一个插槽，第二个键与第一个键进行比较，第三个键与＃1和＃2进行比较，第四个键与＃1，＃2和＃3进行比较等等。当你到达关键＃100万时，你已经完成了超过一万亿次的比较。
@Oscar：呃，我不明白这是不是真的。 这更像是一个“让我澄清”。 但是，是的，如果您使用与现有条目相同的密钥创build新条目，那么这会覆盖第一个条目。 当我谈到在最后一段中寻找重复项时，这就是我的意思：只要一个密钥散列到同一个槽中，HashMap就必须检查它是否与现有密钥重复，或者它们是否恰好在同一个槽中散列函数。 我不知道这是一个HashMap的“全部”：我认为“整点”是你可以通过快速检索元素。
但无论如何，这并不影响我正在尝试做的“整点”：当你有两个键 – 是的，不同的键，不同的键再次出现 – 映射到表中的同一个插槽，HashMapbuild立一个链表。 然后，因为它必须检查每个新密钥以查看它是否实际上是现有密钥的副本，所以每次尝试添加映射到该相同时隙的新条目都必须追查链接列表，检查每个现有条目以查看是否这个是以前看到的密钥的副本，或者是新的密钥。
在原始post之后更新很久
在发帖之后的6年，我刚刚得到了这个答案的投票权，使我重新阅读了这个问题。
问题中给出的哈希函数对于2600万个条目来说不是一个好的哈希函数。
它将[0] + a [1]和b [0] + b [1] + b [2]加在一起。 他说每个字节的值从0到51，所以只给出（51 * 2 + 1）*（51 * 3 + 1）= 15,862个可能的散列值。 有2600万个条目，这意味着每个散列值平均约有1639个条目。 这是很多很多的碰撞，需要通过链表进行大量的连续search。
OP表示，数组a和数组b中的不同顺序应该被认为是相等的，即[[1,2]，[3,4,5]]等于（[[2,1]，[5,3,4] ]），所以要履行合同，他们必须有相同的哈希码。 好的。 尽pipe如此，还是有超过15,000个可能的值。 他提出的第二个散列函数要好得多，给出了更广泛的范围。
尽pipe正如其他人所评论的，散列函数似乎不适合改变其他数据。 当创build对象时，“标准化”这个对象会更有意义，或者让哈希函数可以从数组的副本中工作。 另外，每次通过函数使用循环来计算常量是无效的。 由于这里只有四个值，所以我会写
return a[0]+a[1]*52+b[0]*52*52+b[1]*52*52*52+b[2]*52*52*52*52;
这会导致编译器在编译时执行一次计算; 或者在类中定义了4个静态常量。
此外，哈希函数的第一个草案有几个计算，不会增加任何输出的范围。 注意他甚至在考虑了class级的数值之前，先设置hash = 503比乘以5381。 所以…实际上他增加了503 * 5381到每个值。 这完成了什么？ 给每个哈希值添加一个常量只会烧毁cpu周期而不会完成任何有用的操作。 这里的教训：增加散列函数的复杂性不是目标。 目标是获得广泛的不同价值观，而不仅仅是为了增加复杂性而复杂化。
我的第一个想法是确保你正在适当地初始化你的HashMap。 从JavaDocs的HashMap ：
HashMap的一个实例有两个影响其性能的参数：初始容量和负载因子。 容量是哈希表中桶的数量，初始容量就是哈希表创build时的容量。 加载因子是散列表在其容量自动增加之前被允许得到的满度的度量。 当哈希表中的条目数量超过了负载因子和当前容量的乘积时，散列表被重新映射（也就是内部数据结构被重build），使得散列表的数量大约是存储桶数量的两倍。
所以，如果你从一个太小的HashMap开始，那么每当它需要resize时， 所有的哈希都会被重新计算，这可能是你在达到2-3百万个插入点时所感觉到的。
我build议三方面的做法：
-
用更多的内存运行Java：例如
java -Xmx256M以256兆字节运行。 如果需要使用更多，你有很多的RAM。 -
按照另一张海报的build议caching计算的散列值，因此每个对象只计算一次散列值。
-
使用更好的哈希algorithm。 你发布的那个会返回相同的散列，其中a = {0,1}，就像其中a = {1,0}一样，其他的都是相等的。
利用Java给你免费的东西。
public int hashCode() { return 31 * Arrays.hashCode(a) + Arrays.hashCode(b); }
我敢肯定，这比现有的hashCode方法有更less的冲突机会，尽pipe这取决于数据的确切性质。
进入“开/关主题”的灰色区域，但必须消除有关奥斯卡·雷耶斯的混淆build议更多的散列冲突是一件好事，因为它减less了HashMap中元素的数量。 我可能会误解奥斯卡所说的，但似乎并不是唯一的一个：kdgregory，delfuego，Nash0和我似乎都有同样的（错误的）理解。
如果我明白奥斯卡用相同的哈希码说同一个类，他build议只有一个具有给定哈希码的类的实例将被插入到HashMap中。 例如，如果我有一个哈希码为1的SomeClass实例和一个哈希码为1的SomeClass的第二个实例，则只插入一个SomeClass实例。
http://pastebin.com/f20af40b9上的Java pastebin示例似乎表明上述正确地总结了奥斯卡提出的内容。
无论有什么理解或误解，如果相同类的不同实例具有相同的哈希码，则不会只在HashMap中插入一次，直到确定这些密钥是否相等为止。 哈希码合约要求相同的对象具有相同的哈希码; 然而，它并不要求不平等的对象有不同的hashcode（尽pipe这可能是其他原因所需要的）[1]。
这个例子（Oscar至less提到过两次），但稍微修改，以使用JUnit断言而不是printline。 这个例子用于支持相同的哈希码造成冲突的提议，并且当类相同时，只有一个条目被创build（例如，在这个特定情况下只有一个string）：
@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都相等的事实：它们都是string“ese”。 因此，使用s或ese或"ese"作为键插入或获取映射的内容都是等价的，因为s.equals(ese) && s.equals("ese") 。
第二个testing表明，当在testing中调用map.put(ese, 2)时，认为在同一个类上相同的哈希码是ese -> 2覆盖键 – >值s -> 1的原因是错误的。 在testing二中， s和ese仍然具有相同的散列码（经过assertEquals(s.hashCode(), ese.hashCode()); ）AND它们是相同的类。 然而， s和ese是这个testing中的MyString实例，而不是Java的String实例 – 与此testing相关的唯一区别是equals： String s equals String ese上面testing1中的String s equals String ese ，而MyStrings s does not equal MyString esetesting二中的MyStrings s does not equal MyString ese ：
@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; } }
根据后来的评论，奥斯卡似乎扭转了他之前所说的，并承认平等的重要性。 然而，似乎仍然认为平等是重要的，而不是“同一个阶级”，这是不明确的（我的重点）：
“不是真的，只有散列值相同才能创build列表，但是关键字是不同的。例如，如果一个string给出了散列码2345，并且整数给出了相同的散列码2345，那么这个整数就被插入到了列表中。 如果你有相同的类（或者至less.equals返回true），那么使用相同的条目，例如new String（“one”）和`new String（“one”）用作键，将使用相同的条目，实际上这是HashMap的全部首要位置！请亲自看看：pastebin.com/f20af40b9 – Oscar Reyes“
而之前的评论明确地说明了相同的类和相同的哈希码的重要性，没有提及等于：
“@delfuego：亲自看看：pastebin.com/f20af40b9所以，在这个问题中，正在使用同一个类（稍等一会，正在使用相同的类吗？）这意味着当相同的哈希使用相同的条目被使用，并没有“名单”的条目 – 奥斯卡雷耶斯“
要么
“实际上，这会增加性能，在hashtable eq中，碰撞次数越less，工作量就越less，不是哈希（看起来不错），也不是哈希表（它工作的很好），我敢打赌它是在对象创作的表演正在退化 – 奥斯卡·雷耶斯“
要么
“@ kdgregory：是的，但是只有当碰撞发生在不同的class级时，对于同一个class级（这种情况）使用相同的条目 – 奥斯卡·雷耶斯”
再一次，我可能误解了奥斯卡究竟在说什么。 然而，他原来的意见已经引起了很大的困惑，似乎谨慎的做法是用一些明确的testing来清除所有的东西，所以没有任何疑问。
[1] – 从有效的Java，第二版 Joshua Bloch：
-
只要在应用程序执行过程中多次调用同一对象，hashCode方法必须始终返回相同的整数，前提是在对象的相等比较中不使用修改的信息。 从应用程序的一次执行到同一应用程序的另一次执行，此整数不必保持一致。
-
如果两个对象按照相等的s（Obj ect）方法相等，则对这两个对象的每一个调用hashCode方法必须产生相同的整数结果。
-
如果两个对象按照等于s（Object）方法不相等，则不要求对这两个对象中的每一个调用hashCode方法都必须产生不同的整数结果。 但是，程序员应该知道，为不相等的对象生成不同的整数结果可以提高散列表的性能。
如果你发布的hashCode中的数组是字节，那么你可能会得到大量的重复。
a [0] + a [1]将始终在0到512之间。添加b将始终产生一个介于0到768之间的数字。将这些数字相乘，您将得到400,000个唯一组合的上限，假设您的数据是完美分布的在每个字节的每个可能的值中。 如果你的数据是完全正常的，那么这个方法的独特输出可能会less得多。
HashMap具有初始容量，HashMap的性能非常依赖生成底层对象的hashCode。
试着调整两者。
如果键有任何模式，那么你可以将地图分成更小的地图，并有一个索引图。
示例：键：1,2,3，… n 28个地图，每个100万。 索引图：1-1,000,000 – > Map1 1,000,000-2,000,000 – > Map2
所以你会做两个查找，但关键集将是100万对28,000,000。 你也可以用刺痛的图案轻松做到这一点。
如果密钥是完全随机的，那么这是行不通的
如果你提到的两个字节数组是你的整个密钥，值在0-51范围内，是唯一的，a和b数组的顺序是微不足道的，我的math告诉我，只有大约2600万个可能的排列您可能正在尝试用所有可能的键的值填充地图。
在这种情况下，如果使用数组而不是HashMap并从0到25989599对其进行索引，那么从数据存储中填充和检索值当然会快得多。
我在这里迟到了，但是有一些关于大地图的评论：
- 正如在其他文章中详细讨论的，使用一个好的hashCode（），Map中的26M条目没什么大不了的。
- 然而，这里一个潜在的隐藏问题是GC对巨型地图的影响。
我假设这些地图是长期居住的。 即你填充他们，他们坚持应用程序的持续时间。 我也假设应用程序本身是很长寿的 – 就像某种服务器。
Java HashMap中的每个条目都需要三个对象：键，值和将它们连接在一起的Entry。 所以地图上的26M条目意味着26M * 3 == 78M的对象。 这是没有问题的，直到你打满了GC。 那么你有一个暂停世界的问题。 GC会查看每个78M的对象，并确定它们都是活着的。 78M +对象只是很多对象。 如果你的应用程序可以容忍偶尔很长（也许是几秒钟）的暂停，那么没有问题。 如果你试图达到任何延迟保证你可能有一个主要问题（当然，如果你想延迟保证，Java不是平台select:)）如果你的地图中的值快速stream失，你可以结束频繁的完整收集这大大地增加了这个问题。
我不知道这个问题的一个很好的解决scheme。 思路：
- 有时可能调整GC和堆大小，以“主要”防止完整的GC。
- 如果您的地图内容翻滚很多，您可以尝试Javolution的FastMap – 它可以将Entry对象集中起来，这可以降低完整收集的频率
- 你可以创build自己的映射impl，并在byte []上进行显式的内存pipe理（即通过将数百万个对象序列化成单个字节来交易cpu以获得更可预测的延迟。
- 不要在这部分中使用Java – 通过套接字与某种可预测的内存数据库通信
- 希望新的G1收集器能够帮助（主要适用于高转速的情况下）
只是一些人花了很多时间在Java中使用巨型地图的想法。
您可以尝试使用像HSQLDB这样的内存数据库。
SQLite让你在内存中使用它。
你有没有考虑过使用embedded式数据库来做到这一点。 看看Berkeley DB 。 它是开源的，现在由Oracle拥有。
它将所有东西都存储为Key-> Value对，它不是一个RDBMS。 它的目标是快速。
首先，你应该检查你是否正确使用Map，用于key的hashCode（）方法，Map的初始容量，Map的执行等等，就像很多其他的答案描述的一样。
然后我会build议使用一个分析器来查看实际发生的事情以及执行时间的花费。 例如，是否执行了数十亿次的hashCode（）方法？
如果这没有帮助，那么如何使用EHCache或memcached ？ 是的，他们是caching产品，但你可以configuration它们，以便他们有足够的容量，永远不会从caching存储器中清除任何值。
另一个select是一些比完整的SQL RDBMS更轻的数据库引擎。 就像伯克利DB ，也许。
请注意，我个人没有这些产品性能的经验，但他们可能是值得的尝试。
您可以尝试将计算的哈希码caching到关键对象。
像这样的东西：
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之后不要改变密钥的内容。
编辑：看来，caching有代码值是不值得的，当你只添加每个键一次到地图。 在其他一些情况下，这可能是有用的。
另一个海报已经指出，你的hashcode实现会导致很多的碰撞，因为你一起添加值的方式。 I'm willing to be that, if you look at the HashMap object in a debugger, you'll find that you have maybe 200 distinct hash values, with extremely long bucket chains.
If you always have values in the range 0..51, each of those values will take 6 bits to represent. If you always have 5 values, you can create a 30-bit hashcode with left-shifts and additions:
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;
The left-shift is fast, but will leave you with hashcodes that aren't evenly distributed (because 6 bits implies a range 0..63). An alternative is to multiply the hash by 51 and add each value. This still won't be perfectly distributed (eg, {2,0} and {1,52} will collide), and will be slower than the shift.
int code = a[0]; code *= 51 + a[1]; code *= 51 + b[0]; code *= 51 + b[1]; code *= 51 + b[2]; return code;
As pointed out, your hashcode implementation has too many collisions, and fixing it should result in decent performance. Moreover, caching hashCodes and implementing equals efficiently will help.
If you need to optimize even further:
By your description, there are only (52 * 51 / 2) * (52 * 51 * 50 / 6) = 29304600 different keys (of which 26000000, ie about 90%, will be present). Therefore, you can design a hash function without any collisions, and use a simple array rather than a hashmap to hold your data, reducing memory consumption and increasing lookup speed:
T[] array = new T[Key.maxHashCode]; void put(Key k, T value) { array[k.hashCode()] = value; T get(Key k) { return array[k.hashCode()]; }
(Generally, it is impossible to design an efficient, collision-free hash function that clusters well, which is why a HashMap will tolerate collisions, which incurs some overhead)
Assuming a and b are sorted, you might use the following hash function:
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;
I think this is collision-free. Proving this is left as an exercise for the mathematically inclined reader.
In Effective Java: Programming Language Guide (Java Series)
Chapter 3 you can find good rules to follow when computing hashCode().
Specially:
If the field is an array, treat it as if each element were a separate field. That is, compute a hash code for each significant element by applying these rules recursively, and combine these values per step 2.b. If every element in an array field is significant, you can use one of the Arrays.hashCode methods added in release 1.5.
In my case I want to create a map with 26 million entries. Using the standard Java HashMap the put rate becomes unbearably slow after 2-3 million insertions.
From my experiment (student project in 2009):
- I built up a Red Black Tree for 100.000 nodes from 1 to 100.000. It took 785.68 seconds (13 minutes). And I failed to build up RBTree for 1 million nodes (like your results with HashMap).
- Using "Prime Tree", my algorithm data structure. I could build up a tree/map for 10 million nodes within 21.29 seconds (RAM: 1.97Gb). Search key-value cost is O(1).
Note: "Prime Tree" works best on "continuous keys" from 1 – 10 millions. To work with keys like HashMap we need some minors adjustment.
So, what is #PrimeTree? In short, it is a tree data structure like Binary Tree, with branches numbers are prime numbers (instead of "2"-binary).
Allocate a large map in the beginning. If you know it will have 26 million entries and you have the memory for it, do a new HashMap(30000000) .
Are you sure, you have enough memory for 26 million entries with 26 million keys and values? This sounds like a lot memory to me. Are you sure that the garbage collection is doing still fine at your 2 to 3 million mark? I could imagine that as a bottleneck.
You could try two things:
-
Make your
hashCodemethod return something simpler and more effective such as a consecutive int -
Initialize your map as:
Map map = new HashMap( 30000000, .95f );
Those two actions will reduce tremendously the amount of rehashing the structure is doing, and are pretty easy to test I think.
If that doesn't work, consider using a different storage such a RDBMS.
编辑
Is strange that setting the initial capacity reduce the performance in your case.
See from the javadocs :
If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
I made a microbeachmark ( which is not by anymeans definitive but at least proves this point )
$cat Huge*java import java.util.*; public class Huge { 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.*; public class 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 Huge real 0m16.207s user 0m14.761s sys 0m1.377s $time java -Xms2g -Xmx2g Huge2 real 0m21.781s user 0m20.045s sys 0m1.656s $
So, using the initial capacity drops from 21s to 16s because of the rehasing. That leave us with your hashCode method as an "area of opportunity" 😉
编辑
Is not the HashMap
As per your last edition.
I think you should really profile your application and see where it the memory/cpu is being consumed.
I have created a class implementing your same hashCode
That hash code give millions of collisions, then the entries in the HashMap is reduced dramatically.
I pass from 21s, 16s in my previous test to 10s and 8s. The reason is because the hashCode provokes a high number of collisions and you are not storing the 26M objects you think but a much significant lower number ( about 20k I would say ) So:
The problems IS NOT THE HASHMAP is somewhere else in your code.
It is about time to get a profiler and find out where. I would think it is on the creation of the item or probably you're writing to disk or receiving data from the network.
Here's my implementation of your class.
note I didn't use a 0-51 range as you did but -126 to 127 for my values and admits repeated, that's because I did this test before you updated your question
The only difference is that your class will have more collisions thus less items stored in the 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 ); } }
Using this class has Key for the previous program
map.put( new Item() , i );
gives me:
real 0m11.188s user 0m10.784s sys 0m0.261s real 0m9.348s user 0m9.071s sys 0m0.161s
Maybe try using if you need it to be synchronized
http://commons.apache.org/collections/api/org/apache/commons/collections/FastHashMap.html
I did a small test a while back with a list vs a hashmap, funny thing was iterating through the list and finding the object took the same amount of time in milliseconds as using the hashmaps get function… just an fyi. Oh yeah memory is a big issue when working with hashmaps that size.
The popular hashing methods used are not really very good for large sets and, as pointed out above, the hash used is particularly bad. Better is to use a hash algorithm with high mixing and coverage such as BuzHash (sample implementation at http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm )
