HashMap源码解析：PUT流程详解
HashMap源码解析摘要 HashMap是基于哈希表的Map接口实现，采用数组+链表/红黑树结构存储键值对。默认初始容量16，负载因子0.75，当链表长度超过8且数组长度≥64时会转为红黑树。PUT操作核心流程：1)计算key哈希值；2)通过(n-1)&hash确定数组索引；3)处理哈希冲突（链表尾插/红黑树插入）；4)必要时扩容。扩容时采用2倍扩容机制，将旧数组元素重新分配到新数组。迭
·
HashMap源码解析
基础讲解
- hashMap是key value 键值对的集合
- hashMap继承自 AbstractMap、并且实现Map, Cloneable, Serializable
- hashMap底层是 Node<K,V>[] table 数组
- hashMap的迭代器是fail-fast 快速失败
- 默认初始化数组长度16，负载因子0.75，链表转换红黑树阈值8 退回链表6，链表转换红黑树必须链表大于等于8才会进入转换红黑树的方法里面 ，进入后还要判断当前hashmap的数组长度大于64 不大于要进行扩容 下次该桶再进行转换为红黑树
- 数组每次扩容则是把旧数组循环到新数组
PUT流程
put方法
首先put的过程中首先是调用了hash方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash方法
//hash方法进行判断key是否为空 如果为空hash值则为0, //如果不为空进行获取key的hashCode()值进行异域计算， //那这一块什么意思呢？说实话刚开始我也不懂得什么意思 //Map<String,String> param = new HashMap<>(); //param.put("张三","123"); //System.out.println(param.hashCode()); 结果：774889 //System.out.println(param.hashCode()>>>16); 结果：11 //这里说的就是>>>计算的时候要转换为二进制 //774889的二进制为：10111010110110010001 //无符号右移操16位 就等于二进制1011 //意思就是 // 10111101001011101001无符号右移操16位等于00000000000000001011 //1011等于十进制11 //(h = key.hashCode()) ^ (h >>> 16) // 774889 ^ 11 //10111101001011101001^00000000000000001011 //10111101001011101001 //00000000000000001011// 答案 10111101001011100010
// 这里说的就是11计算成二进制为1011 既然1011不够774889那么长那就补前面补0
// 补到一样长
// 我们只计算1011同位的
// 如果两个相应的位相同，结果为0。
// 如果两个相应的位不同，结果为1。
// 结果就是：774882
// 这下我们就明白了什么是异域计算了，面试官不管问不问，咱们最起码能知道是怎么计算的了
putVal 方法
/**
* @param hash 是key的整型hash值
* @param key 存储的key
* @param value 存储的value
* @param onlyIfAbsent 当调用hashmap的putIfAbsent方法时才会为true，这个为true的时候，key的value为null的时候才会进行修改值
* @param evict只有在方法 afterNodeInsertion(boolean evict) { }用到，可以看到它是一个空实现，因此不用关注这个参数
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
/**
tab : 创建临时节点表
p : 临时节点
n : hashMap.table 的长度
i : 记录table的索引
*/
Node<K,V>[] tab; Node<K,V> p; int n, i;
//这里是table赋值给临时节点tab判断是否null,为null时进行resize()方法初始化数组
//以及下次要扩容的阈值
// 当 tab != null 接着判断 tab的长度也不能为0 , 否则还是调用 resize() 方法进行初始化。
if ((tab = table) == null || (n = tab.length) == 0)
// 把初始化后的 table 赋给 tab table的长度赋给 n
n = (tab = resize()).length;
//根据当前key的hash值找到它在数组中的index索引上是否为空，
//若没有，则把key、value包装成Node节点，直接添加到数组上。
if ((p = tab[i = (n - 1) & hash]) == null)
// 在索引为i的位置，创建一个新节点直接放在这里即可
tab[i] = newNode(hash, key, value, null);
else {
//如果当前位置已经有元素了，分为三种情况。
Node<K,V> e; K k;
//1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，
//则把p赋值给e，跳转到①处，后续需要做值的覆盖处理
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//2.如果当前是红黑树结构，则把它加入到红黑树
else if (p instanceof TreeNode)
// 如果是一个红黑树，则调用红黑树的 putTreeVal 方法
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部,这里bitCount 记录的是链表长度，
for (int binCount = 0; ; ++binCount) {
// 如果 p.next == null ，则直接新建一个节点并让p.next 指向它
if ((e = p.next) == null) {
//如果头结点的下一个节点为空，则插入新节点
p.next = newNode(hash, key, value, null);
//如果在插入的过程中，链表长度超过了8，则转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//调用 treeifyBin(tab, hash) 进行树化
treeifyBin(tab, hash);
//插入成功之后(树化后)，跳出循环，跳转到①处
break;
}
//这里判断，当e.hash和传入hash相同时，且他们的key也相同，则跳出循环
//若在链表中找到了相同key的话，直接退出循环，跳转到①处
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//①
//说明发生了碰撞，e代表的是旧值，因此节点位置不变，但是需要替换为新值
// 当e != null ,说明这个key对应的映射关系已经存在
if (e != null) { // existing mapping for key
// 取出原先的值
V oldValue = e.value;
//当onlyIfAbsent 为false 或 oldValue == null时，会用新值替换旧值，并返回旧值。
if (!onlyIfAbsent || oldValue == null)
// 把e的value设为新传入value
e.value = value;
//看方法名字即可知，这是在node被访问之后需要做的操作。其实此处是一个空实现，
//只有在 LinkedHashMap才会实现，用于实现根据访问先后顺序对元素进行排序，hashmap不提供排序功能
// Callbacks to allow LinkedHashMap post-actions
//void afterNodeAccess(Node<K,V> p) { }
afterNodeAccess(e);
//返回旧值
return oldValue;
}
}
//modCount：fail-fast机制 如果两个线程同时进行操作就会出发fail-fast
++modCount;
//如果当前数组的长度大于了阈值就会触发扩容
if (++size > threshold)
resize();
//空实现
afterNodeInsertion(evict);
return null;
}
- if ((p = tab[i = (n - 1) & hash]) == null) 分析
这里我们要搞清楚，这里说的是n是当前数组的长度 -1 & hash 值 单个& 是位运算 也就是 16 -1 = 15 & 123
通过实践得出结论 那么这里计算出的就是当前要保存数组下标的位置 那么要保存数组的位置就是11
resize()方法
final Node<K,V>[] resize() {
// 保存旧的table
Node<K,V>[] oldTab = table;
// 获取旧table的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 获取旧table的阈值
int oldThr = threshold;
int newCap, newThr = 0;
// 如果旧table不为空
if (oldCap > 0) {
// 如果旧table的长度已经达到最大容量，则不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 否则，将旧table的长度翻倍作为新的容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 阈值也翻倍
}
// 如果旧table为空，但是threshold不为0，意味着用户指定了初始容量
else if (oldThr > 0) {
newCap = oldThr;
}
// 如果旧table为空且threshold也为0，那么使用默认的初始容量
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的阈值仍为0，那么根据负载因子计算新的阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新阈值
threshold = newThr;
// 创建新的table
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 更新table引用
table = newTab;
// 如果旧table不为空
if (oldTab != null) {
// 遍历旧table中的每一个桶
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 如果桶中有元素
if ((e = oldTab[j]) != null) {
// 清空旧桶中的元素
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;
// 根据元素的哈希值，决定放入新table的哪个桶
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;
}
}
}
}
}
// 返回新的table
return newTab;
}
- if ((e.hash & oldCap) == 0) { 这里要注意一下 这里说的是当前链表里面得数据得hash值 进行和 原链表得长度进行位运算，如果等于0 是要放到新链表原位置。若是不等于为0得话则是要会被放入新数组中索引为 j + oldCap 的位置对应的链表中。
- else if (e instanceof TreeNode)
/**
* 红黑树节点的拆分方法，用于HashMap扩容时将红黑树拆分为两个子结构
* @param map 所属的HashMap实例
* @param tab 新的哈希表数组
* @param index 当前节点在原哈希表中的索引位置
* @param bit 原哈希表的容量（oldCap），用于计算新位置
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
// 当前红黑树的根节点（this代表调用该方法的TreeNode实例）
TreeNode<K,V> b = this;
// 声明低位和高位子树的头节点和尾节点，用于拆分后重组
// lo表示低位（low），对应新数组中的原索引位置index
// hi表示高位（high），对应新数组中的新索引位置index + bit
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
// 记录两个子树的节点数量
int lc = 0, hc = 0;
// 遍历当前红黑树的所有节点
for (TreeNode<K,V> e = b, next; e != null; e = next) {
// 先保存下一个节点的引用（防止后续操作破坏链表结构）
next = (TreeNode<K,V>)e.next;
// 断开当前节点与下一个节点的连接，准备重组
e.next = null;
// 核心判断：通过哈希值与原容量的与运算决定节点归属
// 原理同链表拆分，利用哈希值中对应bit位的值进行分组
if ((e.hash & bit) == 0) {
// 放入低位子树：原索引位置index
// 如果是第一个节点，初始化头节点
if ((e.prev = loTail) == null)
loHead = e;
else
// 否则链接到当前尾节点后面
loTail.next = e;
// 更新尾节点为当前节点
loTail = e;
// 低位节点计数+1
++lc;
} else {
// 放入高位子树：新索引位置index + bit
// 逻辑同上，处理高位子树的节点链接
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
// 高位节点计数+1
++hc;
}
}
// 处理低位子树：放入新数组的原索引位置index
if (loHead != null) {
// 如果低位子树节点数 <= 6（UNTREEIFY_THRESHOLD），则转为普通链表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
// 否则保持为红黑树结构
tab[index] = loHead;
// 如果存在高位子树且也是红黑树，需要维持红黑树特性
if (hiHead != null)
loHead.treeify(tab);
}
}
// 处理高位子树：放入新数组的新索引位置index + bit
if (hiHead != null) {
// 如果高位子树节点数 <= 6，则转为普通链表
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
// 否则保持红黑树结构
tab[index + bit] = hiHead;
// 如果存在低位子树且是红黑树，需要维持红黑树特性
if (loHead != null)
hiHead.treeify(tab);
}
}
}
1.要注意这里会把红黑树拆分为低位子树和高位子树，若是低高位子树的长度低于或等于6的话则转换为链表。低位子树会放入到扩容后的新数组中原原先的索引位置，高位子树则会放入到新数组中原索引加原始数组长度的地方。若是低高位子树的长度超过6的话会继续保持红黑树结构。
面试无脑回答 hashMap put 全过程
- hashMap在put过程中 首先是计算hash值，计算hash值分为两种情况 若是key 为null得话hash值为0 不为空则进行 异域计算 也就是说 把hash值转换为二进制，从左到右移动16位 前面得都为0 取值最后面得值 并进行转换为十进制。
- 接下来进行判断是否table数组是否为null 为null 则进行初始化数组长度为16。
- 然后进行当前数组长度位运算hash值获取index索引值 通过索引下标获取当前数组是否为null ，若是为null 则进行保存在当前计算得索引上。
- 若是不为null得话则进行判断hash值和key是否相同，若是相同的话则进行覆盖原先得value值，若是不相同则就是hash碰撞，hashmap 采用得是拉链法，每个hash节点都有next指针，当前数组本身存放得是一个值，因为hash冲突得原因接下来这个数组位置得概念就变成了桶得概念，当前数组就变成了链表，紧接着会判断当前链表得长度有没有达到8 达到8了则会进行调用转换红黑树得代码，进入红黑树得代码第一件事就是判断当前数组得长度有没有达到64 若是没有则进行扩容下次再进行转换为红黑树，若是达到了则进行转换为红黑树。
- 代码执行到最后会调用一个扩容得代码resize方法，会把当前数组中得数据遍历到新的数组中 ，如果桶中有一个数据则重新计算下标位置存放到新的数组中，若是桶中不是一个得话会校验当前桶是不是红黑树，是的话会调用split方法 会把红黑树拆分为低位子树和高位子树，若是低高位子树的长度低于或等于6的话则转换为链表。低位子树会放入到扩容后的新数组中原原先的索引位置，高位子树则会放入到新数组中原索引加原始数组长度的地方。若是低高位子树的长度超过6的话会继续保持红黑树结构。若不是得话只能是链表了
循环遍历当前链表里面得数据 根据hash值进行和 原链表得长度进行位运算，如果等于0 是要放到新数组原位置上。若是不等于为0得话则是要会被放入新数组中索引为 j + oldCap （原先位置+原先数组长度）= 新数组的位置对应的链表中。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
26
0- 0
已为社区贡献5条内容
所有评论(0)