More
More
文章目录
  1. ☞ compute()
  2. ☞ BiFunction
  3. ☞ @FunctionalInterface
  4. ☞ afterNodeAccess()
  5. ☞ computeIfAbsent()/computeIfPresent()
  6. 彩蛋

【java源码一带一路系列】之HashMap.compute()

  |  

本文以jdk1.8中HashMap.compute()方法为切入点,分析其中难理解、有价值的源码片段(类似源码查看是ctrl+鼠标左键的过程)。本篇涉及少许Java8(以下简称J8)新特性,请驴友们系好安全带,准备开车。观光线路图:compute() –> BiFunction –> @FunctionalInterface –> afterNodeAccess() –> computeIfAbsent() –> computeIfPresent()…

☞ compute()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
@Override
public V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Node<K,V>[] tab; Node<K,V> first; int n, i;
int binCount = 0;
TreeNode<K,V> t = null;
Node<K,V> old = null;
if (size > threshold || (tab = table) == null ||
(n = tab.length) == 0)
n = (tab = resize()).length;
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
}
V oldValue = (old == null) ? null : old.value;
V v = remappingFunction.apply(key, oldValue);
if (old != null) {
if (v != null) {
old.value = v;
afterNodeAccess(old);
}
else
removeNode(hash, key, null, false, true);
}
else if (v != null) {
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);
}
return v;
}

compute()是java8在Map中新增的一个方法,相对而言较为陌生。其作用是把remappingFunction的计算结果关联到key上(即remappingFunction返回值作为新value)。写一段它的简单应用的代码,并与“同级生”merge()类比加深理解:

1
2
3
4
5
6
7
8
9
10
11
HashMap map = new HashMap();
map.put("a", "c");
map.put("b", "h");
map.put("c", "e");
map.compute("a", (k, v) -> "C") ;
map.merge("b", "h", (k, v) -> "H") ;
map.compute("d", (k, v) -> "D") ;
map.merge("c", "e", (k, v) -> null) ;
System.out.println(map.toString());
// 输出结果为:{a=C, b=H, d=D}

下面用一张表来总结源码最后的判断对应的操作:
image

☞ BiFunction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* Represents a function that accepts two arguments and produces a result.
* This is the two-arity specialization of {@link Function}.
*
* <p>This is a <a href="package-summary.html">functional interface</a>
* whose functional method is {@link #apply(Object, Object)}.
*
* @param <T> the type of the first argument to the function
* @param <U> the type of the second argument to the function
* @param <R> the type of the result of the function
*
* @see Function
* @since 1.8
*/
@FunctionalInterface
public interface BiFunction<T, U, R> {
/**
* Applies this function to the given arguments.
*
* @param t the first function argument
* @param u the second function argument
* @return the function result
*/
R apply(T t, U u);
/**
* Returns a composed function that first applies this function to
* its input, and then applies the {@code after} function to the result.
* If evaluation of either function throws an exception, it is relayed to
* the caller of the composed function.
*
* @param <V> the type of output of the {@code after} function, and of the
* composed function
* @param after the function to apply after this function is applied
* @return a composed function that first applies this function and then
* applies the {@code after} function
* @throws NullPointerException if after is null
*/
default <V> BiFunction<T, U, V> andThen(Function<? super R, ? extends V> after) {
Objects.requireNonNull(after);
return (T t, U u) -> after.apply(apply(t, u));
}
}

是的,这也J8新增的梗。当我第一眼看到逼函数(BiFunction)的时候就原地炸了。实际上,“Bi”乃binary缩写,即“二元函数”之意(类似“1+1=2”)。这类接口称为“函数式接口”,可以看出,它的方法有方法体。且以“default”修饰符修饰,不影响接口的实现类,算是一种向下兼容吧。

☞ @FunctionalInterface

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* An informative annotation type used to indicate that an interface
* type declaration is intended to be a <i>functional interface</i> as
* defined by the Java Language Specification.
*
* Conceptually, a functional interface has exactly one abstract
* method. Since {@linkplain java.lang.reflect.Method#isDefault()
* default methods} have an implementation, they are not abstract. If
* an interface declares an abstract method overriding one of the
* public methods of {@code java.lang.Object}, that also does
* <em>not</em> count toward the interface's abstract method count
* since any implementation of the interface will have an
* implementation from {@code java.lang.Object} or elsewhere.
*
* <p>Note that instances of functional interfaces can be created with
* lambda expressions, method references, or constructor references.
*
* <p>If a type is annotated with this annotation type, compilers are
* required to generate an error message unless:
*
* <ul>
* <li> The type is an interface type and not an annotation type, enum, or class.
* <li> The annotated type satisfies the requirements of a functional interface.
* </ul>
*
* <p>However, the compiler will treat any interface meeting the
* definition of a functional interface as a functional interface
* regardless of whether or not a {@code FunctionalInterface}
* annotation is present on the interface declaration.
*
* @jls 4.3.2. The Class Object
* @jls 9.8 Functional Interfaces
* @jls 9.4.3 Interface Method Body
* @since 1.8
*/
@Documented
@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.TYPE)
public @interface FunctionalInterface {}

“@FunctionalInterface”并非必须,就像javascript中的“use strict”,使得编译器能检查该接口是否存在语法错误。此外,从注释还可以看出:

函数接口仅有一个抽象方法;

default方法、Object的重载方法(、静态方法)非抽象方法;

☞ afterNodeAccess()

1
2
3
4
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

从注释可以看到这是为LinkedHashMap留的后路,不过HashMap存取操作中经常发现他们的身影,即使实现为空。。

☞ computeIfAbsent()/computeIfPresent()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
@Override
public V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
if (mappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Node<K,V>[] tab; Node<K,V> first; int n, i;
int binCount = 0;
TreeNode<K,V> t = null;
Node<K,V> old = null;
if (size > threshold || (tab = table) == null ||
(n = tab.length) == 0)
n = (tab = resize()).length;
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
V oldValue;
if (old != null && (oldValue = old.value) != null) {
afterNodeAccess(old);
return oldValue;
}
}
V v = mappingFunction.apply(key);
if (v == null) {
return null;
} else if (old != null) {
old.value = v; // old.value null
afterNodeAccess(old);
return v;
}
else 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);
return v;
}
public V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
Node<K,V> e; V oldValue;
int hash = hash(key);
if ((e = getNode(hash, key)) != null &&
(oldValue = e.value) != null) {
V v = remappingFunction.apply(key, oldValue);
if (v != null) {
e.value = v;
afterNodeAccess(e);
return v;
}
else
removeNode(hash, key, null, false, true);
}
return null;
}

computeIfAbsent()与computeIfPresent()可以说是compute()的“子集”。

image

这次的功夫主要花在了学习J8的知识点上,经过前2篇后HashMap本身不再那么可怕。你觉得呢?


更多有意思的内容,欢迎访问笔者小站: rebey.cn


彩蛋

最后分享几个学习Java8过程中看到良心网址(以下链接为网站系列文章之一,希望细心的你举一反三):

Java8初体验(二)Stream语法详解;

Java 8 中的 Streams API 详解;

Java 8 flatMap example;

打赏
手机扫一扫,支持CHE~