-Flyぁ梦-

突然有这么个想法，就写了段代码测试了下。在单线程下对Java里所有Map的性能测试，包括HashMap、Hashtable、LinkedHashMap、IdentityMap、TreeMap，没有测试WeakHashMap。

数据为<Integer, Integer>，范围在0~1千万，共1百万对数据，由Python的random.randint()自动生成。

测试的性能包括写入（put）、随机读（get）和遍历（foreach语法），也是Map这个数据结构最常用的三个操作。其中写入就是将这1百万对测试数据依次put一遍，随机读就是在上一步写入之后再按顺序get一遍。数据显示最后Map大小都为995012（当然IdentityMap的size是1百万），就是有近5000条重复的key。

下面是笔记本上跑出的数据：

Java中各个Map的性能测试（T400笔记本，酷睿P8700/2.46G）数据表

然后又在实验室的台式电脑上跑了一下测试，基本结果类似。

Java中各个Map的性能测试（台式机，i3/4G）数据表

与上一份数据相比，区别如下：

• HashMap和Hashtable的操作结果类似，但数据基本很接近，差异不大
• IdentityHashMap的写入速度比HashMap慢了一些，读的速度依旧最快，foreach虽然仍然很慢但基本和TreeMap一致，没有太夸张

从上面数据上可以看出一些有趣的地方，大部分都很好理解，倒是有2处不太理解呢。

HashMap

HashMap不愧为精心设计的最常用的Map，读写性能基本上都是最优秀的，即使某项不是最最优秀的也相差无多，综合性能是毫无争议的最高。

这边也谈谈HashMap源码中对Object.hashCode()再次hash的内部函数：static int hash(int h) {}。之前看源码的时候也只是知道它二次hash的目的以及全部二进制抑或和移位的实现方法，代码原理完全没看懂，而且也没有深究二次hash的原因直到在面试天猫的时候被问到了，倒是傻了一下含糊了说了一些猜测的原因，提高hash分布均匀这样的。

这里附上源码中对此函数的注释，不是太好理解。个人理解：这个函数用来避免质量差的hashCode，因为HashMap的hash表是2的整数倍大小的，普通的hashCode在低bit位的冲突会发生的特别多。

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions. This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits.
 */

Hashtable

相信应该没有多少代码会用到Hashtable了，但不得不惊讶于其单论写入（put）性能竟然优于HashMap，虽然快了没多少基本可以忽略，但比较与读和遍历上要慢上一些，这不能不说很神奇，而且从源码层面一直没怎么看出来原因在哪里。因为synchronized修饰包含占用锁的消耗，速度慢一些是好理解的，当然代码上比HashMap要简单一些调用的子函数也少一些但这不足以使得性能会优于HashMap啊，不得其解，求指导~

LinkedHashMap

LinkedHashMap从HashMap继承而来，自然速度会慢一些些。主要重写了内部addEntry()方法（主要写操作put时候被调用）来维护插入顺序链表，所以写入速度比HashMap慢是好理解的；默认内部变量accessOrder == false表示不会在get()方法调用时使用LRU策略修改链表，所以默认随机读的性能和HashMap完全一致；至于foreach遍历，HashMap走的是hash table数组，LinkedHashMap走的是链表，指针操作比数组操作慢了一些。

IdentityHashMap

IdentityHashMap和以上几个Map使用的冲突策略不同为线性探测法，所有的冲突操作由邻接链表的指针操作转化为数组操作，所以随机读速度比HashMap快了不少，至于写的话大概差不多（两份测试数据不一致），但是foreach遍历却这么慢有点想不通了源代码也没看出所以然来。

TreeMap

这个就不用多说了，时间复杂度都不一样的，实现巨复杂的红黑树，当然速度非常慢了，不过它的foreach遍历效率相对而言是比较高的，因为Tree中邻接节点是有连接关系的，和其他Map相差并不多。

—————————分割线—————————

再把上面提到的2个问题列举下：

1. 为什么Hashtable单论写入速度比HashMap快？（不同机器、JVM、JDK版本会导致运行结果差异，所以问题意义不大）
2. 为什么IdentityHashMap的foreach遍历速度却很慢？