隔一段时间撸一次,特别香,HashMap中remove、getOrDefault源码,一遍一遍、又一遍

2020/7/13 18:20:36 人评论 次浏览 分类:学习教程

前言

点赞在看,养成习惯。

点赞收藏,人生辉煌。

点击关注【微信搜索公众号:编程背锅侠】,防止迷路。

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;
}
谢谢点赞
  • 创作不易, 非常欢迎大家的点赞、评论和关注(^_−)☆
  • 你的点赞、评论以及关注是对我最大的支持和鼓励
  • 是我继续创作高质量博客的动力 !!!

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->