Java集合系列-Map系列-HashMap剩余源码解析

一、HashMap对元素的删除
第一个删除方法clear()：清除所有元素

public void clear() {
Node<K,V>[] tab;
modCount++;
//首先判断数组是否为空，然后判断数组中是否存在元素
if ((tab = table) != null && size > 0) {
//走到这一步：说明HashMap中存在元素，需要清除
//size:表示当前HashMap的元素个数。
size = 0;
for (int i = 0; i < tab.length; ++i)
//循环数组，然后把都置为null.以便于GC
tab[i] = null;
}
}
1:将size置为0
2：将数组元素只为null,以便于GC
所以清除方法非常的简单，清除所有元素我们知道了，那么有没有把指定key的元素删除呢？答案是肯定的。

第二个删除指定key的方法remove(key):从HashMap中移除指定的元素。

public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
此方法并没有做什么事，而是把删除的工作放到了removeNode方法中，如果指定的key存在，移除成功后返回原来的值，如果指定的key不存在，则返回null,接下来我们继续跟进removeNode方法。

参数分析：
1：hash：key的hash,通过hash(key)
2:key：要删除的键值对的key
3:value:要删除的键值对的value,此value是否作为删除条件，主要取决于下面的matchValue。
matchValue=true，,删除指定的key时，同时需要判断查找的key的值和value相等才被删除，如果查找的key的值与value不相等，则不删除，
matchValue=false：则此时不作为删除条件
4:matchValue:如果为true,则value作为删除条件，如果为false，则value不作为删除条件。
5:movable：删除后是否移动节点，如果为true则移动，如果为false则不移动。
说明：此方法主要有两个流程
第一个流程：查找出指定key对应的节点
第二个流程：根据条件判断是否删除。判断条件如下：
1：指定key的节点n存在
2：如果matchValue=true,则还需要判断n.value==value,或者value.equals(n.value),如果matchValue=false，则这个条件就不需要判断了。
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))))
//走到这一步：说明key对应的下标元素。
node = p;
else if ((e = p.next) != null) {
//走到这一步：说明key对应下标的元素不是key,就需要从链表或者红黑树中查找了。
if (p instanceof TreeNode)
//走到这一步：说明从红黑树中查找key对应的节点，查找方法接下会分析
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//走到这一步：说明从链表中查找key对应的节点。
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)))) {
//走到这一步：说明查找到了key对应的节点，如果matchValue=true的话，查找的节点值node.value与参数给定的值相等。
if (node instanceof TreeNode)
//走到这一步：说明此下标是一颗红黑树，所以从红黑树中删除
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
//走到这一步：说明此下标第一个元素就是key对应的节点，直接删除
tab[index] = node.next;
else
//走到这一步：说明链表中查找的，从链表中删除。
p.next = node.next;
++modCount;
–size;
//这个方法在HashMap中是空实现，没有什么意义，在LinkedHashMap中有意义，在下一篇文章我对LinkedHashMap分析时会讲到
afterNodeRemoval(node);
return node;
}
}
return null;
}
移除指定key的代码做一个总结：

1:首先查找到key对应的节点
1.1：key对应的底层数组的下标第一个元素就是key对应的节点
1.2：此下标是一个红黑树，从红黑树中查找key对应的节点。
1.3：此下标是一个链表，从链表中查找key对应的节点。
2：然后把对应的节点删除
2.1：第一个元素是要删除的节点，直接删除
2.2：如果是红黑树，则调用红黑树的删除方法
2.3：如果是链表，则利用链表的删除机制删除节点。
二、HashMap对元素的查询
第一个查询方法：get(key)

public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
此方法也没有什么实质性的内容，它把查找的工作交给了getNode去完成，然后返回查询的key对应的value
下面我们看一下getNode方法到底怎样查找key对应的值

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
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) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
上面的代码非常的容易，也是从三个方面来查找的
1：如果key对应的数组下标第一个元素，则直接返回
2：如果key计算的下标是一个红黑树，则从红黑树中查找
3：如果key计算的下标是一个链表，则从链表中查找。
第二个方法：查找所有的key:keySet();源码如下：

