HashMap源码分析
在学习HashMap之前我们带着问题去学习。
HashMap的底层存储结构是怎样的啊？ 为什么要引入红黑树，什么时候转变红黑树？ 为什么加载因子默认0.75？ 为什么退化为链表的阈值是6？ 为什么HashMap底层树化标准的元素个数是8？ HashMap的容量为什么需要是2的n次幂？ HashMap的计算哈希值的算法是怎样的？ 线程安全吗？为什么不安全？ HashMap添加元素的过程？ HashMap扩容的过程？ HashMap为什么要自己重写序列化相关的方法？
❝本文基于JDK8
HashMap基本介绍
HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，即主要用来存放键值对。HashMap的实现不是同步的，这意味着它不是线程安全的。它的key和value都可以为null。此外，HashMap中的映射不是有序的。
JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（"拉链法"解决冲突）。
JDK1.8以后在解决哈希冲突时有了较大的变化，底层的数据结构改为了数组+链表+红黑树，当链表长度大于阈值（或者红黑树的边界值，默认为8)并且当前数组的长度大于64时，此时此索引位置上（桶）的所有数据改为使用红黑树存储。
需要注意：将链表转换成红黑树前会判断，即使阈值大于8，假如数组长度小于64，此时并不会将链表变为红黑树，而是选择进行数组扩容。这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡。同时数组长度小于64时，搜索时间相对要快些。所以综上所述为了提高性能和减少搜索时间，底层在阈值大于8并且数组长度大于64时，链表才转换为红黑树。当红黑树的节点少于6的时候，还是会变回链表。
当然虽然增了红黑树作为底层数据结构，结构变得复杂了，但是阈值大于8并且数组长度大于64时。链表转换为红黑树时，效率也变的更高效。
小结：
（1）存取无序的
（2）键和值位置都可以是null，但是键位置只能是一个null
（3）键位置是唯一的，底层的数据结构控制键的
（4）JDK1.8前数据结构是：链表+数组 JDK.8之后是：链表+数组+红黑树
（5）阈值(边界值)>8并且数组长度大于64,才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。
添加元素过程例子
public class HashMapDemo01 {
public static void main(String[] args) {
HashMap<String,Integer> map = new HashMap<>();
map.put("曹操",26);
map.put("张辽",23);
map.put("夏侯惇",25);
map.put("曹操",23); // 因为Key唯一，所以这行就是修改功能，覆盖
System.out.println(map);
}
}
测试结果：
{张辽=23, 曹操=23, 夏侯惇=25}
（1）当使用空参构造方法创建集合对象的时候，在JDK8前，构造方法中默认创建一个长度是16的Entry[] table 用来存储键值对数据的。在JDK8以后不是在HashMap的构造方法底层创建数组了，是在第一次调用put方法时创建数组Node[] table用来存储键值对数据的。
（2）假设向哈希表中存储“曹操-26”数据，根据曹操调用String类重写之后的hashCode()方法计算出值，然后结合数组长度采用某种算法计算出向Node数组中存储数据的空间索引值。如果计算出的索引空间（桶中）没有数据，则直接将“曹操-26”存储到数组中。举例：假如计算的索引是3。
（3）假如向哈希表中存储“张辽-23”数据，假设结合数组长度求出的索引的长度为6，发现6位置没有元素，那么直接放到数组中。
（4）向哈希表中存储数据“夏侯惇-25”，假设夏侯惇计算出的hashCode方法结合数组长度计算出的索引值也是3，那么此时数组空间不是null（桶位存在数据），此时底层会比较曹操和夏侯惇的hash值是否一致，如果不一致，则在此空间上划出一个节点来存储键值对数据“夏侯惇-25”。这这种方式就是拉链法。ps.假如hash值相等，还需进一步通过equal方法判断它们是否相等。
（5）假设向哈希表中存储数据“曹操-23”，那么首先根据曹操调用hashCode方法结合数组长度计算出索引肯定是3。此时比较后存储在此索引位置的数据曹操和已经存在的数据的hash值是否相等，如果hash值相等，此时发生哈希碰撞。
那么底层会调用曹操所属类String中的equals方法比较两个内容是否相等：
相等：则将后添加的数据的value覆盖之前的value。
不相等：那么继续向下和其他的数据的key进行比较，如果都不相等，则划出一个节点存储数据。
此小结大概讲了下HashMap是如何添加元素的，当然隐藏了一些细节和特殊情况，先大致了解一下。
小结:
保证元素唯一的原理:哈希表结构存储数据,依赖于：hashCode与equals方法。(Object类中的)
（1）首先调用元素的hashCode()方法计算该元素的哈希值
（2）判断该哈希值对应的位置上是否有相同哈希值的元素
（3）如果该哈希值对应的位置上没有相同的哈希值元素，那么就直接存储
（4）如果该哈希值对应的位置上有相同的哈希值元素，那么就产生了哈希冲突
（5）如果产生了哈希冲突，就得调用元素的equals()方法，跟该哈希值位置上的所有元素进行一一比较；
如果该哈希值位置上任意一个元素与该元素相等，那么就新增，而是覆盖旧值。
如果该哈希值位置上任意一个元素与该元素都不相等，那么就存储。
微信公众号：肝帝笔记
源码分析
继承关系
Cloneable空接口，表示可以克隆。创建并返回HashMap对象的一个副本。 Serializable序列化接口。属于标记性接口。HashMap对象可以被序列化和反序列化。 AbstractMap父类提供了 Map实现接口。以最大限度地减少实现此接口所需的工作。
注意：通过上述继承关系我们发现一个很奇怪的现象，就是HashMap已经继承了AbstractMap而AbstractMap类实现了Map接口，那为什么HashMap还要在实现Map接口呢？同样在ArrayList中LinkedList中都是这种结构？
据java集合框架的创始人Josh Bloch，描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个的失误值得去修改，所以就这样存在下来了。
成员变量
（1）序列化版本号
private static final long serialVersionUID = 362498820763181265L;
（2）默认的初始化容量（必须是2的n次幂）
/**
* HashMap的默认初始容量16，必须是2的n次幂，这是为了后续增加运算效率的前提
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
（3）默认的加载因子，默认值是0.75
假如我们默认创建的数组的长度是16，加载因子是0.75的情况下，数组会在HashMap存储的元素个数达到16*0.75为12的时候扩容。
/**
* 默认加载因子0.75，当HashMap的元素个数大于0.75倍的容量时，就需要进行扩容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
（4）集合的最大容量，是2^30
/**
* HashMap的最大初始容量，必须是2的n次幂，也就是 2^n <= 2^30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
（5）当链表的长度超过8的时候会转为红黑树
/**
* 链表转换为红黑树的节点个数的阈值，除了这个条件，还需要HashMap的数组长度大于等于64(默认)
*/
static final int TREEIFY_THRESHOLD = 8;
（6）当链表的值小于6的时候会由红黑树转换为链表
/**
* 红黑树恢复为链表的节点个数的阈值
*/
static final int UNTREEIFY_THRESHOLD = 6;
（7）当Map里面的数量超过这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化,为了避免进行扩容、树形化选择的冲突，这个值不能小于4 *TREEIFY_THRESHOLD (8)，其实就是需要数组长度大于等于64
微信公众号：肝帝笔记
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*
* 链表转换为红黑树的HashMap底层数组的长度阈值
*/
static final int MIN_TREEIFY_CAPACITY = 64;
（8）table就是底层数组了（长度必须是2的n次幂）
/**
* 结点数组，数组长度必须是2的n次幂
*/
transient Node<K,V>[] table;
table在JDK1.8中我们了解到HashMap是由数组加链表加红黑树来组成的结构，其中table就是HashMap中的数组，JDK1.8之前数组类型是Entry<K,V>类型。从JDK1.8之后是Node<K,V>类型。只是换了个名字，都实现了 一样的接口：Map.Entry<K,V>。负责存储键值对数据的。
（9）用来存放缓存，记录key和value
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
* 存放具体元素的集合
*/
transient Set<Map.Entry<K,V>> entrySet;
（10）HashMap中存放元素的个数，size为HashMap中K-V的实时数量，不是数组table的长度
/**
* 存放元素的个数，注意这个不等于数组的长度
*/
transient int size;
（11）用来记录HashMap的修改次数，并发修改异常就是这个值引起的
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
* 每次扩容和更改Map结构的计数器
*/
transient int modCount;
（12）扩容临界值，用来调整大小下一个容量值，计算方式为（容量 × 加载因子）
注意：
假如数组未初始化，threshold表示初始数组长度 假如数组已经初始化了，threshold表示下一次扩容的临界值， capacity * load factor
。
/**
* 下一次扩容的数组长度，capacity * load factor
* 假如数组还没有初始化的时候，threshold表示初始数组长度
*/
int thresold;
（13）哈希表的加载因子
/**
* 加载因子
*/
final float loadFactor;
（1）loadFactor加载因子，是用来衡量HashMap满的程度，表示HashMap的疏密程度，影响哈希操作到同一个数组位置的概率，计算HashMap的实时加载因子的方法为：size/capacity，而不是占用桶的数是去除以 capacity，capacity是桶的数量，也就是table的长度length。 （2）loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为 0.75f，是官方给出的一个比较好的临界值。
（3）当HashMap里面容纳的元素已经达到HashMap数组长度的75%时，表示HashMap太挤了，需要扩容，而扩容 这个过程涉及到rehash、复制数据等操作，非常消耗性能，所以开发中尽量减少扩容的次数，可以通过创建 HashMap集合对象时指定初始容量来尽量避免。
（4）同时在HashMap的构造器中可以指定loadFactor。
变量部分问题
问题：为什么要引入红黑树？
在JDK8之前HashMap的是数组+链表构成的，而JDK8之后是数组+链表+红黑树组成的。
链表取元素是从头结点一直遍历到对应的结点，这个过程的复杂度是O(N) ，而红黑树基于二叉树的结构，查找元素的复杂度为O(logN) ，所以，当桶内元素个数过多时，用红黑树存储可以提高搜索的效率。
既然红黑树的效率高，那怎么不一开始就用红黑树存储呢？
微信公众号：肝帝笔记
这其实是基于空间和时间平衡的考虑，HashMap注释里有解释：大概的意思是说树结点占用大小是普通结点的两倍，只会在桶内有足够多的结点的时候才会去转为红黑树。
Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins.
问题：为什么转换红黑树的阈值是8
在HashMap中有一段注释说明：我们继续往下看：
Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use(see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)).
The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
TreeNodes占用空间是普通Nodes的两倍，所以只有当bin包含足够多的节点时才会转成TreeNodes，而是否足够 多就是由TREEIFY_THRESHOLD的值决定的，当bin中节点数变少时，又会转成普通的bin。并且我们查看源码的时候发现，链表长度达到8就转成红黑树（还有数组长度大于等于64的条件），当长度降到6就转成普通bin。
这样就解释了为什么不是一开始就将其转换为TreeNodes，而是需要一定节点数才转为TreeNodes，说白了就是 权衡，空间和时间的权衡。
这段内容还说到：当hashCode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中， 几乎不会有bin中链表长度会达到阈值。但是在随机hashCode下，离散性可能会变差，然而JDK又不能阻止用户实现这种不好的hash算法，因此就可能导致不均匀的数据分布。不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，我们可以看到，一个bin中链表长度达到8个元素的_为0.00000006，几乎是不可能事件，所以，之所以选择8，不是随便决定的，而是根据概率统计决定的。由此可见，发展将近30年的Java每 一项改动和优化都是非常严谨和科学的。
微信公众号：肝帝笔记
也就是说：选择8是因为符合泊松分布，超过8的时候，概率已经非常小了，所以我们选择8这个数字。
补充：
Poisson分布，是一种统计与概率学里常见到的离散概率分布，泊松分布的概率函数为：
泊松分布的参数λ是单位时间(或单位面积)内随机事件的平均发生次数。泊松分布适合于描述单位时间内随机事件发生的次数。
不知道哪位大神说的下面的解释：
红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，平均链表的平均查找长度为n/2，当长度为8/2时，平均查找长虔为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，而log(6)=2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
问题：为什么退化为链表的阈值是6？
可能我们有疑问为什么不是小于8就退化呢？链表转换为红黑树是一个需要浪费时间和空间的操作，假如我们某个时刻桶内元素有7个，新增一个到达8个就转为红黑树了，假如此时又变为7个元素1了，又要转回链表，这样就很浪费性能。默认6转为链表是避免链表和红黑树之间频繁的转换
微信公众号：肝帝笔记
问题：为什么数组的长度必须是2的n次幂呢？如果输入值不是2的幂，比如10或怎样？
HashMap构造方法还可以指定集合初始化容量大小
// 构造一个带有指定初始容量和默认加载因子（0.75）的空HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
根据上述讲解我们已经知道，当向HashMap中添加一个元素的时候，需要根据key的hash值，去确定其在数组中的具体位置。HashMap为了存取高效，要尽量较少哈希碰撞，就是要尽是把数据分配均匀，每个链表长度大致相同， 这个实现就需要一个算法把数据存到哪个桶中。
这个算法实际就是取模，hash%length
，计算机中求余效率不如位移运算。所以源码中做了优化，
使用hash&(length-1)
，而实际上hash%length
等价hash&(length-1)
的前提是数组length是2的n次幂。
问题又来了，为什么这样就能均匀分布减少碰撞呢？
2的n次方实际就是1后面n个0，2的n次方减一实际就是n个1。
示例：
按位与运算（&）相同的二进制数位上都是1的时候，结果为1，否则为0。
# 为什么这样就能均匀分布减少碰撞呢
（1）当数组长度是2的n次幂的时候，假如数组的长度是8
假如key的hash值为3
3 & (8-1)
00000011
00000111
--------
00000011 = 3
假如key的hash值为2
2 & (8-1)
00000010
00000111
--------
00000010 = 2
（2）当数组长度不是2的n次幂的时候，假如数组的长度是9
假如key的hash值为3
3 & (9-1)
00000011
00001000
--------
00000000 = 0
假如key的hash值为2
2 & (9-1)
00000010
00001000
--------
00000000 = 0
# 如果数组长度不是2的n次幂，计算出的索引特別容易相同，极其容易发生hash碰撞，导致其余数组空间很大程度上并没有存储数椐，链表或者红黑树过长，效率降低
当然假如不考虑效率直接求余即可（就不需要要求长度必须是2的n次方了）
小结：
（1）由上面可以看出，当我们根据key的hash确定其在数组的位置时，如果n为2的幂次方，可以保证数据的均匀插入，如果n不是2的幂次方，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大hash冲突。
（2）另一方面，一般我们可能会想通过％求余来确定位置，这样也可以，只不过性能不如&运算。而且当n是2的幂次方时：hash & (length -1) == hash % length
（3）如果创建HashMap对象时，输入的数组长度是10，不是2的幂，HashMap通过一通位移运算和或运算得到的肯定是大于等于该数的2的n次幂。
问题：为什么加载因子设置为0.75,初始化临界值是12?
load Factor越趋近于1，那么数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。
如果希望链表尽可能少些，要提前扩容，有的数组空间有可能一直沒有存储数据，加载因子尽可能小一些。
举例：
加载因子是0.4。那么16 * 0.4 = 6 如果数组中满6个空间就扩容会造成数组利用率太低了。 加载因子是0.9。那么16 * 0.9 = 14 那么这样就会导致链表有点多了。导致查找元素效率低。
所以既兼顾数组利用率又考虑链表不要太多，经过大量测试0.75是最佳方案。
微信公众号：肝帝笔记
问题：什么时候退化为链表?
有两个地方会判断并退化成链表的条件
remove时退化
// 在 removeTreeNode的方法中
// 在红黑树的root节点为空 或者root的右节点、root的左节点、root左节点的左节点为空时 说明树都比较小了
if (root == null || (movable && (root.right == null || (rl = root.left) == null|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}
123456在扩容时 low、high 两个TreeNode 长度小于6时 会退化为树。
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD) // 判断是否需要退化为链表
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD) // 判断是否需要退化为链表
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
节点对象
普通结点：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 哈希值
final K key;
V value;
Node<K,V> next; // 指向链表的下一个节点
// 省略方法...
}
树结点：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 红黑树结点颜色标志
// 省略...
}
构造函数
（1）空参构造方法，默认初始容量16和默认负载因子0.75
// 将默认的加载因子赋值给loadFactor，并没有创建数组，在第一次put的时候创建数组
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
（2）构造一个指定初始容量和默认负载因子0.75的HashMap
// 指定容量大小的构造方法，建议使用，减少hashMap扩容，因为扩容一次代价很大
// 会调用方法获取大于等于传入值的最小的2的n次幂
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
（3）构造一个指定初始容量和指定负载因子的HashMap
public HashMap(int initialCapacity, float loadFactor) {
// 判断传入的容量initialCapacity是否小于0，小于0则抛出非法参数异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 判断传入的值initialCapacity是否大于集合的最大容量 2的30次方
if (initialCapacity > MAXIMUM_CAPACITY)
// 超过MAXIMUM_CAPACITY，就将MAXIMUM_CAPACITY赋值给initialCapacity
initialCapacity = MAXIMUM_CAPACITY;
// 判断传入的加载因子是否小于等于0 或者 加载因子是否是非数字值(NaN)
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 调用tableSizeFor获取和传入数组长度最近的2次幂的数值
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
tableSizeFor(initialCapacity)
判断指定的初始化容量是否是2的n次幂，如果不是那么会变为比指定初始化容量大的最小的2的n次冪。这点上述已经讲解过。但是注意，在tableSizeFor方法体内部将计算后的数据返回给调用这里了，并且直接赋值给threshold边界值了。
有些人会觉得这里是一个bug，应该这样书写：this.threshold = tableSizeFor(initialCapacity) * this.1oadFactor;
这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。但是，请注意，在：JDK8以后的构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算，put方法的具体实现我们下面会进行讲解。
微信公众号：肝帝笔记
下面分析这个算法：
（1）首先，为什么要对cap做减1操作。int n = cap-1;
这是为了防止，cap已经是2的幂。如果cap已经是2的幂，又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍，如果不懂，要看完后面的几个无符号右移之后再回来看看， 下面看看这几个无符号右移操作：
（2）如果n这时为0了（经过了cap-1
之后），则经过后面的几次无符号右移依然是0，最后返回的capacity是1（最后有个n+1的操作），这里只讨论n不等于0的情况。
假如传入的是10
（1）首先减一，此时n为9
（2）第一次右移
n |= n >>> 1;
00000000 00000000 00000000 00001001 // 9
00000000 00000000 00000000 00000100 // 9右移之后变为4
-----------------------------------
00000000 00000000 00000000 00001101 // 按位异或操作得到13
（3）第二次右移
n |= n >>> 2;
00000000 00000000 00000000 00001101 // 13
00000000 00000000 00000000 00000011 // 13右移之后变为3
-----------------------------------
00000000 00000000 00000000 00001111 // 按位异或操作得到15
（3）第三次右移
n |= n >>> 4;
00000000 00000000 00000000 00001111 // 13
00000000 00000000 00000000 00000000 // 13右移之后变为0
-----------------------------------
00000000 00000000 00000000 00001111 // 按位异或操作得到15
（4）...后面的操作得到的还是15
（5） return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
n+1之后就是16了
注意：
容量最大也就是32bit的正数，因此最后n |= n >>> 16;
最多也就32个1（但是这已经是负数了。在执行 tableSizeFor之前，对initialCapacity做了判断，如果大于MAXIMUM_CAPACITY(2^30)
,则取 MAXIMUM_CAPACITY
。如果等于MAXIMUM_CAPACITY(2^30)
，会执行移位操作。所以这里面的移位操作之后，最大30个1，不会大于等于MAXIMUM_CAPACITY
。30个1，加一之后得到2^30。
但是，得到的这个Capacity却被赋值给threshold了，是数组扩容的阈值。
// 构造器中将获得到的Capacity值赋值给threshold了
this.threshold = tableSizeFor(initialCapacity);
（4）构造一个包含另一个Map的HashMap
// 构造一个映射关系与制定的Map相同的HashMap
public HashMap(Map<? extends K, ? extends V> m) {
// 负载因子loadFactor变为默认的负载因子0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 调用putMapEntries方法 后面讲
putMapEntries(m, false);
}
成员方法
只说重要的方法。无非就是增删改查。
put方法
put方法里面涉及了很多其他的方法，例如扩容等方法。
/**
* 添加元素的方法
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
求哈希值方法
static final int hash(Object key) {
int h;
// 假如key为null的时候，返回0，这也说明了HashMap是可以存储null键的
// key不为null的时候，进行后面的无符号右移16位再与原来值异或操作获得hash值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我们可以看到当我们传入的key为null的时候，会返回一个默认的哈希值0，这也是HashMap的key为什么可以存null的原因。
示例：
求出key的hash值的算法：h = key.hashCode()) ^ (h >>> 16)
求出key在桶中位置的算法：i = (n - 1) & hash
假设key.hashCode计算出的值：
1111 1111 1111 1111 1111 0000 1110 1010 就是h
首先h无符号右移16位 h >>> 16
0000 0000 0000 0000 1111 1111 1111 1111
与原来的h进行异或操作后：
1111 1111 1111 1111 1111 0000 1110 1010
0000 0000 0000 0000 1111 1111 1111 1111
---------------------------------------
1111 1111 1111 1111 0000 1111 0001 0101
再与数组的长度减一做与操作
1111 1111 1111 1111 0000 1111 0001 0101
0000 0000 0000 0000 0000 0000 0000 1111 数组长度16 - 1
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 结果：5
简单来说就是：高16bit不变，低16bit和高16bit做了一个异或（得到的hashcode转化为32位二进制，前16位和后16位）
为什么要做这样的操作呢？
如果n即数组长度很小，假设是16的话，那么n-1的二进制位1111，这样的值和hashCode()直接做按位与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。
说的不好看，看下例子：
假如我们不进行右移16再异或操作，而是直接使用hashCode方法获得的值进行按位与运算
求出key在桶中位置的算法：i = (n - 1) & hash
假设key.hashCode计算出的值 1：1111 1111 1111 1111 1111 0000 1110 1010
1111 1111 1111 1111 1111 0000 1110 1010
0000 0000 0000 0000 0000 0000 0000 1111 数组长度16 - 1
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 结果：5
假设key.hashCode计算出的值 2：1111 1111 1111 0000 1111 0000 1110 1010
1111 1111 1111 0000 1111 0000 1110 1010
0000 0000 0000 0000 0000 0000 0000 1111 数组长度16 - 1
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 结果：5
微信公众号：肝帝笔记
当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了。我们发现高位发生了很大的变化，但是求出来的索引还是5，就会发送哈希冲突，造成这个桶很拥挤。所以hash方法将高低位都利用起来，从而解决了这个问题。
问题：哈希表底层采用何种算法计算哈希值？还有哪些算法可以计算出哈希值？
底层采用key的hashCode方法的值结合数组长度进行无符号右移16位（>>>）、按位异或（^）、按位与（&）计算出索引。
还可以采用：平方取中法、求余数、伪随机数法。例如取余法：
10 % 8 = 2
11 % 8 = 3
那么为什么HashMap底层不使用这些方法呢？因为下面的几种算法的效率比较低，而位运算的效率比较高。
真正添加元素的方法
/**
* 真正添加元素的方法
*
* @param hash key的哈希值
* @param key
* @param value
* @param onlyIfAbsent if true, don't change existing value 如果为true代表不更改现有的值
* @param evict false表示初始化状态
* @return 返回添加之前的原值，null或者其他
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab:底层存数据的数组
// p:哈希值命中数组的位置的元素
// n:数组的长度
// i:哈希值命中数组的位置的索引
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 将节点数组赋值给tab
// 当数组为空或者数组长度为0的时候，就调用resize()方法进行扩容
// 并将扩容后的数组的长度赋值给变量n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 因为数组table长度是2的n次幂，所以(n - 1) & hash这个运算和%取模运算等价
// 这样做是为了提高效率
// 假如tab[i]的位置为null，也就是没有元素，没发生哈希碰撞，就直接创建节点放入该位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 此处是发生了哈希碰撞
// e:
// k:哈希命中位置的元素的key
Node<K,V> e; K k;
// 发生哈希碰撞可能是因为两个key对象一样
// 还有一种可能就是key不一样，但是恰好哈希值一样
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 发生了哈希碰撞，且两个key对象相等
e = p;
else if (p instanceof TreeNode)
// 假如此时的p节点已经是树节点了，调用putTreeVal方法添加元素
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 遍历链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 假如p的下一个节点为null，就创建一个节点
p.next = newNode(hash, key, value, null);
// 若binCount此时大于等于8，就需要将链表转成红黑树
// 但并不是一定会转出红黑树，还需要数组长度至少为64，后面讲
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 依次和链表的每个节点做比较，如果两个key对象相等导致的哈希碰撞
// 两个key相等，直接退出
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // 链表指针后移
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 根据onlyIfAbsent来决定是否更改旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 由LinkedHashMap实现
return oldValue; // 返回旧值
}
}
++modCount;
// 假如自增后的元素个数大于扩容阈值，则进行扩容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict); // 由LinkedHashMap实现
return null;
}
只要两个元素的key计算的哈希码值相同就会发生哈希碰撞。JDK8前使用链表解决哈希碰撞。jdk8之后使用链表+红黑树解决哈希碰撞。
问题：简述put方法过程？
put方法是比较复杂的，实现步骤大致如下：
（1）首先通过哈希算法集合数组长度算出Key在数组中的位置，即计算元素放在哪个桶里。
（2）如果此桶还没有元素，即没有发送哈希碰撞，则直接插入。
（3）如果此桶上有元素了，即发生了哈希碰撞，则需要进行处理。调用key所属类的equals方法，依次判断该桶下链表或者红黑树的所有key是否和要添加的这个key重复。假如重复则直接覆盖相同key的value值。假如不重复：
A：如果该桶使用了红黑树进行处理冲突，则调用红黑树方法插入数据。
B：如果该桶还是使用的链表来处理哈希冲突，如果长度达到临界值则把链表转变为红黑树。
（4）如果Size大于扩容阈值threshold则进行扩容。
扩容方法
在初始化数组或者需要扩容的时候就会调用resize
方法，会根据不同的构造方法来对数组进行初始化。
在扩容的时候需要将旧元素按照新的数组长度进行路由寻址，由于HashMap的容量是2的n次幂，且每次扩容的时候是扩容原容量的两倍，所以旧元素的位置只可能是在原位置或者原位置间隔2的n次幂偏移。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 旧数组长度，初始化的时候oldCap的值为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧的扩容阈值
// 空参构造初始化的时候threshold的值为0
// 有参构造初始化时此时threshold的值代表数组的长度
int oldThr = threshold;
int newCap, newThr = 0;
// table的长度不为0
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果原容量已经达到最大容量了，无法进行扩容，直接返回旧数组
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 假如旧的容量扩容两倍后的大小小于最大容量，且旧容量大于等于默认容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 阈值也变为原来的两倍
newThr = oldThr << 1; // double threshold
}
// 构造方法指定容量initialCapacity的，将新的容量设置为旧threshold
// 在构造方法中有行代码 this.threshold = tableSizeFor(initialCapacity);
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 构造方法中没有指定容量，也就是空参构造器，则使用默认值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr可能为0是因为调用了有参构造函数，设置了initialCapacity的
// 需要重新赋值newThr
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 空参构造时threshold真正是在此处赋值的
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的数组，HashMap的数组是在第一次添加元素时创建的
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 赋值新数组给table
if (oldTab != null) {
// 遍历旧数组，重新计算位置，放入新数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 清空旧表的引用，help GC
if (e.next == null)
// e.next为空，说明原数组此节点下面没有挂链表，直接赋值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 红黑树，里面会有红黑树退为链表的操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 拆链表
Node<K,V> loHead = null, loTail = null; // lo低位链表
Node<K,V> hiHead = null, hiTail = null; // hi高位链表
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
// 扩容后还在同一个桶
if (loTail == null)
loHead = e; // 低位链表第一添加元素
else
loTail.next = e; // 低位链表尾部添加元素
loTail = e; // 低位尾部指针后移
}
else {
// 扩容后不在同一个桶
if (hiTail == null)
hiHead = e; // 高位链表第一次添加元素
else
hiTail.next = e; // 高位链表尾部添加元素
hiTail = e; // 高位尾部指针后移
}
} while ((e = next) != null); // 链表指针后移
if (loTail != null) {
loTail.next = null;
// 低位链表放在原位置
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 高位链表放在偏移oldCap位置
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
扩容方法解释：
可能大家对扩容时重新计算哈希值并移动元素位置的操作不太理解。
微信公众号：肝帝笔记
在扩容的过程会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。
HashMap在进行扩容时，使用的rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算的(n-1)&hash
的结果相比，只是多了一个bit位，所以节点要么就在原来的位置，要么就被分配到**”原位置+旧容量”**这个位置。
rehash过程分析
初始化一个HashMap，给一个初始容量8，此时的元素的存储示意如下
HashMap<Integer, String> map = new HashMap<>(8);
map.put(1,"开");
map.put(9,"源");
map.put(17,"节");
map.put(25,"流");
假如后面添加元素，达到了HashMap的扩容阈值，那么数组的长度将会变为16，此时会进行重新计算哈希，重新路由寻址的操作。
哈希值路由寻址的算法等价于求余，显然，上面四个元素都存在数组的索引为1的桶位。扩容之后新数组长度是16，采用e.hash & oldCap
来决定位置
假如值为1，扩容后不在一个桶内。 假如值为0，扩容后在一个桶内，新桶在原索引+oldCap(原位置+旧容量)
正是因为这样巧妙的rehash方式，既省去了重新计算hash值的时间，而且同时，由于新增的1个bit是0还是1可以认为是随机的，在resize的过程中保证了rehash之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了 rehash之后不会出现更严重的hash冲突，均匀的把之前的冲突的节点分散到新的桶中了。
问题：什么时候会调用这个扩容resize方法呢？
第一：在数组初始化的时候会调用resize
方法。
第二：在HashMap中元素个数达到了扩容阈值时，回调用resize
方法进行扩容。
当HashMap中的元素个数超过 数组大小(数组长度) * loadFactor(负载因子) 时，就会进行数组扩容，loadFactor的 默认值(DEFAULT_LOAD_FACTOR)是0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当 HashMap中的元素个数超过16 × 0.75 = 12 (这个值就是阈值或者边界值threshold值)的时候，就把数组的大小扩展为 2 × 16 = 32，即扩大一倍，然后重新计算每个元素在数组中的而这是一个非常耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预知元素的个数能够有效的提高HashMap的性能。
微信公众号：肝帝笔记
当HashMap中的其中一个链表的对象个数如果达到了8个，此时如果数组长度没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链表会变成红黑树，节点类型由Node变成TreeNode类型。当然，如果映射关系被移除后，下次执行resize方法时判断树的节点个数低于6，也会再把树转换为链表。
转换红黑树的方法
链表转换红黑树不仅仅需要链表长度大于等于8，还需要底层数组的长度大于等于64。假如底层数组的长度小于64，此时并不会去转换红黑树，而是去扩容底层数组。这样做是因为数组长度太小了非常容易产生哈希碰撞，而维护红黑树也是有代价的。
/**
* 替换指定哈希表的索引处桶中的所有链接节点，假如表太小就扩容
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// table数组为null或者长度小于阈值64，就进行扩容，不转换红黑树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 当table数组的index位置有元素时，才转成红黑树
else if ((e = tab[index = (n - 1) & hash]) != null) {
// hd: 头节点
// tl: 指针
TreeNode<K,V> hd = null, tl = null;
do {
// 将链表节点转换成树节点TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
// 第一遍循环时：hd指向头节点
hd = p;
else {
// 后面的循环：依次将遍历到的节点放在上一个节点的后面
p.prev = tl;
tl.next = p;
}
tl = p; // 后移
} while ((e = e.next) != null);
// 让桶中的第一个元素，即数组中的元素指向新建的红黑树的节点，
// 以后这个桶里的元素就是红黑树，而不是链表数据结构了
if ((tab[index] = hd) != null)
// 将链表进行树化
hd.treeify(tab);
}
}
/**
* 将Node节点(链表节点)转换成TreeNode节点(红黑树节点)
*/
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
/**
* 1. 将头结点作为root节点，然后依次将next节点插入到根节点，转变红黑树。
* 2. 再插入时候key比较
* 1. 如果key实现了comparable接口，通过实现方式比较
* 2. 否则比较key的hashCode
* 3. 否则比较key的class.getName
* 4. 否则比较key的System.identityHashCode比较
* 3. 最后树化后，取出root节点（TreeNode），放到entry下标位置
*/
final void treeify(Node<K,V>[] tab) {
// 树的根节点
TreeNode<K,V> root = null;
// x是当前节点，next是后继节点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
// 当前节点的直接后继节点
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
// 如果根节点为空，就把当前节点设置为根节点
if (root == null) {
x.parent = null;
x.red = false; // 根节点是黑色
root = x;
}
// 不是根节点
else {
// k：当前遍历的节点的key值 h：当前遍历节点的哈希值
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
// p:当前遍历的节点 pk：当前遍历节点的key值 ph：当前遍历节点的哈希值
int dir, ph;
K pk = p.key;
// dir用来指示x节点与p的比较，-1表示比p小，1表示比p大
// 不存在相等情况，因为HashMap中是不存在两个key完全一致的情况
if ((ph = p.hash) > h)
// 根节点的哈希值大于当前节点的哈希值
dir = -1;
else if (ph < h)
// 根节点的哈希值小于当前节点的哈希值
dir = 1;
// 如果hash值相等，那么判断k是否实现了comparable接口
// 如果实现了comparable接口就使用compareTo进行进行比较
// 如果仍旧相等或者没有实现comparable接口，则在tieBreakOrder中比较
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// kc：当前节点key的class k：当前节点的key pk：根节点的key
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
// 假如dir小于等于0，p就指向p的左子节点的引用
// 大于0，p指向右子节点的引用
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 指定移动后的p节点的父节点
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 做平衡操作
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
添加一个Map方法
putMapEntries
/**
* 添加一个map集合
*
* @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size(); // 代添加的map的大小
if (s > 0) {
if (table == null) { // pre-size
// 底层数组未初始化时，需要计算初始容量
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 参数为Map的构造函数调用时，threshold为0
// putAll调用，假如是第一次添加元素，threshold为0
if (t > threshold)
// 因为threshold可能小于t，需将初始容量为2的n次幂
threshold = tableSizeFor(t);
}
// 此处数组已经初始化过了，判断是否需要扩容
else if (s > threshold)
resize();
// 循环添加数据
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
问题来了，为什么float ft = ((float)s / loadFactor) + 1.0F;
这一行要加一操作？
s/loadFactor
的结果是小数，加1.0F
与(int)ft
相当于是对小数做一向上取整以尽可能的保证更大容量，更大的容容量能够减少resize的调用次数。所以+ 1.0F是为了获取更大的容量。
例如：假如插入集合的元素个数是6个，那么6/0.75是8，是2的n次幂，那么新的数组大小就是8了。然后原来数组的数据就会存储到长度是8的新的数组中了，这样会导致后续在存储元素的时候，容量可能不够，还得继续扩容，那么性能降低了，而如果+1呢，数组长度直接变为16了，这样可以减少数组的扩容。
获取方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
// tab:数组引用
// first:路由寻址命中的元素，是链表的头结点
// e:指针，指向每次遍历链表的结点
// n:数组长度
// k:每次遍历链表的结点的key
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 哈希路由寻址找到的位置元素存在
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
// 头结点就是要找的key，直接返回
return first;
// 此时要找的结点在链表或者红黑树中
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// 获取红黑树结点
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 此时要找的结点在链表中，遍历链表找到即可
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 未找到返回null
return null;
}
删除方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods
*
* @param hash 要删除的key的哈希值
* @param key 要删除的key
* @param value 待匹配的值
* @param matchValue 为true，则需要匹配value
* @param movable 为false则删除时无需移动其它结点
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// tab:数组
// p:路由寻址命中的元素
// n:数组长度
// index:命中位置索引
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// node:要删除的结点
// e:遍历到的每个结点
// k:遍历的结点的key
// v:遍历的结点的value
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 命中的第一个结点，也就是链表的头结点就是要找的结点
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
// 获得红黑树结点
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
// 此时要找的结点在链表中，遍历链表找到结点
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 删除操作
if (node instanceof TreeNode)
// 删除红黑树结点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 要删除是头结点，将链表的第二个元素作为新的头结点
tab[index] = node.next;
else
// 要删除的是链表中间或者尾部的结点
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
// 不存在该结点直接返回null
return null;
}
序列化相关
序列化的目的是将Java对象序列化，在某个时刻能够将该对象反序列化，而且一般来讲序列化和反序列化所在的机器是不同的，因为序列化最常用的场景就是跨机器的调用（把对象转化为字节流，才能进行网络传输），而序列化和反序列化的一个最基本的要求就是，反序列化之后的对象与序列化之前的对象是一致的。
HashMap有自己实现的writeObject和readObject方法。
这两个方法私有的好处是，子类也可以重写这两个方法，而不受HashMap重写的影响。
至于为什么要重写这两个方法，是因为对于同一个Key，在不同的JVM实现中计算得出的Hash值可能是不同的。Hash值不同导致的结果就是：有可能一个HashMap对象的反序列化结果与序列化之前的结果不一致。
微信公众号：肝帝笔记
即有可能序列化之前，某个元素本来放在数组的第0个位置，而反序列化值后，根据Key获取元素的时候，可能需要从数组为2的位置来获取，而此时获取到的数据与序列化之前肯定是不同的。
所以为了避免这个问题，HashMap的处理方法是
将可能会造成数据不一致的元素使用transient关键字修饰，从而避免JDK中默认序列化方法对该对象的序列化操作。不序列化的包括：Node[ ] table、size、modCount等。 自己实现writeObject和readObject方法，从而保证序列化和反序列化结果的一致性。
那好我们来看看是如何重写这两个方法的：
首先，HashMap序列化的时候不会将保存数据的数组序列化，而是将元素个数以及每个元素的Key和Value都进行序列化。 在反序列化的时候，重新计算Key和Value的位置，重新填充一个数组。
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
int buckets = capacity(); // 获得桶的个数，也就是数组的长度
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
s.writeInt(buckets); // 写入数组长度
s.writeInt(size); // 写入集合元素个数
internalWriteEntries(s); // 将key value分别写入
}
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException {
// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
reinitialize(); // 重置那些transient的变量
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
// 读出数组长度，但是没有用到
s.readInt(); // Read and ignore number of buckets
// 读出元素个数
int mappings = s.readInt(); // Read number of mappings (size)
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
else if (mappings > 0) { // (if zero, use defaults)
// Size the table using given load factor only if within
// range of 0.25...4.0
// 计算新建的数组长度
float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
float fc = (float)mappings / lf + 1.0f;
int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
DEFAULT_INITIAL_CAPACITY :
(fc >= MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY :
tableSizeFor((int)fc));
float ft = (float)cap * lf;
threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
(int)ft : Integer.MAX_VALUE);
// Check Map.Entry[].class since it's the nearest public type to
// what we're actually creating.
SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, cap);
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的数组
Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
table = tab;
// Read the keys and values, and put the mappings in the HashMap
// 读出key value 重新计算哈希值并添加到新的数组中去
for (int i = 0; i < mappings; i++) {
@SuppressWarnings("unchecked")
K key = (K) s.readObject();
@SuppressWarnings("unchecked")
V value = (V) s.readObject();
putVal(hash(key), key, value, false, false);
}
}
}
小结
JDK8的HashMap的底层数据结构是数组+链表+红黑树，相对于JDK8之前的版本引入的红黑树，在桶位元素较多的时候，查询起来比较慢，故此引入红黑树来增加查询效率。
HashMap的数组长度必须是2的n次幂，为了配合位运算提高哈希路由的效率。底层数组是在第一次添加元素的时候才去初始化的。
当HashMap中元素的个数达到扩容阈值后，会调用扩容方法创建一个新的数组，长度为旧长度的两倍，再扩容过程中有个重要的事要做，那就是重新计算哈希，重新路由寻址，在此过程中假如重新路由之后，某个红黑树的结点个数小于6了，红黑树就会退化为链表。ps.在删除结点的时候也会进行判断是否需要退化为链表。
微信公众号：肝帝笔记
❝参考
为什么HashMap要自己实现writeObject和readObject方法？
HashMap底层树化标准？
