全网!最全!最完整!HashMap解析 三

三 HashMap删除过程HashMap#remove()

这次，废话少说，先看源码。PS:码上有注释,要注意多看啊

/** * 从map中删除指定的key,如果key存在的话 * @param key key whose mapping is to be removed from the map * @return value 如果key存在,返回key对应的Value,如果不存在返回null */public V remove(Object key) { HashMap.Node<K, V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;}

其中计算hash值的方法还是和之前的一样。

removeNode

/** * Implements Map.remove and related methods. * 实现Map.remove相关的方法 * @param hash hashCode * @param key key * @param valuevalue * @param matchValue 如果是true，仅在value相等的时候删除。 * @param movable 如果为false，则在删除节点的时候不移动其他节点。 * @return 返回删除的节点 */final HashMap.Node<K, V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) { HashMap.Node<K, V>[] tab; HashMap.Node<K, V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { HashMap.Node<K, V> node = null, e; K k; V v; if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { if (p instanceof HashMap.TreeNode) {// 找到红黑树中的节点node = ((HashMap.TreeNode<K, V>) p).getTreeNode(hash, key); } else {// 删除链表中的节点1: 查找到节点的位置。do {if (e.hash == hash && ((k = e.key) == key ||(key != null && key.equals(k)))) { node = e; break;}p = e;} while ((e = e.next) != null); } } // 真正的去删除的过程。 if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) { if (node instanceof HashMap.TreeNode) {// 删除红黑树的节点((HashMap.TreeNode<K, V>) node).removeTreeNode(this, tab, movable); }else if (node == p) {// 桶中只有当前的节点。tab[index] = node.next; }else {// 链表中节点的删除p.next = node.next; } // 修改次数+1 ++modCount; --size; afterNodeRemoval(node); return node; } } return null;}

还有一个最难理解的方法落在了红黑树的移除上了。

HashMap#TreeNode#removeTreeNode

还是先了解下红黑树的删除是怎么回事。

可以去看一下，我之前文章,在【数据结构和算法】目录下 就有红黑树的相关内容。这里我就只贴出文章名字了: 【听说你还不懂红黑树? 二】

在删除方法调用之前必须要有存在的给定节点。这比典型的红黑删除代码更混乱，因为我们不能将内部节点的内容与叶子后继交换，后者由遍历期间可独立访问的“下一个”指针固定。所以我们交换树链接。如果当前树似乎有太少的节点，则红黑树(bin)将转换回普通的链表(普通bin). （测试会在2到6个节点之间触发，具体取决于树结构）。上面是 removeTreeNode方法的解释.说实话，没理解..

HashMap的删除不同于普通的红黑树的删除, 因为它其中还维护了，一个链表的指向. HashMap采用的是将树中的两个节点进行换位, 颜色也要进行互换，来保证红黑树的平衡,并不改变二者在链表中的位置,互换后,删除节点此时的左子树是空的，将问题转换成了对左子树为空的节点的删除。

有一个简单的问题,千万不要弄混了,就是TreeNode中要删除的节点是谁??

删除的签名是这样的:final void removeTreeNode(HashMap<K, V> map, HashMap.Node<K, V>[] tab,boolean movable),并没有传 TreeNode啊?是不是??

干吗呢！大兄嘚. 要删除的节点是：this啊。我们现在走到了TreeNode内部了!! 它本身就是要被删除的节点啊。

好了，那我现在要告诉你: 删除自己！

HashMap删除红黑树的节点，实际上就是 TreeNode自己删除自己。那么它是怎么删的呢?

它分成了三步:

1.将删除节点从双链向链表中删除.

2.将删除节点与其右子树最小节点互换,之后平衡树

3.将树根节点，移动到tab[index]指针处

final void removeTreeNode(HashMap<K, V> map, HashMap.Node<K, V>[] tab, boolean movable) { // 注意了：这个时候被删除的节点是谁?? // 是this. int n; if (tab == null || (n = tab.length) == 0) return; // 找到对应的索引(确定对应桶的位置), n 是当前表的长度 int index = (n - 1) & hash; // first: 第一个树节点(当前为父节点),root，父节点。rl: HashMap.TreeNode<K, V> first = (HashMap.TreeNode<K, V>) tab[index], root = first, rl; // succ:下一个节点(链表的指向)。pred, 前一个节点。 HashMap.TreeNode<K, V> succ = (HashMap.TreeNode<K, V>) next, pred = prev; if (pred == null) { // 前一个为空时，即当前接是父节点:(被删除的节点是根节点) tab[index] = first = succ; } else { // 否测,前一个节点的下一个执行当前节点的下一个。(意会) pred.next = succ; } if (succ != null) { // 当前节点的后节点不为null,后一个节点的前节点指向当前节点的前节点(意会) succ.prev = pred; } if (first == null) { // 如果删除当前节点，该桶变成了null的。就直接返回 return; } if (root.parent != null) { // 重置table[index]处为树的根节点。 root = root.root(); } // PS: 说点没用， JDK除了部分ifelse不加括号之外， // 其实换行，还是用的挺多的，看起来也挺舒服的。 // 值得借鉴 if (root == null|| (movable && (root.right == null|| (rl = root.left) == null|| rl.left == null))) { // 树太小了，将树转换成链表 tab[index] = first.untreeify(map); // too small return; } /*****注意！！！此时已经从双向链表中删除了, 第一步走完。******/ // p是待删除的节点，pl当前节点的左孩子节点,pr当前节点的右孩子节点,replacement,用来交换的节点。 HashMap.TreeNode<K, V> p = this, pl = left, pr = right, replacement; if (pl != null && pr != null) { // s为右子树的最小的节点,sl为左子树(一下五行和源码略有不同) HashMap.TreeNode<K, V> s = pr, sl = s.left; while (sl != null) { // find successors = sl;sl = s.left; } // 交换颜色 boolean c = s.red; s.red = p.red; p.red = c; // swap colors // 交换节点连接 HashMap.TreeNode<K, V> sr = s.right; HashMap.TreeNode<K, V> pp = p.parent; // pr是当前节点的右孩子节点 // s是当前节点的右子树的最小的节点 // p的右子树,只有s这一个节点 if (s == pr) { // p was s"s direct parentp.parent = s;s.right = p; } else { //// sp：最小节点的父节点HashMap.TreeNode<K, V> sp = s.parent;if ((p.parent = sp) != null) {if (s == sp.left) sp.left = p;else sp.right = p;}if ((s.right = pr) != null)pr.parent = s; } // 置null孩子。 p.left = null; if ((p.right = sr) != null) {sr.parent = p; } if ((s.left = pl) != null) {pl.parent = s; } if ((s.parent = pp) == null) {root = s; } else if (p == pp.left) {pp.left = s; } else {pp.right = s; } // 确定要交换的节点完毕，交换节点 if (sr != null) {replacement = sr; } else {replacement = p; } } else if (pl != null) { // 当前树只含有左子树 replacement = pl; } else if (pr != null) { // 当前树，只有又子树 replacement = pr; } else { // 无孩子 replacement = p; } if (replacement != p) { HashMap.TreeNode<K, V> pp = replacement.parent = p.parent; if (pp == null)root = replacement; else if (p == pp.left)pp.left = replacement; elsepp.right = replacement; p.left = p.right = p.parent = null; } // 是否要进行重平衡树? HashMap.TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement); // 在平衡后删除该节点 if (replacement == p) { // detach HashMap.TreeNode<K, V> pp = p.parent; p.parent = null; if (pp != null) {if (p == pp.left)pp.left = null;else if (p == pp.right)pp.right = null; } } // 参数moveable控制是否删除节点后确保树的根节点为链表的头节点 if (movable) { // 将树根节点，移动到tab[index]指针处 moveRootToFront(tab, r); } }

这样呢，整个删除过程就完成了。用官方中的话，比较混乱。尤其是涉及到红黑树的删除，这部分内容。还是需要好好消化，消化的。

下面我们还剩下两个内容：修改和查找

敬请期待吧。马上就来...

如果喜欢的，就点个在看吧 吧 吧 吧~

最后贴两张电影票，喜欢的朋友，抓紧抢座哦！