介绍

这篇文章将会介绍以JDK中HashMap作为标准的五种知名库的hash map实现，并逐一测试：

• 原始数据类型到原始数据类型的映射
• 原始数据类型到对象的映射
• 对象到原始数据类型的映射
• 对象到对象的映射（JDK仅在这部分出现）

这篇文章将会综述一个测试——使用一组随机key进行map读取访问（给定大小的待测试Collection共用同一组key）。

我们也会关注这些集合内的数据存储方式和一些颇为有趣的实现细节。

评估对象

JDK 8

在这个测试中，JDK中的HashMap是最古老的hash map实现。最近它有两个主要的更新——一个在Java 7u40版本中对于空map的共享的底层存储，以及在Java 8中将底层hash bucket链接成为哈希树（改进更差情况下的性能）。

FastUtil 6.5.15

FastUtil为开发者提供了一套涵盖上述四个方面的API（包括所有基本类型和对象的组合）。除了那些，这也有一些其它类型的映射适用于每一个参数的类型组合：数组映射、AVL树映射和RB树映射。然后，这篇文章中我们只对hash映射感兴趣。

Goldman Sachs Collections 5.1.0

高盛集团在三年前公开了他的集合库的源代码。在我看来，（如果你有需要）这个库提供最宽泛的开箱即用的集合。你应该注意你需要的不仅仅是一个hash map、tree map和你工作所需的其它东西。本文的目标，GS collections为每一个hash map提供了一个常规的、同步的和不可修改的版本。最后两个仅仅提供了常规的映射，所以没有什么性能优势。

HPPC 0.6.1

HPPC为所有原始数据类型提供了数组列表、数组队列、哈希集合和哈希映射。HPPC为原始数据类型key提供了普通的hash map，并且为object key提供了普通的和带标识的hash map。

Koloboke 0.6

Koloboke是这篇文章中最年轻的库。它是Roman Leventov开发的OpenHFT工程中的一部分。目前该库为所有原始数据类型或对象的组合提供了hash map和hash set。这个库最近被重命名成了HFTC，因此在一些我测试的实例中会使用一些旧的库名。

Trove 3.0.3

Trove发布了很长的时间且十分稳定。不幸的是，现在这个项目已经没有进一步的开发。Trove为所有的原始数据类型、对象的组合提供了链表、栈、队列、hash set和hash map。我曾经写过一篇关于Trove的文章。

数据存储的实现和测试

本文将着眼于4种不同的map：

1. int-int
2. int-Integer
3. Integer-int
4. Integer-Integer

让我们来看看这些map各自是如何存储数据的。我们将参考测试命名而不是实际实现的名字。因为许多这些实现调用方式十分相似，同时也不容易通过命名来区分。在了解实现细节之后，我们将验证它们是如何影响实际的测试结果。

我们将会使用JMH 1.0来测试。这里是测试描述：遍历所有大小在（10K、100K、1M、10M和100M）的映射（外循环）从而生成一组随机key（它们将在给定大小的映射中进行测试），然后运行每一个测试来实现映射（内循环）。每一个测试将会运行1亿次 / map_size（以便我们对每个测试实例调用map.get 1亿次）。

1. 准备：设置好一组int key和所需的填充因子
2. 初始化一个map给定填充因子和容量=key的数量
3. 填充map的key，设置values = keys
4. 存储一个key数组引用或者转换为Integer[]型用以测试object key（否则会使用相同的key）
5. 所有的测试几乎是相同的——得到key数组所存储的值然后再使用这些值，这样JVM将不会优化你的代码：

public int runRandomTest() {      int res = 0;      for ( int i = 0; i < m_keys.length; ++i )          res = res ^ m_map.get( m_keys[ i ] );      return res;  }

int-int

如你所见，FastUtil、HPPC和Trove使用相同的存储，所以可以预见它们有相同的性能。

处理GS Collections和Koloboke中空单元和被删除的单元