public Set keySet() {
Set ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
通过查看此方法，我们只看到返回了一个KeySet的对象。并没有看到把所有的key放到Set集合中去，我们首先看下面一个例子：

public static void main(String[] args) throws InterruptedException {
Map<Integer, Integer> map = new HashMap<>();
map.put(6, 1);
map.put(20, 2);
map.put(1, 3);
map.put(3, 4);
Set integers = map.keySet();
}
通过对上面的代码进行debug结果如下图：

Java集合系列-Map系列-HashMap剩余源码解析
看到这个结果，可能会有人疑惑，HashMap的key什么时候添加到KeySet集合中的呢？我们顺着这个思路去探索，上面的keySet不是返回一个内部类KeySet吗，那我们就进入这个类中，寻找它的构造函数，一定会有把key放到Set集合中的逻辑。KeySet的代码如下：

final class KeySet extends AbstractSet {
//重点：重写了size方法，直接返回的是HashMap的size
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
//重点：重写了iterator方法
public final Iterator iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
从上面的代码中，我们并没有看到KeySet的构造函数，说明调用的默认无参数构造函数，那这和我们想象的逻辑有冲突啊，并没有看到key放到Set集合中去，那这个逻辑是不是在KeySet父类中的，我们接下来进入AbstractSet中，我们会发现此父类就一个默认构造函数。

protected AbstractSet() {
}
也没有找到我们想象的会把HashMap的所有key放到Set集合中，但是上面的例子通过跟踪断点，确实看到了Set集合有元素啊。那这到底怎么回事呢？这完全打破了我们对Java的理解。

其实这并不是打破了我们对Java的理解，我们在keySet方法中所看到的只是获取了KeySet的一个引用，此时HashMap的key并没有加入到KeySet集合中去，我们在调试时看到已经有了元素，因为IDE在显示对象的时候调用了对象的toString方法，而KeySet的toString方法中调用了迭代器。我们首先看以下toString方法。

public String toString() {
//上来就调用了迭代器。
Iterator it = iterator();
if (! it.hasNext())
return “[]”;
StringBuilder sb = new StringBuilder();
sb.append(’[’);
for (;???? {
E e = it.next();
sb.append(e == this ? “(this Collection)” : e);
if (! it.hasNext())
return sb.append(’]’).toString();
sb.append(’,’).append(’ ');
}
}
从toString方法中我们看到，它调用了迭代器iterator(),而KeySet的从新覆写了iterator方法。

public final Iterator iterator() { return new KeyIterator(); }
我们接着进入KeyIterator源码中看个究竟。

final class KeyIterator extends HashIterator
implements Iterator {
//直接就返回了HashMap的key了。
public final K next() { return nextNode().key; }
}
所以我们总结keySet()方法如下：

1：keySet方法只返回了KeySet对象，自始至终就没有把HashMap的key放入到Set集合中
2：KeySet的toString方法(在父类AbstractSet中)调用iterator方法，KeySet又重写了iterator方法。
3：调用size()方法有值，只是KeySet重写了size方法，直接返回了HashMap中的size。
4：用IDE调试时发现有值，因为IDE显示对象信息时，调用了toString方法
归根结底：调用keySet()方法时，HashMap并没有把所有的key放到Set集合中，Set集合永远是空的，我们看到的有值，只是KeySet重写了相应的方法，直接返回HashMap的数据，所以想象的Set集合中有值是错误的，只是一种假象罢了。

第三个方法：查找所有的值values():此机制和上面的KeySet一致，代码如下：

public Collection values() {
Collection vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
第四个方法：查找所有的Map.Entry()：此机制和上面的keySet一致。代码如下：

public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
三、HashMap其他有用的方法
第一个方法：compute

首先我们看一个例子：

统计一个整型数组nums中每一个数字出现的个数。
Integer[] nums = new Integer[]{1,2,5,1,3,2,6,4,5,10,20,10,6};
我们首先会想到如下的方案：

private static void test1(Integer[]nums){
Map<Integer,Integer>map = new HashMap<>();
for(int i=0;i<nums.length;i++){
Integer num = nums[i];
if(map.containsKey(num)){
Integer integer = map.get(num);
map.put(num,++integer);
}else{
map.put(num,1);
}
}
for(Map.Entry<Integer,Integer>me:map.entrySet()){
System.out.println(me.getKey()+“出现了”+me.getValue()+“次”);
}
}
运行结果如下图：

Java集合系列-Map系列-HashMap剩余源码解析
那还有没有其他简便的方法呢？答案是肯定的，HashMap为我们提供了compute方法，代码如下：

private static void test2(Integer[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer num = nums[i];
map.compute(num, (k, v) -> v + 1);
}
for (Map.Entry<Integer, Integer> me : map.entrySet()) {
System.out.println(me.getKey() + “出现了” + me.getValue() + “次”);
}
}
运行结果如下：

接下来我们分析computer到底做了什么，请看下面代码：

public V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
…//此处省略了查找指定key的代码，因为上面我们已经分析过了。
//获取查找到的值
V oldValue = (old == null) ? null : old.value;
//调用功能接口的apply方法
V v = remappingFunction.apply(key, oldValue);
if (old != null) {
//走到这一步：说明查找到了key对应的值，然后把计算的值赋值给key对应的节点
if (v != null) {
old.value = v;
afterNodeAccess(old);
}
else
removeNode(hash, key, null, false, true);
}
else if (v != null) {
//走到这一步：说明HashMap中没有对应的key的值。
if (t != null)
t.putTreeVal(this, tab, hash, key, v);
else {
tab[i] = newNode(hash, key, v, first);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
}
++modCount;
++size;
afterNodeInsertion(true);
}
其中BiFunction是一个功能接口，定义如下：

public interface BiFunction<T, U, R> {
//这个就是上面调用的，remappingFunction.apply(key, oldValue);
//也是我们例子当中(k, v) -> v + 1
R apply(T t, U u);

default BiFunction<T, U, V> andThen(Function<? super R, ? extends V> after) {
Objects.requireNonNull(after);
return (T t, U u) -> after.apply(apply(t, u));
}

通过实例大家明白了compute方法的作用了吧，就是通过apply(key,value)计算出新值，然后赋值给此key对应的，而apply就是需要我们实现的。

第二个方法：meger

我们首先也是通过一个例子入手：

public static void main(String[] args) {
Map<String, String> map = new HashMap<>();
map.put(“a”, “a”);
map.merge(“a”, “b”, (oldValue, value) -> oldValue + value);
System.out.println(map.get(“a”));
}
运行结果如下：

Java集合系列-Map系列-HashMap剩余源码解析
通过结果可以看出，key="a"对应的旧值和“b”合并了。

接下来我们分析以下：

public V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
…//此处省略了获取key的代码。
if (old != null) {
V v;
if (old.value != null)
//走到这一步：说明找到了旧值，然后通过我们在apply定义的逻辑把旧值和给定的值进行计算。
v = remappingFunction.apply(old.value, value);
else
//走到这一步：说明没有找到旧值，直接返回给定的值。
v = value;
if (v != null) {
//如果通过上面的步骤，v！=null,则把key对应的修改成v.
old.value = v;
afterNodeAccess(old);
}
else
//走到这一步：说明通过计算，v==null，移除节点
removeNode(hash, key, null, false, true);
return v;
}
if (value != null) {
if (t != null)
t.putTreeVal(this, tab, hash, key, value);
else {
tab[i] = newNode(hash, key, value, first);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
}
++modCount;
++size;
afterNodeInsertion(true);
}
return value;
上面两个方法看起来用起来非常的方便，也容易理解。现在总结如下：

1：对于compute:如果key存在且值不为null,则覆盖，如果key不存在则添加

1:获取key对应的节点值：oldValue
2：通过remappingFunction.apply(key, oldValue)计算出v
3:如果oldValue==null,则直接将put(key,v)
4:如果oldValue!=null,则直接覆盖原来put(key,v)
2：对于meger：如果key存在且值不为null，则按照我们给出的覆盖，如果key不存在则直接添加

1:获取key对应的节点值：oldValue
2：通过remappingFunction.apply(old.value, value)计算出v
3:如果oldValue==null,则直接将put(key,v)
4:如果oldValue!=null,则直接覆盖原来put(key,v)