【java】HashMap1.8源码详解_hashmap1.8 详解

前言

之前，博主对HashMap1.7的源码进行了详细的讲解，建议先看HashMap1.7源码详解，在一些重要属性的默认设置上，两个版本的HashMap有相同之处，遇到时本篇不再赘述；它们虽有相似之处，但1.8无论在数据结构还是代码细节上都产生了很大的变化，因此，阅读和分析它的源码是必要的。

概要

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
1
2

HashMap继承了AbstractMap抽象类，实现了Map接口，AbstractMap本质上也实现了Map接口，Map接口规范了HashMap的通用操作，这也算是典型的模板设计模式；
HashMap还实现了Cloneable接口，此接口是进行克隆操作的基础，需要强调的是HashMap实现的是浅克隆，在它的clone()方法中使用super.clone()，本质上调用的是Object的clone()；除此之外，HashMap还实现了Serializable接口，这个接口是为对象序列化提供服务的，它可以将对象写进入文件，再通过反序列化将对象读入内存中。

数据结构

HashMap1.8使用的是数组+链表+红黑树的数据结构；红黑树的引入是为了解决结点发生哈希碰撞后，形成一条长链表而造成的索引效率低的问题；在HashMap1.7中，出现这种情况的索引时间复杂度为O(n)，而红黑树可以控制在O(lgn)，关于红黑树的具体讲解，可参看博文红黑树。

由于table数组过于简单，因此不在此列举，将在属性块列出。

Node类 普通结点

与HashMap1.7中的Entry类基本一致

static class Node<K,V> implements Map.Entry<K,V> {
	// 结点哈希值，1.8中加上了final关键字
    final int hash;
    // 结点key
    final K key;
    // 结点value
    V value;
    // 本结点的下一结点，单向链表
    Node<K,V> next;

    	
    // 构造方法
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

	// 替换旧值，oldValue可能是null
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}
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

TreeNode类 树结点

// 继承关系：LinkedHashMap.Entry<K,V> extends HashMap.Node<K,V>
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
	// 红黑树的链接
    TreeNode<K,V> parent;  
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    // 与Node.next形成双向链表
    // 需要说明的是：结点形成红黑树时还保存了另外一条链表，作用后面解释
    TreeNode<K,V> prev;		
    boolean red;
    
    TreeNode(int hash, K key, V val, Node<K,V> next) {
    	// 调用HashMap.Node的构造方法
        super(hash, key, val, next);
    }
    
	... ...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

属性

// 默认的初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 默认的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认的加载因子，0.75f是时间与空间的取平衡结果
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转成红黑树的阈值，在存储数据时，当链表长度 >= 8时，将链表转换成红黑树
// jdk作者根据泊松分布，实际测试出：在loadFactor=0.75时
// 出现一条链上有8个节点的概率为0.00000006；因为转红黑树是代价高昂的
// 所以在极端情况下再转化为树结构是值得的。
static final int TREEIFY_THRESHOLD = 8;

// 红黑树转为链表的阈值，当树结点数 <= 6时，将红黑树转换成链表
static final int UNTREEIFY_THRESHOLD = 6;

// 若数组容量 < 64，即使链表长度达到树化阈值，也只扩容而非树化链表
// 这个比较容易理解，毕竟树化的时间和空间代价是高昂的
// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 保存结点的数组，需要时进行初始化
transient Node<K,V>[] table;

// 保存缓存的entrySet()，而keySet()和values()则使用了AbstractMap的属性
transient Set<Map.Entry<K,V>> entrySet;

// 结点总数（数组+链表+树结点）
transient int size;

// 修改次数：当增加新数据（不代表修改value），删除数据，或者清空时modCount++
// 与ConcurrentModificationException异常有关，博主在Hashmap1.7中对此进行了讲解
transient int modCount;

// 扩容阈值：当size > threshold时，进行扩容
// threshold = table.length * loadFactor
int threshold;

// 加载因子
final float loadFactor;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

构造方法

// 双参构造：容量，加载因子
public HashMap(int initialCapacity, float loadFactor) {
	// 判断是否非法
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // Float.isNaN() 判断是否是数字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    // 这里与1.7有所不同，1.7是直接将initialCapacity赋值给threshold
    // 1.8通过tableSizeFor()计算出合法的capacity
    this.threshold = tableSizeFor(initialCapacity);
}

