JDK源码学习(5)-Map的性能比较，HashMap和TreeMap，ConcurrentSkipListMap

在之前已经学习过：

JDK源码学习(1)-HashMap源码分析,HashMap与HashTable的差别

JDK源码学习(2)-TreeMap源码分析

这篇文章对jdk提供的Map实现类的性能进行比较：

- 问题：

比较Java原生的 3种Map的效率。

1.TreeMap

2.HashMap

3.ConcurrentSkipListMap

- 结果

插入和删除操作的性能如下：

- 分析

• TreeMap基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到O(log n)。
• HashMap是基于散列表实现的，时间复杂度平均能达到O(1)。
• ConcurrentSkipListMap是基于跳表实现的，时间复杂度平均能达到O(log n)。

  

  图1- 1常数和logn函数效率对比示例图（横轴-n数据量，纵轴-f(n)时间）

如图所示：

当数据量增加时，HashMap会引起散列冲突，解决冲突需要多花费一些时间代价，故在f(n)=1向上浮动。随着数据量的增加，HashMap的时间花费小且稳定，在单线程的环境下比TreeMap和ConcurrentSkipListMap在插入和查找上有很大的优势。

1. TreeMap与HashMap相比较

• HashMap里面存入的键值对在取出的时候是随机的，它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。在Map中插入、删除和定位元素HashMap是最好的选择。
• TreeMap取出来的是排序后的键值对。插入、删除需要维护平衡会牺牲一些效率。但如果要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。

2.TreeMap与ConcurrentSkipListMap相比较

• Skip list(跳表）是一种可以代替平衡树的数据结构，默认是按照Key值升序的。Skiplist让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，通过“空间来换取时间”的一个算法，在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。
• 从概率上保持数据结构的平衡比显示的保持数据结构平衡要简单的多。对于大多数应用，用Skip list要比用树算法相对简单。由于Skiplist比较简单，实现起来会比较容易，虽然和平衡树有着相同的时间复杂度(O(logn)),但是skiplist的常数项会相对小很多。Skip list在空间上也比较节省。一个节点平均只需要1.333个指针（甚至更少）

图1-2 Skip list结构图（以7,14,21,32,37,71,85序列为例）

• ConcurrentSkipListMap具有Skip list的性质，并且适用于大规模数据的并发访问。多个线程可以安全地并发执行插入、移除、更新和访问操作。与其他有锁机制的数据结构在巨大的压力下相比有优势。
• TreeMap插入数据时平衡树采用严格的旋转（比如平衡二叉树有左旋右旋）来保证平衡，因此Skip list比较容易实现，而且相比平衡树有着较高的运行效率。
• 本测试的增加功能，ConcurrentSkipListMap和TreeMap效率相差不大。查找功能在50W数据量以后，TreeMap更有效率，因为ConcurrentSkipListMap自带锁机制，会占用一些效率，但对于多线程并发的环境下，ConcurrentSkipListMap的效率会比Treep要好的。

本测试查找方法使用Map的get方法，循环、离散获取。对于ConcurrentSkipListMap，获得顺序片段，可用subMap()方法，提取50w的子序列只需要1ms，具有巨大优势。 SkipListMap的范围查询效率比HashMap和TreeMap效率都要高。

Skip list的性质

1. 由很多层结构组成，level是通过一定的概率随机产生的。
2. 每一层都是一个有序的链表，默认是升序，也可以根据创建映射时所提供的Comparator进行排序，具体取决于使用的构造方法。
3. 最底层(Level 1)的链表包含所有元素。
4. 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现。
5. 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

SkipList 参考资料

[1] http://stackoverflow.com/questions/256511/skip-list-vs-binary-tree

[2] http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html

[3] http://imtinx.iteye.com/blog/1291165