1. 集合类库
通常，程序总是根据运行时才知道的某些条件去创建新对象，在此之前，不会知道所需对象的数量，甚至不知道确切的类型。为了解决这个普遍的编程问题，需要在任意时刻和任意位置创建任意数量的对象。java 实用类库提供了一套相当完整的集合类来解决这个问题 。其中基本类型是List、Set、Queue和Map，这些对象被称为集合类。
这里给出一个经常引用的一个类库关系图：
从图中可以看出，Java集合分为Collection和Map两大种。下面就两大类型进行分别说明：
2. Collection
查看jdk源码看到Collection接口定义了集合分支的基础方法，有查询方法，修改集合方法，批量操作方法和比较与hash方法，这些都是集合的基础方法。其继承接口可以分为以下几类：
- List: 有序集合，值允许有重复
- Set:无需集合，值不允许有重复
- Queue:保持先进先出顺序
2.1 List集合: ArrayList&LinkedList
ArrayList底层通过数组实现，数组因为可以通过下标访问成为一个随机访问第n个数效率很高的数据结构，随机访问查询的时间复杂度是O(1)，而删除/增加新的元素到某个位置时，需要一个一个的移动数组中的元素直至适合的位置，所以时间复杂度是O(n)；
LinkedList底层由双向链表实现，在链表中插入元素时，只需要改变插入位置前后结点的结点指向和添加新元素的结点指向即可，时间复杂度是O(1)，在访问元素的时候，无论是随机方位第几位的元素还是查询某个定值时，链表的时间复杂度均为O(n)。
所以，ArrayList适用于随机访问的场景，而LinkedList则适用于频繁随机位置删除和插入的场景。
2.2 Set集合: HashSet&TreeSet
HashSet：封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。 HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的，具体原理在HashMap分析。
TreeSet：TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法，具体原理在TreeMap分析。
2.3 Queue: PriorityQueue
优先级队列，元素可以按照任意的顺序插入，但总是按照排序的顺序进行检索，内部实现的数据结构是堆。堆是一个可以自我调整的二叉树，对树执行添加和删除的时候，可以让最小的元素移动到根，而不用花费时间对元素进行排序。使用的典型实例是任务调度场景。
3. Map
表示键值对，键必须是唯一的，不能对同一个键存放两个值。
3.1 HashMap
HashMap底层实现上是一个“链表散列”的数据结构，即数组和链表的结合体。具体如下图所示：
从上图我们可以看出HashMap底层实现还是数组，只是数组的每一项都是一条链。其中数组和链表在jdk源码中体现：
/**The table, resized as necessary.
Length MUST Always be a power of two. */
// table对象即是上图中对应的数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// 而内部类Entry则是代表了链表上的没给节点
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
3.1.1 如何插入一个值
HashMap插入一个值包括以下几个步骤：
- 调用hash计算key的hash值
- 根据hash值推算出放在数组的位置
- 找到具体数组某个位置，遍历该位置的Entry链表，比较key值如果相等则直接替换value，如果不同则插入链表的尾部。
可以看出，如果hashCode()和hash()足够好，尽可能的减少冲突，那么对HashMap的访问等价于对数组的随机方位，如果不够好有大量冲突存在，则退化为对链表的随机方位。
3.1.2 再散列rehash
当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。
3.1.3 容量参数
可以看出整个再散列过程是比较耗时的，需要将所有老数据重新计算后放到新的散列表中。HashMap维护一个threshold变量，它始终被定义为当前数组总容量和负载因子的乘积，他表示的是HashMap的阈值，当超过该值，HashMap便会扩容。
关于负载因子定义首先看一下HashMap的constructor如下：
public HashMap(int initalCapacity);
public HashMap(int initalCapacity, float loadFactor);
其中initalCapacity 表示初始化容量，loadFactor表示负载因子一般是介于0和1之间，它决定了HashMap扩容之前，其内部数组的填充度。默认情况下，初始量为16，负载因子为0.75。
负载因子 = 元素个数/内部数组总大小
可以看出如果负载因子大于1，一定会存在冲突，元素个数大于数组的容量。
3.1.4 如何取一个值
查看jdk源码可以看出从HashMap中获取一个值分为两种情况当key为null的时候单独处理，非null的时候一套处理逻辑。这里也提醒我们HashMap可以存放key为null的键值对。
查看获取非null的key的值的具体实现
分析查找一个非null的键流程：
- 调用hash计算key的hash值
- 根据hash值推算出放在数组的位置
- 遍历对应位置上的链表找到key相同的Entry对象返回即可，找不到则返回为null
3.2 TreeMap
HashMap和LinkedHashMap底层存储容器都是选择了数组，内容为内部类Entry。但是TreeMap底层通过一颗红黑树来维护，初始化的时候有个root根节点，同时TreeMap不允许key为null。TreeMap 本质上就是一棵“红黑树”，而 TreeMap 的每个 Entry 就是该红黑树的一个节点。
3.2.1 红黑树
排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 它的左、右子树也分别为排序二叉树。
排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表。
红黑树在原有的排序二叉树增加了如下几个要求：
- 性质 1：每个节点要么是红色，要么是黑色。
- 性质 2：根节点永远是黑色的。
- 性质 3：所有的叶节点都是空节点（即 null），并且是黑色的。
- 性质 4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
- 性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
上面的性质 3 中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。
4. 迭代器（Iterator）
迭代器是一种设计模式，在java里它是一个对象，可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。迭代器接口Iterable是Collection类的父接口。它只有一个方法: iterator()，方法返回一个代表当前集合对象的泛型<T>迭代器，用于之后的遍历操作。所有的Collection集合对象都实现这个Iterable接口，允许使用foreach进行遍历。
常用Iterator遍历方式
List<Integer> lstint = new ArrayList<Integer>();
// Iterator遍历一
Iterator<Integer> iterator = lstint.iterator();
while (iterator.hasNext()){
int i = iterator.next();
System.out.println(i);
}
// Iterator遍历二
for (Iterator<Integer> it = lstint.iterator(); it.hasNext();){
int i = it.next();
System.out.println(i);
}
5. Fail-Fast机制
前面叙述的集合类均不是线程安全的，所以java集合(Collection)规定在使用迭代器的过程中有其他线程修改了同一个集合类，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。
注意点：迭代器的快速失败行为无法得到保证，迭代器的快速失败行为应该仅用于检测 bug。
例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容同时被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
5.1 实现原理
这里以HashMap为例进行说明，其他集合类实现类似，这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，具体定义如下：
HashMap在put函数添加元素时修改此值代码如下：
在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，将会抛出ConcurrentModificationException异常，具体代码如下：
5.2 遍历删除指定元素
在实际应用中，我们常会遇到一种需求是从集合中删除符合某个特定条件的元素，对比下面几种写法：
/**
* 使用增强的for循环
* 在循环过程中从List中删除非基本数据类型以后，此时modCount被修改,
* 继续遍历List,此时expectCount仍然是初始化时值比较不相等,
* 会报ConcurrentModificationException
*/
public void listRemove() {
List<Student> students = this.getStudents();
for (Student stu : students) {
if (stu.getId() == 2)
students.remove(stu);
}
}
改写法如注释中描述由于remove操作导致modCount发生变化，继续遍历就会触发Fail-Fast机制。这种写法如果确定只删除其中一个，此时break掉程序不会抛异常。
/**
* 该写法不使用增强的for循环意味着不会使用Iterator相关方法,
* 这样也不会涉及到modCount比较判断的问题,
* 但是数据不一定是正确的，这主要是因为删除元素后，被删除元素后
* 的元素索引发生了变化。假设被遍历list中共有10个元素，当
* 删除了第3个元素后，第4个元素就变成了第3个元素了，第5个就变成
* 了第4个了，但是程序下一步循环到的索引是第4个，
* 这时候取到的就是原本的第5个元素了。
*/
public void listRemove2() {
List<Student> students = this.getStudents();
for (int i=0; i<students.size(); i++) {
if (students.get(i).getId()%3 == 0) {
Student student = students.get(i);
students.remove(student);
}
}
}
该种写法通过遍历数组的形式，在删除过程中导致数组元素减少位置发生变化影响了最后的结果。
/**
* 使用Iterator的方式可以顺利删除和遍历
*/
public void iteratorRemove() {
List<Student> students = this.getStudents();
Iterator<Student> stuIter = students.iterator();
while (stuIter.hasNext()) {
Student student = stuIter.next();
if (student.getId() % 2 == 0)
//这里要使用Iterator的remove方法移除当前对象，
//使用List的remove方法，则同样会出现 ConcurrentModificationException
stuIter.remove();
}
}
推荐写法使用Iterator遍历并使用迭代器对应的remove方法删除。该删除方法会同步size大小以及修改expectCount。
6. 总结
简单总结上述各种类使用和实现特点，如下表所示：