GS collections只使用了键值数组。如果你曾经接触过hash map的实现应该知道，一个map应该至少可以从占用的集合中区分空单元（一些映射也使用“被删除的单元”来标记）。如果没有额外存储，你要怎样实现这些功能呢？GS IntIntHashMap使用了一个包括key=0（空单元）和key=1（被删除单元）的合作哨兵对象（sentinel object）。所有在keys=0或者1上的操作都在这个哨兵对象上完成。这样，一个对象允许GSIntIntHashMap来使用复杂度为O(1)的存储来标记而不是使用O（容量）来标记。这样只需访问2个存储单元而不是3个，操作起来更快速。

Koloboke int-int map（map的实际名称隐藏在工厂类中且可能变化）的实现更进一步。首先，一些例子中它使用更长的数据类型数组作为存储，这能让键值保持在一个元素中。int-int map是这种方法的一个例子：一个key被存储在long类型的低32位，值则被存放在高32位上。在这样的布局下，查找冷门数据时只会出现1次缓存未命中。GS collections可能会出现2次不中，其他情况可能会有3次。

Koloboke使用了一种完全不同的技术来标记没有使用的条目。当一个map初始化后，它随机选择一个int，使用它作为一个自由的单元标记。如果你尝试插入一个key = 自由单元标记，它就会获取另一个map中不存在的随机值。这意味着Koloboke仅仅4使用了个字节就极其高效地处理了空节点。

一般而言，这种方式不会强加任何性能上的损失，除非你的映射大小非常接近一个给定数据类型的上限。你可能会想，如果在更小的key数据类型情况下会发生什么？如果想要添加所有数据类型进入map，那么将会得到一个在koloboke-api库中定义的HashOverflowException。可以使用以下这些测试来重现这种情况：

HashByteIntMap m = HashByteIntMaps.newMutableMap( 256 );  for ( int i = Byte.MIN_VALUE; i < Byte.MAX_VALUE; ++i )  {      final byte key = (byte) i;      m.put( key, i );  }  m.put( Byte.MAX_VALUE, 127 );   //exception will be thrown here  System.out.println( m.size() );

然而，在现实生活中这还不算问题。如果你想将每个或者大多数byte、char、short映射到一些值的话，最好使用key索引下的值类型数组。

int-int测试结果

每个测试部分将以结果数据表开始，之后配有一幅图。表中的第一行是map大小，所有测试结果单位为毫秒。

如你所见，这些函数库明显的分成了四组（从快至慢）：

1. Koloboke结果最好：使用long[]类型来存储和一个不错的技巧，将一个随机自由的单元值复制给结果。Koloboke collections所有的3个版本都得到完全相同的结果（这并不意味着在其它测试中它们会一样得快）。
2. 用GS collections的实现速度排名是第二：使用2个数组而不是3个在这里获得了不错的代码质量。
3. FastUtil 和 HPPC性能表现完全相同的（相差不到不到2%）。
4. 测试中Trove的实现最慢：在大多数映射的情况下，大概比Koloboke慢两倍。在巨型映射（10M+）的情况下更慢。

int-Object

tests.maptests.prim_object.FastUtilIntObjectMapTest	int[] key, Object[] value, boolean[] used
tests.maptests.prim_object.GsIntObjectMapTest	int[] keys, Object[] values
tests.maptests.prim_object.HftcIntObjectMapTest	int[] keys, Object[] values
tests.maptests.prim_object.HppcIntObjectMapTest	int[] keys, Object[] values, boolean[] allocated
tests.maptests.prim_object.TroveIntObjectMapTest	int[] _set, Object[] _values, byte[] _states

不出意外，FastUtil、HPPC 和 Trove使用了3个数组（包括一个单元状态的数组）。GS collections 和 Koloboke使用了2个数组，这个技巧类似于上面列出的特殊情况。

int-Object测试结果

本次测试结果分三组（从快至慢）：

1. Koloboke只使用了2个数组所以是最快的，对于空的单元而言代码更简单。
2. FastUtil 和 HPPC紧随GS collections身后（它们没有尽力去发挥2个存储数组的优势而是使用了3个数组）。在不同的测试结果下它们略有不同，但彼此非常接近。
3. Trove又是最慢的那个，比Koloboke要慢1.5至2倍。

Object-int

