Java集合类框架详解

　　Java集合框架概述
　　集合可以看作是一种容器，用来存储对象信息。所有集合类都位于java.util包下，但支持多线程的集合类位于java.util.concurrent包下。
　　Java集合类主要由两个根接口Collection和Map派生出来的，Collection派生出了三个子接口：List、Set、Queue，因此Java集合大致也可分成List、Set、Queue、Map四种接口体系（注意：Map不是Collection的子接口）。
　　其中：
　　List代表了有序可重复集合，可直接根据元素的索引来访问；
　　Set代表无序不可重复集合，只能根据元素本身来访问；
　　Queue是队列集合；
　　Map代表的是存储key-value对的集合，可根据元素的key来访问value。
　　常见的实现类分别是ArrayList、LinkedList、ArrayQueue、HashSet、TreeSet、HashMap、TreeMap等。
　　Java集合类常见接口及实现类
　　01
　　Collection接口
　　Collection接口是最基本的集合接口，它不提供直接的实现，Java SDK提供的类都是继承自Collection的＂子接口＂如List和Set。
　　在Java中所有实现了Collection接口的类都必须提供两套标准的构造函数，一个是无参，用于创建一个空的Collection，一个是带有Collection参数的有参构造函数，用于创建一个新的Collection，这个新的Collection与传入进来的Collection具备相同的元素。
　　02
　　List接口
　　List接口为Collection直接接口。List所代表的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。
　　用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。
　　实现List接口的集合主要有：ArrayList、LinkedList、Stack等。
　　03
　　Map接口
　　Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。同时它也没有继承Collection。
　　在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。
　　实现map的有：HashMap、TreeMap、HashTable。
　　ArraysList 和 LinkedList
　　01
　　ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
　　02
　　对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
　　03
　　对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。
　　04
　　ArrayList的大小默认为10，每次扩容为1.5倍，即为int newCapacity = oldCapacity + (oldCapacity >> 1)。随着容器中的元素不断增加，容器的大小也会随着增加。
　　在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。
　　05
　　ArrayList中的size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。
　　add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）。
　　06
　　同样实现List接口的LinkedList与ArrayList不同，LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get、remove、insert方法在LinkedList的首部或尾部。
　　由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。
　　这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。
　　HashMap 和 TreeMap
　　01
　　HashMap
　　以哈希表数据结构实现，查找对象时通过哈希函数计算其位置，它是为快速查询而设计的，其内部定义了一个hash表数组（Entry[] table），元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来，可能通过查看HashMap.Entry的源码它是一个单链表结构。
　　其不是同步的，且允许空值作为键和值。
　　HashMap的数据结构为数组+链表/红黑树（冲突的链表多于8个时，就把这个链表转换成红黑树），初始容量是16，默认加载因子为0.75。
　　HashMap的长度n为什么是2的整数次幂？一是为了减少hash冲突的概率，n为偶数 最低位为0异或后结果必为偶数。
　　其次是为了加快hash计算，&比%速度快；还有在JDK1.8中，扩容更方便，关注特殊位（n-1会多出一位，然后关注和这位对齐的hash，0不变，1加一个扩容之前的n）。
　　HashMap在JDK 1.7中使用的是头插法，在并发put时出现Entry链表形成环形数据结构，导致死循环，为了解决这个问题，在JDK1.8中使用的是尾插法。
　　如何保证HashMap的线程安全：
　　一是Collections工具类中synchronizedCollection；
　　二是采用装饰者模式实现map接口对HashMap进行封装；
　　三是直接使用ConcurrentHashMap。
　　02
　　TreeMap
　　TreeMap存储K-V键值对，通过红黑树（R-B tree）实现。
　　TreeMap继承了NavigableMap接口，NavigableMap接口继承了SortedMap接口，可支持一系列的导航定位以及导航操作的方法，当然只是提供了接口，需要TreeMap自己去实现。
　　TreeMap实现了Cloneable接口，可被克隆，实现了Serializable接口，可序列化。
　　TreeMap因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过Key值的自然顺序进行排序。
　　对集合的选择
　　01
　　对List的选择
　　对于随机查询与迭代遍历操作，数组比所有的容器都要快。所以在随机访问中一般使用ArrayList
　　LinkedList使用双向链表对元素的增加和删除提供了非常好的支持，而ArrayList执行增加和删除元素需要进行元素位移。
　　对于Vector而已，我们一般都是避免使用。
　　将ArrayList当做首选，毕竟对于集合元素而已我们都是进行遍历，只有当程序的性能因为List的频繁插入和删除而降低时，再考虑LinkedList。
　　02
　　对Set的选择
　　HashSet由于使用HashCode实现，所以在某种程度上来说它的性能永远比TreeSet要好，尤其是进行增加和查找操作。
　　虽然TreeSet没有HashSet性能好，但是由于它可以维持元素的排序，所以它还是存在用武之地的。
　　03
　　对Map的选择
　　HashMap与HashSet同样，支持快速查询。虽然HashTable速度的速度也不慢，但是在HashMap面前还是稍微慢了些，所以HashMap在查询方面可以取代HashTable。
　　由于TreeMap需要维持内部元素的顺序，所以它通常要比HashMap和HashTable慢。