常用JFC主要区别梳理

        应用开发中集合就像水一样离不开，这里对ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、Hashtable、ConcurrentHashMap和TreeMap的关系做一点对比，虽然这些类型都是很常用的，基本上也都大概了解，但一直没有深入理解，现在就做一些梳理，以便更准确的应用。

1. 数据存储结构的区别
        首先，大家都知道List、Set、Map这3个大类的区别，当然是很明显的，就不再重复了。
        List里面最常用的ArrayList就是线性连续列表，底层用的数组，默认或提供一个容量(capacity)参数，初始化时就创建一个capacity大小的数组，当长度超过capacity*加载因子(loadFactory)并且小于最大长度时，就会创建一个容量翻倍的新数组，然后把原数组存储的数据拷贝到新数组，其实很多容器的实现都是基于类似的方式的。LinkedList名字就很明显，是链表实现的列表，具体是一个双向链表，其他没有什么特别的。
Map是特别重要的存储容器，键值对结构经常是特别有用，常用类型也比较多：HashMap、Hashtable、ConcurrentHashMap和TreeMap，各自都有很大区别。从底层数据结构来看，主要就是分两大类，一类是二叉树结构的TreeMap，另一类是散列表结构，但其中的ConcurrentHashMap其实又有一些不一样，等会儿再来说明,不过有人会说明明有一个LinkedHashMap，看名字就知道是链式结构嘛，其实看名字也会发现，主体还是HashMap，其实也确实是继承自HashMap的，仔细阅读源码，会发现这个链式结构是在底层散列存储的基础上再次封装实现的,LinkedHashMap.Entry继承自HashMap.Entry，扩展了双向链接字段，并在原操作(如get、put、remove等等)基础上再进行链接操作，所以也会比HashMap稍微慢一点点(并不精准的测试了一下，各操作大约平均慢12%左右，仅作参考)。TreeMap是典型的二叉树实现，按照默认(自然)或指定(Comparator)顺序排列，例如查询就是二分查找，从根节点开始，通过比较确定一个子数，如此遍历。散列结构就是按散列值排序，最底层其实都是数组+链表，用数组来存放对应散列值(键的散列值)的Entry(键值对元素，带有链接指针next)链表，如下图。

capacity取默认或设定值，当put一个Entry时，先计算key的hash(只有Hashtable是采用原始的hashCode，其他都对hashCode做了再处理)，然后对capacity取模作为数组index，取出table对应元素，遍历链表，如果没有相等(不相等的定义是hashCode不相等或者equals返回false)对象，就存放在链表末尾。如果元素总数大于capacity*loadFactory，同样也要扩大table，一般是加倍，然后把原有全部Entry的hashCode重新取模重新存放(ConcurrentHashMap较特别，不是用原有Entry对象，而是直接克隆新的Entry，这与快速线程安全实现相关)。可能会觉得比较奇怪，这样的结构不应该只能存放capacity个Entry，如果所有元素散列值取模是一样的，岂不全部集中在table的一个index上？事实的确是这样的，可以自己写个程序重写hashCode验证一下，但是，在实际应用中，散列值是一种相对随机的数值，因此在这个结构中，Entry实际是相对平均的分布在个index中。又有人可能觉得奇怪，这样的结构容量可不止capacity了，为啥还要扩展？这个我想主要是为了算法效率，链表越短，遍历也越快。当然这只是散列结构的基础形式，具体来说ConcurrentHashMap相对就更特别一点，在此基础上引入分段的概念，这也是为了加互斥锁能更细粒度，加大线程并发。
        最后再来看看Set，以前一直觉得Set一个节点只有一个数据，理应比Map结构简单，仔细一看才发现，JDK的Set实现是基于Map的封装，也就是说，底层是通过Map存储数据的，只是再提供特定的访问接口屏蔽Map结构，具体存储键值对只用到了key，value采用的是一个常量。HashSet就是持有了一个HashMap对象，LinkedHashSet类似LinkedHashMap，继承自HashSet，并且初始化时将HashMap创建成了LinkedHashMap实例，其他的具体是现就比较简单，不需要细说了，所以，也可以预见，Set虽然看起来比Map简单，但速度是基本一致的，实测也确实如此，在ns级差别也可忽略不计。

2. 线程安全(thread-safe)
        都知道HashMap和TreeMap是不安全的，Hashtable和ConcurrentHashMap是线程安全的，ConcurrentHashMap比Hashtable速度快。具体来看保证并发访问安全的实现，Hashtable和ConcurrentHashMap确大有不同。
        Javadoc中明确说明Hashtable is synchronized，可以从Hashtable的源码中看到，读写相关方法（如：get、put、remove、clone等等），全部采用synchronized关键字进行方法同步，这样效率肯定是最低的。在文档中也提到，Hashtable是较早的实现，现在应当使用ConcurrentHashMap替代。如果使用Collections中一系列转同步集合的方法，也是使用加 synchronized 关键字，不过是包装的块同步不是方法同步。
        ConcurrentHashMap文档中写到“This class obeys the same functional specification as java.util.Hashtable”，可见ConcurrentHashMap定位就是用来替代Hashtable的。可以看到ConcurrentHashMap属于JDK1.5加入的java.util.concurrent包，就是为了解决并发编程的问题，源码中也可以看到ConcurrentHashMap用到了新提供的ReentrantLock，文档介绍ReentrantLock是一个可重入的互斥锁的实现，类似于synchronized的语义，不过更强大，最重要的是 ConcurrentHashMap 引入了分段的结构，每次加锁都可以只对一个片段加锁，不影响其他段，而且Entry采用了final字段，因此读取也可以不用加锁，这样减少锁的情境而且更加细粒度，大大提高了并发性能。

3.数据操作方式的区别

        这里必须要提到 ConcurrentHashMap这个最特别的类型，其他类型数据操作都是最普通的方式，唯独  ConcurrentHashMap采用了Unsafe类的直接操作内存的方式，应该也是为了操作原子化，不知道会不会也有效率提升，没有测试过，大家可以试试，不过 Unsafe并没有公开，平时使用的确也不安全，还是看看就行了。