java.util中几个Map的性能测试
突然有这么个想法，就写了段代码测试了下。在单线程下对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）数据表
Map | Run Time(ms) | Type[order] |
|---|---|---|
HashMap | 744, 739, 736, 741, 741 | Put[3] |
220, 225, 228, 225, 221 | Get[2] | |
239, 218, 213, 209, 210 | Foreach[1] | |
Hashtable | 694, 726, 699, 685, 686 | Put[2] |
264, 272, 272, 266, 264 | Get[4] | |
331, 291, 284, 295, 286 | Foreach[2] | |
LinkedHashMap | 814, 802, 817, 825, 818 | Put[4] |
227, 229, 218, 223, 227 | Get[2] | |
481, 466, 472, 475, 473 | Foreach[4] | |
IdentityHashMap | 649, 660, 658, 662, 659 | Put[1] |
181, 186, 188, 191, 182 | Get[1] | |
754, 774, 773, 774, 773 | Foreach[5] | |
TreeMap | 1880, 1879, 1876 | Put[5] |
1229, 1234, 1270 | Get[5] | |
420, 403, 399, 401, 401 | Foreach[3] |
然后又在实验室的台式电脑上跑了一下测试，基本结果类似。
Java中各个Map的性能测试（台式机，i3/4G）数据表
Map | Run Time(ms) | Type[order] |
|---|---|---|
HashMap | 422, 423, 438 | Put[2] |
234, 218, 218 | Get[2] | |
250, 234, 234 | Foreach[1] | |
Hashtable | 407, 422, 406 | Put[1] |
249, 250, 250 | Get[4] | |
250, 250, 249 | Foreach[1] | |
LinkedHashMap | 610, 594, 594 | Put[4] |
234, 234, 234 | Get[3] | |
265, 280, 280 | Foreach[3] | |
IdentityHashMap | 532, 516, 531 | Put[3] |
172, 172, 172 | Get[1] | |
327, 328, 312 | Foreach[4] | |
TreeMap | 1437, 1421, 1431 | Put[5] |
1185, 1185, 1186 | Get[5] | |
327, 328, 343 | Foreach[4] |
与上一份数据相比，区别如下：
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个问题列举下：
为什么Hashtable单论写入速度比HashMap快？（不同机器、JVM、JDK版本会导致运行结果差异，所以问题意义不大）
为什么IdentityHashMap的foreach遍历速度却很慢？
发博文后，辛苦串叔拿着测试代码和数据在不同的JVM和不同JDK的版本下进行测试，发现结果并不是太一致，所以纠结这快一点慢一点没有太大的意义，可能就是本身Java代码和JVM实现的问题了，所以不再深究啦，大致了解这么一个情况就可以啦。