HashMap源码解析（JDK1.8）
文章目录
- HashMap源码解析（JDK1.8）
- 前置知识：红黑树
- HashMap的整体结构
- HashMap的属性
- 默认容量DEFAULT_INITIAL_CAPACITY
- 默认加载因子DEFAULT_LOAD_FACTOR
- TREEIFY_THRESHOLD
- UNTREEIFY_THRESHOLD
- MIN_TREEIFY_CAPACITY
- Node< K,V >[] table
- Set< Map.Entry< K,V > > entrySet
- size
- modCount
- threshold
- loadFactor
- HashMap的内部类
- 红黑树结点TreeNode< K,V >
- 链表节点Node< K,V >
- HashMap的方法
- 构造方法
- 空参构造HashMap()
- HashMap(int initialCapacity)
- HashMap(int initialCapacity, float loadFactor)
- HashMap(Map< ? extends K,? extends V > m)
- 扩容方法resize()
- 增删改查方法
- 添加：put方法
- 删除：remove方法
- 改：put方法
- 查：get方法
前置知识：红黑树
要说红黑树，首先要提到二叉查找树（BST），它利用了二分查找的思想，来使正常情况下查找的时间复杂度为O(logn)，例子如下图：
满足下列三个条件的树，即是二叉查找树：
- 左子树的值小于等于根的值
- 右子树的值大于等于根的值
- 左右子树也都是二叉查找树
满足了上述3个性质，BST的查找和插入都可以用二分查找思想来做，在BST中进行查找所需的最大次数=BST的高度，插入也是同理，通过不断比较大小来找到插入位置
但BST有一个弊端，那就是在极端条件下，BST会退化成链，如下图所示：
退化成链后，查找和插入的时间复杂度将退化到O(n)，即退化为线性查找。也就是说BST具有不平衡性，为了弥补它的这个缺点，人们提出了平衡二叉树（AVL）。
平衡二叉树（AVL）具有BST的所有特性，它还有其独有的特性，那就是：左右子树的高度差最多为1。有了该特性，平衡二叉树将保保持它的平衡性，弥补了BST的不足，例子如下图所示：
AVL树由于其平衡性，查找和插入的最坏时间复杂度变为了O(logn)
那么既然有了AVL，为什么还要提出红黑树呢？AVL虽好，但其对于平衡的定义：左右子树高度差最多为1这个条件过于严格，导致我们几乎每次进行插入或删除结点时，都会破坏平衡二叉树的结构，以至于要进行左旋或右旋处理，再将其变为平衡的。如果在那种插入、删除很频繁的场景中，平衡树需要频繁地进行调整，这会使平衡树的性能大打折扣。还有一个次要原因是，AVL的实现代码比较复杂，理论上的数据结构模型应用于实际还需要稍许修改折中。
基于上述两个原因，人们提出了一种不太严格的平衡树，也可以称之为一个折中方案，那就是红黑树。红黑树查找的最坏时间复杂度也为O(logn)，但它在插入、删除等操作中，不会像AVL那样，频繁地破坏红黑树的规则，所以不需要频繁地调整，这也是我们为什么大多数情况下使用红黑树的原因。红黑树的例子如下（叶子NIL节点未画出）：
红黑树是一种自平衡的二叉查找树，它除了拥有BST的基本特性外，还拥有以下5个特性：
- 结点带颜色属性（红或黑）
- 根节点为黑色
- 每个叶节点都是黑色的空节点（NIL结点）
- 每个红色结点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色结点）
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色节点
根据上述5个特性，可以推出红黑树从根到叶子的最长路径不会超过最短路径的2倍。在插入或删除结点时，可能会破坏红黑树的规则，需要进行调整，调整的方法包括两个：变色和旋转，旋转又分为左旋和右旋
红黑树插入结点时，有5种局面，每种局面对应特定的调整方法，虽然比较复杂，但调整的套路是固定不变的，这里就不介绍了
HashMap的整体结构
HashMap的整体结构是一个数组，数组中的元素称为哈希桶，哈希桶可以为链表，也可以为红黑树，如下图所示：
哈希桶中的每个元素都存储了key，value值，以及key对应的hash值等信息
在jdk 1.8之前HashMap都是数组+链表的结构，因为在链表的查询操作都是O(N)的时间复杂度，而且hashMap中查询操作也是占了很大比例的，如果当节点数量多，转换为红黑树结构，那么将会提高很大的效率，因为红黑树结构中，增删改查都是O(log n)。所以JDK1.8作出了这样的调整。
HashMap的属性
默认容量DEFAULT_INITIAL_CAPACITY
DEFAULT_INITIAL_CAPACITY即为HashMap的默认容量，即数组默认大小，为16
为什么取16，是因为16是经不断统计实验所得到的最优解
默认加载因子DEFAULT_LOAD_FACTOR
DEFAULT_LOAD_FACTOR是HashMap的默认加载因子，为0.75，加载因子会在扩容时被用到。
何为加载因子？HashMap作为哈希表型数据结构的实现，一定要预留出一部分空间供新元素散列进来，当空间快要满时，就要进行扩容了，而不是等到真正满了再去扩容，因为等到真正放满了，那么之前肯定发生了很多Hash冲突，加载因子为0.75的意思就是，HashMap最多放75%乘以容量Capacity的键值对，若数据量超过了75%乘以容量，则需进行扩容。
加载因子为什么取0.75，和默认初始容量16一样，因为0.75是经不断统计实验所得到的最优解
TREEIFY_THRESHOLD
TREEIFY_THRESHOLD是哈希桶转化为红黑树的阈值，当某个哈希桶中结点数大于8时，且数组长度大于MIN_TREEIFY_CAPACITY = 64，该哈希桶将会转换为红黑树结构
UNTREEIFY_THRESHOLD
UNTREEIFY_THRESHOLD是红黑树转化为链表的阈值。当某个哈希桶中结点数小于6时，该哈希桶会转换为链表，前提是它当前是红黑树结构
MIN_TREEIFY_CAPACITY
链表长度大于TREEIFY_THRESHOLD = 8且数组长度大于MIN_TREEIFY_CAPACITY = 64时，链表转化为红黑树
链表长度大于TREEIFY_THRESHOLD = 8（且数组长度不大于MIN_TREEIFY_CAPACITY = 64），数组进行扩容，链表不转为红黑树，还是链表
也就是说，设置了MIN_TREEIFY_CAPACITY这个属性后，链表长度并不是大于8就变为红黑树，而是还要满足数组长度大于64这个条件时，链表才转为红黑树。这样做的目的是尽可能避免冲突，这是经过长期经验和数学推算总结出来的，数组长度小于一定数目的话，数组扩容会比哈希桶树化效果要好。
以通俗的话来说，数组长度小于等于64，表示数组还没放很多哈希桶，这时候某个桶中元素大于8，那么我扩容数组，将减少哈希冲突，桶中元素不会增加地很快，单纯把链表变为红黑树并不能减少冲突发生的可能性。数组长度大于64时，这时数组已经放了够多的哈希桶了，再对数组进行扩容会影响HashMap的操作效率，此时将链表变为红黑树，来提高查找等操作的效率。
Node< K,V >[] table
table表示存储哈希桶的数组，数组元素类型为Node<K,V>，即哈希桶。table中的元素称之为哈希桶，哈希桶可以是链表结构，也可以是红黑树结构
Set< Map.Entry< K,V > > entrySet
将数据转换为Set的另一种存储形式，主要用于迭代
我们不妨来看看Set的泛型Map.Entry<K,V>是什么：
Map.Entry<K,V>是Map中定义的接口，其实就是表示键值对，其中定义了对key，value的get，set方法，以及key和value的比较方法等
调用Map.entrySet()，可以将Map转为Set形式，Set中的元素类型就是Entry，即键值对形式
size
size表示HashMap中键值对的数量，当size>threshold时会执行resize扩容操作
modCount
modCount表示HashMap被结构性修改的次数，主要用于在迭代器迭代时，若又对HashMap进行了修改，会抛出ConcurrentModificationException，并发修改异常
threshold
threshold为临界值，当HashMap存储的key-value键值对数量大于threshold临界值时，数组会进行扩容
loadFactor
loadFactor表示加载因子，作为变量使用
HashMap的内部类
HashMap的内部类有红黑树结点TreeNode<K,V>以及链表节点Node<K,V>
红黑树结点TreeNode< K,V >
红黑树结点TreeNode<K,V>继承了LinkedHashMap.Entry<K,V>，相当于继承了Node<K,V>，因为LinkedHashMap.Entry<K,V>继承了HashMap.Node<K,V>。
TreeNode<K,V>内部类中包含了在红黑树中插入、查找元素，将红黑树转化为链表等方法
链表节点Node< K,V >
链表节点Node<K,V>实现了Map.Entry<K,V>接口，其属性有key,value,key对应的hash值，以及下一个Node结点，方法包括key,value对应的get、set方法等
HashMap的方法
构造方法
空参构造HashMap()
使用空参构造，将得到一个空的HashMap，其容量（即数组大小）为默认的16，装填因子为0.75
HashMap(int initialCapacity)
使用这种构造函数，将设置初始容量为参数的值，装填因子为默认的0.75
HashMap(int initialCapacity, float loadFactor)
使用该构造函数，将设置对应的初始容量和装填因子
该方法会验证参数的正确性，将属性loadFactor赋为对应参数，并设置属性threshold（数组扩容临界值）为tableSizeFor(initialCapacity)
tableSizeFor方法用于计算>=参数的最小2的整数次方，因为HashMap的大小总是2的整数幂
为什么HashMap的大小要设置为2的整数幂？主要是为了方便进行位运算，具体可以看如下链接：
HashMap(Map< ? extends K,? extends V > m)
该构造函数传入一个Map，然后再将该Map转换为HashMap。转换的HashMap的装填因子为0.75。该方法调用了putMapEntries(m, false)方法，putMapEntries方法其实就是把Map中的数据放入HashMap中：
其中，Map.entrySet()方法返回一个Set<Map.Entry<K,V>>，这个Set的泛型为Map的内部类Entry，Entry是一个存放key-value的实例
putMapEntries方法的执行流程如下图所示：
扩容方法resize()
当数组中的key-value键值对个数大于临界值threshold时，将调用resize()方法进行数组扩容，我们来看看该方法是如何实现的：
该方法做了两件事，一是获取扩容后的数组newTab的大小以及临界值，二是将扩容前原有元素再哈希到新数组中。该方法具体的流程如下图所示：
链表哈希桶的再哈希过程如下图所示：
增删改查方法
添加：put方法
put方法实际上是调用了putVal方法，除开key,value外，还将key的hash值作为了参数，通过调用hash(key)方法来获得key对应的hash值，我们来看看hash方法是如何计算hash值的：
若key为null，其hash值为0，否则为key的hashCode与hashCode向右无符号右移16位的异或
put方法实际上是通过调用putVal方法向HashMap中加入元素，我们来看看putVal方法：
putVal方法的流程如下图所示：
注意，在table为空时，会调用resize方法进行初始化，这也是为什么说HashMap是懒加载的原因，因为它只有在使用它的时候才会分配空间，否则不会为其分配存储空间
值得注意的是，jdk提供了几个钩子函数：
它们的默认实现为空，可以由程序员重写，使得在key值重复和成功插入两种情况下分别进行不同的处理
删除：remove方法
remove方法实际上是调用了removeNode方法，我们来看看该方法：
删除还有一个clear()方法，该方法删除所有键值对，其实就是将数组所有元素都置为null
改：put方法
元素的修改也是put方法，因为key是唯一的，且onlyIfAbsent为false，所以修改元素，是把新值覆盖旧值。
查：get方法
get方法实际上是调用了getNode方法，我们来看看该方法：
还有一个常用的方法，containsKey方法，查找是否存在某个key，其实就是调用了getNode方法：
而与之对应的一个查找是否有value值存在的方法containsValue方法，效率就很低了，是用的遍历数组暴搜：
