释放双眼，带上耳机，听听看~！
一、HashMap成员变量
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
2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
3 //HashMap最大长度2的30次幂
4 static final int MAXIMUM_CAPACITY = 1 << 30;
5 //默认加载因子
6 static final float DEFAULT_LOAD_FACTOR = 0.75f;
7 //链表最大长度，大于8会转红黑树，
8 static final int TREEIFY_THRESHOLD = 8;
9 //红黑树最小节点数，小于6转链表
10 static final int UNTREEIFY_THRESHOLD = 6;
11 //转红黑树的最小table容量，table容量小于64，链表长度大于8，会执行扩容，并不会转红黑树
12 static final int MIN_TREEIFY_CAPACITY = 64;
13 //存放Node的数组
14 transient Node<K,V>[] table;
15 //将数据转换成set存储，用于迭代
16 transient Set<Map.Entry<K,V>> entrySet;
17 //实际存储的数量，则HashMap的size()方法，实际返回的就是这个值，isEmpty()也是判断该值是否为0
18 transient int size;
19 //hashmap结构被改变的次数，fail-fast机制(遍历时候修改数据，抛ConcurrentModificationException)
20 transient int modCount;
21 //HashMap的扩容阈值，在HashMap中存储的Node键值对超过这个数量时，自动扩容容量为原来的二倍
22 int threshold;
23 //HashMap的负加载因子，可计算出当前table长度下的扩容阈值：threshold = loadFactor * table.length
24 final float loadFactor;
25
26
transient 关键字：transient关键字只能修饰变量，而不能修饰方法和类，被其修饰的变量不会被序列化。换言之，将不需要序列化的变量前添加关键字transient，序列化对象的时候，这个属性就不会被序列化。值得注意的是静态变量不管是否被transient修饰，均不能被序列化。
二、HashMap流程图
三、HashMap的构造方法
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
2 public HashMap(int initialCapacity, float loadFactor) {
3 if (initialCapacity < 0)
4 throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
5 //初始化容量不得大于最大容量2的30次幂
6 if (initialCapacity > MAXIMUM_CAPACITY)
7 initialCapacity = MAXIMUM_CAPACITY;
8 if (loadFactor <= 0 || Float.isNaN(loadFactor))
9 throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
10 //使用指定加载因子
11 this.loadFactor = loadFactor;
12 //处理指定的初始化容量（不管输入多少，取该数最接近的2的次幂，下面有该方法解释）
13 this.threshold = tableSizeFor(initialCapacity);
14 }
15
16 //使用指定的初始化容量initial capacity和默认加载因子DEFAULT_LOAD_FACTOR（0.75）构造一个空HashMap
17 public HashMap(int initialCapacity) {
18 this(initialCapacity, DEFAULT_LOAD_FACTOR);
19 }
20
21 //使用指定的初始化容量（16）和默认加载因子DEFAULT_LOAD_FACTOR（0.75）构造一个空HashMap
22 public HashMap() {
23 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
24 }
25
26 // 使用指定Map m构造新的HashMap。默认加载因子DEFAULT_LOAD_FACTOR（0.75，初始化容量随m.size变化
27 public HashMap(Map<? extends K, ? extends V> m) {
28 this.loadFactor = DEFAULT_LOAD_FACTOR;
29 putMapEntries(m, false);
30 }
31
32
四、HashMap的put()，putVal()方法
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
2 //倒数第二个参数false：表示允许旧值替换
3 //最后一个参数true：表示HashMap不处于创建模式
4 public V put(K key, V value) {
5 return putVal(hash(key), key, value, false, true);
6 }
7 /**
8 * @param hash 指定参数key的哈希值
9 * *@param key 指定参数key
10 * @param value 指定参数value
11 * @param onlyIfAbsent 如果为true，即使指定参数key在map中已经存在，也不会替换value
12 * @param evict 如果为false，数组table在创建模式中
13 * @return 如果value被替换，则返回旧的value，否则返回null。当然，可能key对应的value就是null。
14 */
15 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
16 Node<K,V>[] tab; Node<K,V> p; int n, i;
17 //此处初始化hashmap
18 if ((tab = table) == null || (n = tab.length) == 0)
19 n = (tab = resize()).length;
20 //该下标不存在值 新增新节点
21 if ((p = tab[i = (n - 1) & hash]) == null)
22 tab[i] = newNode(hash, key, value, null);
23 else {
24 Node<K,V> e; K k;
25 //当前值与该下标中第一个值匹配，则记录当前下标中的值e（后面会执行新旧value的替换）
26 if (p.hash == hash &&
27 ((k = p.key) == key || (key != null && key.equals(k))))
28 e = p;
29 //为树结构，走红黑树查询返回匹配的TreeNode赋值给e，TreeNode继承Node，如果红黑树中未匹配到key则新增树节点，返回null赋值给e
30 else if (p instanceof TreeNode)
31 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
32 //链表中匹配到Key则返回Node赋值给e，未匹配到执行新增返回null赋值给e
33 else {
34 for (int binCount = 0; ; ++binCount) {
35 // 遍历到链表尾部，执行新增，此时e为null。注意该if条件执行完会将p.next赋值给e
36 if ((e = p.next) == null) {
37 p.next = newNode(hash, key, value, null);
38 //检查链表长度是否达到阈值8，达到则转为红黑树
39 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
40 treeifyBin(tab, hash);
41 break;
42 }
43 //
44 if (e.hash == hash &&
45 ((k = e.key) == key || (key != null && key.equals(k))))
46 //新数据与链表数据匹配成功，直接break，因为上面代码已经将匹配成功节点赋值给了e。
47 break;
48 // p = e将当前节点赋值给p,与上面e = p.next联合，构成了一个循环，建议多读几遍代码
49 p = e;
50 }
51 }
52 //如果存在原数据key与新数据匹配成功，e则不为null
53 if (e != null) { // existing mapping for key
54 V oldValue = e.value;
55 //匹配成功没有直接做value替换，只有onlyIfAbsent 为false，才替换旧值
56 if (!onlyIfAbsent || oldValue == null)
57 e.value = value;
58 afterNodeAccess(e);
59 //只有存在匹配成功的key才返回旧值
60 return oldValue;
61 }
62 }
63 //hashMap的结构改变次数加1，遍历会用到改变量
64 ++modCount;
65 //键值对超过阀值，进行扩容
66 if (++size > threshold)
67 resize();
68 //该方法可以忽略，是为继承HashMap的LinkedHashMap类服务的。保证LinkedHashMap的有序性，可能以后会写一篇LinkedHashMap的源码讲解
69 afterNodeInsertion(evict);
70 //新节点做的插入，返回null
71 return null;
72 }
73
74
有不懂，评论区留言，下班写的，时间比较仓促！
五、HashMap的hash()与tab[i = (n – 1) & hash]的取下标运算
5.1源码讲解
2
3
4
5
6
2 int h;
3 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4 }
5
6
1.上面为hash()方法，将key=null的hash值直接置为了0，putVal方法没有对key=null的数据专门处理，这点与jdk7不同，因为key=null的数据在计算hash时已经做了处理，后面计算下标“与”运算时key=null的下标始终为0。
2.非null的key计算hash时，做了(h=hashCode() )^ (h >>> 16)运算，将hashCode低16位与其高16位（int：32位）做了异或(相同为0，不同为1)运算，加大低位的随机性,加大了hash的随机性，减少了碰撞。
5.2为何哈希 table 的大小控制为 2 的次幂数？
tab[i = (n – 1) & hash]，其中n是table的长度也就是Node[]的长度，(n – 1) & hash为下标，为了使下标尽量的分散均匀，需要hash值对table长度做取模运算也就是hash % n,但是代码并不是这么写的。
原因1.当哈希 table 的大小控制为 2 的次幂数时满足，(n – 1) & hash = hash % n，两者等价不等效，“与”运算效率更高。取模运算降低发生碰撞的概率，使散列更均匀，实验得知，可以自己动手试试。
原因2.table 长度为 2 的次幂，那么(length-1)的二进制最后一位一定是 1，在对 hash 值做“与”运算时，最后一位就可能为 1，也可能为 0，换句话说，取模的结果既有偶数，又有奇数。设想若(length-1)为偶数，那么“与”运算后的值只能是 0，奇数下标的 bucket 就永远散列不到，会浪费一半的空间。
原因3.扩容在重新计算链表所处于桶的下标时，用了一个计算：(e.hash & oldCap) == 0表示该节点还在原下标，此计算要求oldCap二进制格式低位为0，也就是oldCap需要为2次幂。
六、HashMap的resize()方法
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
2 * 对table进行初始化或者扩容。
3 * 如果table为null，则对table进行初始化
4 * 如果对table扩容，因为每次扩容都是翻倍，与原来计算（n-1）&hash的结果相比，节点要么就在原来的位置，要么就被分配到“原位置+旧容量”这个位置
5 * resize的步骤总结为:
6 * 1.计算扩容后的容量，临界值。
7 * 2.将hashMap的临界值修改为扩容后的临界值
8
9 * 3.根据扩容后的容量新建数组，然后将hashMap的table的引用指向新数组。
10 * 4.将旧数组的元素复制到table中。
11 *
12 * @return the table
13 */
14 final Node<K,V>[] resize() {
15 Node<K,V>[] oldTab = table;
16 int oldCap = (oldTab == null) ? 0 : oldTab.length;
17 int oldThr = threshold;
18 int newCap, newThr = 0;
19 //第一个if条件处理的是已经初始化过的table
20 if (oldCap > 0) {
21 if (oldCap >= MAXIMUM_CAPACITY) {
22 threshold = Integer.MAX_VALUE;
23 return oldTab;
24 }
25 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
26 oldCap >= DEFAULT_INITIAL_CAPACITY)
27 newThr = oldThr << 1; // double threshold
28 }
29 //第二个if处理的是未经过初始化的table,给定初始容量的table
30 else if (oldThr > 0) // initial capacity was placed in threshold
31 newCap = oldThr;
32 //第三个if处理的是未经过初始化的table,且未给定初始容量
33 else { // zero initial threshold signifies using defaults
34 newCap = DEFAULT_INITIAL_CAPACITY;
35 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
36 }
37 //只有上面第二个if条件满足
38 if (newThr == 0) {
39 float ft = (float)newCap * loadFactor;
40 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
41 (int)ft : Integer.MAX_VALUE);
42 }
43 threshold = newThr;
44 //@SuppressWarnings该注解用于消除警告
45 @SuppressWarnings({"rawtypes","unchecked"})
46 //创建新table,赋值新的初始化容量
47 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
48
49 table = newTab;
50 //如果旧table不为空，将旧table中的元素复制到新的table中
51 if (oldTab != null) {
52 //遍历旧哈希表的每个桶，将旧哈希表中的桶复制到新的哈希表中
53 for (int j = 0; j < oldCap; ++j) {
54 Node<K,V> e;
55 //如果桶中存在数据则处理，否则过
56 if ((e = oldTab[j]) != null) {
57 oldTab[j] = null;
58 //桶中只有一个节点 直接再次执行新增节点
59 if (e.next == null)
60 newTab[e.hash & (newCap - 1)] = e;
61 //桶中数据结构为红黑树
62 else if (e instanceof TreeNode)
63 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
64 //桶中数据结构是链表 讲解一下 这个代码挺有意思
65 else { // preserve order
66 //loHead 高位链表头结点 loTail 高位链表尾结点
67 Node<K,V> loHead = null, loTail = null;
68 //hiHead 低位链表头结点 hiTail 低位链表尾结点
69 Node<K,V> hiHead = null, hiTail = null;
70 Node<K,V> next;
71 do {
72 //下面代码 配合e = next实现循环
73 next = e.next;
74 //oldCap与newCap-1最高位一致都是1（无补位情况下），而newCap-1比oldCap-1多一个高位1，可能会影响e.hash & length-1值，如果e.hash在newCap-1最高位位置为0则不影响值，否则影响，而oldCap是2次幂二进制表示最高位1其他位0（无补位情况下），所以与e.hash & oldCap是否为0等效
75 if ((e.hash & oldCap) == 0) {
76 //该情况下容量扩容后不影响下标，计算试一下就知道e.hash & oldCap-1 = e.hash & newCap-1
77 if (loTail == null)
78 //e的引用给loHead
79 loHead = e;
80 else
81 //修改loTail引用所指向的对象，也就是修改loHead引用所指向的对象
82 loTail.next = e;
83 //e的引用给loTail
84 loTail = e;
85 }
86 else {
87 //该情况下容量扩容后影响下标，计算试一下就知道e.hash & newCap-1 = (e.hash & oldCap-1)+oldCap 扩容后newCap-1多的最高位1也就是oldCap
88 if (hiTail == null)
89 hiHead = e;
90 else
91 hiTail.next = e;
92 hiTail = e;
93 }
94 } while ((e = next) != null);
95 if (loTail != null) {
96 //尾节点指向null
97 loTail.next = null;
98 //低位链表还在原位置
99 newTab[j] = loHead;
100 }
101 if (hiTail != null) {
102 hiTail.next = null;
103 //高位链表下标位置发生变化
104 newTab[j + oldCap] = hiHead;
105 }
106 }
107 }
108 }
109 }
110 //返回扩容后Node数组
111 return newTab;
112 }
113
114
七、HashMap的tableSizeFor()方法,保证容量永远为2次幂
扩容时候是位移运算保证了容量为2次幂，
但是初始化hashMap指定容量时怎么保证的呢？
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2 if (initialCapacity < 0)
3 throw new IllegalArgumentException("Illegal initial capacity: " +
4 initialCapacity);
5 if (initialCapacity > MAXIMUM_CAPACITY)
6 initialCapacity = MAXIMUM_CAPACITY;
7 if (loadFactor <= 0 || Float.isNaN(loadFactor))
8 throw new IllegalArgumentException("Illegal load factor: " +
9 loadFactor);
10 this.loadFactor = loadFactor;
11 //tableSizeFor处理了用户的初始化容量
12 this.threshold = tableSizeFor(initialCapacity);
13 }
14
15
以上代码可见，走了tableSizeFor()方法，看一下源码:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2static final int tableSizeFor(int cap) {
3 //此处减1是因为当cap本身为2次幂时，最终返回的是cap不是cap*2
4 int n = cap - 1;
5 //能确定n的最高位为1（除去补位），n>>>1将高位1左移1位，n与n>>>1做或运算，则高位，次高位为1
6 n |= n >>> 1;
7 n |= n >>> 2;
8 n |= n >>> 4;
9 n |= n >>> 8;
10 //处理到此处则将n的所有位数都变为1（除去补位），最后一位为1，也就导致此处一定是奇数
11 n |= n >>> 16;
12 //n+1处理将奇数调整为2次幂
13 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
14 }
15
16
七、HashMap的get()，getNode()方
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
2 * 返回指定的key映射的value，如果value为null，则返回null
3 * get可以分为三个步骤：
4 * 1.通过hash(Object key)方法计算key的哈希值hash。
5 * 2.通过getNode( int hash, Object key)方法获取node。
6 * 3.如果node为null，返回null，否则返回node.value。
7 */
8 public V get(Object key) {
9 Node<K,V> e;
10 return (e = getNode(hash(key), key)) == null ? null : e.value;
11 }
12
13 /**
14 * 根据key的哈希值和key获取对应的节点
15 * getNode可分为以下几个步骤：
16 * 1.如果哈希表为空，或key对应的桶为空，返回null
17 * 2.如果桶中的第一个节点就和指定参数hash和key匹配上了，返回这个节点。
18 * 3.如果桶中的第一个节点没有匹配上，而且有后续节点
19 * 3.1如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点
20 * 3.2如果当前的桶不采用红黑树，即桶中节点结构为链式结构，遍历链表，直到key匹配
21 * 4.找到节点返回，否则返回null。
22 */
23 final Node<K,V> getNode(int hash, Object key) {
24 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
25 //table不为空执行逻辑，否则返回null
26 if ((tab = table) != null && (n = tab.length) > 0 &&
27 (first = tab[(n - 1) & hash]) != null) {
28 //匹配第一个节点，返回
29 if (first.hash == hash && // always check first node
30 ((k = first.key) == key || (key != null && key.equals(k))))
31 return first;
32 //如果存在第二个节点
33 if ((e = first.next) != null) {
34 //桶采用了红黑树结构
35 if (first instanceof TreeNode)
36 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
37 //桶采用了链表结构，循环查找
38 do {
39 if (e.hash == hash &&
40 ((k = e.key) == key || (key != null && key.equals(k))))
41 return e;
42 } while ((e = e.next) != null);
43 }
44 }
45 return null;
46 }
47
48
七、HashMap的remove()，removeNode()，clear()方法
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
2 * 删除hashMap中key映射的node
3 * remove方法的实现可以分为三个步骤：
4 * 1.通过 hash(Object key)方法计算key的哈希值。
5 * 2.通过 removeNode 方法实现功能。
6 * 3.返回被删除的node的value。
7 * @param key 参数key
8 * @return 如果没有映射到node，返回null，否则返回对应的value
9 */
10 public V remove(Object key) {
11 Node<K,V> e;
12 return (e = removeNode(hash(key), key, null, false, true)) == null ?
13 null : e.value;
14 }
15
16 /**
17 * removeNode方法的步骤总结为:
18 * 1.如果数组table为空或key映射到的桶为空，返回null。
19 * 2.如果key映射到的桶上第一个node的就是要删除的node，记录下来。
20 * 3.如果桶内不止一个node，且桶内的结构为红黑树，记录key映射到的node。
21 * 4.桶内的结构不为红黑树，那么桶内的结构就肯定为链表，遍历链表，找到key映射到的node，记录下来。
22 * 5.如果被记录下来的node不为null，删除node，size-1
23 * 6.返回被删除的node。
24 *
25 * @param hash key的哈希值
26 * @param key key的哈希值
27 * @param value 如果 matchValue 为true，则value也作为确定被删除的node的条件之一，否则忽略
28 * @param matchValue 如果为true，则value也作为确定被删除的node的条件之一
29 * @param movable 如果为false，删除node时不会删除其他node
30 * @return 返回被删除的node，如果没有node被删除，则返回null（针对红黑树的删除方法）
31 */
32 final Node<K,V> removeNode(int hash, Object key, Object value,
33 boolean matchValue, boolean movable) {
34 Node<K,V>[] tab; Node<K,V> p; int n, index;
35 if ((tab = table) != null && (n = tab.length) > 0 &&
36 (p = tab[index = (n - 1) & hash]) != null) {
37 Node<K,V> node = null, e; K k; V v;
38 //桶中第一个元素是要删除的元素
39 if (p.hash == hash &&
40 ((k = p.key) == key || (key != null && key.equals(k))))
41 node = p;
42 //桶中第一个元素不是要删除的元素，且桶中存在其他元素
43 else if ((e = p.next) != null) {
44 //桶中元素是红黑树
45 if (p instanceof TreeNode)
46 //红黑树中查询该元素
47 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
48 else {
49 //桶中元素是链表结构
50 do {
51 if (e.hash == hash &&
52 ((k = e.key) == key ||
53 (key != null && key.equals(k)))) {
54 //找到该元素
55 node = e;
56 break;
57 }
58 p = e;
59 } while ((e = e.next) != null);
60 }
61 }
62 //如果得到的node不为null且(matchValue为false||node.value和参数value匹配)
63 if (node != null && (!matchValue || (v = node.value) == value ||
64 (value != null && value.equals(v)))) {
65 if (node instanceof TreeNode)
66 //使用红黑树的删除方法删除node
67 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
68 else if (node == p)
69 //桶中第一个元素就是要删除的node
70 tab[index] = node.next;
71 else
72 //链表方式删除node
73 p.next = node.next;
74 //结构性修改次数加一
75 ++modCount;
76 //哈希表大小减一
77 --size;
78 afterNodeRemoval(node);
79 //返回删除的node
80 return node;
81 }
82 }
83 return null;
84 }
85
86
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2 * 删除map中所有的键值对
3 **/
4 public void clear() {
5 Node<K,V>[] tab;
6 //结构性修改次数加一
7 modCount++;
8 if ((tab = table) != null && size > 0) {
9 //哈希表大小置为0
10 size = 0;
11 //每个桶中的数据置为null
12 for (int i = 0; i < tab.length; ++i)
13 tab[i] = null;
14 }
15 }
16
17
八、HashMap的7种遍历方式以及Iterator类解析
8.1 7种遍历方式
2
3
4
5
6
2 map.put("1","测试1");
3 map.put("2","测试2");
4 map.put("3","测试3");
5
6
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
2 Iterator<Map.Entry<String,Object>> iterator = map.entrySet().iterator();
3 while (iterator.hasNext()){
4 Map.Entry<String,Object> entry = iterator.next();
5 System.out.printf("key= " + entry.getKey() + " and value= " + entry.getValue());
6
7 //遍历方式2 Iterator 迭代器 迭代keySet(只需要操作key时推荐使用，不建议再次走map.get()方法)
8 Iterator<String> keyIterator = map.keySet().iterator();
9 while (keyIterator.hasNext()){
10 String key = keyIterator.next();
11 System.out.printf("key= " + key + " and value= " + map.get(key));
12 }
13
14 //遍历方式3 Iterator 迭代器 迭代values(只操作value使用)
15 Iterator<Object> valueIterator = map.values().iterator();
16 while(valueIterator.hasNext()){
17 Object value = valueIterator.next();
18 System.out.printf("value= " + value);
19 }
20
21 //遍历方式4 遍历entrySet(推荐此方法，数据量大时速度快)
22 for(Map.Entry<String,Object> entry : map.entrySet()){
23 System.out.printf("key= " + entry.getKey() + " and value= " + entry.getValue());
24 }
25
26 //遍历方式5 遍历keySet(只需要操作key时推荐使用，不建议再次走map.get()方法)
27 for(String key : map.keySet()){
28 System.out.printf("key= " + key + " and value= " + map.get(key));
29 }
30
31 //遍历方式6 遍历values(只操作value使用)
32 for (Object value : map.values()) {
33 System.out.println("value= " + value);
34 }
35 //遍历方式7 foreach方法
36 map.forEach((key,value) -> {
37 System.out.printf("key= " + key + " and value= " + value);
38 });
39 }
40
41
上述7种遍历方式其实3种使用迭代器形式，4种foreach,分别是对entry对象遍历，key遍历,value遍历，其实for与foreach是一种语法糖，实际执行的还是iterator。
说到遍历就不得不提，关于在遍历时删除数据抛异常的问题。
8.2 Iteretor解析
看一下关于Iterator的继承关系图：
Iterator接口代码：
2
3
4
5
6
7
8
9
10
11
12
2 E next();
3 default void remove() {
4 throw new UnsupportedOperationException("remove");
5 }
6 default void forEachRemaining(Consumer<? super E> action) {
7 Objects.requireNonNull(action);
8 while (hasNext())
9 action.accept(next());
10 }
11
12
Iterator接口非常简单就4个接口方法，HashMap中新增了一个内部抽象类HashIterator实现了这4个方法，看一下代码：
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
2 Node<K,V> next; // next entry to return
3 Node<K,V> current; // current entry
4 //hashmap结构改动次数
5 int expectedModCount; // for fast-fail
6 int index; // current slot
7
8 HashIterator() {
9 expectedModCount = modCount;
10 Node<K,V>[] t = table;
11 current = next = null;
12 index = 0;
13 if (t != null && size > 0) { // advance to first entry
14 do {} while (index < t.length && (next = t[index++]) == null);
15 }
16 }
17
18 public final boolean hasNext() {
19 return next != null;
20 }
21
22 final Node<K,V> nextNode() {
23 Node<K,V>[] t;
24 Node<K,V> e = next;
25 //判断了一下当前modCount 与expectedModCount是否相等，如果发生了结构化改动执行了hashMap的put,或者remove,modCount将大于expectedModCount
26 //修改次数的一致性校验，防止遍历时有并发的一致性校验。
27 if (modCount != expectedModCount)
28 throw new ConcurrentModificationException();
29 if (e == null)
30 throw new NoSuchElementException();
31 if ((next = (current = e).next) == null && (t = table) != null) {
32 do {} while (index < t.length && (next = t[index++]) == null);
33 }
34 return e;
35 }
36 //这个方法是我们是要关注的 实现了Iterator接口中的删除方法，与HashMapremove()方法不同
37 public final void remove() {
38 Node<K,V> p = current;
39 if (p == null)
40 throw new IllegalStateException();
41 if (modCount != expectedModCount)
42 throw new ConcurrentModificationException();
43 current = null;
44 K key = p.key;
45 //调用HashMap的removeNode方法
46 removeNode(hash(key), key, null, false, false);
47 //该处是重点，在原来的removeNode方法之后，又重新赋值给expectedModCount 所以如果执行的删除是HashIterator的删除将不会在nextNode抛异常，执行的是HashMap的删除会抛异常。
48 expectedModCount = modCount;
49 }
50 }
51
52
现在关于在遍历hashMap时，删除节点为何会抛异常相信都很明了了。因为使用的remove方法不一致，我们在for遍历的时候，使用的删除节点的方法是hashMap提供的remove()方法，该方法没有在删除后更新Iteretor中expectedModCount 变量，导致执行nextNode()方法时抛异常ConcurrentModificationException。Iteretor遍历时删除写法为 iterator.remove()，则不存在该问题。
下面写几个代码示例：
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
2 Map<String,Object> map= new HashMap<String, Object>();
3 map.put("1","测试1");
4 map.put("2","测试2");
5 map.put("3","测试3");
6
7 for(String key : map.keySet()){
8 System.out.printf("key= " + key + " and value= " + map.get(key));
9 //该方法会导致抛异常ConcurrentModificationException
10 map.remove(key);
11 }
12
13 Iterator<String> keyIterator = map.keySet().iterator();
14 while (keyIterator.hasNext()){
15 String key = keyIterator.next();
16 System.out.printf("key= " + key + " and value= " + map.get(key));
17 if(key.equals("1")){
18 //iteretor提供的remove方法不会导致异常
19 keyIterator.remove();
20 }
21 }
22
23 Iterator<Map.Entry<String,Object>> iterator = map.entrySet().iterator();
24 while (iterator.hasNext()){
25 Map.Entry<String,Object> entry = iterator.next();
26 System.out.printf("key= " + entry.getKey() + " and value= " + entry.getValue());
27 if(entry.getKey().equals("1")){
28 //iteretor提供的remove方法不会导致异常
29 iterator.remove();
30 }
31 }
32 }
33
34
另外在遍历时，如果发生节点的新增，也会导致modCount++，抛异常。同一key的value值替换则不会导致modCount++，不抛异常。
8.3 fail-fast 策略
fail-fast就是在系统设计中，当遇到可能会诱导失败的条件时立即上报错误，快速失效系统往往被设计在立即终止正常操作过程，而不是尝试去继续一个可能会存在错误的过程。
再简洁点说，就是尽可能早的发现问题，立即终止当前执行过程，由更高层级的系统来做处理。
在 HashMap 中，我们前面提到的modCount域变量，就是用于实现 hashMap 中的fail-fast。出现这种情况，往往是在非同步的多线程并发操作。
在对 Map 的做迭代(Iterator)操作时，会将modCount域变量赋值给expectedModCount局部变量。在迭代过程中，用于做内容修改次数的一致性校验。若此时有其他线程或本线程的其他操作对此 Map 做了内容修改时，那么就会导致modCount和expectedModCount不一致，立即抛出异常ConcurrentModificationException。
但也要注意一点，能安全删除，并不代表就是多线程安全的，在多线程并发执行时，若都执行上面的操作，因未设置为同步方法，也可能导致modCount与expectedModCount不一致，从而抛异常ConcurrentModificationException。
九、HashMap、HashTable 关系
9.1 共同点和异同点
共同点：
2
3
2
3
区别：
2
3
4
5
6
7
22.HashTable 诞生自 JDK1.0，HashMap 从 JDK1.2 之后才有；
33.HashTable 线程安全，HashMap 线程不安全；
44.初始值和扩容方式不同。HashTable 的初始值为 11，扩容为原大小的2*d+1。容量大小都采用奇数且为素数，且采用取模法，这种方式散列更均匀。但有个缺点就是对素数取模的性能较低（涉及到除法运算），而 HashTable 的长度都是 2 的次幂，设计就较为巧妙，前面章节也提到过，这种方式的取模都是直接做位运算，性能较好。
55.HashMap 的 key、value 都可为 null，且 value 可多次为 null，key 多次为 null 时会覆盖。当 HashTable 的 key、value 都不可为 null，否则直接 NPE(NullPointException)。
6
7
9.2 HashMap 的线程安全
2
3
4
22.put 操作、get 操作、remove 操作、equals 操作，都使用了synchronized关键字修饰。
3
4
这么做是保证了 HashTable 对象的线程安全特性，但同样也带来了问题，突出问题就是效率低下。为何会说它效率低下呢？
2
3
4
5
6
7
2大家不妨想下计时用的沙漏，中间最细的瓶颈处阻挡了上方细沙的下落，同样的道理，当有大量线程要执行get()操作时，也存在此类问题，大量线程必须排队一个个处理。
32.这时可能会有人说，既然get()方法只是获取数据，并没有修改 Map 的结构和数据，不加不就行了吗？不好意思，不加也不行，别的方法都加，就你不加，会有一种场景，
4那就是 A 线程在做 put 或 remove 操作时，B 线程、C 线程此时都可以同时执行 get 操作，可能哈希 table 已经被 A 线程改变了，也会带来问题，因此不加也不行。
53.现在好了，HashMap 线程不安全，HashTable 虽然线程安全，但性能差。解决办法是使用ConcurrentHashMap类，线程安全，操作高效。
6
7
十、HashMap 的线程不安全问题
10.1数据覆盖问题
a、b两个线程同时执行put()操作，且两个线程的key对应一个桶，都是执行的新节点的插入，如果a线程获取到了该桶中的最后一个节点，此时线程时间片用完b线程开始执行，b线程将新节点插入到了旧尾节点的后面。当a线程再次执行的时候，依旧将节点插入到旧节点的尾部，则会覆盖掉b节点的数据，导致数据丢失。
并不只有put()方法会导致数据的覆盖，其他方法像删除、修改同样会存在问题。
10.2扩容时死循环问题
只有 JDK7 及以前的版本会存在死循环现象，在 JDK8 中，resize()方式已经做了调整，使用两队链表，且都是使用的尾插法，及时多线程下，也顶多是从头结点再做一次尾插法，不会造成死循环。而 JDK7 能造成死循环，就是因为 resize()时使用了头插法，将原本的顺序做了反转，才留下了死循环的机会。
JDK7 中的扩容代码片段：
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
2 //新table初始化大小
3 int newCapacity = newTable.length;
4 //for循环原table的每一个节点
5 for (Entry<K,V> e : table) {
6 //当前节点为null停止循环
7 while(null != e) {
8 //将当前节点e的下一节点赋给next
9 Entry<K,V> next = e.next;
10 //重新计算hash
11 if (rehash) {
12 e.hash = null == e.key ? 0 : hash(e.key);
13 }
14 //计算新的下标i
15 int i = indexFor(e.hash, newCapacity);
16 //将e的下一节点指向原先的桶中数据，此时e节点构成一个链表，第一个值是当前while中遍历的节点，每次循环都如此，也就是将原链表进行了倒转
17 e.next = newTable[i];
18 //e放入桶中
19 newTable[i] = e;
20 //将e指向下一节点用于循环
21 e = next;
22 }
23 }
24 }
25
26
十一、HashMap 的线程不安全问题解决方案
11.1 使用Collections.SynchronizedMap()方法，示例代码：
2
3
4
5
6
2...
3// 转为线程安全的 map
4Map<String, Integer> map = Collections.synchronizedMap(testMap);
5
6
其内部实现也很简单，等同于 HashTable，只是对当前传入的 map 对象，新增对象锁（synchronized）：
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
2 private static final long serialVersionUID = 1978198479659022715L;
3
4
5 private final Map<K,V> m; // Backing Map
6 final Object mutex; // Object on which to synchronize
7
8
9 SynchronizedMap(Map<K,V> m) {
10 this.m = Objects.requireNonNull(m);
11 mutex = this;
12 }
13
14
15 SynchronizedMap(Map<K,V> m, Object mutex) {
16 this.m = m;
17 this.mutex = mutex;
18 }
19
20
21 public int size() {
22 synchronized (mutex) {return m.size();}
23 }
24 public boolean isEmpty() {
25 synchronized (mutex) {return m.isEmpty();}
26 }
27 public boolean containsKey(Object key) {
28 synchronized (mutex) {return m.containsKey(key);}
29 }
30 public boolean containsValue(Object value) {
31 synchronized (mutex) {return m.containsValue(value);}
32 }
33 public V get(Object key) {
34 synchronized (mutex) {return m.get(key);}
35 }
36
37
38 public V put(K key, V value) {
39 synchronized (mutex) {return m.put(key, value);}
40 }
41 public V remove(Object key) {
42 synchronized (mutex) {return m.remove(key);}
43 }
44 public void putAll(Map<? extends K, ? extends V> map) {
45 synchronized (mutex) {m.putAll(map);}
46 }
47 public void clear() {
48 synchronized (mutex) {m.clear();}
49 }
50}
51
52
11.2 使用 ConcurrentHashMap
同 HashMap 的使用。
JDK1.5 版本引入，位于并发包java.util.concurrent下。
在 JDK7 版本及以前，ConcurrentHashMap类使用了分段锁的技术（segment + Lock），但在 jdk8 中，也做了较大改动，使用回了 synchronized 修饰符。
2
3
4
5
6
2 cuMap.put("1","测试1");
3 cuMap.put("2","测试2");
4 cuMap.put("3","测试3");
5
6
