HashMap源码学习(JDK 1.8)
程序员文章站
2022-03-23 22:47:32
什么是hash？把任意长度的输入通过一个hash算法之后，映射成固定长度的输出。在这个过程中会产生一种情况，就是两个不同的值通过hash算法计算出的结果是相同的，这个就是造成了哈希冲突。hash冲突理论上是无法避免的，只能说尽量取避免它。比如说通过该hash算法计算出来的值区间为[m , n] 。 但是现在有（n- m）* 2 个值要用该hash算法计算，那总会造成冲突。以String类来打个比方，String重写了Object类的hashCode() , 该方法返回的是一个int类型的值，也就是....
什么是hash？
hash是散列，杂凑的意思。hash算法可以把任意长度的输入通过一个hash算法之后，映射成固定长度的输出，这个输出内容和源数据每一个字节之间都有紧密的联系。在这个过程中会产生一种情况，就是两个不同的值通过hash算法计算出的结果是相同的，这个就是造成了哈希冲突。hash冲突理论上是无法避免的，只能说尽量取避免它。比如说通过该hash算法计算出来的值区间为[m , n] 。 但是现在有（n- m）* 2 个值要用该hash算法计算，那总会造成冲突。
以String类来打个比方，String重写了Object类的hashCode() , 该方法返回的是一个int类型的值，也就是说他最多能表示一个整形范围的hash值。 但是不同的字符串远远不止这个范围。所以这种hash冲突是无法避免的。
hash值是不能通过计算的方式反推出原值的。一个好的hash算法要尽可能降低hash冲突。
首先Jdk1.8的HashMap底层数据结构： 数组 + 链表 + 红黑树。（每一个数据单元都是一个Node对象）
Node类中的成员与构造方法如下
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //key的hashCode再经过计算之后的值（使哈希值更加散列）
final K key; //保存key值
V value; //保存value值
Node<K,V> next; //下一个节点的引用（哈希碰撞之后会先形成链表）
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
HashMap中的一些默认常量：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
//默认table大小 --> 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//table的最大长度
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的负载因子大小0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默认链表升级为红黑树的阈值 == 8（注意：这只是树化的条件之一）
static final int TREEIFY_THRESHOLD = 8;
//树降级为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//树化的另一个参数---当哈希表中所有元素个数超过64时才被允许树化
static final int MIN_TREEIFY_CAPACITY = 64;
}
HashMap中的属性成员：
transient Node<K,V>[] table; //散列表
transient Set<Map.Entry<K,V>> entrySet;
transient int size; //记录当前哈希表的元素个数
transient int modCount; //记录元素结构性修改次数
int threshold; //扩容阈值（当哈希表中的元素超过阈值时触发扩容）
final float loadFactor; //负载因子用于计算扩容阈值 threshold = capacity * loadFactor
HashMap的构造方法（列举其中三个）
//指定初始容量和负载因子
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;
//获取初始的扩容阈值：手动指定initialCapacity为16及其以下得到值为16，传32及其以下得到32
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; //设置默认的负载因子0.75
}
双参构造方法需要指定初始容量与负载因子。当所指定的初识容量小于0时抛异常。且容量最大不能超过HashMap中规定的最大限度。负载因子不能为负数或者非法的值，因为负载因子要用于计算扩容阈值。接着得到初始的扩容阈值，利用tableSizeFor(int)方法。该方法的定义如下：
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;
}
对该方法进行变量跟踪：
若cap == 10 则n 为9 (0000 1001)
n |= n >>> 1：0000 1001 | 0000 0100(4) ==>0000 1101(13)
n |= n >>> 2：0000 1101 | 0000 0011(3) ==>0000 1111(15)
n |= n >>> 4：0000 1111 | 0000 0000(0) ==>0000 1111(15)
n |= n >>> 8和n |= n >>> 16 的结果还是15
返回n最终结果为负数时取1，大于 MAXIMUM_CAPACITY时 取 MAXIMUM_CAPACITY 否则取16
若cap == 16 则n为15 (0000 1111)
0000 1111 | 0000 0111 == 0000 1111（15） 最终返回n为16
当没有int n = cap - 1;时n == 16(0001 0000)
0001 0000 | 0000 1000 ==> 0001 1000(24)
0001 1000 | 0000 0110 ==> 0001 1110(30)
0001 1110 | 0000 0001 ==> 0001 1111(31)
0001 1111 | 0000 0000 ==> 31 (返回32) 想要的结果16---得到的结果32
综上发现规律：....
4以上8及其以下： 最终得到补码0000 0111(8) 2的3次方减一
8以上16及其以下： 最终得到补码：0000 1111(15) 2的4次方减一
16以上32及其以下： 最终得到补码0001 1111(31) 2的5次方减一
2的6次方减一
......
所以最终得到的初始扩容阈值总为2的次方数
特别的：指定初始容量为0时，得到的初始阈值为0
单参和无参构造方法是用的负载因子都是默认值。而且通过构造方法可以看出，在实例化对象时并没有为真正的散列表table开辟内存空间。
put方法的定义：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
当我们调用put方法是其底层是调用了核心方法：putVal 而且在调用该方法时执行了一次hash(key)
hash方法定义如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到在该方法中并没有直接使用对象的hashCode值，它是对该对象的hashCode值还进行了一次异或运算。这样可以使得hash值更加的散列。具体分析如下：
^运算符：相异为1，相同为0
>>>运算符：无符号右移 高位直接补0
首先不同的key对象，如果hashCode相同，则(h = key.hashCode()) ^ (h >>> 16) 相同 ---> 哈希冲突
h >>> 16 一定是 0000 0000 0000 0000 xxxx xxxx xxxx xxxx
对象A的hashCode ： 00010100 10110000 00001111 00000001
对象B的hashCode ： 01000100 01101001 00000111 00000001
如果没有此处的hash()方法， 直接使用对象的hashCode值，那么计算出的散列表中的桶位为：
（桶位也就是table数组的下标位置，只不过采用数组加链表的方式，该下标位置的节点可能会形成一条链，就好像
桶一样将各个节点装起来了一样，所以好多人给他起了个名字，叫桶位或者槽位。
计算公式tab[i = (n - 1) & hash]，这个公式也叫寻址算法）
假如现在散列表容量为16 ==> 16 - 1 == 15(0000 1111)
对象A在散列表中的位置： table[1]
对象B在散列表中的位置： table[1]
如果加上此处的hash()
对象A ： h >>> 16 ==> 00010100 10110000 那么异或运算后的值为：00010100 10110000 00011011 10110001
对象B： h >>> 16 ==> 01000100 01101001 那么异或运算后的值为：01000100 01101001 01000011 01101000
对象A在散列表中的位置：table[1]
对象B在散列表中的位置：table[8]
这种方案得到的hash值更加散列
得到hash值之后将其传入putVal方法中。
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; //n(散列表的长度) i(寻址的结果)
//若当前散列表为null(构造方法并没有初始化散列表)执行resize()，触发第一次扩容(懒汉式)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //此处是触发第一次扩容
//如果该桶位没有任何元素（p在此处被赋值）
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//该下标（桶位）处已经有值 -----这里又会被分为两种情况(一种是树结构，一是链表结构)
else {
Node<K,V> e; K k;
//如果这里的判断条件满足，即证明(散列表中已经存在该key对象)
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果是树结构
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果是链表结构
else {
//这里循环遍历链表
for (int binCount = 0; ; ++binCount) {
/**
* 将当前节点的下一个节点引用保存在e中进行判断是否为null（也就是判断当前链表是不是遍历完了）
* 此处是已经遍历完链表的情况。如果已经遍历完了没有重复的元素，那就创造一个Node对象保存数据。并且添加到末尾
*/
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
/**
* TREEIFY_THRESHOLD的值为8。binCount从0开始， 0 -- 7，也就是循环到第8次才进如到下面if中。
* 到第8次的时候先进入上面if创造一个新的节点，在进入当前if中去。
* 强烈注意：此处执行treeifyBin并不是说直接就升级为树。
*/
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break; //新数据保存完毕，跳出循环
}
//下面条件如果成立，那就是我们所说的“键重复”了
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
/**
*当创造出新节点时 p.next = newNode(hash, key, value, null); 并没有让e指向新节点。故e可能为null
* 如果e != null 那就是“键重复”了，此处是将之前该节点的值（V）替换为新值。
*/
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue; //结束put方法返回put进的新值
}
}
/**
* 能执行到这说明 e == null 也即put进了一个新的元素，散列表结构被改变了。
* 键重复替换那不算 “结构性” 改变，只是某个“节点的值”改变了，所以结构性改变就是这个意思。
* 该成员配合迭代器来检测并发修改异常。
*/
++modCount;
//++size(先让散列表中元素的计数加1)再判断是否需要扩容了
if (++size > threshold)
resize();
afterNodeInsertion(evict); //该方法是一个空方法，其主要目的是为了让子类重写该方法
return null;
}
扩容方法resize()
首先扩容的是散列表(table数组)的长度。
为什么需要扩容：假如不扩容的情况下是否就不能完成任务，当然可以完成存取任务。因为散列表它本生是数组+链表+红黑树的方式实现，这一点就已经克服了数组的固定长度的短板。链表和树都是可以直接添加节点的。假如说现在没有扩容方法，那么在数据量非常庞大的情况下，可能会造成哈希冲突比较严重，也就是说它形成的树（JDK1.7的时候还没有引入红黑树，只是数组 + 链表的形式）或者链会很长。假如假如假如现在一个链现在有10000个节点，但是你要查找的元素恰好是最后一个节点，注意此处是单向链表。所以你只能从头开始往后一个一个找，这就会造成效率低下。如果能将一个长的链拆分成多个子链，或者说将一个很庞大的树拆分成多颗子树。那么查询效率就会好很多。所以扩容就是为了解决查询效率问题。当然扩容会增加内存占用量。所以这是一个空间换时间的思想。总的来说它是为了解决哈希冲突导致的链化影响查询效率的问题，扩容会缓解该问题。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //保存原table数组的引用
int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldCap表示原容量，当第一次扩容时oldTab == null
int oldThr = threshold; //触发本次扩容的阈值
int newCap, newThr = 0; //表示扩容之后的新容量 和 新的扩容阈值
//原容量大于0，只有第一次扩容时原容量为0，这里就是为了区别是否为第一次扩容
if (oldCap > 0) {
//容量都达到最大限度了那就别扩了
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; // 阈值变为原阈值的双倍
}
/**
* oldCap == 0 且 oldThr > 0。
* 就当前列举的三种构造方法而言：（首先需要oldCap == 0，即第一次扩容时才执行）
* 双参构造方法手动指定阈值是会出现这种情况的（oldThr > 0）。
* 单参构造方法也会 默认传入初始阈值为16
* 无参则不会（第一次触发扩容时oldCap和oldThr都为0）
*/
else if (oldThr > 0)
newCap = oldThr;
//oldCap == 0 && oldThr == 0 无参构造触发第一次扩容时走这条路
else {
newCap = DEFAULT_INITIAL_CAPACITY; //16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // (int)(0.75f * 16) == 12
}
/**
* newThr == 0的情况（即newThr这个局部变量并没有被重新赋值）：
* oldCap > 0时 oldCap >= DEFAULT_INITIAL_CAPACITY不成立，也即手动指定的容量为16以下。
* oldCap == 0 且 oldThr > 0时 （第一次扩容时 双参和单参构造方法都可能造成这种情况）
*/
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
//更新新的阈值
threshold = newThr;
/*------------------------------上面一大堆都是在计算newCap和newThr----------------------------------------------------------*/
@SuppressWarnings({"rawtypes","unchecked"})
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) { //将原桶位处头元素的引用临时保存在e中
oldTab[j] = null;
if (e.next == null) //如果该桶位只有一个节点
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //如果是树结构
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //不是树也不是单个节点 -----> 链表的情况
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next; //先获取当前节点的下一个节点
/**
* 下面是将一条链拆分为两个子链的过程,若现在是从16扩容到32
* 假设现在遍历到下标为3的位置，之前存的时候是这样计算的：（e.hash & (cap - 1)）== 3
* 也就是e.hash & 0000 1111 == 3
* 那么之前在这条链上的元素的hash值就可能为 0010 0011 或者 0011 0011
*
* e.hash & oldCap：（注意此时j == 3）
* 对于hash值为0010 0011 的元素： 0010 0011 & 0001 0000 == 0000 0000 判断成立 将其保存至低位链中。
* 最后 loTail != null成立： 那么newTab[j](j == 3) ---> 这个元素在新数组中的位置还是下标为3
*
* 对于hash值为 0011 0011的元素： 0011 0011 & 0001 0000 == 0001 0000 == 16。进入else将其保存至高位链中。
* 最后hiTail != null成立： 那么 newTab[j + oldCap] = hiHead; --->这个元素在新数组中的位置为 3 + 16 == 19。下标为19
*
* 若不扩容则是将一个hash值(二进制)的低4位拿出来做索引。
* 扩容了他就相当于再拿出来一个位来用，用低5位。（利用一条链中那一个位的差别来重新分派桶位(如果均匀的话就是平分了链)）
* 所以在查询的时候效率会大大提升。
* 就这样将原数组中的一个链中的各个节点拆分重组成两条子链
*/
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;
}
在整个put的过程中还有一个方法treeifyBin
treeifyBin
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index;
Node<K,V> e;
/**
* MIN_TREEIFY_CAPACITY == 64
* 若表为null 或者 表长度 < 64
* 从这里可以看出树化的两个条件：假如此时某一个桶位处的链表长度已经为8，但是此时散列表长度为16。它还是不会进行树化。只是会扩容一次
* n在此处被赋值为表长度
*/
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 链表长度为8，而且容量大于64的情况。找到该桶位处的索引。 此处将此索引赋值给index变量
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//这个过程是将链表节点转化为树节点，然后重组成一条由树节点组成的双向链表。TreeNode间接继承与Node。所以它也有前驱和后继
do {
/**
* 实例化一个TreeNode对象。一个二叉树节点，最基本要有三个引用父节点、左孩子、右孩子。
* 注意此时构造的树节点 其父节点 左孩子 右孩子 指向都为null
*/
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); //这才是真正地将链表结构转换为红黑树结构的方法
}
}
一个红黑树节点的数据结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; //父节点
TreeNode<K,V> left; //左孩子
TreeNode<K,V> right; //右孩子
TreeNode<K,V> prev; // 删除后需要取消链接
boolean red; //节点颜色
//实例化TreeNode对象 注意此时red为false(黑) 而且parent left right prev都为null
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
将链表结构转变为红黑树结构的方法
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//变量x在此处声明和赋值，这个循环是遍历链表。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中的语句，再次过程中树根被初次确定
if (root == null) {
x.parent = null; //树根没有父节点
x.red = false; //树根默认为黑色
root = x; //root变量在此处被赋值
}
else {
K k = x.key; //该节点的key值
int h = x.hash; //该节点的key的hash值
Class<?> kc = null;
//首先让p == root，这个循环目的是将链表一步一步转换调整成红黑树
for (TreeNode<K,V> p = root;;) {
int dir, ph; //dir用来标记当前节点应该成为树的左孩子还是右孩子。 ph用来保存树节点的hash值
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
//如果两个节点的key的hash值相等，下面判断条件是只是另一种比较方式
else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
//分情况处理 分配左孩子和右孩子 (如果父节点的hash值大于当前节点的hash的情况下是左孩子)
if (dir <= 0)
xp.left = x;
else
p.right = x;
//传进root与x(当前节点)
root = balanceInsertion(root, x); //旋转方法
break; //注意 这里会跳出内层循环
}
}
}
}
//旋转调整完之后树根可能发生改变，该方法让散列表中的头元素保存的永远是root树根
moveRootToFront(tab, root);
}
balanceInsertion方法
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true; //当前节点先设置为红色
/**
* xp == 当前节点的父节点
* xpp ==......爷爷节点
* xppl == 爷爷的左孩子
* xppr == 爷爷的右孩子
*/
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//如果当前节点的父节点为 null 说明为树根
if ((xp = x.parent) == null) {
x.red = false; //树根染为黑色
return x;
}
//如果父节点是黑色 或者 不存在爷爷节点
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//如果存在父节点，而且父节点是爷爷节点的左孩子
if (xp == (xppl = xpp.left)) {
//如果爷爷节点的右孩子存在（也就是当前节点存在叔叔节点） 而且是红色
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
//如果不存在叔叔节点 或者 叔叔节点为黑色
else {
//当前节点是父节点的右孩子的情况
if (x == xp.right) {
root = rotateLeft(root, x = xp); //以父节点为支点左旋（传入根节点和 ）父节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
//如果父节点是爷爷节点的右孩子 或者 父节点是爷爷节点的右孩子但是为黑色
else {
//如果爷爷节点的左不为null 而且 是红色
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//如果当前节点是父节点的左孩子
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//如果父节点不为null
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp); //以xpp为支点左旋
}
}
}
}
}
}
get方法：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
get方法底层也是调用的核心方法getNode
getNode方法：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; //散列表
Node<K,V> first, e; //first 桶位中的头元素
int n; K k;
//如果当前散列表不为空 && 散列表长度大于0 && 该桶位处有值
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//如果头元素是就直接返回头元素
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
//判断是否含有下一个节点（即是否为一个链）
if ((e = first.next) != null) {
//树的情况(first为树根)
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);
}
}
return null;
}
如果是树的情况则执行getTreeNode方法遍历树：
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null); //先找到树根后调用find方法查找目标
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this; //p表示当前定位的元素
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl; //如果当前定位元素的hash值 大于 目标元素的hash值 则只找定位元素的左子树
else if (ph < h)
p = pr; //右子树
//此处判断的前提是hash值相等
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
/*--------------------------------------------------下面情况是hash值相同 key不相同--------------------------*/
else if (pl == null) //左子树为null 则让其往右子树方向
p = pr;
else if (pr == null) //右子树为null 则让其往左子树方向
p = pl;
//左右子树都不为null 而且 key不相同 按compare区分接下来应该往左还是往右找
else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null; //没找到则返回null
}
【天下事有难易乎，为之，则难者亦易矣；不为，则易者亦难矣】
本文地址：https://blog.csdn.net/weixin_44641388/article/details/107591912