hashmap移除元素_HashMap1.8 源码解析(2)--删除元素

完整代码:代码

前言

删除

删除有两种方式:

1. remove(Object key)根据key删除

2. remove(Object key, Object value) 根据key和value删除

注意:只有扩容,没有说删除后缩小容量这个操作.

/**

* 注意与remove(Object key)不同的两点:

* 1. 要根据key,value同时符合才可以删除该节点

* 2. 返回值是true 表明正确删除

* 返回值是false 表明没有这个节点

*/

@Override

public boolean remove(Object key, Object value) {

return removeNode(hash(key), key, value, true, true) != null;

}

/**

* 根据key来remove在HashMap中的节点

*/

public V remove(Object key) {

Node e;

return (e = removeNode(hash(key), key, null, false, true)) == null ?

null : e.value;

}

/**

*

* @param hash hash值

* @param key

* @param value

* @param matchValue 如果true表明必须key和value同时符合要求才可以删除,如果false的话只需要key符合就可以

* @param movable 用于红黑树中的操作 在红黑树分析中会有提及

* @return 如果存在这个节点,会返回此节点 否则返回null

*/

final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {

Node[] tab;

Node p;

int n, index;

/**

* 如果hash值对应的bucket存在的话就继续寻找

* 分两步:

* 1. 先寻找到节点,如果存在则放到node中

* 2. 如果存在删除该节点

*/

// 第一步 查找节点

if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {

Node node = null, e;

K k;

V v;

/**

* 如果存在这个节点,会把节点赋值给node

* 分三种情况:

* 1. 就在hash值对应的bucket中是第一个元素

* 2. 在红黑树中

* 3. 在链表中

*/

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

node = p; // 情况1

else if ((e = p.next) != null) {

if (p instanceof TreeNode) // 情况2 会在HashMap红黑树中专门分析

node = ((TreeNode) p).getTreeNode(hash, key);

else { // 情况3

do { // 循环链表查找 查找到后赋值给node

if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {

node = e;

break;

}

p = e;

} while ((e = e.next) != null);

}

}

/**

* 第二步:删除操作

* 三种情况:

* 1. 树节点

* 2. bucket节点,直接bucket节点设置为node.next

* 3. 在链表中删除node节点

*

* modCount会在分析HashMap Iterator中详细分析

*/

if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {

if (node instanceof TreeNode)

((TreeNode) node).removeTreeNode(this, tab, movable);

else if (node == p)

tab[index] = node.next;

else

p.next = node.next;

++modCount;

--size;

afterNodeRemoval(node); //留作子类LinkedHashMap中使用

return node;

}

}

return null;

}

小例子

这个例子是为了说明一下两个remove之间的区别

还是和上篇一样定义了一个Person类

public class Person {

String name;

int age;

public Person() {}

public Person(String name, int age) {

this.name = name;

this.age = age;

}

@Override

public String toString() {

return "Person [name=" + name + ", age=" + age + "]";

}

@Override

public boolean equals(Object obj) {

if (this == obj) return true;

if (obj instanceof Person) {

Person p = (Person)obj;

return p.name.equals(this.name);

}

return false;

//return true;

}

@Override

public int hashCode() {

// TODO Auto-generated method stub

return age;

}

}

测试

public class TestHashMap {

public static void main(String[] args) {

HashMap map = new HashMap<>(3);

map.put(new Person("tom_1", 12), 12);

map.put(new Person("tom_2", 0), 0);

map.put(new Person("tom_3", 4), 4);

System.out.println("capacity:" + map.table.length);

//printMap(map);

map.put(new Person("tom_4", 16), 16);

//System.out.println("------------------after insert tom_4---------------------");

System.out.println("capacity:" + map.table.length);

printMap(map);

System.out.println("---------------------------------------------------------");

boolean f = map.remove(new Person("tom_4", 4), 4); //没有删除成功 因为必须key和value都要对应上才可以删除

System.out.println("delete : " + f);

printMap(map);

System.out.println("---------------------------------------------------------");

map.remove(new Person("tom_4", 16));

map.remove(new Person("tom_3", 4));

map.remove(new Person("tom_2", 0));

map.remove(new Person("tom_1", 12));

printMap(map);

}

private static void printMap(HashMap map) {

HashMap.Node[] table = map.table;

for (int i = 0; i < table.length; i++) {

System.out.print(i + ":");

HashMap.Node e;

if ((e = table[i]) != null) {

System.out.print(e);

HashMap.Node p;

while ((p = e.next) != null) {

System.out.print("->" + p);

e = e.next;

}

}

System.out.println();

}

}

}

结果

image.png

参考

1.java1.8 源码