集合的两大顶层接口：Collection和Map
Collection：（线性结构）
（一）List：有序
1. ArrayList： *0.5
底层由数组实现，访问速度快，删除插入速度慢。进行删除插入操作需要对原数组进行复制移动，代价比较高。扩容0.5倍
2. LinkedList：
底层由双向链表实现，访问速度慢，删除插入速度快。访问需要把遍历链表，耗时多。提供了List中没有的方法，方便操作表头表尾元素，适合用来做堆栈队列
3. Vector：*1
底层由数组实现，线程安全。因此速度比ArrayList慢。扩容1倍
（二）Set：无序，不允许有重复。根据计算hashCode值和比较equals方法来判断是否相等
1. HashSet：
hash表。使用hashmap的key存储元素，顺序不是按照存入的顺序排列的，而是通过hashCode值排列的。如果hashCode值相同，equals方法不等的情况，则在同一个hash值下顺延，形成hash桶
2. TreeSet：（可排序：自然排序/比较器排序）
二叉树。使用二叉树原理进行排序，底层使用TreeMap的key存储元素。每插入一个元素都会进行一次排序。如果是Integer、String对象的话就会自动排序，即自然排序。如果是自己创建的对象，需要在对象中实现Compare接口，覆写compareTo方法，制定排序规则，即比较器排序。
3. LinkedHashSet：
hashSet+LinkedHashMap。继承hashSet，又基于LinkedHashMap来实现。底层通过创建LinkedHashMap来实现。在操作上与父类HashSet相同
Map：（键值对）
1. HashMap：*1 数组＋链表＋红黑树、 线程不安全
hashMap是根据健的hashcode值来排列元素的。
只允许一个key为null，可以多个value为空。不允许重复的key。
线程不安全。如果要实现线程安全需要使用collection中的方法，synchronizedMap方法，或者使用另一个map，ConcurrentHashMap。
java7中对于重复的hashcode值，是用单相链表形式往下存的。每一个entry中包含有key、value、hashcode、用于单向链表的next
java8中对于重复的hashcode值，加入了红黑树。如果链表长度大于8，数组容量大于64，就会把链表自动转换成红黑树；如果链表长度小于6，就会把红黑树转换回链表。
扩容：hashmap的数组容量是16，负载因子是0.75，所以大于容量12时就会，扩容1倍（为了保证数组长度是2的整次幂，与计算下标的方法有关）
2. ConcorrentHashMap：线程安全
默认由16个segment组成，jdk1.7，每一个segment都是继承了reentrantLock锁的hashmap。
jdk1.8以后每一个segment是用CAS和synchronized实现的，每一个node节点的next和value都用了volatile关键字，保证了可见性。
3. HashTable：线程安全
继承Dictionary类。不怎么使用。可以被hashmap和concorrentHashMap取代
