首页  思维导图  详情

Java 集合

2022-07-25 14:10:45   165  举报





AI智能生成

根据 JavaGuide 整理的 Java集合脑图

java

集合类

学习总结

作者其他创作

大纲/内容

概念

概览

Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素； 另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。

框架图

虚线：实现；实线：继承 注：图中只列举了主要的继承派生关系，并没有列举所有关系。比方省略了AbstractList, NavigableSet等抽象类以及其他的一些辅助类

四者区别

List

(对付顺序的好帮手): 存储的元素是有序的、可重复的。

Set

(注重独一无二的性质): 存储的元素是无序的、不可重复的。

Queue

(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。

Map

(用 key 来搜索的专家): 使用键值对（key-value）存储，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

Collection

List

ArrayList

底层数据结构：Object[ ] 数组，不过是数组队列，所以可以动态的插入和删除。

适用于频繁的查找工作，线程不安全

插入/删除受元素位置影响

ArrayList 采用数组存储，所以插入/删除元素的时间复杂度受元素位置的影响。 比如：执行 add(E e) 方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。 但是如果要在指定位置 i 插入/删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的（n-i）个元素都要执行向后位/向前移一位的操作。

支持快速随机访问

快速随机访问就是通过元素的序号快速获取元素对象（对应于 get(int index) 方法）。

内存空间占用

ArrayList 的空间浪费主要体现在 list 列表的结尾会预留一定的容量空间

扩容机制

默认初始容量为 10，可以在创建 ArrayList 对象时指定容量

每次扩容之后容量都会变为原来的 1.5 倍左右，左右是因为扩容公式为：新容量 = 原容量 + (原容量 >> 1)，当原容量是奇数时，会向下取整。

底层源码分析：

LinkedList

底层数据结构：双向链表（JDK1.6 之前为循环链表，JDK1.7 取消了循环）

插入/删除不受元素位置影响

LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst() 、 removeLast()），时间复杂度为 O(1)； 如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入。

不支持快速随机访问

内存空间占用

LinkedList 的空间花费体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

在项目中一般是不会使用到 LinkedList，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好。

Vector

List 的古老实现类

底层数据结构：Object[ ] 数组

线程安全（加了 synchronized 锁）

Set

无序性和不可重复性的含义

无序性：不等于随机性，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。

不可重复性：添加的元素按照 equals() 判断时 ，返回 false，需要同时重写 equals() 方法和 HashCode() 方法。

HashSet

底层数据结构：哈希表（基于HashMap实现）

HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject() 是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

元素唯一，线程不安全

如何检查重复

当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较， 如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查  hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

应用场景：不需要保证元素插入和取出顺序的场景

LinkedHashSet

底层数据结构：链表+哈希表，元素的插入和取出满足FIFO

元素唯一，线程不安全

应用场景：保证元素的插入和取出顺序满足 FIFO 的场景

TreeSet

元素唯一，线程不安全

底层数据结构：红黑树，元素有序，排序方式有自然排序和定制排序

应用场景：支持对元素自定义排序规则的场景

Queue

Deque（Interface）

ArrayDeque

Queue和Deque的区别

Queue是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循FIFO。

Queue扩展了Collection的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法:  一种在操作失败后会抛出异常，另一种则会返回特殊值。

Deque是双端队列，在队列的两端均可插入或删除元素 Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类

操作失败后的处理方式

Queue

Deque

ArrayDeque和LinkedList的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。

ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。

ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。

ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。 虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

PriorityQueue（Class）

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据

PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。

PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。

PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

PriorityQueue的典型例题包括堆排序、求第K大的数、带权图的遍历等

Collections 工具类

排序

查找、替换

同步控制（不推荐使用，线程安全集合使用JUC）

Collections 提供了多个 synchronizedXxx() 方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。 我们知道 HashSet，TreeSet，ArrayList,LinkedList,HashMap,TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。

最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。

Map

HashMap

底层数据结构

JDK 1.7：数组+链表

JDK1.8 之前的 HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

“拉链法”：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK 1.8：数组+链表+红黑树

JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断， 如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。 因为红黑树是一颗自平衡的二叉查找树，查找效率高。由于平衡二叉树不能自平衡，调整所需的次数比红黑树多，所以采用红黑树；

什么是红黑树

从 2-3-4 树说起

2-3-4 树是阶数为 4 的 B树（Balance Tree），这种结构主要用于查找，可以把搜索元素均分，从而达到 O(log n) 的复杂度。

2-3-4 树是一颗阶数为 4 的 B树，所以它会存在：2节点、3节点、4节点。

2节点中存放着一个 key[x]，两个指针，分别指向小于 x 的子节点和大于 x 的子节点； 3节点中存放着两个 key[x, y]，三个指针，分别指向小于 x 的子节点，介于 x-y 之间的子节点和大于 y 的子节点； 4节点以此类推。

2-3-4 树到红黑树的转化

红黑树是对概念模型2-3-4树的一种实现，由于直接进行不同节点间的转化会造成较大的开销， 所以选择以二叉树为基础，在二叉树的属性中加入一个 <span style="font-weight: 600; font-synthesis: style; font-family: -apple-system, BlinkMacSystemFont, "Helvetica Neue", "PingFang SC", "Microsoft YaHei", "Source Han Sans SC", "Noto Sans CJK SC", "WenQuanYi Micro Hei", sans-serif;">颜色属性 来表示2-3-4树中不同的节点。

2-3-4树中的 2节点对应着红黑树中的黑色节点，而2-3-4树中的非2节点是以 <span style="font-weight: 600; font-synthesis: style; font-family: -apple-system, BlinkMacSystemFont, "Helvetica Neue", "PingFang SC", "Microsoft YaHei", "Source Han Sans SC", "Noto Sans CJK SC", "WenQuanYi Micro Hei", sans-serif;">红节点+黑节点 的方式存在， 红节点的意义是与黑色父节点结合，表达着2-3-4树中的 3，4节点。

先看2-3-4树到红黑树的节点转换。2节点直接转化为黑色节点；3节点这里可以有两种表现形式， 左倾红节点或者右倾红节点。而 4节点被 强制<span style="font-synthesis: style; font-family: -apple-system, BlinkMacSystemFont, "Helvetica Neue", "PingFang SC", "Microsoft YaHei", "Source Han Sans SC", "Noto Sans CJK SC", "WenQuanYi Micro Hei", sans-serif;">要求<span style="font-weight: 600; font-synthesis: style; font-family: -apple-system, BlinkMacSystemFont, "Helvetica Neue", "PingFang SC", "Microsoft YaHei", "Source Han Sans SC", "Noto Sans CJK SC", "WenQuanYi Micro Hei", sans-serif;"> 转化为一个黑父带着左右两个红色儿子。

我们研究的主体是 2-3树（原因会在后文给出），并且是2-3树中较为特殊的一种转化--左倾红黑树。 顾名思义，左倾红黑树限制了如果在树中出现了 红色节点，那么这个节点 必须是左儿子。

对于红黑树转2-3树，只需要把 左倾红黑树中的红色节点顺时针旋转45°， 使其与父节点平行，然后再将它们看作一个整体即可：

所以，红黑树其实就是对概念模型2-3树（或者2-3-4树）的一种实现

红黑树

红黑树有五条定义： <ol><li>节点颜色有红色和黑色；</li><li>根节点必须为黑色；</li><li>所有叶子节点都是黑色；</li><li>任意节点到叶子节点经过的黑色节点数量相同；</li><li>不会有连续的红色节点；</li></ol>

左倾红黑树的插入

对于左倾红黑树的插入一共有三种情况

情况一：待插入元素比黑父大，插在了黑父的右边，而黑父左边 是红色儿子。这种情况会导致在红黑树中 出现右倾红节点。 这时需要进行调整，将原本红色的左右儿子染黑，再将黑父染红。

情况二：待插入元素比红父小，且红父自身就是左倾。这时 红父和待插入元素同时靠在了左边，形成了 连续的红节点。 这种情况我们需要用两步来调整。由于我们插入的是红色节点，其实 不会破坏黑色 完美平衡，所以要注意的是 在旋转和染色的过程种继续保持这种完美黑色平衡。 <ol><li>首先对红父的父亲进行一次右旋，这次右旋不会破坏黑色平衡，但是也没有解决连续红色的问题。</li><li>接下来 将12所在节点与15所在节点交换颜色，为了消除连续红色，并且这个操作依旧维持了黑色平衡。</li><li>现在我们已经得到了情况一的场景，直接按情况一处理即可。</li></ol>

情况三：待插入元素比红父大，且红父自身就是左倾。这时插入的节点 形成了一个右倾的红节点。 这只需要将红父进行一次左旋，就能使得右倾红节点变为左倾，现在出现了连续的左倾红节点，按情况二处理即可。

可以看到，左倾红黑树的插入 最多只需要操作三次即可将红黑树调整平衡，效率是很高的。

key，value 都允许为 null

线程不安全

因为线程安全问题，HashMap效率比Hashtable高

可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个

初始容量和扩容大小

初始容量

创建时不指定容量： <ul><li>不指定容量时，不会初始化容量，只会初始化一个加载因子 loadFactor；</li><li>当执行插入方法时，才会初始化容量，默认大小为 16； </li><li>之后 每次扩容时容量为原来的 2 倍 </li></ul>

创建时指定容量： <ul><li>HashMap会将其扩充为 2 的幂次方大小</li><li>若指定容量不是 2 的幂次方，则会向上寻找里的最近的 2 的幂次方大小的数）</li></ul>

扩容大小

至于为什么每次扩容到原来的 2 倍，一因为要 维持容量为 2 的幂次方（原因在下）。

二是因为 在扩容后进行 rehash（重新计算旧数组元素在新数组地址）时可以尽可能的减少元素位置的移动。 ‌从下面一个简单的扩容示例可以看出，数组初始长度为 2 的幂次方，随后以 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 的长度为什么是 2 的幂次方。

除了使用 & 更加高效外，最重要的是 使用（n - 1）& hash 得到的下标位置可以均匀的散布在数组中，减少哈希冲突。 ‌n若是2的幂次方，则 n-1 的二进制就是 11111***111 这样的形式，那么 (n-1) 与 hash 进行位运算不仅效率很高， ‌而且能均匀的散列，因为 1 只有和 1 进行 & 运算时结果才为 1，所以只有哈希值的 1 的位置都相同时，才会出现哈希冲突。 我们画图位运算一下。就拿数组长度为4来说，4 - 1 = 3 的二进制为 011

何时扩容

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  中，该形成链表形成链表，该转为红黑树转为红黑树。

put 过程

首先判断数组是否为空或者长度是否为 0，是则先进行初始的扩容，默认大小为 16。

然后定位到的数组位置，若没有元素则直接插入。

如果定位到的数组位置有元素，则有如下步骤： <ul><li>如果 key 相同，说明是更新元素，则直接覆盖；</li><li>如果 key 不同，说明哈希冲突了，则判断 p 是否为一个树节点；</li></ul><ol><li>如果是则将元素添加到红黑树上；</li><li>如果不是则遍历链表，插入到链表尾部；</li></ol>

详细的过程如下图：

get 过程

首先根据 hash 方法获取到 key 的 hash 值，然后通过 hash & (len - 1) 获取 key 所对应的 Node 数组下标

首先判断此结点是否为空，是则返回空；是否就是要找的值，若是则直接返回该值；否则进入第二个结点。

接着判断第二个结点是否为空，是则返回空，不是则判断此时数据结构是链表还是红黑树

链表结构进行顺序遍历查找操作，满足条件则直接返回该结点。链表遍历完都没有找到则返回空。

红黑树结构执行相应的 getTreeNode( ) 查找操作。

底层源码分析：

Hashtable

底层数据结构：数组+链表

线程安全（方法都经过 synchronized 修饰）

实现线程安全的方式

使用 synchronized 来保证线程安全，因为是全局锁，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能 会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

基本被淘汰，不要在代码中使用

Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。

初始容量和扩容大小

创建时不指定容量：默认大小为11，之后每次扩容时容量为原来的2n+1 创建时指定容量：Hashtable直接使用给定的大小

TreeMap

底层数据结构：红黑树

TreeMap 和 HashMap 都继承自AbstractMap ，但是需要注意的是 TreeMap 它还实现了 NavigableMap 接口和 SortedMap 接口。 <ul><li>实现 NavigableMap 接口让 TreeMap 有了 对集合内元素的搜索的能力。例如：返回集合中小于大于某一值的元素等类似操作。</li><li>实现 SortedMap 接口让 TreeMap 有了 对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。</li></ul>

ConcurrentHashMap

底层数据结构

JDK 1.7：(Segment)分段数组+链表

JDK 1.8：(Node)数组+链表+红黑树

key，value 都不允许为 null

二义性问题

假设 ConcurrentHashMap 允许插入 null，那么此时会有二义性问题： <ul><li>value 没在集合中，所以返回 null；</li><li>value 本身就是 null，所以返回它本身的 null 值；</li></ul>

这就是 ConcurrentHashMap 的二义性问题，那为什么 HashMap 就不怕二义性问题呢？

可证伪的 HashMap

HashMap 的设计是给单线程使用的，所以如果查询到了 null 值，我们可以通过 containsKey(key) 方法来区分这个 null 值是集合中没有这个 key，还是这个 key 的 value 就是 null： <ul><li>若 containsKey 返回 false，那说明集合中没有这个 key；</li><li>若 containsKey 返回 true，则说明这个 key 的 value 就是 null；</li></ul>

这样 HashMap 的二义性就通过 containsKey() 方法得到了解决。

不可证伪的 ConcurrentHashMap

ConcurrentHashMap 就不一样了，因为它是设计在多线程下使用的，所以它的情况更加复杂。

假设 ConcurrentHashMap 可以存入 null 值，如果有一个线程 T1 查询到了 null 值，它也想通过 containsKey(key) 方法来判断这个值到底是哪种情况，我们来看看是否会有二义性问题。

因为 ConcurrentHashMap 是在并发场景下使用的，所以假设在 T1 调用 containsKey 方法后， 另一个线程 T2 立马插入了一个 key 为 null 的值，这样便使得 T1 的返回结果为 true。

发现问题了吗？T1 返回 true，那它会认为它之前读取到的 value 就是为 null，认为之前存在这个 key。

但实际上，在 T1 查询到 null 值的时候，这个 null 值还没被添加进去，正确的答案应该是：之前不存在这个 key 。

所以，并发场景下，如果 key、value 允许为 null，是存在二义性的。

线程安全

ConcurrentHashMap 实现线程安全通过 synchronized 和 CAS 来保证

例如在初始化容量、判断桶是否为空都是通过 CAS 实现，不用加锁，效率高；

在需要操作链表或红黑树时，使用 synchronized 加锁，不过也只是锁某个桶，只要不发生哈希冲突，就不会阻塞；

实现线程安全的方式

JDK 1.7

ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。 但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。

底层具体实现：

JDK 1.8

摒弃了 Segment 的概念，不再是之前的 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。 不过，Node 只能用于链表的情况，红黑树的情况需要转为 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。

底层具体实现：

并发控制使用 synchronized 和 CAS 来操作。 <ul><li>在初始化容量、判断桶是否为空等都是通过 CAS 实现，不用加锁，效率高；</li></ul><ul><li>在需要操作链表或红黑树时，使用 synchronized 加锁，不过也只是锁某个桶，只要不发生哈希冲突，就不会阻塞；</li></ul>

synchronized 只锁定当前链表或红黑树的首节点，这样只要 hash 不冲突，就不会产生影响其他操作，效率提高了很多。

ConcurrentHashMap 1.8 底层源码分析

初始化 initTable

从源码中可以发现 ConcurrentHashMap 的初始化是通过 自旋和 CAS 操作完成的。 里面需要注意的是变量 sizeCtl ，它的值决定着当前的初始化状态： <ul><li>-1 说明正在初始化</li><li>-N 说明有N-1个线程正在进行扩容</li><li>表示 table 初始化大小，如果 table 没有初始化</li><li>表示 table 容量，如果 table 已经初始化。</li></ul>

put

直接过一遍 put 源码。

流程： <ul><li>根据 key 计算出 hashcode 。</li></ul> <ul><li>判断是否需要进行初始化。</li></ul> <ul><li>即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。</li></ul> <ul><li>如果当前位置的 hashcode == MOVED == -1，则需要进行扩容。</li></ul> <ul><li>如果都不满足，则利用 synchronized 锁写入数据，锁首节点 Node。</li></ul> <ul><li>如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法，在 treeifyBin 中会首先判断当前数组长度 ≥ 64 时才会将链表转换为红黑树。</li></ul>

get

get 流程比较简单，直接过一遍源码。

总结一下 get 过程： <ul><li>根据 hash 值计算位置。</li><li>查找到指定位置，如果头节点就是要找的，直接返回它的 value.</li><li>如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，使用 find() 查找之。</li><li>如果是链表，遍历查找之。</li></ul>

常用集合源码分析

ArrayList

简介

ArrayList 的底层是 数组队列，相当于 动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前， 应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

ArrayList继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。 <ul><li>RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。 在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。</li><li>ArrayList 实现了 Cloneable 接口 ，即覆盖了函数clone()，能被克隆。</li><li>ArrayList 实现了 java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。</li></ul>

ArrayList 和 Vector 的区别？

ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储，适用于频繁的查找工作，线程不安全 ；

Vector 是 List 的古老实现类，底层使用 Object[ ]存储，线程安全的。几乎所有方法都加了 Synchronized，所以 效率很低。

ArrayList 和 LinkedList 的区别？

是否保证线程安全： <ul><li>都不保证线程安全；</li></ul>

底层数据结构：  <ul><li>Arraylist 底层使用的是 Object 数组；</li><li>LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环）</li></ul>

是否支持快速随机访问：  <ul><li>LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。</li><li>快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。</li></ul>

内存空间占用：  <ul><li>ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间；</li><li>而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。</li></ul>

扩容机制

先从 ArrayList 的构造函数说起

（JDK8）ArrayList 有三种方式来初始化，构造方法源码如下：

以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组 进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。

一步一步分析 ArrayList 扩容机制

当添加元素时，如果元素个数+1> 当前数组长度 【size + 1 > elementData.length】时， 进行扩容，扩容后的数组大小是： oldCapacity + (oldCapacity >> 1)。

注意：扩容并不是严格的1.5倍，当 oldCapacity 为奇数时，会向下取整。

扩容因子的大小选择，需要考虑如下情况： <ul><li>扩容容量不能太小，防止频繁扩容，频繁申请内存空间 + 数组频繁复制</li></ul><ul><li>扩容容量不能太大，需要充分利用空间，避免浪费过多空间；</li></ul><ul><li>为了能充分使用之前分配的内存空间，最好把增长因子设为 1<k<2.</li></ul>

HashMap

上面

ConcurrentHashMap

上面

使用注意事项

集合判空

《阿里巴巴 Java 开发手册》的描述如下： 判断所有集合内部的元素是否为空，使用 isEmpty() 方法，而不是 size()==0 的方式。 这是因为 isEmpty() 方法的可读性更好，并且时间复杂度为 O(1)。

绝大部分我们使用的集合的 size() 方法的时间复杂度也是 O(1)，不过，也有很多复杂度不是 O(1) 的， 比如 java.util.concurrent 包下的某些集合（ConcurrentLinkedQueue 、ConcurrentHashMap...）。

集合转 Map

《阿里巴巴 Java 开发手册》的描述如下： 在使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合时，一定要注意当 value 为 null 时会抛 NPE 异常。

原因

首先，我们来看 java.util.stream.Collectors 类的 toMap() 方法 ，可以看到其内部调用了 Map 接口的 merge() 方法。

Map 接口的 merge() 方法如下，这个方法是接口中的默认实现。

merge() 方法会先调用 Objects.requireNonNull() 方法判断 value 是否为空，为空则抛出异常。

集合遍历

《阿里巴巴 Java 开发手册》的描述如下： 不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。

通过反编译你会发现 foreach 语法糖底层其实还是依赖 Iterator 。不过， remove/add 操作直接调用的是集合自己的方法，而不是 Iterator 的 remove/add方法。 这就导致 Iterator 莫名其妙地发现自己有元素被 remove/add ，然后，它就会抛出一个 ConcurrentModificationException 来提示用户发生了并发修改异常。这就是单线程状态下产生的 fail-fast 机制。 fail-fast 机制 ：多个线程对 fail-fast 集合进行修改的时候，可能会抛出ConcurrentModificationException。 即使是单线程下也有可能会出现这种情况，上面已经提到过。

Java8 开始，可以使用 Collection#removeIf() 方法删除满足特定条件的元素,如：

集合去重

《阿里巴巴 Java 开发手册》的描述如下： 可以利用 Set 元素唯一的特性，可以快速对一个集合进行去重操作，避免使用 List 的 contains() 进行遍历去重或者判断包含操作。

以 HashSet 和 ArrayList 为例，两者的核心差别在于 contains() 方法的实现。

HashSet 的 contains() 方法底部依赖 HashMap 的 containsKey() 方法，时间复杂度接近 O(1)（未出现哈希冲突时）。 当我们有 N 个元素插入 Set 时，时间复杂度就接近 O(n) 。

ArrayList 的 contains() 方法是通过遍历所有元素的方法来做的，时间复杂度接近是 O(n)。 当我们有 n 个元素插入 List 时，时间复杂度就接近 O(n^2) 。

集合转数组

《阿里巴巴 Java 开发手册》的描述如下： 使用集合转数组的方法，必须使用集合的 toArray(T[] array)，传入的参数是类型完全一致、长度为 0 的空数组。

toArray(T[] array) 方法的参数是一个泛型数组，如果 toArray 方法中没有传递任何参数的话返回的是 Object 类型数组。 由于 JVM 优化，new String[0] 作为 Collection.toArray() 方法的参数现在使用更好，new String[0] 就是起一个模板的作用， 指定了返回数组的类型，0 是为了节省空间，因为它只是为了说明返回的类型。

数组转集合

《阿里巴巴 Java 开发手册》的描述如下： 使用工具类 Arrays.asList() 把数组转换成集合时，不能使用其修改集合相关的方法， 它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。

1. Arrays.asList() 是泛型方法，传递的数组必须是对象数组，而不是基本类型。

当传入一个原生数据类型数组时，Arrays.asList() 的真正得到的参数就不是数组中的元素，而是数组对象本身！ 此时 List 的唯一元素就是这个数组，这也就解释了上面的代码。 我们使用包装类型数组就可以解决这个问题。

2. 使用集合的修改方法: add()、remove()、clear() 会抛出异常。

Arrays.asList() 方法返回的并不是 java.util.ArrayList ，而是 java.util.Arrays 的一个内部类 java.util.Arrays$ArrayList，这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。

java.util.Arrays$ArrayList 内部类继承了 AbstractList<E>，并没有重写add/remove/clear 方法， 再看看 java.util.AbstractList的 add/remove/clear 方法就知道为什么会抛出 UnsupportedOperationException 了。

3. 如何正确的将数组转为 ArrayList

（1）手动实现工具类

（2）最简便的方法，直接使用 ArrayList 的构造方法创建 ArrayList

（3）使用 Java8 的 Stream (推荐)

（4）使用 Java9 的 List.of() 方法