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插入一个值包括以下几个步骤：

1. 调用hash计算key的hash值
2. 根据hash值推算出放在数组的位置
3. 找到具体数组某个位置，遍历该位置的Entry链表，比较key值如果相等则直接替换value，如果不同则插入链表的尾部。

可以看出，如果hashCode()和hash()足够好，尽可能的减少冲突，那么对HashMap的访问等价于对数组的随机方位，如果不够好有大量冲突存在，则退化为对链表的随机方位。

3.1.2 再散列rehash

当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。

rehash

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的键值对。

获取值get()

查看获取非null的key的值的具体实现

查找key对应Entry对象

分析查找一个非null的键流程：

1. 调用hash计算key的hash值
2. 根据hash值推算出放在数组的位置
3. 遍历对应位置上的链表找到key相同的Entry对象返回即可，找不到则返回为null