java.util中几个Map的性能测试

五月 27th, 2013 6,920 留下评论 阅读评论

突然有这么个想法,就写了段代码测试了下。在单线程下对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个问题列举下:

  1. 为什么Hashtable单论写入速度比HashMap快?(不同机器、JVM、JDK版本会导致运行结果差异,所以问题意义不大
  2. 为什么IdentityHashMap的foreach遍历速度却很慢?
发博文后,辛苦串叔拿着测试代码和数据在不同的JVM和不同JDK的版本下进行测试,发现结果并不是太一致,所以纠结这快一点慢一点没有太大的意义,可能就是本身Java代码和JVM实现的问题了,所以不再深究啦,大致了解这么一个情况就可以啦。
Categories: Java, 数据结构和算法 标签:
  1. 李钊 | #沙发
    六月 5th, 2013 13:03

    求加友情链接啊,刚建的新站blog.bluefancy.com

    • 好…你咋把我名添加到”页面”里了…多多写博客呗~

icon_wink.gif icon_neutral.gif icon_mad.gif icon_twisted.gif icon_smile.gif icon_eek.gif icon_sad.gif icon_rolleyes.gif icon_razz.gif icon_redface.gif icon_surprised.gif icon_mrgreen.gif icon_lol.gif icon_idea.gif icon_biggrin.gif icon_evil.gif icon_cry.gif icon_cool.gif icon_arrow.gif icon_confused.gif icon_question.gif icon_exclaim.gif