一、主要内容
1.List
ArrayList
1）ArrayList是List接口的可变数组非同步实现，并允许包括null在内的所有元素。
2）底层使用数组实现
3）该集合是可变长度数组，数组扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量增长大约是其容量的1.5倍，这种操作的代价很高。
4）采用了Fail-Fast机制（通过记录modCount参数来标识多个线程操作），面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险
5）remove方法会让下标到数组末尾的元素向前移动一个单位，并把最后一位的值置空，方便GC
LinkedList
1）LinkedList是List接口的双向链表非同步实现，并允许包括null在内的所有元素。
2）底层的数据结构是基于双向链表的，该数据结构我们称为节点
3）双向链表节点对应的类Node的实例，Node中包含成员变量：prev，next，item。其中，prev是该节点的上一个节点，next是该节点的下一个节点，item是该节点所包含的值。
4）（没找到对应方法，indexof方法实现是从头开始循环判断元素）它的查找是分两半查找，先判断index是在链表的哪一半，然后再去对应区域查找，这样最多只要遍历链表的一半节点即可找到
Vector
1）动态数组实现的List，跟ArrayList一样，其容量能自动增长
2）JDK1.0引入了，它的很多实现方法都加入了同步语句，因此是线程安全的（在操作数据的方法声明时加synchronized关键字：同步方法，在内部的迭代器操作数据的方法内部的代码块加Vector的synchronized的同步对象锁：同步代码块）
3）适用于快速访问和修改，不适用随机插入和删除（底层实现是对象数组的原因）
4）初始容量大小为10，扩容由初始容量和capacityIncrement共同决定
5）元素允许为null
6）现在已经基本不再使用，如果不需要线程安全的实现，推荐使用ArrayList代替Vector
Vector与ArrayList的区别
最大的是Vector是线程安全的，而ArrayList不是线程安全的。
1）ArrayList不可以设置扩展的容量，默认1.5倍；Vector可以设置扩展的容量，如果没有设置，默认2倍
2）ArrayList的无参构造方法中初始容量为0（初次调用add()会更新为10）；Vector的无参构造方法中初始容量为10
3）Vector线程安全，ArrayList线程不安全
2.Map
HashMap
1)HashMap是基于哈希表的Map接口的非同步实现，允许使用null值和null键，但不保证映射的顺序。
2)底层使用数组实现（Node<K,V>数组），数组中每一项是个单向链表，即数组和链表的结合体；
当链表长度大于一定阈值时，链表转换为红黑树，这样减少链表查询时间。
3)HashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Node对象。HashMap底层采用一个Node[]数组来保存所有的key-value对，
当需要存储一个Node对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；
当需要取出一个Node时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Node。
4)HashMap进行数组扩容需要重新计算扩容后每个元素在数组中的位置，很耗性能
5)采用了Fail-Fast机制，通过一个modCount值记录修改次数，对HashMap内容的修改都将增加这个值。迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，马上抛出异常
LinkedHashMap
1）LinkedHashMap继承于HashMap，底层使用哈希表和双向链表来保存所有元素，并且它是非同步，允许使用null值和null键。
2）基本操作与父类HashMap相似，通过重写HashMap相关方法，重新定义了数组中保存的元素Entry，来实现自己的链接列表特性。
该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而构成了双向链接列表，用于记录前一个插入的元素和记录后一个插入的元素
HashTable
1)Hashtable是基于哈希表的Map接口的同步实现，不允许使用null值和null键
2)底层使用数组实现，数组中每一项是个单链表，即数组和链表的结合体
3)Hashtable在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，
当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；
当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
4)synchronized是针对整张Hash表的，即每次锁住整张表让线程独占（使用同步方法）
ConcurrentHashMap
1）ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。
2）它使用了多个锁来控制对hash表的不同段进行的修改，每个段其实就是一个小的hashtable，它们有自己的锁。只要多个并发发生在不同的段上，它们就可以并发进行。
3）ConcurrentHashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。
4）与HashMap不同的是，ConcurrentHashMap使用多个子Hash表，也就是段(Segment)，1.8中改用CAS+synchronized保证并发安全性，将存放数据的 HashEntry 改为 Node
5）ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁。如果使用传统的技术，如HashMap中的实现，如果允许可以在hash链的中间添加或删除元素，读操作不加锁将得到不一致的数据。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的。
6）ConCurrentHashMap 在 jdk1.8 中主要做了两方面的改进。
（1） 取消segments字段，直接采用transient volatile HashEntry<K,V>[] table保存数据，
采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。
（2） 把Table数组＋单向链表的数据结构 变成为 Table数组 ＋ 单向链表 ＋ 红黑树的结构。
注： 当链表长度超过8以后，单向链表变成了红黑树； 在哈希表扩容时，如果发现链表长度小于 6，则会由红黑树重新退化为链表。
