java hashmap 删除指定值 hashmap 删除指定键
删
同样看主要部分 (不同的删除操作细节上会有些不同,比如map.remove(key)就不匹配值只根据key来删除,且会调整根节点与头结点的匹配关系,不过都是基于这个方法啦)
这个查部分理解,问题不大,整个方法还是分为两部分
1.查找,就是普通的查找(不了解的话可以看看此文对应部分) 2.删除,如果想要删除的点被查找到了(没找到自然不用处理,而且有需要匹配value的话,如果value不一致也不会进行删除,返回null,),链表的删除部分很简单,
如果是头结点,换下一个节点为头结点;如果不是就是让被删除的节点的前结点跳过该节点即可。
树部分见下
//3.对map的修改次数+1
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;
如果该节点有可能存在于树中
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;
头结点就是目标节点
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 = 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.next = node.next;
修改次数+1
++modCount;
--size;
//用于linkedhashmap处理
afterNodeRemoval(node);
返回被删除的节点
return node;
}
}
return null;
}
HashMap中的红黑树的删除方法的思路大概是这样的:
1.特判:
首先特判:桶表如果未初始化则直接返回
2.重整链表
找到目标节点(就是需要被删除那个)所在桶,首先将链表重置一下(移除目标节点)
然后再判断下树的高度是否小于2(高度为2的红黑树最大节点数为6),若小于则退化为链表,返回。
3.用目标节点的右子树的最左节点替代目标节点。
4.清空对目标节点的引用
6.如果目标节点原来为红结点则不做操作,否则重新平衡树
7.如果允许改动头结点,则将头结点设置为根节点(本来更新后也该是一致的,不过使用迭代器的时候就不让更新了)
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
如果tab未初始化,那直接return
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;
记录下查找需要删除节点,链表结构下的下一个节点和上一个节点
(用于重整链表)
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();
如果根节点为空,或者说树高度小于2
(红链接都是左节点的连接,高度为2的红黑树是最大值刚好为6),
就说明太小了将其链表化
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
如果需要删除的节点有左右子树,
hashmap中红黑树里采取的策略是
用右子树的最左节点替代目标节点
(因为这个节点肯定比原目标节点的左大右小)
if (pl != null && pr != null) {
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是个叶子节点,且目标节点p是s的爹
if (s == pr) { // p was s's direct parent
将p置于s的右儿子(交换父子关系,不过还没有和树接上)
p.parent = s;
s.right = p;
}
如果p不是s的爹,执行的操作结果也是一样的功能,
交换s和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;
将原来s的右子树移动到p身上
if ((p.right = sr) != null)
sr.parent = p;
将p原来的左子树赋予给s
(s本身是没有左子树的,它就是最左了)
if ((s.left = pl) != null)
pl.parent = s;
将p原来的爸爸变为s的爸爸,
如果没有爸爸,则说明p是根节点,将根节点置为s
if ((s.parent = pp) == null)
root = s;
如果不是根节点,
则看p是原来爸爸的左儿子还是右儿子,
将这个左/右儿子身份给s
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
如果s原来是有右子树的,
则将右子树给保存下来,之后用于替换s
if (sr != null)
replacement = sr;
若没有右子树,则设置为本身
else
replacement = p;
}
下面就是独生子女或者丁克的情况,这种贼好处理。
要么子承父业,要么就充公(null)
如果原来的p没有左子树,则将替代存为左子树
else if (pl != null)
replacement = pl;
如果原来没有右子树,则将替代存为右子树
else if (pr != null)
replacement = pr;
else
replacement = p;
p有孩子(无论是否交换过爹和孩子)
if (replacement != p) {
保存下p现在的爹,作为唯一孩子的爹
TreeNode<K,V> pp = replacement.parent = p.parent;
如果p没得爹,就说明p原来是大家的爹(根节点)
if (pp == null)
root = replacement;
如果不是则将p的左/右儿子身份给唯一的孩子
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
这时再放开p的所有引用以及对p的引用,
防止重复引用,便于垃圾回收
p.left = p.right = p.parent = null;
}
如果p本身是红结点,删了倒是没影响,
要不然就得重新平衡树了
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
如果p现在是个孤寡老人,则将对它的引用清空,利于垃圾回收
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;
}
}
如果允许更改头结点,则将头结点设置为根节点,
只有迭代器中的remove方法不允许修改头结点
if (movable)
moveRootToFront(tab, r);
}
替
emmm这个看了下代码实现比较简单,没啥好讲的,不过平时用的比较多的好像是直接用put方法修改,replace()这些方法倒是用得比较少(不过replace相对比较安全,如果不存在呢就添加了(当然如果自行判断下那也行))
其他HashMap内容:
浅析HashMap(均基于JDK11)
推荐阅读
-
java hashmap 删除指定值 hashmap 删除指定键
-
Hashcat命令详解-常用 -a 指定要使用的破解模式,其值参考后面对参数。“-a 0”字典攻击,“-a 1” 组合攻击;“-a 3”掩码攻击。 -m 指定要破解的hash类型,如果不指定类型,则默认是MD5 -o 指定破解成功后的hash及所对应的明文密码的存放位置,可以用它把破解成功的hash写到指定的文件中 --force 忽略破解过程中的警告信息,跑单条hash可能需要加上此选项 --show 显示已经破解的hash及该hash所对应的明文 --increment 启用增量破解模式,你可以利用此模式让hashcat在指定的密码长度范围内执行破解过程 --increment-min 密码最小长度,后面直接等于一个整数即可,配置increment模式一起使用 --increment-max 密码最大长度,同上 --outfile-format 指定破解结果的输出格式id,默认是3 --username 忽略hash文件中的指定的用户名,在破解linux系统用户密码hash可能会用到 --remove 删除已被破解成功的hash -r 使用自定义破解规则 按s键可以查看破解的状态, p键暂停 r键继续破解 q键退出破解