Java教程
HashMap 源码分析
每当你想要努力一把的时候，都是未来的你在求救！！！
1. 概述
HashMap 是我们开发中很常用的一个键值对集合。底层基于散列算法实现，HashMap 允许 Null 值和 Null 键，并且键不能重复（重复会被覆盖），计算键的 Hash 值时 Null 键的哈希值是 0。另外，HashMap 不保证插入顺序，并且 HashMap 是非线程安全的，在多线程下可能会导致一些问题，如：
HashMap进行put操作会引起死循环，导致CPU利用率接近100%（后面有解释为什么会死循环哦）；- 多线程本来一共要 put 进1000个不同的键，结果只 put 进了 998个。
2. 原理
HashMap 底层是基于拉链式的散列算法实现的，在 JDK1.7 中是数组+链表，在JDK1.8 中是 数组+链表+红黑树，使用红黑树优化过长的链表。JDK1.8 中数据结构示意图：
在JDK1.8 中是 数组+链表+红黑树。在对HashMap进行增删查操作时，先要定位到元素所在桶数组的位置，之后再通链表或者红黑树中定位对应的元素，比如现在要查询上图中的元素 35，就有以下步骤：
- 定位元素 3 所在的桶数组的位置，index = 35 % 16 = 3；所以元素在数组下标为 3 的位置
- 在 3 号下标的位置是一个链表，然后遍历链表查询元素 3
HashMap 的大致原理就是这样，下面再看看HashMap的源码分析。
3. 源码分析
3.1 构造方法分析
3.1.1 构造方法源码
构造方法只会初始化一些重要的变量，比如负载因子和容量。底层的数据结构（如桶数组）是延迟在put 操作时进行初始化的。
// 构造方法 1
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 构造方法 2
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 构造方法 3
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
// 构造方法 4
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
构造方法 1 是我们平时用的最多的，它默认初始容量为 16，负载因子是 0.75，阈值=初始容量*负载因子。
构造方法 2 是自定义了初始容量，这里负载因子还是使用默认的 0.75，这里如果自定义的初始容量不是 2 的 n 次幂，会有一个坑，后面讲解。
构造方法 3 是自定义了初始容量和负载因子。
构造方法 4 是将另一个 Map 中的映射拷贝一份到自己的存储结构中来，这个方法不是很常用。
3.1.2 初始容量，负载因子，阈值
三个名词介绍：
initialCapacity：HashMap 初始容量，默认 16
loadFactor：负载因子，默认 0.75
threshold ：当前 HashMap 所能容纳键值对数量的最大值，超过这个值，则需扩容，等于 initialCapacity*loadFactor
源码如下：
// The default initial capacity - MUST be a power of two.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
// The load factor used when none specified in constructor.
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// The next size value at which to resize (capacity * load factor).
int threshold;
// The load factor for the hash table.
final float loadFactor;
3.1.3 经典问题
问题一：为什么HashMap的加载因子是 0.75，不是 0.5 或者 1
如果负载因子是 1
如果负载因子是 1，意味着要把 HashMap 填满之后才扩容，就会发生大量的哈希冲突，然后链表变长，链表长度达到8就会转化成红黑树，大量的哈希冲突还会使红黑树更复杂，查询效率就会变低。总结一句话就是：负载因子越大，空间利用率越高，时间效率就越低
如果负载因子是 0.5
如果负载因子是 0.5，就意味着容量达到一半时就要扩容，哈希冲突会减少，查询效率会变高，但是空间利用率就变低了。
如果负载因子是 0.75
负载因子默认 0.75，是时间效率和空间效率的权衡。
问题二：是HashMap 的数组占用达到阈值就扩容，还是集合中元素总和达到阈值就扩容
去 debug 一下 HashMap 的源码就可以知道了，是集合中元素总和达到阈值就会扩容。这里我理解的是这样可以避免小概率的大量哈希冲突导致红黑树复杂度变高吧！
问题三：如果自定义初始化容量为 18，那实际初始化的容量是多少，经历一次扩容后又是多少
先上结论：实际初始化的容量是 32（阈值是 24），经历一次扩容之后容量是 64
看上面的构造方法 2 指定了初始化容量，然后构造方法 2是调用了构造方法 3，在构造方法 3 中有这么一行代码this.threshold = tableSizeFor(initialCapacity);，我们来看看tableSizeFor(initialCapacity) 做了什么：
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;
}
如果看不懂这个方法，没关系，我们把这个方法拿出来测试一下，测试代码如下：
public class TestHashMap {
static final int MAXIMUM_CAPACITY = 1 << 30;
public static void main(String[] args) {
// 这里传入任何值 ，最后打印的都是大于传入值的2的n次幂，
// 如传入5，返回8；传入 18，返回 32
System.out.println(tableSizeFor(5));
}
static 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;
}
}
经过上面的测试应该就明白了吧，不管你自定义初始化容量是多大，它都会给你转化成大于自定义初始化容量，并且最近的一个 2 的 n 次幂。可能有点绕，举个例子：
- 如果你自定义初始化容量是 -1，它会给你转成 1（2的0次幂）；
- 如果你自定义初始化容量是 5，它会给你转成 8（2的3次幂）；
- 如果你自定义初始化容量是 18，它会给你转成 32（2的5次幂）；
那有人可能要说了，这里在上面的构造方法中的代码this.threshold = tableSizeFor(initialCapacity);，明明是给 threshold 赋值的， threshold 不是阈值嘛，它不是初始容量啊，初始容量不应该是 threshold/loadFactor 吗？这个问题就要说HashMap 的数据结构初始化是在put 操作时延迟初始化的了，留在后面讲插入（put 方法）的时候说吧（看了扩容的方法就明白了）。
问题四：多线程下使用 HashMap 为什么会出现死循环
HashMap是采用链表解决哈希冲突，因为是链表结构，那么就很容易形成闭合的链路，这样在循环的时候只要有线程对这个HashMap进行get操作就会产生死循环。- 在单线程情况下，只有一个线程对
HashMap的数据结构进行操作，是不可能产生闭合的回路的。 - 那就只有在多线程并发的情况下才会出现这种情况，那就是在
put操作的时候，如果size>initialCapacity*loadFactor，那么这时候HashMap就会进行rehash操作，随之HashMap的结构就会发生翻天覆地的变化。很有可能就是在两个线程在这个时候同时触发了rehash操作，产生了闭合的回路。
3.2 插入（put 方法）
3.2.1 补充说明
这里先补充一下HashMap的数据结构吧，前面说了在JDK1.8中，HashMap是 数组+链表+红黑树实现的。看一下数据结构的源码：
// 数组
transient Node<K,V>[] table;
// 链表
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;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
//...
}
3.2.1 插入方法
话不多说，直接看我们常用的 put 方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
在这里调用了putVal 方法进行插入，并计算了 key 的哈希值，先看看哈希值怎么计算的：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到这里并不是直接使用hashcode() 方法去计算哈希值的，而是这样操作的：
- 如果 key 是 null，哈希值就会 0；
- 如果 key 不是 null，就获取对象的哈希值然后再进行位移和异或操作，获取最终的哈希值。
这里引出一个问题，为什么取到哈希值之后要进行位移和异或操作？
先上结论：就是为了减少哈希碰撞，让元素更均匀的分布在散列表中。
再看原因：
-
如果直接使用
key.hashCode()作为hash值的话，存在一些问题：HashMap的默认长度为16，并且是通过(table.length - 1) & hash的方式得到 key 在 table 数组中的下标。如果
key1.hashCode()=1661580827(二进制为0110,0011,0000,1001,1011,0110,0001,1011)，key2.hashCode()=1661711899(二进制为0110,0011,0000,1011,1011,0110,0001,1011)。在与掩码进行与的过程中，只有后4位起作用，导致
(table.length - 1) & hash得到的下标值均为11，导致高位完全失效，加大了冲突的可能性。一句话总结：就是如果不进行位移和异或的操作，在计算元素所处的 table 数组下标的位置时，哈希值的二进制高位就会失效，只有低位参与计算，增大了哈希冲突的可能性
-
如果通过高位向低位异或传播的话，高位同样参与到key在table中下标的运算，减少了碰撞的可能性
key1.hashCode() ^ (key1.hashCode() >>>16)=1661588754(二进制为0110,0011,0000,1001,1101,0101,0001,0010)key2.hashCode() ^ (key2.hashCode() >>>16)=1661719824(二进制为0110,0011,0000,1011,1101,0101,0001,0000)在和掩码进行与操作（
(table.length - 1) & hash）得到的下标分别为2和0，减少了冲突的可能性。
上面说了hash(Object key) 方法，我们接着往下看，就是 put 方法实际调用的 putVal ：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 初始化桶数组 table，table 被延迟到插入新数据时再进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算当前元素的key的下标位置，并判断这个下标位置是不是空的，不是空的就直接将元素放在这里
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果桶中的引用类型为 TreeNode，则调用红黑树的插入方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 对链表进行遍历，并统计链表长度, binCount 就是链表的长度
for (int binCount = 0; ; ++binCount) {
// 链表中不包含要插入的键值对节点时，则将该节点接在链表的最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果链表长度大于或等于树化阈值，则进行树化操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 条件为 true，表示当前链表包含要插入的键值对，终止遍历
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 判断要插入的键值对是否存在 HashMap 中，如果存在，前面就已经给 e 赋值了
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 键值对数量超过阈值时，则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上面写在代码中的注释已经比较清楚了，putVal 主要做了以下几件事情：
- 当桶数组 table 为空时，通过扩容的方式初始化 table（这里第一次put的时候就会进行一次扩容，其实就是初始化 table）
- 查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值
- 如果不存在，则将键值对链入链表中（是放在链表尾部哦），并根据链表长度决定是否将链表转为红黑树
- 判断键值对数量是否大于阈值，大于的话则进行扩容操作
3.3 扩容（resize 方法）
扩容方法相对会复杂一点，先说一下扩容的大概过程：
- 在
put第一个元素时，会先初始化数据结构，按照默认的是初始化容量为 16，负载因子是 0.75 - 当
HashMap中的键值对达到 最大容量*负载因子（也就是 12）之后，会进行扩容。 - 扩容就是将数组（table）的长度变为原来的 2 倍，阈值也会变为原来的 2 倍
- 扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去
接下来看看 resize 方法的源码：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果 table 不为空，表明已经初始化过了
if (oldCap > 0) {
// 当 table 容量超过容量最大值，则不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 按旧容量和阈值的2倍计算新容量和阈值的大小
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 初始化时，将 threshold 的值赋值给 newCap
// HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 调用无参构造方法时，桶数组容量为默认容量
// 阈值为默认容量与默认负载因子乘积
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr 为 0 时，按阈值计算公式进行计算
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 创建新的桶数组，桶数组的初始化也是在这里完成的
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 如果旧的桶数组不为空，则遍历桶数组，并将键值对映射到新的桶数组中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 如果 oldTable 此处下表位置就一个元素，则直接填充到 newTab
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;
Node<K,V> hiHead = null, hiTail = null;
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;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
这个源码稍微有点长，可以多看几遍。主要做了以下几件事情：
- 计算新桶数组的容量 newCap 和新阈值 newThr
- 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
- 将键值对节点重新映射到新的桶数组里。如果节点是
TreeNode类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。（具体情况后面红黑树和链表互相转换时讲解）
这里也查阅了一些资料，关于 JDK1.7 和 JDK1.8 扩容的区别：
JDK 1.8版本下HashMap扩容效率要高于之前版本。如果大家看过JDK 1.7的源码会发现，JDK 1.7为了防止因 hash 碰撞引发的拒绝服务攻击，在计算 hash 过程中引入随机种子。以增强 hash 的随机性，使得键值对均匀分布在桶数组中。在扩容过程中，相关方法会根据容量判断是否需要生成新的随机种子，并重新计算所有节点的 hash。而在JDK 1.8中，则通过引入红黑树替代了该种方式。从而避免了多次计算 hash 的操作，提高了扩容效率。
3.4 链表转为红黑树
很多资料说当链表长度达到 8 的时候，就会转化为红黑树，我们先看一下源码，到底是不是这样：
来吧，看一下treeifyBin 方法的源码：
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
// 将普通节点链表转换成树形节点链表
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// hd 为头节点（head），tl 为尾节点（tail）
TreeNode<K,V> hd = null, tl = null;
do {
// 将普通节点替换成树形节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null); // 将普通链表转成由树形节点链表
if ((tab[index] = hd) != null)
// 将树形链表转换成红黑树
hd.treeify(tab);
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
看看上面的代码和截图，可以很清楚，链表树化需要两个条件：
-
链表长度大于等于
TREEIFY_THRESHOLD就是我们常说的当链表长度大于 8 的时候，链表转化为红黑树
-
桶数组容量大于等于
MIN_TREEIFY_CAPACITY实际上进入转化为红黑树的方法中（
treeifyBin方法）可以看到：桶数组（table数组）长度小于 64 时会优先进行扩容操作，而不是直接将链表转化为红黑树。我的理解是当 table 数组长度比较小的时候，键的哈希碰撞会比较严重，导致链表变长，这个时候可以选择优先进行扩容。毕竟高碰撞率是因为桶数组容量较小引起的。容量小时，优先扩容可以避免一些列的不必要的树化过程。并且桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射（这个扩容方法中有）。所以在桶容量比较小的情况下，将长链表转成红黑树，然后再经历扩容，可能又将红黑树拆分转成链表了，这是一件吃力不讨好的事情。
我们继续说上面的 treeifyBin 方法，这个方法主要是将普通链表转化为由 TreeNode 节点组成的链表，再调用treeify 方法将其转化为红黑树。可以了解一下，HashMap 中的内部类TreeNode继承了LinkedHashMap.Entry，LinkedHashMap.Entry 又继承了 HashMap.Node。
所以 TreeNode 里面还是包含有 next 引用的，这个在后面红黑树转化为链表就会很有用了，后面再说哦。
先来画个图，假设在树化之前，HashMap 里面的数据是这样的：
然后说说调用treeify 方法将TreeNode 链表转化为红黑树吧，因为红黑树的结构特点（自己去了解哦），这个就涉及到 key 的比较了，这里直接说一下怎么比较的（就不再深追了）：
- 比较键与键之间 hash 的大小，如果 hash 相同，继续往下比较
- 检测键类是否实现了 Comparable 接口，如果实现调用
compareTo方法进行比较 - 如果仍未比较出大小，就需要进行仲裁了，仲裁方法为
tieBreakOrder
通过上面说的三种比较，就可以按照红黑树的结构特性去构造红黑树了，树化后是这样子的：
黄色箭头代表TreeNode 保留的next引用，其实还有 prev 引用，这里就不画了。这里就是说明链表转化为红黑树后，原来链表的顺序结构依然保留着，这样就可以按照链表的方式去遍历红黑树，而且这个结构给后面红黑树转化成链表提供了便利。
那下面再看一下红黑树转化为链表是怎么操作的吧！
3.5 红黑树转为链表
3.5.1 红黑树拆分
再回去看看扩容的方法吧，里面有这么一行代码：((TreeNode<K,V>)e).split(this, newTab, j, oldCap);，它就是拆分红黑树的。扩容的时候所有节点都需要重新计算位置，所以肯定要拆分红黑树。
扩容后，所有节点（包括数组，链表节点，红黑树节点）都要重新计算下标位置，上面说到链表转化为红黑树时，通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样拆分红黑树重新计算下标时，就可以直接按照链表的方式拆分了，一定程度上是提升了效率的。
上面说了红黑树拆分的大致逻辑，下面看一下源码中怎么拆分的：
// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。
// 下面的循环是对红黑树节点进行分组，与上面类似
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
// 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
// hiHead == null 时，表明扩容后
// 所有节点仍在原位置，树结构不变，无需重新树化
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);
}
}
}
重新映射红黑树的逻辑和重新映射链表的逻辑基本一致。只是重新映射后，会将红黑树拆分成两条由 TreeNode 组成的链表。如果链表长度小于 UNTREEIFY_THRESHOLD，则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。举个例子说明一下，假设扩容后，重新映射上图的红黑树，映射结果如下：
3.5.2 红黑树链化
在上面的 split 方法中，当链表长度小于等于 6 时，就会调用 tab[index] = loHead.untreeify(map); 将红黑树转化为链表。
上面说了，红黑树中仍然保留了原链表节点顺序。这样想将红黑树转化为链表就很简单了，只需要将TreeNode 链表转化为 Node 链表就可以了。
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
// 遍历 TreeNode 链表，并用 Node 替换
for (Node<K,V> q = this; q != null; q = q.next) {
// 替换节点类型
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
3.6 查找（get 方法）
到这里，最难啃的骨头基本上啃完了。
先说一下思想：先定位键值对所在的桶的下标位置（就是在数组的哪个位置），然后去查找链表或红黑树。
下面就看一下 HashMap 的查找方法，上源码：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
计算哈希值的方法就不说了吧，和插入（put）数据时是一致的。如果 key 是 null，下标位置就是 0，就直接返回它的值。否则就调用 getNode 方法了。
看看getNode 方法：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1. 定位键值对所在桶的位置
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))))
return first;
if ((e = first.next) != null) {
// 2. 如果 first 是 TreeNode 类型，则调用黑红树查找方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 2. 对链表进行查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
上面的注释比较清楚了，红黑树的查找自己看看源码了解一下吧，这里就不赘述了。
3.7 遍历
遍历操作也是一个高频操作，我们一般使用的遍历方式有以下几种：
// 遍历方式 1
for(Object key : map.keySet()) {
// do something
}
// 遍历方式 2
for(HashMap.Entry entry : map.entrySet()) {
// do something
}
// 遍历方式 3
Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
Object key = ite.next();
// do something
}
上面的几种遍历方式，可以看出来遍历Map集合时，都是对 HashMap 的 key 集合或 Entry 集合进行遍历。
看一下遍历相关的源码吧：
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
// 键集合
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
// 键迭代器
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
// 寻找第一个包含链表节点引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
// 寻找下一个包含链表节点引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
不知道细心的你有没有发现一个问题，多次遍历一个 HashMap 集合时，遍历出来的顺序是一样的，然而遍历出来的这个顺序又和插入顺序不一样。那我们就拿这个图看一下吧：
不管插入顺序是怎样，最后存到HashMap中的结构就是上图这样的，相信这篇文章看到这里，也不用再解释为什么了吧。
然而在遍历时，会先从table数组的 0 下标开始往后遍历。找到包含链表节点引用的桶，对应图中就是 12 号桶,随后由遍历该桶所指向的链表。遍历完 12 号桶后，会继续寻找下一个不为空的桶，对应图中的 28 号桶。之后流程和上面类似，直至遍历完最后一个桶。
遍历的方法就到这里了，再思考一个问题，遍历的过程中并没有看到遍历红黑树的代码，那红黑树怎么遍历？如果你还不知道，就再回到上面看一下链表是怎么转为红黑树的吧（红黑树保留了 原始的链表结构）！
3.8 删除
删除操作的三个步骤：
- 确定元素在table数组的下标位置
- 遍历链表并找到键值对应的节点
- 删除节点
上源码：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
// 1. 定位桶位置
(p = tab[index = (n - 1) & hash]) != null) {
// 这个 node 就是记录要删除的那个节点
Node<K,V> node = null, e; K k; V v;
// 如果键的值与链表第一个节点相等，也就是说第一个就是要删除的节点，则将 node 指向该节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 如果是 TreeNode 类型，调用红黑树的查找逻辑定位待删除节点，将待删除的节点赋值给node
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 2. 遍历链表，找到待删除节点，并将待删除的节点赋值给 node
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 3. 删除节点，并修复链表或红黑树
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;
}
}
return null;
}
红黑树中的节点怎么删除的就不要再看了，伤脑筋，哈哈！！！
-
怎么通过 JavaScript 或其他编程语言来实现监听屏幕高度变化功能？-icode9专业技术文章分享11-13
-
聊聊我们那些年用过的表达式引擎组件11-12
-
让项目数据更有说服力：五款必备数据可视化管理工具推荐11-12
-
人到一定年纪，要学会远离多巴胺11-12
-
解读：精益生产管理的目的是什么？如何操作？11-12
-
Sku预研作业11-12
-
文心一言API密钥：分步申请指南11-12
-
初学者指南：轻松掌握后台交互11-12
-
从零开始学习：封装基础知识详解11-12
-
JSON对象入门教程：轻松掌握基础用法11-12
-
后台交互学习入门指南11-12
-
封装入门：Python面向对象编程的第一步11-12
-
后台交互入门：轻松掌握基础概念与操作11-12
-
python获取小说11-12
-
后台交互教程：新手入门指南11-12
