大型HashMap评估：JDK、FastUtil、Goldman Sachs、HPPC、Koloboke与Trove

介绍

这篇文章将会介绍以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

tests.maptests.primitive.FastUtilMapTest	int[] keys, int[] values, boolean[] used
tests.maptests.primitive.GsMutableMapTest	int[] keys, int[] values
tests.maptests.primitive.HftcMutableMapTest	long[] (key-low bits, value-high bits)
tests.maptests.primitive.HppcMapTest	int[] keys, int[] values, boolean[] allocated
tests.maptests.primitive.TroveMapTest	int[] _set, int[] _values, byte[] _states

如你所见，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+）的情况下更慢。