集合入门
本文内容
1. 集合概念
Java 集合框架主要包括两种类型的容器:
- 集合（Collection），存储一个元素集合;
- 图（Map），存储键/值对映射。
Collection 接口又有 3 种子接口类型分别为 List、Set 和 Queue，再下面是一些子接口和实现类。
Map 接口下有常见的 HashMap、Hashtable 实现类，以及SortedMap 子接口。
常见集合的主要关系图如下所示：
我们比较常用的接口有 4 个：
- List：有序、可重复；
- Set：无序、不可重复；
- Queue：有序、可重复，可以按特定的规则来确定先后顺序；
- Map：键值对（key-value）存储，key 无序、不可重复；value 无序、可重复。
2. Collection
2.1 List
List 接口是一个有序的 Collection，使用此接口能够精确的控制每个元素插入的位置，能够通过索引下标来访问 List 中的元素，第一个元素的索引为 0，而且允许有相同的元素。
2.1.1 ArrayList
底层数据结构：
- ArrayList 是一个 动态数组，底层数据结构是
Object[]数组，可以任意的添加或删除元素，支持快速随机访问。
插入/删除受元素位置影响：
- ArrayList 采用数组存储，所以插入/删除元素的时间复杂度受元素位置的影响。 比如：执行
add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)； - 但是如果要在指定位置 i 插入/删除元素的话（
add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的（n-i）个元素都要执行向后位/向前移一位的操作。
内存空间占用：
- ArrayList 的空间浪费主要体现在列表的 结尾会预留一定的容量空间。
扩容机制：
- 默认初始容量为 10，可以在创建 ArrayList 对象时指定容量；
- 每次扩容之后容量都会变为原来的 1.5 倍左右，左右是因为扩容公式为：新容量 = 原容量 + (原容量 >> 1)，当原容量是奇数时，会向下取整。
使用场景：
- 元素需要 频繁修改/查找。
常用方法
| 方法 | 描述 |
|---|---|
| boolean add(Object element) | 向列表的尾部添加指定的元素 |
| E get(int index) | 返回列表中指定位置的元素 |
| void add(int index, Object element) | 在列表的指定位置插入指定元素 |
| E set(int i, Object element) | 将索引 i 位置元素替换为元素 element 并返回被替换的元素 |
| void clear() | 从列表中移除所有元素 |
| boolean contains(Object o) | 如果列表包含指定的元素，则返回 true |
| E remove(int index) | 移除列表中指定位置的元素，并返回被删元素 |
| boolean remove(Object o) | 移除集合中第一次出现的指定元素 |
2.1.2 LinkedList
底层数据结构：
- LinkedList 中的元素 在逻辑上有序（每一个节点里存到下一个节点的地址），底层数据结构为 双向链表（JDK1.6 之前为循环链表，JDK1.7 取消了循环）。不支持快速随机访问。
插入/删除受元素位置影响：
- LinkedList 采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响，时间复杂度为 O(1)；
- 如果是要在指定位置 i 插入和删除元素的话（
add(int index, E element)，remove(Object o)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入。
内存空间占用：
- LinkedList 的空间花费体现在它的 每一个元素都需要消耗更多的空间（因为要存放直接后继和直接前驱以及数据）。
使用场景：
- 在项目中一般是不会使用到 LinkedList，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且性能通常会更好。
常用方法
| 方法 | 描述 |
|---|---|
| boolean add(E e) | 链表末尾添加元素 |
| void add(int index, E element) | 向指定位置插入元素 |
| void addFirst(E e) | 元素添加到头部 |
| void addLast(E e) | 元素添加到尾部 |
| boolean remove(Object o) | 删除某一元素 |
| E remove(int index) | 删除指定位置的元素 |
| E removeFirst() | 删除并返回第一个元素 |
| E removeLast() | 删除并返回最后一个元素 |
| E get(int index) | 返回指定位置的元素 |
| E getFirst() | 返回第一个元素 |
| E getLast() | 返回最后一个元素 |
| int indexOf(Object o) | 查找指定元素从前往后第一次出现的索引 |
| int size() | 返回链表元素个数 |
| boolean contains(Object o) | 判断是否含有某一元素 |
| void clear() | 清空链表 |
2.1.3 Vector
Vector 是 List 的古老实现类，底层数据结构为 **`Object[]` 数组**，是 **线程安全** 的（加了 synchronized 锁）。
2.2 Set
Set 接口存储一组唯一，无序的对象。
无序性和不可重复性的含义：
- 无序性：不等于随机性，无序性是指存储的数据在底层数组中 并非按照数组索引的顺序添加 ，而是 根据数据的哈希值决定的。
- 不可重复性：添加的元素按照
equals()判断时 ，返回 false，需要同时重写equals()方法和HashCode()方法。
2.2.1 HashSet
HashSet 是基于 HashMap 来实现的（key 为 Set 的元素，value 为空对象），所以 HashSet 的源码非常少，许多方法都是直接调用 HashMap 的。元素唯一，**线程不安全**。
底层数据结构：**哈希表**（基于HashMap实现）。
如何检查重复：
当把对象加入 HashSet 时，HashSet 会 先计算对象的 hashcode 值 来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较：
- 如果没有相符的 hashcode，HashSet 会假设对象没有重复出现；
- 但是如果发现有相同 hashcode 值的对象，这时会 调用
equals()方法 来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。
应用场景：不需要保证元素插入和取出的顺序。
2.2.2 LinkedHashSet
LinkedHashSet 是一个 **哈希表和链表** 的结合，所以具有 Set 集合不重复的特点，同时具有 **可预测的迭代顺序**。有序，元素唯一，**线程不安全**。
应用场景：保证元素的插入和取出顺序满足 FIFO 的场景。
2.2.3 TreeSet
底层数据结构：**红黑树**，元素有序，排序方式有自然排序和定制排序。元素唯一，**线程不安全**。
应用场景：支持对元素自定义排序规则的场景。
2.3 Queue
Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 FIFO。
Queue 根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法：一种在操作失败后会 抛出异常，另一种则会 返回特殊值。
具体方法的对于处理方式如下：
2.3.1 子接口 Deque
Deque 扩展了 Queue 的接口，增加了在队首和队尾进行插入和删除的方法。同样根据失败后处理方式的不同分为两类：
Deque 是双端队列，在队列的两端均可插入或删除元素，Deque 还提供有 `push()` 和 `pop()` 等其他方法，可用于模拟栈。
LinkedList 和 ArrayDeque 都是 Deque 的实现类，它们的区别如下：
- ArrayDeque 是基于 可变长的数组和双指针 来实现，而 LinkedList 则通过 链表 来实现；
- ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持；
- ArrayDeque 是在 JDK1.6 才被引入的，而 LinkedList 早在 JDK1.2 时就已经存在；
- ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。
- 从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。
2.3.2 PriorityQueue
PriorityQueue 是在 JDK1.5 中被引入的，其与 Queue 的区别在于 **元素出队顺序是与优先级相关的**，即总是优先级最高的元素先出队。PriorityQueue 利用了 **二叉堆** 的数据结构来实现的，底层使用 **可变长的数组** 来存储数据。
PriorityQueue 的特性：
- PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素；
- PriorityQueue 是 非线程安全的，且不支持存储 NULL 和 non-comparable 的对象；
- PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后；
- PriorityQueue 的典型例题包括堆排序、求第K大的数、带权图的遍历等。
2.4 Collections 工具类
Collections 工具类常用方法：
- 排序
- 查找，替换操作
- 同步控制（不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合）
排序：
查找、替换：
同步控制：
Collections 提供了多个
synchronizedXxx()方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。HashSet、TreeSet、ArrayList、LinkedList、HashMap、TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合：
3. Map
Map 接口存储一组键值对象，提供 key（键）到 value（值）的映射。
Map 的 key 不允许重复（Map 的 keySet() 返回的是 key 的 Set 集合），而 Map 的 value 值是可以重复的（Map 的 values() 返回类型是 Collection）。
Map 中的 key 组成一个Set集合，所以可以通过 keySet() 方法返回所有 key，values() 方法返回所有 value。
Set 底层也是通过 Map 实现的，只不过 value 都是空对象的 Map。
3.1 HashMap
HashMap 特性如下：
- key，value 都允许为 null，但 null 作为键只能有一个，null 作为值可以有多个；
- 线程不安全，因为线程安全问题，HashMap效率比 Hashtable 高；
3.1.1 底层数据结构
JDK 1.7：数组+链表
JDK1.8 之前的 HashMap 的 key 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同：
如果相同的话，直接覆盖更新；
不相同就通过拉链法解决冲突，如下图所示：
扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的
hashCode()方法 换句话说使用扰动函数之后可以减少碰撞。
JDK 1.8：数组+链表+红黑树
JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当 链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
因为红黑树是一颗自平衡的二叉查找树，查找效率高。由于平衡二叉树不能自平衡，调整所需的次数比红黑树多，所以采用红黑树。
3.1.2 初始容量和扩容大小
初始容量
创建时不指定容量：
- 不指定容量时，不会初始化容量，只会初始化一个加载因子 loadFactor；
- 当执行插入方法时，才会初始化容量，默认大小为 16；
- 之后 每次扩容时容量为原来的 2 倍
创建时指定容量：
- HashMap 会将其 扩充为 2 的幂次方大小；
- 若指定容量不是 2 的幂次方，则会向上寻找最近的 2 的幂次方大小的数
扩容大小
每次扩大到 原来容量的 2 倍，至于为什么每次扩容到原来的 2 倍，因为要维持 HashMap 的容量是 2 的幂次方。
HashMap 的容量为什么是 2 的幂次方？
为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。
Hash 值的范围值 -2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。
但问题是一个 40 亿长度的数组，内存是放不下的，所以这个散列值是不能直接拿来用的。用之前还要 先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是 (n - 1) & hash（n 代表数组长度）。
(n - 1) & hash 的设计：
- 我们首先可能会想到采用 % 取余的操作来实现。但是 取余 (%) 操作中如果除数是 2 的幂次，则等价于与其除数减一的与 (&) 操作（也就是说
hash % length == hash & (length - 1)的前提是 length 是 2 的 n 次方）； - 采用二进制位操作 &，相对于 % 能够提高运算效率；
- 还有一个原因是在扩容后不需要重新计算每一个元素的哈希值就可以快速判断新的位置，具体见 HashMap源码分析：数据结构
这就解释了 HashMap 的容量为什么是 2 的幂次方。
3.1.3 何时扩容
loadFactor 加载因子：
loadFactor 加载因子是 控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么数组中存放的数据 (entry) 也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据 (entry) 也就越少，也就越稀疏。
loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。
给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。
threshold：
threshold = capacity * loadFactor，当 Size >= threshold 的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。
扩容后，会重新计算每个元素的 hash 值，使每个元素尽量放在原本的位置上。所以扩容会遍历所有元素，十分耗时。
不管是链表还是红黑树，都会进行 rehash，相当于重新 put 进 Map 中，该形成链表形成链表，该转为红黑树转为红黑树。
3.1.4 put() 过程
- 首先判断数组是否为空或者长度是否为 0，是则先进行初始的扩容，默认大小为 16。
- 然后定位到的数组位置，若没有元素则直接插入。
- 如果定位到的数组位置有元素，则有如下步骤：
- 如果 key 相同，说明是更新元素，则直接覆盖；
- 如果 key 不同，说明哈希冲突了，则判断 p 是否为一个树节点：
- 如果是则将元素添加到红黑树上；
- 如果不是则遍历链表，插入到链表尾部；
详细过程如下图所示：
3.1.5 get() 过程
- 首先根据 hash 方法获取到 key 的 hash 值，然后通过
hash & (len - 1)获取 key 所对应的 Node 数组下标； - 首先判断此结点是否为空，是则返回空；是否就是要找的值，若是则直接返回该值；否则进入第二个结点；
- 接着判断第二个结点是否为空，是则返回空，不是则判断此时数据结构是链表还是红黑树；
- 链表结构进行顺序遍历查找操作，满足条件则直接返回该结点。链表遍历完都没有找到则返回空；
- 红黑树结构则执行相应的 getTreeNode( ) 查找操作。
3.2 Hashtable
Hashtable 特性如下：
- 底层数据结构：数组+链表；
- 线程安全（方法都经过 synchronized 修饰）；
- Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException；
- 基本被淘汰，不要在代码中使用
实现线程安全的方式：
使用 synchronized 来保证线程安全，因为是全局锁，效率非常低；
当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态。如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争越激烈效率越低。
初始容量和扩容大小：
- 创建时不指定容量：默认大小为 11，之后每次扩容时容量为原来的 2n+1；
- 创建时指定容量：Hashtable 直接使用给定的大小。
3.3 TreeMap
TreeMap 特性如下：
底层数据结构：红黑树；
TreeMap 和 HashMap 都继承自AbstractMap ，但是 TreeMap 还实现了 NavigableMap 接口和 SortedMap 接口：
- 实现 NavigableMap 接口让 TreeMap 有了 对集合内元素的搜索的能力。例如：返回集合中小于大于某一值的元素等类似操作；
- 实现 SortedMap 接口让 TreeMap 有了 对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。