// 单参构造：容量；调用双参构造，使用默认的加载因子
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 无参构造，只初始化加载因子
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

// 单参构造：map；使用默认的加载因子
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
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

关联的方法

int tableSizeFor(int cap)
此方法模仿了Integer.highestOneBit(int i)，有兴趣请参看Integer.highestOneBit(int i)详解

// 得到合法的容量：大于等于cap的最小2的指数次幂
static final int tableSizeFor(int cap) {
	// 临界情况，当cap为2的指数次幂时，若不减一，结果为 2 * capacity
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 数组容量不能超过规定最大容量
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12

void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)

// 一、table == null 
// 二、在原数组上添加结点
// boolean evict: 此参数在putVal()方法中讲解
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
	// 结点数量
    int s = m.size();
    if (s > 0) {
    	// 数组不存在，需要初始化
        if (table == null) {
        	// 预测大致需要的capacity大小，+1.0F避免ft = 0
        	// +1.0F只有当s / loadFactor = 2的指数次幂时才会扩大2倍
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
                     
            // 在调用本方法之前，一定先调用了构造方法
            // 1、单参(参数是map的不算)、双参构造：
            // 一定执行this.threshold = tableSizeFor(initialCapacity)得到了合法容量		
            // t > threshold : 预测容量大于原合法容量，需要根据预测容量得到新合法容量
            // t < threshold : 预测容量小于原合法容量，不用重新规划容量
            // 2、无参构造，参数为map的单参构造：
            // threshold = 0，而 t >= 1，则t > threshold成立，重新规划容量
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 如果数组不为null，且m的结点数大于扩容阈值，则扩容
        else if (s > threshold)
            resize();
      	
      	// 调用putVal()添加结点，对外的put()方法也是调用它来增加新结点
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}
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

int size()

public int size() {
    return size;
}
1
2
3

核心方法

此模块将解析部分核心方法及其关联方法，顺序为源码中的顺序；程序中出现的链表插入、删除、遍历等细节处理手段，博主不作详细讲解，这些都属于链表中最基本的操作。

get(Object key)

getNode()步骤总结：

• 判断table数组是否初始化过，没有则返回null
• 检查首结点，若key相同，返回该结点
• 判断后面结点，若为树结构，getTreeNode()
• 若为链表，遍历，找到目标结点就返回，未找到返回null
  

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

// 实现了map.get()和相关方法
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; 
    Node<K,V> first, e; 
    int n; 
    K k;
    // table不为null，table.length != 0，数组存在且有效
    if ((tab = table) != null && (n = tab.length) > 0 &&
    	// 简化操作：直接得到下标再得到node
        (first = tab[(n - 1) & hash]) != null) {
        // 总是检查第一个节点；无论是链表还是树，对于第一个结点的检查并无差异
        // 在一定程度上是用代码量挽救检查性能，树中结点的查找代价较大
			// 与1.7一致，相同对象或满足equals()就可以匹配
        if (first.hash == hash &&  
            ((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-while隔离操作，while也可以，只不过会多一次判断
            // while(e != null) {e = e.next}，第一次循环中，e != null没有必要
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}
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

在 first = tab[(n - 1) & hash]) 中，这里直接取得下标，而1.7中单独写了一个方法来求下标，1.8显得更加简洁。对于这里的求下标操作，我复制了以前的博文，以免对没有看HashMap1.7讲解博文的读者造成困惑，看过的可以跳过。

// HashMap1.7中求数组下标的方法
static int indexFor(int h, int length) {
    return h & (length-1);
}
1
2
3
4

这个方法虽然只有一条语句，但关联到的东西却非常多。比如读者肯定好奇为什么默认的容量是1 << 4 = 16，为什么调用roundUpToPowerOf2(toSize)方法？这就要说到Hashmap最关键的地方，通过哈希值来确定数组下标，因为hash值的散列度是非常大的，而数组的容量是有限的，所以如何确定下标就非常关键。
编程者最容易想到的方法就是取模运算：hash % length
hash是一个int类型的数值，假设length为默认容量16，那么 hash % length 得到的数组范围就是 0 - 15，符合数组存储原则。
然而jdk作者的选择是位运算：hash & (length - 1)
下面通过例子来验证一下：假设length=16，则length-1=15，二进制表示 0000 1111

一、hash = 1001 1010 0101 0111
 	hash & length - 1 
 =	1001 1010 0101 0111
 &			  0000 1111
 = 	0000 0111 = 7
 
一、hash = 1001 1010 0101 0000
 	hash & length - 1 
 =	1001 1010 0101 0000
 &			  0000 1111
 = 	0000 0000 = 0
 
三、hash = 1111 1111 0101 1111
 	hash & length - 1 
 =	1111 1111 0101 1111
 &			  0000 1111
 = 	0000 1111 = 15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

从上面验证的结论来看，取得的下标依然在0-15之间，且位运算的运算速度比取模运算快。而带来的影响就是capacity必须是2的指数次幂（二进制数每一位的权重都是2的指数次幂），如果不是，那么capacity-1的二进制结果中的低位就不全为1，就会增加哈希碰撞的概率；这个很好理解，若低位中的某一位是0，那么hash值对应的那一位无论取1还是取0，与运算的结果都将是0，则取到相同下标的可能性就变大了。

put(K key, V value)

putVal()步骤总结：

• table若未初始化，则先初始化table数组
• 假设目标下标为index，判断table[index]是否为空，若为空，直接添加结点
• 不为空，检查第一个结点，key相同则保存该对象
• 判断后面结点，若为树结构，putTreeVal()
• 若为链表，找到key相同结点保存该对象，不存在则尾追新结点
• 链表尾追结点后，可能需要将链表转红黑树
• 若保存的对象不为null，则可能需要替换oldValue
• 新加结点后都要判断是否需要对数组进行扩容
  

// 若容器中没有此映射，则添加；有，则替换旧值，并返回旧值
public V put(K key, V value) {
	//	参数false：改变现有值；参数true：不处于创建模式
    return putVal(hash(key), key, value, false, true);
}

// @param onlyIfAbsent 如果为true，则不改变现有值（不替换旧值）
// @param evict 此参数传递给了空方法，用于LinkedHashMap
// 实现了map.put()及相关方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; 
    Node<K,V> p; 
    int n, i;
    
    // 懒加载模式，判断数组是否初始化，没有则先初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果该下标中没有任何结点，则直接创建结点
    if ((p = tab[i = (n - 1) & hash]) == null)
    		// null表示本结点的下一结点为空，本结点即为链表末节点
        tab[i] = newNode(hash, key, value, null);
    // 该下标中有结点，可能是链表，也可能是树
    else {
        Node<K,V> e;
        K k;
        // 常规检查第一个，原因与getNode()方法一致
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 直接复制引用，在最后进行oldValue替换
            e = p;
        // 红黑树
        else if (p instanceof TreeNode)
        	// 1、存在oldTreeNode，直接返回该结点
        	// 2、不存在oldTreeNode，将其加在树上
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        	// 遍历链表
            for (int binCount = 0; ; ++binCount) {
            	// 在末节点判断链表的长度才有意义
                if ((e = p.next) == null) {
                	// p存在的意义：链表基本操作，保存最末尾节点，用来尾加
                	// 尾加法增加结点
                    p.next = newNode(hash, key, value, null);
                    // TREEIFY_THRESHOLD = 8，当节点个数 >= 8时转为树结构
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到了key对应的结点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 存在旧的映射关系
        if (e != null) {
            V oldValue = e.value;
            // onlyIfAbsent控制是否改变现有值，对于1.7是加强
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 空方法
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 扩容条件对于1.7有所降低
    // 1.7的条件：(size >= threshold) && (null != table[bucketIndex])
    if (++size > threshold)
        resize();
    // 空方法
    afterNodeInsertion(evict);
    return null;
}

// 虽转化为了树，但还保留了链表的关系，为了查询value
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 如果程序没有问题，那么tab永远不等于null
    // 如果数组较小，可以通过扩容的方式来减少哈希碰撞，不必转为树
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 得到目标下标的链表，准备转树
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
        	// 仅仅是调用了Node的构造方法，生成一个个独立的节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            // 这里将独立的节点变成链表
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                // next成员来自HashMap.Node，继承关系
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
        	// 真正转为树的方法
            hd.treeify(tab);
    }
}

public void putAll(Map<? extends K, ? extends V> m) {
    putMapEntries(m, true);
}
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

在HashMap1.7中，链表增加结点的方法是前插法，虽然前插法会提高插入的效率，但会造成严重的死循环问题，在博主HashMap1.7博文中有详细的说明；所以1.8采用的是尾加法，但同样避免不了出现多线程安全性问题，下面将进行讲解。

resize() - 多线程的数据丢失问题

// 初始化table，或者扩容，依然是尾加法增加链表
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;

	// 初始化情况：
	// 1、用户设置了capacity，则oldThr > 0成立
	// 2、用户没有设置capacity(无参构造)，则最后的else成立
	// 非初始化情况：
	// oldCap > 0 成立，newCap必然扩容一倍，而threshold不一定会变
    if (oldCap > 0) {
   		// 超过最大容量则更改临界值，大约是最大容量的两倍，2^31-1 = 2*(2^30)
   		// 如果oldCap >= MAXIMUM_CAPACITY不成立，那么oldCap最大只能是2^29
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // choice 1 ：扩容一倍后仍小于最大值 && oldCap >= 16，不一定成立
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 如果条件成立，因为线性关系，只用将扩容阈值扩大一倍即可
            newThr = oldThr << 1;
    }
    else if (oldThr > 0)
   		// choice 2 ：使用双参或单参构造方法(不包括参数为map的构造方法)的结果
   		// 初始容量设置为阈值，因为在双参构造方法中将容量赋值给了threshold
   		// this.threshold = tableSizeFor(initialCapacity);
        newCap = oldThr;
        
    // oldCap == 0 && oldThr == 0
    else { 
   		// 使用的是无参构造方法或参数为map的单参构造方法
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // choice 1 不成立或choice 2 成立时，newThr == 0 成立
    if (newThr == 0) {
   		// ft是threshold
        float ft = (float)newCap * loadFactor;
        // 临界情况：newCap > MAXIMUM_CAPACITY && threshold < MAXIMUM_CAPACITY
        // 这里newCap < MAXIMUM_CAPACITY若不成立，那newCap = MAXIMUM_CAPACITY必成立
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 由于capacity设定的规则，这里newCap最大为MAXIMUM_CAPACITY，所以不用考虑合法问题
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
    	//遍历数组下标，在hash表的存储规则下，结点存储的下标并不连续
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
           		// 线程1在if判断之前挂起，线程2到这里，保留了独有的oldTab[j]
           		// 线程1继续执行，发现oldTab[j]为空，跳过此下标的所有元素
           		// 那么原table数组中的数据被分成了两部分，而两个线程有各自的newTab
           		// 都会覆盖table成员，无论两个线程覆盖table的前后顺序，总有一组数据丢失
           		// 这里造成了严重的数据丢失，情况严重的话，可能只会保留原来的一条链或一棵树
           		// 让人不由得觉得这是个神来之笔，为什么要置空oldTab[j]？
           		// e = oldTab[j]语句已经保留链表或树的头结点的引用了，gc回收不了这一块结点集
           		// 而在方法运行结束后，gc会自动回收原来的table引用，所以这不是多此一举吗？
           		// 如果这里不置空，那每个线程转移的都一样，虽然会降低性能，但在这种情况下不会丢失
                oldTab[j] = null;
                // 先检查第一个，提高效率
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
               		// 拆散原树形结构，形成新树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 此结点集是链表，下面可能会将原来的一条链变为两条链
                // 至于为什么可能是两条链，请读者继续向下看
                else {
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 此处的do-while与getNode()方法中的一致
                    do {
                        next = e.next;                        
                        // 原下标形成新链
                        if ((e.hash & oldCap) == 0) {
                        	// 第一个节点时，loTail == null
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 另一下标形成新链
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                	// oldIndex下有链，交给数组
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // oldIndex + oldCap下有链，交给数组
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

线程安全性问题我已经在代码的注释中做了非常详细的讲解，因此不再赘述。
在HashMap1.7中，在进行扩容后也会将原来的结点分配到新的数组中，在转移过程中会进行rehash，即重哈希、重定位；而1.8中却不是这样的，下面，我们需要仔细地研究一下1.8中的重哈希问题。

情况一：假设某结点的hash值为：0000 0101  扩容前的数组容量为16，即 0001 0000

扩容前，计算下标：
0000 0101 & 0000 1111  = 0000 0101
扩容后，数组容量为32，即 0010 0000
计算下标：
0000 0101 & 0001 1111 = 0000 0101

结论：与原下标相同，即，newIndex = oldIndex

情况二：假设某结点的hash值为：0001 0101  扩容前的数组容量为16，即 0001 0000

扩容前，计算下标：
0001 0101 & 0000 1111  = 0000 0101
扩容后，数组容量为32，即 0010 0000
计算下标：
0000 0101 & 0001 1111 = 0001 0101

结论：与原下标不同，刚好增加了 0001 0000
即，newIndex = oldIndex + oldCap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

通过上面的验证，可以得出结论，rehash的结果无非是两种，而形成这两种的条件就是，e.hash & oldCap 是否为0，如上例所示，oldCap = 0001 0000，则e.hash & oldCap就是判断hash值得对应第四位是否为1，若为1，则结果为1，若结果为1，则newIndex = oldIndex + oldCap，不为1，则newIndex = oldIndex，所以rehash的结果只能是这两种情况，可以通过这种简单的方式实现1.7中rehash相同的功能，提高了效率。

remove(Object key)

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
 
// @param matchValue 如果为true，则仅在值相等时删除，键值对都必须相等
// @param movable 如果为false，则在删除时不移动其他节点
// 实现了map.remove和相关方法
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;
    // table存在且有效, 且当前下标存有有效节点
    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 为上一节点
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // matchValue = false时，不用进行value的对比
        // 判断value是否相同是1.8新增加的功能，而且可以开闭
        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)
            	// 满足 node == p 的条件是：第一个节点即为目标节点
                tab[index] = node.next;
            else
            	// 不为第一个节点，则将上一节点与后一节点相链接
                p.next = node.next;
            // 修改数加一
            ++modCount;
            --size;
            // 空方法
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        // 遍历数组，将所有下标元素置为null
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}
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

HashMap1.7中调用Arrays.fill(tab, null)来实现clear()方法；但两个实质其实相同，都是暴力清空，靠gc来回收；

// 1.7中调用：Arrays.fill(table, null);

public static void fill(Object[] a, Object val) {
	for (int i = 0, len = a.length; i < len; i++) {
		a[i] = val;
	}
}
1
2
3
4
5
6
7

containsValue(Object value)

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
    	// 外层循环，遍历数组
        for (int i = 0; i < tab.length; ++i) {
       		// 内层循环，遍历链表，虽为树，但也保留了一个链表的关系，看treeifyBin()
       		// 树结点的查询是以key作为查找的依据，可以优化性能，get()方法使用树自带查询方法
       		// 但查找值，无法优化，必须遍历全部节点，因此直接使用for循环
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这个方法其实并没有什么特殊的，将它列举出来，只是想解释一下为什么树结构还要保留一个隐式的链表关系，当然在下面的方法中也有所体现。

forEach(BiConsumer<? super K, ? super V> action)

public final void forEach(Consumer<? super K> action) {
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException();
    // table存在结点
    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
                action.accept(e.key);
        }
        // 这里是遍历完成后报出的异常，因此当改变了原table后
        // 上面的遍历结果可能也会变，但下面就会报异常
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

使用过for-each的都知道，这是java提供的一种遍历集合的语法。在HashMap1.8中提供了一种显示的forEach()，下面将演示它的使用，代码比较简单，不作解释。

new HashMap<String, String>().keySet().forEach(new Consumer<String>() {
	@Override
	public void accept(String t) {
		 // TODO
	}
});
1
2
3
4
5
6

在keySet()、values()、entrySet()对应的KeySet、Values、EntrySet类中也提供了显示的forEach()方法，但它们的其它方法都基本和1.7中的一致，所以就不再讲解了。

总结

HashMap是一个非常强大的工具，但也有很多缺陷，其中最严重的就是多线程的安全性无法保证，所以它最好在单线程的系统中使用。
本篇博文对HashMap1.8的核心进行了讲解，由于篇幅原因，其它一些不重要的方法，就不进行列举了，如果读者想要完整的HashMap1.8的注释分析，可以在评论处留言。