tests.maptests.object_prim.FastUtilObjectIntMapTest	Object[] key, int[] value, boolean[] used
tests.maptests.object_prim.GsObjectIntMapTest	Object[] keys, int[] values
tests.maptests.object_prim.HftcObjectIntMapTest	Object[] keys, int[] values
tests.maptests.object_prim.HppcObjectIntMapTest	Object[] keys, int[] values, boolean[] allocated
tests.maptests.object_prim.TroveObjectIntMapTest	Object[] _set, int[] _values

对于Object key，FastUtil和HPPC使用了第三个数组。这看上去并不是什么好主意。因为你可以允许使用一个私有的哨兵对象作为object key的一个标志。实际上它的性能略差。

GS collections、Koloboke 和 Trove使用的是2个数组，所以有理由期待它们会快一点。

Object-int测试结果

这里分三组再次进行测试，但是不像之前那样特意区分（由快到慢）：

1. Koloboke略快于GS collections，但是GS collections在10K和10M大小上的测试略胜一筹。
2. Trove和HPPC紧随其后。
3. FastUtil是本次测试最慢的那个——它比Koloboke慢2-2.5倍。有趣的是，虽然使用的都是底层数组=3的情况，但是HPPC的实现明显比FastUtil要快。

现在，对这些map的实现了解之后。让我们开始测试这些map的性能。

Object-Object测试结果

Object-Object测试结果更为复杂。

1. 通常情况下，Koloboke比JDKHashMap更快。但除了超大型map，其他情况即使Koloboke胜出，速度优势也不是那么明显。
2. 对于大型和超大map，GS Collections已经非常接近Koloboke 和 JDKmaps的性能，但对于小型map测试结果相去甚远了。
3. 最后，FastUtil、HPPC和Trove对于各种大小的map下性能几乎相同。

10亿项测试

我将创建一个大小为10亿项（entry 键值对），然后看看这些集合会发生什么。测试中设置因子为0.5，这意味着所有这些映射必须分配一个非常大的数组，允许的最大长度接近2³¹。

FastUtil、HPPC和GS collections因为各种异常失败了(并不是因为OOM——我为这次测试分配了110G的内存)。

Koloboke、Trove和JDK设法通过了这些测试。不幸的是，这些测试在JMH上却没有成功运行。他们运行了另外一套代码。

以上就是测试的结果（如果需要和之前的结果进行比较，需要把之前的结果乘以10。因为所有之前的结果总共调用了100M次map.get）：

tests.maptests.primitive.HftcMutableMapTest : time = 95.05 sec  tests.maptests.primitive.TroveMapTest : time = 235.062 sec    tests.maptests.prim_object.HftcIntObjectMapTest : time = 216.361 sec  tests.maptests.prim_object.TroveIntObjectMapTest : time = 304.019 sec    tests.maptests.object_prim.HftcObjectIntMapTest : time = 335.139 sec  tests.maptests.object_prim.TroveObjectIntMapTest : time = 217.412 sec    tests.maptests.object.HftcMutableObjTest : time = 272.792 sec  tests.maptests.object.JdkMapTest : time = 163.335 sec  tests.maptests.object.TroveObjMapTest : time = 239.133 sec

如你所见，Koloboke在primitive-primitive的转化上赢得了很大的优势。在primitive-to-object的转换测试方面也明显快了不少。

在object-primitive转换测试中，Koloboke就明显比Trove用时要久。

最后，对于object-object的转换测试，我必须改变Koloboke map的初始化代码，因为一旦我添加5亿个元素性能就开始迅速下降：

HashObjObjMaps.getDefaultFactory().withHashConfig(HashConfig.fromLoads(0.5, 0.6, 0.8)).newMutableMap(keys.length)

Koloboke 2.0？

Roma Leventov刚刚宣布他正在考虑建一个更新更快的Koloboke库，但是这需要你的反馈。你能帮他给出一点建议吗？

总结

• Koloboke已经被证明是hash map实现最快也是存储最高效的库，但是它还刚刚诞生并没有被广泛使用，难道你不想试试？
• 如果你正在寻找更加稳定和成熟的库（或者愿意牺牲部分性能），你或许应该看看GS collections library。与Koloboke不同，GS Collection给了你一个更加宽泛的开箱即用的集合。

源代码

文章源代码