Java 里多个 Map 的性能比较（TreeMap、 HashMap、ConcurrentSkipListMap） 问题： 比较 Java 原生的 3 种 Map 的效率。 1. TreeMap 2. HashMap 3. ConcurrentSkipListMap 结果： 模拟 150W 以内海量数据的插入和查找，通过增加和查找两方面的性能测试，结果如下： 插入 10W 50W 100W 150W 62 ms 227 ms 433 ms 689ms 查找（在 100W 数据量中） 0-1W 7 ms 0-25W 0-50W 80 ms 119 ms 18 ms 93 ms 217 ms 303ms 2 ms 13 ms 45 ms 33 ms 228 ms 429 ms 584 ms 4ms 34 ms 61 ms Map 类型 Concurrent SkipListMap HashMap TreeMap 分析说明 

图 1- 1 常数和 logn 函数效率对比示例图（横轴-n 数据量，纵轴-f(n)时间） TreeMap 基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到 O(log n)。 HashMap 是基于散列表实现的，时间复杂度平均能达到 O(1)。 ConcurrentSkipListMap 是基于跳表实现的，时间复杂度平均能达到 O(log n)。 如图所示： 当数据量增加时，HashMap 会引起散列冲突，解决冲突需要多花费一些时间代价，故在 f(n)=1 向上浮 动。 随着数据量的增加，HashMap 的时间花费小且稳定，在单线程的环境下比 TreeMap 和 ConcurrentSkipListMap 在插入和查找上有很大的优势。 (1) TreeMap 与 HashMap 相比较 Ø HashMap 里面存入的键值对在取出的时候是随机的，它根据键的 HashCode 值存储数据,根据键可以 直接获取它的值，具有很快的访问速度。在 Map 中插入、删除和定位元素，HashMap 是最好的选择。 Ø TreeMap 取出来的是排序后的键值对。插入、删除需要维护平衡会牺牲一些效率。但如果要按自然顺 序或自定义顺序遍历键，那么 TreeMap 会更好。 本测试增加和查找功能，HashMap 比 TreeMap 的效率要高。 

(2) TreeMap 与 ConcurrentSkipListMap 相比较 Ø Skip list(跳表）是一种可以代替平衡树的数据结构，默认是按照 Key 值升序的。Skip list 让已排序的 数据分布在多层链表中，以 0-1 随机数决定一个数据的向上攀升与否，通过“空间来换取时间”的一个算法， 在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了 效率。 从概率上保持数据结构的平衡比显示的保持数据结构平衡要简单的多。对于大多数应用，用 Skip list 要比 用树算法相对简单。由于 Skip list 比较简单，实现起来会比较容易，虽然和平衡树有着相同的时间复杂度 (O(logn)),但是 skip list 的常数项会相对小很多。Skip list 在空间上也比较节省。一个节点平均只需要 1.333 个指针（甚至更少）。 图 1-2 Skip list 结构图（以 7,14,21,32,37,71,85 序列为例） Skip list 的性质 (1) 由很多层结构组成，level 是通过一定的概率随机产生的。 (2) 每一层都是一个有序的链表，默认是升序，也可以根据创建映射时所提供的 Comparator 进行排序， 具体取决于使用的构造方法。 (3) 最底层(Level 1)的链表包含所有元素。 (4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。 (5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。 Ø ConcurrentSkipListMap 具有 Skip list 的性质 ，并且适用于大规模数据的并发 访问。多个线程可以安全地并发执行插入、移除、更新和访问操作。与其他有锁机制的数据 结构在巨大的压力下相比有优势。 

Ø TreeMap 插入数据时平衡树采用严格的旋转（比如平衡二叉树有左旋右旋）来保证平衡， 因此 Skip list 比较容易实现，而且相比平衡树有着较高的运行效率。 本测试的增加功能，ConcurrentSkipListMap 和 TreeMap 效率相差不大。 查找功能在 50W 数据量以后，TreeMap 更有效率，因为 ConcurrentSkipListMap 自带锁机制，会占用 一些效率，但对于多线程并发的环境下，ConcurrentSkipListMap 的效率会比 Treep 要好的。 本测试查找方法使用 Map 的 get 方法，循环、离散获取。对于 ConcurrentSkipListMap， 获得顺序片段，可用 subMap()方法，提取 50w 的子序列只需要 1ms，具有巨大优势。 SkipListMap 的范围查询效率比 HashMap 和 TreeMap 效率都要高。 (3) SkipList 参考资料 [1] http://stackoverflow.com/questions/256511/skip-list-vs-binary-tre e [2] http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html [3] http://imtinx.iteye.com/blog/1291165