原文：http://www.cnblogs.com/ygj0930/p/6543901.html

一：ConcurrentSkipListMap

          TreeMap使用红黑树按照key的顺序（自然顺序、自定义顺序）来使得键值对有序存储_，_但是只能在单线程下安全使用；多线程下想要使键值对按照key的顺序来存储，则需要使用ConcurrentSkipListMap。

           ConcurrentSkipListMap的底层是通过跳表来实现的。跳表是一个链表，但是通过使用“跳跃式”查找的方式使得插入、读取数据时复杂度变成了O（logn）。

           跳表（SkipList）：使用“空间换时间”的算法，令链表的每个结点不仅记录next结点位置，还可以按照level层级分别记录后继第level个结点。在查找时，首先按照层级查找，比如：当前跳表最高层级为3，即每个结点中不仅记录了next结点（层级1），还记录了next的next（层级2）、next的next的next（层级3）结点。现在查找一个结点，则从头结点开始先按高层级开始查：head->head的next的next的next->。。。直到找到结点或者当前结点q的值大于所查结点，则此时当前查找层级的q的前一节点p开始，在p~q之间进行下一层级（隔1个结点）的查找......直到最终迫近、找到结点。此法使用的就是“先大步查找确定范围，再逐渐缩小迫近”的思想进行的查找。

 二：ConcurrentHashMap【本文concurrentHashMap是jdk1.7中的实现,jdk1.8中使用的不是Segment，特此说明】

        快速存取<Key, Value>键值对使用HashMap；多线程并发存取<Key, Value>键值对使用ConcurrentHashMap；

        我们知道，HashTable和和Collections类中提供的同步HashTable是线程安全的，但是他们线程安全是通过在进行读写操作时对整个map加锁来实现的，故此性能比较低。那既然是由于锁粒度（加锁的范围叫锁粒度）太大造成的性能低下，可不可以从锁粒度着手去改良呢？由此，就引申出了ConcurrentHashMap。

        ConcurrentHashMap采取了“锁分段”技术来细化锁的粒度：把整个map划分为一系列被成为segment的组成单元，一个segment相当于一个小的hashtable。这样，加锁的对象就从整个map变成了一个更小的范围——一个segment。ConcurrentHashMap线程安全并且提高性能原因就在于：对map中的读是并发的，无需加锁；只有在put、remove操作时才加锁，而加锁仅是对需要操作的segment加锁，不会影响其他segment的读写，由此，不同的segment之间可以并发使用，极大地提高了性能。

        1：结构分析