前言
点赞在看，养成习惯。
点赞收藏，人生辉煌。
点击关注【微信搜索公众号：编程背锅侠】，防止迷路。
HashMap系列文章
第一篇 HashMap源码中的成员变量你还不懂? 来来来！！！整理好的成员变量源码解析
第二篇 撸啊撸，再次撸HashMap源码，踩坑源码中构造方法！！！每次都有收获
第三篇 MoxiMoxi ！！！你看过HashMap中的put方法的源码吗？
第四篇 HashMap源码中的resize扩容方法除了扩容还有一个用途你真的知道吗？
第五篇 留一半清醒、留一半醉！！！HashMap中treeifyBin、treeify源码解析
第六篇 隔一段时间撸一次，特别香，HashMap中remove、getOrDefault源码，一遍一遍、又一遍
删除方法public V remove(Object key)
案例演示
测试删除首节点
@Test
public void test_remove_map(){
HashMap<Integer, String> map = new HashMap<>();
map.put(1, "aaa");
map.put(2, "bbb");
map.put(2, "bbb111");
map.put(3, "ccc0333");
map.forEach((k, v) -> System.out.println("k: " + k + " v: " + v));
System.out.println("=========================");
map.remove(2);// 执行remove方法
map.forEach((k, v) -> System.out.println("k: " + k + " v: " + v));
}
案例演示结果
k: 1 v: aaa
k: 2 v: bbb111
k: 3 v: ccc0333
=========================
k: 1 v: aaa
k: 3 v: ccc0333
测试删除链表节点
@Test
public void test_map_hash_remove() {
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < 64; i++){
map.put("BB" + i, i);
}
System.out.println(map.size());
// 构造8个哈希碰撞，会产生链表结构
map.put("3Qj", 800);
map.put("2pj", 801);
map.put("2qK", 802);
map.put("2r,", 803);
map.put("3RK", 804);
map.put("3S,", 805);
map.put("42j", 806);
map.put("43K", 807);
// 删除这个是删除的链表中的节点
map.remove("43K");
}
测试删除树节点
@Test
public void test_map_hash_remove() {
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < 64; i++){
map.put("BB" + i, i);
}
System.out.println(map.size());
// 构造8个哈希碰撞，会转换为红黑树
map.put("3Qj", 800);
map.put("2pj", 801);
map.put("2qK", 802);
map.put("2r,", 803);
map.put("3RK", 804);
map.put("3S,", 805);
map.put("42j", 806);
map.put("43K", 807);
map.put("44,", 808);
// 删除一个🌲节点
map.remove("44,");
}
源码解析
根据指定key的方法remove
// 根据指定的key删除元素,返回被删除的元素或者null
public V remove(Object key) {
// 定义一个节点变量，用来存储要被删除的节点（键值对）
Node<K,V> e;
// 调用removeNode方法根据给定的key获取node，获取的node为空，则返回空。获得的node不为空返回节点的value。
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
根据指定的key和value删除元素
// 返回是否删除成功
@Override
public boolean remove(Object key, Object value) {
// 调用removeNode方法删除元素
return removeNode(hash(key), key, value, true, true) != null;
}
删除节点关键方法removeNode
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;
// 当前集合不为空，并且根据给定的hash值是可以找到桶
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 如果桶上的节点就是要找的key，则将node指向该节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将要被删除的节点赋值给node
node = p;
// 到这，说明桶上的第一个节点不匹配，判断当前节点的下一个节点是否为空
// 如果没有next节点，说明该节点所在位置没有发生hash碰撞, 否则发生了哈希碰撞
else if ((e = p.next) != null) {
// 判断当前节点类型是否是树节点
if (p instanceof TreeNode)
// 从红黑树中获取要删除的节点赋值给node
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
// // 判断是否以链表的⽅式处理hash冲突，是的话则通过遍历链表来寻找要删除的节点
else {
// 循环遍历这个链表
do {
// 根据给定的hash值和key判断下一个节点是否是要删除的节点
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
// 将要删除的节点赋值给node
node = e;
// 跳出循环
break;
}
// 代码执行到这，说明未匹配上
// 把当前节点p指向e，这一步是让p存储的永远是下一次循环里e的父节点，如果下一次e匹配上了，那么p就是node的父节点
// 如果循环中找到了要被删除的节点，那么这个p节点，
p = e;
} while ((e = e.next) != null);
}
}
// 如果node不为空，说明根据key匹配到了要删除的节点
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);
// 如果该节点不是树节点，node == p：说明该node节点就是首节点，当前桶里就一个节点
else if (node == p)
// 删除的是首节点，那么直接将节点数组对应位置指向到下一个节点。
tab[index] = node.next;
else
// 删除链表节点。删除元素的操作是将被删除元素的父节点，指向被删除节点的下一个节点
p.next = node.next;
// 记录修改次数
++modCount;
// 变动的数量
--size;
afterNodeRemoval(node);
// 返回被删除的节点
return node;
}
}
// 没有被删除的元素返回null
return null;
}
源码总结
- 当前集合不为空，并且根据当前的key计算得到的索引拿到节点返回被删除的节点。
1、要删除的节点为首节点并且这个节点没有下一个节点，删除也就是将这个节点赋值为null.
2、要删除的节点为红黑树节点，根据key和key对应的哈希值从红黑树中获取要被删除的节点。
3、要删除的节点为链表节点，循环遍历这个链表，如果获取到要删除的节点跳出循环，删除元素的操作是将被删除元素的父节点，指向被删除节点的下一个节点。
- 当前集合为空，或者无法根据当前的key计算得到的索引拿到节点，返回null。
public V getOrDefault(Object key, V defaultValue)获取指定元素，如果拿不到返回我们自定义的val
案例演示
@Test
public void test_map_hash_getDefaultOf() {
HashMap<Integer, String> map = new HashMap<>();
map.put(1, "aaa");
map.put(2, "bbb");
map.put(3, "bbb111");
// 获取集合中存在的元素
String t = map.getOrDefault(3, "fafafa");
// 获取集合中不存在的元素
String d = map.getOrDefault(4, "lalala");
System.out.println("集合中包含：" + t + " 集合中不包含：" + d);
// 集合中包含：bbb111 集合中不包含：lalala
}
源码解析
getOrDefault源码解析
// 根据指定的key获取对应的val，如果拿到val,则返回拿到的val。否则返回我们给定的默认defaultValue
@Override
public V getOrDefault(Object key, V defaultValue) {
// 用于接收要获取到的node节点
Node<K,V> e;
// 获取到节点返回，节点的val，否则返回我们自定义的defaultValue
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
getNode方法的源码解析
// 根据指定的key和val获取节点
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 如果哈希表不不为空并且key对应的桶上不不为空
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) {
// 判断是否是红黑树，是的话调用红⿊树中的getTreeNode方法获取节点
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 不是红黑树的话，那就是链表结构了，通过循环的方法判断链表中是否存在该key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 返回这个节点
return e;
} while ((e = e.next) != null);
}
}
// 未获取到节点返回null
return null;
}
谢谢点赞
- 创作不易， 非常欢迎大家的点赞、评论和关注(^_−)☆
- 你的点赞、评论以及关注是对我最大的支持和鼓励
- 是我继续创作高质量博客的动力 ！！！
本文使用 mdnice 排版
