Java集合框架体系总览
总的来说，Java集合框架以Collection接口为中心，下属三个重要的子接口，分别是：List（线性表）、Set、Queue（队列），以及还有一个非常重要的Map接口。下面我们分别总结一下每种类型集合下的知识点。
一、Collection接口
首先我们来看一下Collection接口中的方法：
1. 添加元素的功能：
/**添加元素*/
boolean add(E e);
/**将整个集合添加到某个集合*/
boolean addAll(Collection<? extends E> c);
2.从集合中删除(指定)元素
/**清空集合中的所有元素*/
void clear();
//从集合中移除指定元素
boolean remove(Object o);
//从此集合中移除指定集合中包含的元素
boolean removeAll(Collection<?> c);
//移除在c集合中不包含的元素
boolean retainAll(Collection<?> c);
3.判断功能
/**集合中是否有元素o,如果有返回true,否则返回false*/
boolean contains(Object o);
/**如果在此集合中有给定集合中的全部元素那么将返回true*/
boolean containsAll(Collection<?> c);
//判断集合是否为空，如果为空返回true,否者返回false
boolean isEmpty();
4.获取集合的各种信息
//获得遍历集合元素的迭代器，这个方法是Collection继承Iterable接口得到的
Iterator<E> iterator();
//返回集合中元素的个数
int size();
/**判断两个对象是否相等*/
boolean equals(Object o);
//返回集合对象的hashCode
int hashCode();
5. 转换
//将此集合转化为数组
Object[] toArray();
/**=============jdk1.8新增的几个方法=============*/
//在jdk1.8中新增了一下几个方法，都是default方法，在Collection接口中直接给出了实现
//parallelStream()返回并行的Stream
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
//仅仅是返回集合的Stream
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
//删除容器中所有满足filter指定条件的元素
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
//可分割的迭代器，不同以往的iterator需要顺序迭代，Spliterator可以分割为若干个小的迭代器进行并行操
//作，既可以实现多线程操作提高效率，又可以避免普通迭代器的fail-fast机制所带来的异常
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
二、Iterable接口
Collection接口继承了Iterable接口，说明所有的集合元素都是可以通过Iterator迭代器来遍历，事实也确实是这样，下面是Iterable接口中的三个方法：
//获取遍历集合的迭代器，Collection中的iterator方法就是从这里继承得到的
Iterator<T> iterator();
//JDK1.8新增的一个遍历集合的方法，采用函数式接口的方式，可以很方便的遍历所有集合类型
default void forEach(Consumer<? super T> action) {
//方法内部已经判空了，所有在使用这个方法的时候没有必要的时候不用判空
Objects.requireNonNull(action);
//底层实际还是增强for
for (T t : this) {
action.accept(t);
}
}
//作用和Collection中的同名方法一样
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
三、Iterator迭代器
Iterator也是一个接口，使用迭代器可以遍历任何类型的集合，它有三个迭代器必备的基本方法外加jdk1.8新增了一个方便的遍历集合的方法forEachRemaining：
//判断集合是否还有下一个元素
boolean hasNext();
//获取集合的下一个元素
E next();
//移除元素
default void remove() {
throw new UnsupportedOperationException("remove");
}
//JDK1.8新增的一个方法，用法和作用都和Iterable接口中的forEach()方法类似
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
//这里使用的是Iterator接口中的hasNext方法配合while循环实现遍历的
while (hasNext())
action.accept(next());
}
四、List接口
Java 的 List 是非常常用的数据类型。List 是有序的 Collection。Java List 常用的实现类比如： ArrayList、Vector 和 LinkedList等。
1、ArrayList
ArrayList 是最常用的 List 实现类，内部是通过Object数组实现的，它可以实现对元素进行快速随机访问。ArrayList中的Object数组的的默认初始化大小是10，并且默认构造方法中对于数组的创建是在第一次添加元素时执行的，我们可以看看源码的实现：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
//ArrayList默认容量
private static final int DEFAULT_CAPACITY = 10;
//用Object[0]来代替null 很多时候我们需要传递参数的类型，而不是传null，所以用Object[0]
private static final Object[] EMPTY_ELEMENTDATA = {};
//一个空对象，如果使用默认构造函数创建，则默认对象内容默认是该值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储元素的数组
transient Object[] elementData; // non-private to simplify nested class access
//数组中元素个数
private int size;
//数组最大容量
private static final int MAX_ARRAY_SIZE = 2147483639;
//默认构造方法，在构造方法中并没有立即初始化一个大小为10的Object数组，而是采用了懒加载，延迟到第一次添加元素的时候才初始化
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//指定容量的ArrayList则是在构造方法中立即初始化了一个指定容量大小的Object数组
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
}
ArrayList添加元素的方法
ArrayList会在添加新元素之前先检查一下数组的大小是否够用，如果不够用就会扩容，默认的扩容大小是原数组的1.5倍，如果扩容1.5的大小还是没法满足添加元素所需的容量，就会使用传入的容量大小，这样就会导致下一次添加元素的时候又触发扩容，因此在使用任何集合元素的时候请尽量给定一个初始容量，避免频繁的扩容影响性能。
但是当从 ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。
public boolean add(E e) {
//ArrayList的扩容机制在这一步实现
ensureCapacityInternal(size + 1); //确认内部容量
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 如果elementData 指向的是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//可以看到，如果是使用了默认构造方法时，只有在第一次添加元素的时候才会构造一个大小为10的数组
//
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//确定实际容量
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果超出了容量，进行扩展
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//ArrayList的扩容实现
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新数组的大小是旧数组大小的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果1.5倍的新数组大小还是没法满足，那就使用minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//当数组容量超过自大容量限制后MAX_ARRAY_SIZE，将数组的容量设置为Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
2、Vector （ 数组实现、 线程同步）
Vector 与 ArrayList 一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一 个线程能够写 Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此， 访问它比访问 ArrayList 慢。
3、LinkedList（双链表、双端队列）
LinkedList即实现了List接口，同时它也实现了Deque接口。它**使用链表结构存储数据，很适合数据的动态插入和删除。**具体的我们看看源码就清楚了：
//Node结点，是一个双链表
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
//链表的头结点
transient Node<E> first;
//链表的尾结点
transient Node<E> last;
//链表的结点个数
transient int size = 0;
//默认的构造方法，啥都没干...
public LinkedList() {
}
**LinkedList添加元素的方法 **
LinkedList同时具有链表和双向队列的功能，因此添加元素的方法也有两个add方法和offer方法，前者用于向链表中尾插数据，后者用于向队列尾部添加数据。其实在源码中offer方法是把add方法有包装了一下而已。我们直接来看add方法的实现
//添加新元素
public boolean add(E e) {
linkLast(e);
return true;
}
//在链表的尾部插入新节点（尾插法）
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
五、Set接口
Set 注重独一无二的性质,该体系集合用于存储无序(存入和取出的顺序不一定相同)元素，值不能重复。对象的相等性本质是对象 hashCode 值（java 是依据对象的内存地址计算出的此序号）判断的，如果想要让两个不同的对象视为相等的，就必须覆盖 Object 的 hashCode 方法和 equals 方法。
1、HashSet
哈希表边存放的是哈希值。HashSet 存储元素的顺序并不是按照存入时的顺序（和 List 显然不 同） 而是按照哈希值来存的所以取数据也是按照哈希值取得。元素的哈希值是通过元素的 hashcode 方法来获取的, HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较 equals 方法 如果 equls 结果为 true ，HashSet 就视为同一个元素。如果 equals 为 false 就不是 同一个元素。
2、TreeSet
（1）TreeSet()是使用二叉树的原理对新 add()的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。
（2）Integer 和 String 对象都可以进行默认的 TreeSet 排序，而自定义类的对象是不可以的，自己定义的类必须实现 Comparable 接口，并且覆写相应的 compareTo()函数，才可以正常使用。
（3）在覆写 compare()函数时，要返回相应的值才能使 TreeSet 按照一定的规则来排序
（4）比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。
3、LinkedHashSet
对于 LinkedHashSet 而言，它继承与 HashSet、又基于 LinkedHashMap 来实现的。LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素，它继承与 HashSet，其所有的方法操作上又与 HashSet 相同，因此 LinkedHashSet 的实现上非常简单，只提供了四个构造方法，并通过传递一个标识参数，调用父类的构造器，底层构造一个 LinkedHashMap 来实现，在相关操作上与父类 HashSet 的操作相同，直接调用父类 HashSet 的方法即可。
六、Map接口
1、Hashtable
Hashtable 是遗留类，很多映射的常用功能与 HashMap 类似，不同的是它承自 Dictionary 类，并且是线程安全的，任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap，因为ConcurrentHashMap 引入了分段锁。Hashtable 不建议在新代码中使用，不需要线程安全的场合可以用 HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换。
2、HashMap
HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap。我们用下面这张图来介绍HashMap 的结构。
在JDK7中HashMap使用数组+链表实现
大方向上，HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。上图中，每个绿色的实体是嵌套类 Entry 的实例，Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。
- capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。
- loadFactor：负载因子，默认为 0.75。
- threshold：扩容的阈值，等于 capacity * loadFactor
Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，构成了以 数组+链表+红黑 树 的基本数据结构组合。
根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。
具体的原理可以参考我的博客HashMap是如何工作的 。
3、LinkedHashMap
LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
4、TreeMap
TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。如果使用排序的映射，建议使用 TreeMap。在使用 TreeMap 时，key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的Comparator，否则会在运行时抛出 java.lang.ClassCastException 类型的异常。
参考通过分析 JDK 源代码研究 TreeMap 红黑树算法实现
七、安全失败机制（fail-safe）和快速失败机制（fail-fast）
1、快速失败机制 fail-fast
fail-fast是java集合的一种错误检测机制，在遍历集合的时候当对集合的结构进行修改的时候，就会触发fail-fast。比如我们使用迭代器遍历集合的时候，如果在遍历过程中对集合的结构进行了修改（比如删除元素，增加元素），就会抛出ConcurrentmodificationException异常。
比如像这样的情况：
public class FailFast {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(2);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
Integer integer = iterator.next();
if(integer==2) {
list.remove(integer);
}
}
}
}
执行后结果： 
其实不光使用Iterator在遍历的时候不能修改集合元素的个数，增强for、forEach()方法等都不可以再遍历的增加或删除元素。
原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个int类型的变量modCount统计修改的次数，他表示的是集合在遍历之前已经修改过的次数，每当删除或添加元素之后都会把modCount+1，此时当调用hasNext()/next()方法时会判断modCount和exceptedModCount的值是否相等，如果相等就返回继续遍历，否则抛出ConcurrentModificationException，终止遍历。
应用场景：java.util包下的集合类使用了这种机制（Hashtable除外，它使用的是fail-safe）,不能在多线程下发生并发修改（迭代过程中被修改）算是一种安全机制吧。
如何避过快速失败机制，在遍历的时候修增加或减少集合元素？
（1）在单线程环境下的解决办法 其实很简单，细心的朋友可能发现在Itr类中也给出了一个remove()方法. 将上述代码改为下面这样就不会报错了：
public class FailFast {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(2);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
Integer integer = iterator.next();
if(integer==2) {
//注意这里，如果删除不要使用list.remove()，而是使用iterator.remove()
iterator.remove();
}
}
}
}
（2）在多线程环境下的解决办法 上面的解决办法在单线程环境下适用，但是在多线程下适用吗？看下面一个例子：
public class FailFast {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
Thread t1=new Thread(()->{
Iterator<Integer> it = list.iterator();
while (it.hasNext()){
Integer next = it.next();
System.out.println(next);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
Thread t2=new Thread(()->{
Iterator<Integer> it = list.iterator();
while (it.hasNext()){
Integer next = it.next();
if(next==2){
it.remove();
}
}
});
t1.start();
t2.start();
}
}
执行结果： 
有可能有朋友说ArrayList是非线程安全的容器，换成Vector就没问题了，实际上换成Vector还是会出现这种错误。
原因在于，虽然Vector的方法采用了synchronized进行了同步，但是实际上通过Iterator访问的情况下，每个线程里面返回的是不同的iterator，也即是说expectedModCount是每个线程私有。假若此时有2个线程，线程1在进行遍历，线程2在进行修改，那么很有可能导致线程2修改后导致Vector中的modCount自增了，线程2的expectedModCount也自增了，但是线程1的expectedModCount没有自增，此时线程1遍历时就会出现expectedModCount不等于modCount的情况了。
因此一般有2种解决办法： 1）在使用iterator迭代的时候使用锁进行同步；
2）使用并发容器CopyOnWriteArrayList代替ArrayList和Vector。
2、安全失败机制 fail-safe
采用安全失败机制的集合容器，在遍历的时候不会直接在原来的内容量上遍历，而是复制一份在副本上遍历。由于遍历是在拷贝的副本上进行的，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，因此不会引发ConcurrentmodificationException
应用场景：J.U.C包下都是安全失败机制容器，可以在多线程环境下并发的修改和访问。
缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
