“ 本文将主要介绍HashMap的remove操作。”
相关阅读:
JDK1.8HashMap源码学习-数据结构
JDK1.8HashMap源码学习-初始化
JDK1.8HashMap源码学习-put操作以及扩容(一)
JDK1.8HashMap源码学习-put操作以及扩容(二)
JDK1.8HashMap源码学习-get操作
我们先看下我们调用的remove方法
代码语言：javascript复制public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key)
, key, null, false, true)) == null ?
null : e.value;
}我们看到方法比较简单，就是将传入的key进行了hash算法，然后再调用removeNode方法并将返回赋值给e，判断e是否为空，如果为空则返回null，不为空则返回key对应的value。
查看hash方法我们发现是可以传入空的，返回的值是0，那就是说HashMap是允许存在key值为null的，且有且只有一个，因为如果再次放入，hash算法算出来的值是一致的，会覆盖掉原先的值。
那真正执行remove操作就是我们的重头戏，我们一起看下removeNode方法
代码语言：javascript复制/**
* hash 移除key的hash值
* key 要移除的key
* value 要移除的key对应的值 默认传入为null
* matchValue 是否匹配值 默认为false
* movable 是否移除 默认true
*/
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;
//数组不为空且对应key所在的数组下标数据不为空
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;
//数组下标保存的数据hash一致且key一致 即要移除的数据就是该数据
if (p.hash == hash
&& ((k = p.key) == key ||
(key != null && key.equals(k)))){
node = p;
//不是根节点 且根节点的下一节点不为空
}else if ((e = p.next) != null) {
//判断根节点是否是树节点
if (p instanceof TreeNode){
//通过树查找到要移除的节点
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
}else {
//不是红黑树 那就是单链结构 循环遍历找到要移除的节点数据
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
//赋值操作 就要移除的节点前节点赋值给p 便于接下来的移除操作
p = e;
//接下来 移动到当前节点的下一个节点进行再次循环判断
} while ((e = e.next) != null);
}
}
//找到要移除的节点数据
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);
//不是红黑树 移除的是单链的头节点 即数组保存节点改为当前节点的下一个节点
}else if (node == p){
tab[index] = node.next;
}else{
//不是根节点 在前面找节点的时候执行过p的赋值操作即为找到节点的操作 将移除节点的父节点指向移除节点的下一个节点
//因为是单链 只能是这么操作
p.next = node.next;
}
//修改次数 1
modCount;
//map容量-1
--size;
//无操作 留给子类扩展
afterNodeRemoval(node);
return node;
}
}
return null;
}通过代码我们理一下大概的思路：
首先是要查找我们要移除的节点，先判断的是根节点，如果是根节点我们就退出查找，如果不是那就判断是否还有后续节点，如果有则判断根节点的类型是否是树节点类型，如果是就调用查找红黑树节点的方法 getTreeNode，如果不是那就是单向链表结构，循环遍历即可。其中查找红黑树节点的方法我们上一篇已经介绍过，飞机票JDK1.8HashMap源码学习-get操作，这里不再进行介绍。
接着就是如果找到了要移除的节点，就执行对应的移除操作。如果是树节点那就调用树节点的移除方法removeTreeNode，如果不是的话就判断是否是单链表的头节点，如果是直接将根节点赋值为移除节点的后节点即可，如果不是就直接将移除节点的前节点的后节点指向移除节点的后节点即可。
接下来我们看下移除树节点的操作
代码语言：javascript复制final void removeTreeNode(HashMap<K,V> map,
Node<K,V>[] tab,
boolean movable) {
int n;
//数组为空 直接返回
if (tab == null || (n = tab.length) == 0){
return;
}
//计算数组下标
int index = (n - 1) & hash;
//找到树的根节点和链表的头节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index],
root = first, rl;
//从调用处判断 next和prev应该指的是
//要移除节点的下一节点和前一节点
TreeNode<K,V> succ = (TreeNode<K,V>)next,
pred = prev;
//如果移除节点的前节点为空
//说明移除的是根节点 数组保存数据
//即为移除节点的下一节点 链的头节点也是
if (pred == null){
tab[index] = first = succ;
//不为空 则将移除节点的前节点的后节点
//赋值为移除节点的后节点
//就是把移除节点的前后节点直接链接
//移除掉要移除的节点
}else{
pred.next = succ;
}
//移除节点的后节点不为空
//移除节点的后节点的前节点赋值为移除节点的前节点
//完成前后节点的双链链接
if (succ != null){
succ.prev = pred;
}
//链表头为空 直接返回
if (first == null){
return;
}
//根节点的父节点不为空 查找树的根节点
if (root.parent != null){
root = root.root();
}
//如果节点数很少 转为链表结构
if (root == null
|| (movable && (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}
/**
* this 就是要移除的节点 处理树结构怎么移除
* p 要移除的节点
* pl 要移除节点的左孩子
* pr 要移除节点的右孩子
* replacement 应该是要准备替换到当前移除节点的节点
*
* 整体就是找到要替换到当前移除节点的节点 并把移除节点挂载到移除节点右孩子的最左孩子的位置
*/
TreeNode<K,V> p = this,
pl = left,
pr = right,
replacement;
//移除节点的左右孩子均不为空
//则替换移除节点和移除节点右孩子的最左孩子 做交换
if (pl != null && pr != null) {
//s 移除节点右孩子的最左孩子
TreeNode<K,V> s = pr, sl;
//找到移除节点右孩子的最左孩子
//因为红黑树的结构保证了移除节点的右孩子的左孩子一定在移除节点和移除节点右孩子中间
while ((sl = s.left) != null){ // find successor
s = sl;
}
//将要移除节点的颜色和移除节点右孩子的最左孩子执行颜色交换 用于判断是否需要调整数的颜色等
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
//最左孩子的右孩子
TreeNode<K,V> sr = s.right;
//移除节点的父节点
TreeNode<K,V> pp = p.parent;
//s 就是移除节点的右孩子 即s没有左孩子
if (s == pr) { // p was s's direct parent
p.parent = s;//赋值操作 将移除节点的父节点改为s
s.right = p;//将移除节点的右孩子的右孩子赋值为移除节点
}else {
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;
}
}
//将移除节点的左孩子赋值为空
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;
}
//到了这里基本就已经完成了 replacement是移除节点本身或者是移除节点的左右孩子 而且再没有叶子节点了
if (replacement != p) {//如果顶替节点不是本身 主要完成的就是将替换节点挂载到原先移除节点的位置或者是已经移动过的位置 并断开相应的连接
//赋值顶替节点的父节点为移除节点的父节点
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null){//没有父节点 说明replacement就是根节点 赋值根节点
root = replacement;
}else if (p == pp.left){//如果移除节点是父节点的左孩子 赋值父节点的左孩子为顶替节点
pp.left = replacement;
}else{//移除节点肯定是父节点的右孩子 赋值父节点的右孩子为顶替节点
pp.right = replacement;
}
//将移除节点的左右孩子和父节点赋值为空
p.left = p.right = p.parent = null;
}
//前面做过颜色替换 如果是红则使用root 否则执行删除时平衡树方法
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
//如果顶替节点就是移除节点本身 应该就是一个叶子节点 直接执行移除即可
if (replacement == p) { // detach
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;
}
}
}
//确保根节点在数组中
if (movable){
moveRootToFront(tab, r);
}
}移除红黑树节点中如果节点是叶子节点就直接可以执行移除操作，如果不是的话就需要找到可以替换移除节点的节点进行互换，然后再进行移除。有点像移除节点在退到叶子节点。我们上两个动图方便大家可以直观的感受下。
当地
个人学习理解，如有错误还望大家指正，共同学习。
