作为重要的常用集合，HashMap主要是提供键值对的存取，通过key值可以快速找到对应的value值。Hash表是通过提前设定好的规则计算一个元素的hash值来找到他在数组中的存储位置进行快速定位，假设有一个大小为10的数组，可以设定简单的计算规则为元素转为int后mod 10，由此元素的hash值一定会落在大小为10的数组内。由于不同元素可能会计算出相同的hash值，如例子中1和11都应该在下标为1的位置，这就是hash值的冲突。为了解决这个问题有几种常用的策略：
由此引入一个hash表的属性—— 负载因子 ，负载因子=存储的元素个数/数组大小。很显然，链表法由于冲突位置链无限延长的特点，若不加以限制负载因子可以超过1，负载因子越大代表表中的数据越密集。
HashMap的key和value值都可以为null，get操作时若找不到对应的key值会返回null，具体见下方的例子：
1 public static void main(String args[]){
2 Map<string> map = new HashMap<>();/<string>
3 System.out.println(map.put(null, "123"));//null
4 System.out.println(map.put("456", null));//null
5 System.out.println(map.get("123"));//null
6 System.out.println(map.get
7 System.out.println(map.get("456"));//null
8 System.out.println(map.put(null, "345"));//123
9 System.out.println(map.get(null));//345
10 }
View Code
因为篇幅加难度的原因TreeNode部分的分析下次再说了， 争取不鸽
首先大致翻译下note的主要内容：通常是桶式hash表（链表解决冲突），但是桶过大达到TREEIFY_THRESHOLD值的时候会转为树状TreeNode使得密度过高时的操作可以变得更快。一般对象在树中是按hashcode排序，但是对于实现了Comparable的对象是通过comapreTo来排序。由于TreeNode的大小接近普通node的两倍，当桶变小时会转回线性链表。TreeNode是JDK8引入的红黑树结构，树根通常是hash映射的第一个结点，除了Iterator.remove之外。链表在树化或是分裂时保证结点的遍历顺序是一致的。
1 static class Node<K,V>
2 final int hash;
3 final K key;
4 V value;
5 Node next;
6
7 Node(int hash, K key, V value, Node next) {
8 this.hash = hash;
9 this.key = key;
10 this.value = value;
11 this.next = next;
12 }
13
14 public final K getKey() { return key; }
15 public final V getValue() { return value; }
16 public final String toString() { return key + "=" + value; }
17
18 public final int hashCode() {
19 //key和value的hashCode亦或
20 return Objects.hashCode(key) ^ Objects.hashCode(value);
21 }
22
23 public final V setValue(V newValue) {
24 V oldValue = value;
25 value = newValue;
26 return oldValue;
27 }
28
29 public final boolean equals(Object o) {
30 if (o == this)
31 return true;
32 if (o instanceof Map.Entry) {
33 Map.Entry,?> e = (Map.Entry,?>)o;
34 //key == e.getKey()或者key.equals(e.getKey())
35 if (Objects.equals(key, e.getKey()) &&
36 Objects.equals(value, e.getValue()))
37 return true;
38 }
39 return false;
40 }
41 }
View Code
然后我们来看下Node的结构。一般的箱式结点实现了Map.Entry接口，这是一个key-value键值对，内部有4个属性hash值、K、V以及指向下个结点的引用。hashCode方法是对key和value的hash值求异或，也重写了equals和toString方法。
1 static final int hash(Object key) {
2 int h;
3 //key的hashCode无符号右移16位的值与自己进行异或
4 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
5 }
View Code
对于HashMap自身的hash方法，这样做的目的是避免hash值高位因为表大小而永远不会被用于hash值的计算，使得分布可以更加均匀。
1 static final int tableSizeFor(int cap) {
2 int n = cap - 1;//cap=0001 1000 0001 1111(6175) n = 0001 1000 0001 1110
3 n |= n >>> 1;//n = 0001 1100 0001 1111
4 n |= n >>> 2;//n = 0001 1111 0001 1111
5 n |= n >>> 4;//n = 0001 1111 1111 1111
6 n |= n >>> 8;//n = 0001 1111 1111 1111
7 n |= n >>> 16;//n = 0001 1111 1111 1111(8191)
8 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
9 }
View Code
根据cap返回恰好大于等于该值的2的指数大小。以cap = 6175进行演示，可得n最终为8191即2^13-1，所以返回值为2^13
HashMap内部属性如下：
//hash表的底层数组，大小永远是2的指数
transient Node[] table;
//含有键值对的set高速缓存
transient Set<map.entry>> entrySet;/<map.entry>
//键值对的数量
transient int size;
//HashMap被结构性修改的次数，包括改变键值对个数的操作和rehash等改变内部结构的操作，用于迭代器在线程不安全时快速抛错
transient int modCount;
//达到某个大小后就要改变数组大小，等于capacity * load factor
int threshold;
//负载因子
final float loadFactor;
View Code
构造函数：
1 //参数缺省值为16和0.75
2 public HashMap(int initialCapacity, float loadFactor) {
3 if (initialCapacity < 0)
4 throw new IllegalArgumentException("Illegal initial capacity: " +
5 initialCapacity);
6 //大小最大不能超过1<<30
7 if (initialCapacity > MAXIMUM_CAPACITY)
8 initialCapacity = MAXIMUM_CAPACITY;
9 if (loadFactor <= 0 || Float.isNaN(loadFactor))
10
11 loadFactor);
12 this.loadFactor = loadFactor;
13 //计算恰好大于等于initialCapacity的2的指数作为容量大小
14 this.threshold = tableSizeFor(initialCapacity);
15 }
16 public HashMap(Map extends K, ? extends V> m) {
17 this.loadFactor = DEFAULT_LOAD_FACTOR;
18 putMapEntries(m, false);
19 }
View Code
这里通过一个已有Map来构造时用到了putMapEntries这个方法，先来看下这个方法
1 final void putMapEntries(Map
2 int s = m.size();
3 if (s > 0) {
4 if (table == null) { //当前没有元素
5 float ft = ((float)s / loadFactor) + 1.0F;//计算出m的容量
6 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
7 (int)ft : MAXIMUM_CAPACITY);
8 if (t > threshold)
9 threshold = tableSizeFor(t);
10 }
11 else if (s > threshold)
12 resize();//若m的元素个数超过了threhold则需要扩展表
13 for (Map.Entry extends K, ? extends V> e : m.entrySet()) {
14 K key = e.getKey();
15 V value = e.getValue();
16 putVal(hash(key), key, value, false, evict);//将键值对插入到表中
17 }
18 }
19 }
View Code
可以看到其中调用了用于扩展表的resize和插入键值对的putVal。先看resize方法，这个方法在表大小超过threhold时就会被调用，作用就是扩展数组大小，并将元素复制到数组中，同时对于冲突链表不需要重新计算hash值而是会根据他们的hash值决定要不要复制到数组的高位去
1 final Node[] resize() {
2 Node[] oldTab = table;
3 int oldCap = (oldTab == null) ? 0 : oldTab.length;//当前表中元素个数
4 int oldThr = threshold;
5 int newCap, newThr = 0;
6
7 if (oldCap >= MAXIMUM_CAPACITY) {
8 threshold = Integer.MAX_VALUE;
9 return oldTab;
10 }
11 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
12 oldCap >= DEFAULT_INITIAL_CAPACITY)
13 newThr = oldThr << 1; // 当前表中元素个数大于等于16且小于上限的一半时，threshold加倍
14 }
15 else if (oldThr > 0) // 这个条件成立时说明构造时给了capacity参数，由此计算出了threhold
16 newCap = oldThr;
17 else { //没有任何参数的初始化直接使用默认值
18 newCap = DEFAULT_INITIAL_CAPACITY;
19 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
20 }
21 if (newThr == 0) {//当前表中没有元素的情况
22 float ft = (float)newCap * loadFactor;
23 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
24 (int)ft : Integer.MAX_VALUE);
25 }
26 threshold = newThr;
27 @SuppressWarnings({"rawtypes","unchecked"})
28 Node[] newTab = (Node[])new Node[newCap];
29 table = newTab;
30 if (oldTab != null) {
31 for (int j = 0; j < oldCap; ++j) {
32 Node e;
33 if
34 oldTab[j] = null;
35 if (e.next == null)
36 //e没有后续链表结点时，因为newCap是oldCap的2倍，相当于掩码多了一位，原本hash值的这个多出来的有效位是0或1会决定它在新数组中下标是否变化
37 newTab[e.hash & (newCap - 1)] = e;
38 else if (e instanceof TreeNode)
39 ((TreeNode)e).split(this, newTab, j, oldCap);
40 else { // 存在非树的链表时，保持先后顺序不变
41 Node loHead = null, loTail = null;//低位链表
42 Node hiHead =
43 Node next;
44 do {
45 next = e.next;
46 //这里的运算相当于直接检查hash新增的高位是0还是1，因为oldCap是2的指数所以只有最高位是1其余都是0，旧hash的高位为1时要进行移动
47 if ((e.hash & oldCap) == 0) {
48 if (loTail == null)
49 loHead = e;
50 else
51 loTail.next = e;
52 loTail = e;
53 }
54 else {
55 if (hiTail == null)
56 hiHead = e;
57 else
58 hiTail.next = e;
59 hiTail = e;
60 }
61 } while ((e = next) != null);
62 if (loTail != null) {
63 loTail.next = null;
64 newTab[j] = loHead;//低位链表直接复制到原本所在的位置
65 }
66
67 hiTail.next = null;
68 newTab[j + oldCap] = hiHead;//高位链表的移动规则是原本的下标+oldCap
69 }
70 }
71 }
72 }
73 }
74 return newTab;
75 }
View Code
putVal这个方法是把值存入表中，在多个put类方法中被调用
1 /**
2 * Implements Map.put and related methods
3 *
4 * @param hash hash for key
5 * @param key the key
6 * @param value the value to put
7 * @param onlyIfAbsent if true, don't change existing value为true表示不改变已有值
8 * @param evict if false, the table is in creation mode.为false表示是新建表
9 * @return previous value, or null if none
10 */
11 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
12 boolean evict) {
13 Node[] tab; Node p; int n, i;
14 if ((tab = table) == null || (n = tab.length) == 0)
15 n = (tab = resize()).length;//当前表的table数组为空时需进行扩展
16 if ((p = tab[i = (n - 1) & hash]) ==
17 tab[i] = newNode(hash, key, value, null);//若该下标位置为空，则直接放入数组
18 else {
19 Node e; K k;
20 if (p.hash == hash &&
21 ((k = p.key) == key || (key != null && key.equals(k))))
22 e = p;//检查表上的根结点的hash与key值是否与新增的结点相等，若相等则将修改根结点的value
23 else if (p instanceof TreeNode)
24 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);//已经是树调用树的遍历方法
25 else {
26 for (int
27 if ((e = p.next) == null) {
28 p.next = newNode(hash, key, value, null);//若在箱式链表中没有找到key相等的结点，则新建结点插入到链表末尾
29 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
30 treeifyBin(tab, hash);//若增加该结点后，链表上的结点数超过了TREEIFY_THRESHOLD则转为树，该判断仅在遍历到链表末尾时执行
31 break;
32 }
33 if (e.hash == hash &&
34 ((k = e.key) == key || (key != null && key.equals(k))))//找到了key和hash值相等的结点
35 break;
36 p = e;
37 }
38 }
39
40 V oldValue = e.value;
41 if (!onlyIfAbsent || oldValue == null)
42 e.value = value;
43 afterNodeAccess(e);
44 return oldValue;
45 }
46 }
47 ++modCount;//新增结点时增加modCount
48 if (++size > threshold)
49 resize();//大小超过threshold时要扩容
50 afterNodeInsertion(evict);//这个方法是用于继承了HashMap的LinkedHashMap，用来移除最早放入的结点，保持插入的顺序，为false时代表是新建表不需要进行这个过程
51 return null;
52 }
View Code
treeifyBin将指定hash值对应的位置上的链表替换为树，除非整个表的大小太小时调用resize，(n - 1) & hash等效于hash mod n，只保留hash除以n的余数作为index的值
1 final void treeifyBin(Node[] tab, int hash) {
2 int n, index; Node e;
3 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
4 resize();//表长度小于MIN_TREEIFY_CAPACITY调用resize
5 else if ((e = tab[index = (n - 1) & hash]) != null) {//该hash值对应的index位置上有元素
6 TreeNode hd = null, tl = null;
7 do {
8 TreeNode p = replacementTreeNode(e, null
9 if (tl == null)
10 hd = p;
11 else {
12 p.prev = tl;
13 tl.next = p;
14 }
15 tl = p;
16 } while ((e = e.next) != null);
17 if ((tab[index] = hd) != null)
18 hd.treeify(tab);//树放入index的位置
19 }
20 }
View Code
对于移除操作会调用removeNode，这个方法在多个移除方法中被使用。若移除指定key值成功的结点会返回value值，否则返回null
1 public V remove(Object key) {
2 Node e;
3 return (e = removeNode(hash(key), key, null, false, true)) == null ?
4 null : e.value;
5 }
6 /**
7 * 用于移除操作
8 *
9 * @param hash hash for key
10 * @param key the key
11 * @param value 仅matchValue为true时需要考虑，其他时间不起效
12 * @param matchValue 为true时只移除value相等的
13 * @param movable 为false时不移动其他结点
14 * @return the node, or null if none
15 */
16 final Node removeNode(int hash, Object key, Object value,
17 boolean matchValue, boolean movable) {
18 Node[] tab; Node p; int n, index;
19 if ((tab = table) != null && (n = tab.length) > 0 &&
20 (p = tab[index = (n - 1) & hash]) != null) {//表不为空且hash值对应的index位置存在元素
21 Node node = null, e; K k; V v;
22 if (p.hash == hash &&
23 ((k = p.key) == key || (key !=
24 node = p;
25 else if ((e = p.next) != null) {//根结点key值不相等，存在后续结点
26 if (p instanceof TreeNode)
27 node = ((TreeNode)p).getTreeNode(hash, key);//调用树的遍历方法寻找结点
28 else {
29 do {
30 if (e.hash == hash &&//为箱式链表时遍历链表寻找key相等的点
31 ((k = e.key) == key ||
32 (key != null && key.equals(k)))) {
33 node = e;
34 break;
35 }
36 p = e;
37 } while ((e = e.next) != null);
38 }
39 }
40 if (node != null && (!matchValue || (v = node.value) == value ||
41 (value != null && value.equals(v)))) {//matchValue为true还需要验证value是否相等，否则忽略
42 if (node instanceof TreeNode)
43 ((TreeNode)node).removeTreeNode(this, tab, movable);//移除树结点
44 else if (node == p)
45 tab[index] = node.next;//为箱式链表根结点时，将第二个结点放到数组上
46 else
47 p.next = node.next;//为箱式链表非结点时，修改上下结点间的指针
48 ++modCount;//增加modCount
49 --size;
50 afterNodeRemoval(node);//预留给LinkedHashMap的方法
51 return node;
52 }
53 }
54 return null;
55 }
View Code
clear方法不难理解，将表内所有元素设为null，size变为0，增加modCount
1 public void clear() {
2 Node[] tab;
3 modCount++;
4 if ((tab = table) != null && size > 0) {
5 size
6 for (int i = 0; i < tab.length; ++i)
7 tab[i] = null;
8 }
9 }
View Code
寻找表内有无相等的value，遍历整个链表找到则返回true
1 public boolean containsValue(Object value) {
2 Node[] tab; V v;
3 if ((tab = table) != null && size > 0) {
4 for (int i = 0; i < tab.length; ++i) {//遍历hash表
5 for (Node e = tab[i]; e != null; e = e.next) {//遍历链表
6 if ((v = e.value
7 (value != null && value.equals(v)))
8 return true;
9 }
10 }
11 }
12 return false;
13 }
View Code
key是一个set集合，value是一个collection集合，调用keySet()和values()返回的集合是对HashMap中key和value的直接引用，所以操作会直接反应在HashMap上
1 public Set keySet() {
2 Set ks = keySet;
3 if (ks == null) {
4 ks = new KeySet();
5 keySet = ks;
6 }
7 return ks;
8 }
9
10 final class KeySet extends AbstractSet<K> {
11 public final int size() { return size; }
12 public final void clear
13 public final Iterator iterator() { return new KeyIterator(); }
14 public final boolean contains(Object o) { return containsKey(o); }
15 public final boolean remove(Object key) {
16 return removeNode(hash(key), key, null, false, true) != null;
17 }
18 public final Spliterator spliterator() {
19 return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
20 }
21 public final void forEach(Consumer super K> action) {
22 Node[] tab;
23 if (action == null)
24 throw new NullPointerException();
25 if (size > 0 && (tab = table) !=
26 int mc = modCount;
27 for (int i = 0; i < tab.length; ++i) {
28 for (Node e = tab[i]; e != null; e = e.next)
29 action.accept(e.key);
30 }
31 if (modCount != mc)//遍历迭代器要求不能被其他线程修改表内元素个数而引起modCount变化
32 throw new ConcurrentModificationException();
33 }
34 }
35 }
View Code
根据上面对putVal的分析，该方法不会改变已有的key值，返回值为旧值或null
1 public
2 return putVal(hash(key), key, value, true, true);
3 }
View Code
然后来看一下两个replace方法，区别在于返回值和是否检查value值
1 @Override
2 public boolean replace(K key, V oldValue, V newValue) {
3 Node e; V v;
4 if ((e = getNode(hash(key), key)) != null &&
5 ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {//key和value要同时符合条件
6 e.value = newValue;
7 afterNodeAccess(e);//也是用于LinkedHashMap保持结点插入顺序用的
8 return
9 }
10 return false;
11 }
12
13 @Override
14 public V replace(K key, V value) {
15 Node e;
16 if ((e = getNode(hash(key), key)) != null) {//仅key符合条件
17 V oldValue = e.value;
18 e.value = value;
19 afterNodeAccess(e);
20 return oldValue;
21 }
22 return null;
23 }
View Code
computeIfAbsent这个方法的作用是若key值在map中已有非null的value值，则直接返回旧value值；若value值为null则根据mappingFunction计算出新的value值并修改map中存在的键值对，返回新value值；若不存在key值则新增一个键值对插入到key的hash值对应的table数组位置链表的头部，并返回新的value值。 注意， putVal 方法插入的结点是在链表尾部，而该方法是在链表头部。
1 public V computeIfAbsent(K key,
2 Function super K, ? extends V> mappingFunction) {
3 if (mappingFunction == null)
4 throw new NullPointerException();
5 int hash = hash(key);
6 Node[] tab; Node first; int n, i;
7 int binCount = 0;
8 TreeNode t = null;
9 Node old = null;
10 if (size > threshold || (tab = table) == null ||
11 (n = tab.length) == 0)
12 n = (tab = resize()).length;//table空间不足时扩展数组
13 if ((first = tab[i = (n - 1) & hash]) != null) {//hash值对应的下标在table内不为空
14 if (first instanceof TreeNode)
15 old = (t = (TreeNode)first).getTreeNode(hash, key);
16 else {
17 Node e = first; K k;
18 do {
19 if (e.hash == hash &&
20 ((k = e.key) == key || (key != null && key.equals(k)))) {//对箱式链表搜索key相等的结点
21 old = e;
22 break;
23 }
24 ++binCount;
25 } while ((e = e.next) != null);
26 }
27 V oldValue;
28 if (old != null && (oldValue = old.value) != null) {//找到了key相等的结点且value不为null
29 afterNodeAccess(old);//LinkedHashMap方法
30 return oldValue;//返回旧value值
31 }
32 }
33 V v = mappingFunction.apply(key);//根据function计算出新的v值
34 if (v == null) {
35 return null;//新的v值为null则直接返回
36 } else if (old != null) {//找到了key相等的结点且value为null，赋予新v值后返回新v值
37 old.value = v;
38 afterNodeAccess(old);
39 return v;
40 }
41 else if (t != null)
42 t.putTreeVal(this, tab, hash, key, v);//树结点处理
43 else {
44 tab[i] = newNode(hash, key, v, first);//没有找到key相等的结点，新建一个结点并且插入到链表头部
45 if (binCount >= TREEIFY_THRESHOLD - 1)
46 treeifyBin(tab, hash);//若新增结点后链表长度达到了TREEIFY_THRESHOLD则转为树
47 }
48 ++modCount;//该部分仅新增结点时执行
49 ++size;
50 afterNodeInsertion(true);
51 return v;
52 }
View Code
然后是两个相近的方法：computeIfPresent存在key相等且value不为null的结点，计算新的value值，新value不为null则覆盖，新value为null则移除原本的结点。compute方法结合了前两者，存在key相等的结点时不考虑旧value值，新value为null则移除，不为null则覆盖value值；不存在key相等的结点时，新value值不为null则新增结点，对箱式链表插入到链表头部，插入后要检车是否需要转为树。
1 public V computeIfPresent(K key,
2 BiFunction super K, ? super V, ? extends V> remappingFunction) {
3 if (remappingFunction == null)
4 throw new NullPointerException();
5 Node e; V oldValue;
6 int hash = hash(key);
7 if ((e = getNode(hash, key)) != null &&
8 (oldValue = e.value) != null) {//存在key相等且value不为null的结点
9 V v = remappingFunction.apply(key, oldValue);
10 if (v != null) {
11 e.value = v;//新value值不为null则修改value值
12 afterNodeAccess(e);
13 return v;
14 }
15 else
16 removeNode(hash, key, null, false, true);//新value值为null则移除这个结点
17 }
18 return null;
19 }
20
21 @Override
22 public V compute(K key,
23 BiFunction super K, ? super V, ? extends V> remappingFunction) {
24
25 throw new NullPointerException();
26 int hash = hash(key);
27 Node[] tab; Node first; int n, i;
28 int binCount = 0;
29 TreeNode t = null;
30 Node old = null;
31 if (size > threshold || (tab = table) == null ||
32 (n = tab.length) == 0)
33 n = (tab = resize()).length;//table空间不足时调用resize
34 if ((first = tab[i = (n - 1) & hash]) != null) {
35
36 old = (t = (TreeNode)first).getTreeNode(hash, key);//树中寻找key相等的结点
37 else {
38 Node e = first; K k;
39 do {
40 if (e.hash == hash &&
41 ((k = e.key) == key || (key != null && key.equals(k)))) {
42 old = e;//找到了key相等的结点
43 break;
44 }
45 ++binCount;
46 } while ((e = e.next) != null);
47 }
48 }
49 V oldValue = (old == null
50 V v = remappingFunction.apply(key, oldValue);
51 if (old != null) {
52 if (v != null) {
53 old.value = v;//找到了key值相等的结点且新value不为null则旧结点的value设为新值
54 afterNodeAccess(old);
55 }
56 else
57 removeNode(hash, key, null, false, true);//找到了key值相等的结点且新value为null则移除旧结点
58 }
59 else if (v != null) {//没有找到key值相等的结点且新value值不为null
60 if (t != null)
61 t.putTreeVal(this, tab, hash, key, v);//树中插入新结点
62 else {
63 tab[i] = newNode(hash, key, v, first);//新建结点插入到链表头部
64 if (binCount >= TREEIFY_THRESHOLD - 1)
65 treeifyBin(tab, hash);//新增后链表长度达到TREEIFY_THRESHOLD则转为树
66 }
67 ++modCount;//仅新增结点时执行
68 ++size;
69 afterNodeInsertion(true);
70 }
71 return v;
72 }
View Code
merge这个方法和前面差不多，也是先寻找key值相同的结点，若存在则看该结点value是否为null，不为null根据function和参数中的value以及结点原本的value计算出新的value值，否则直接赋予参数中的value值。若没有找到结点，则按照参数中key和value值新建一个结点插入到树中或者箱式链表的头部。
1 public V merge(K key, V value,
2 BiFunction super V, ? super V, ? extends V> remappingFunction) {
3 if (value == null)
4 throw new NullPointerException();
5 if (remappingFunction == null)
6 throw new NullPointerException();
7 int hash = hash(key);
8 Node[] tab; Node first; int n, i;
9 int binCount = 0;
10 TreeNode t = null;
11 Node old = null;
12
13 (n = tab.length) == 0)
14 n = (tab = resize()).length;//表空间不足时调用resize
15 if ((first = tab[i = (n - 1) & hash]) != null) {
16 if (first instanceof TreeNode)
17 old = (t = (TreeNode)first).getTreeNode(hash, key);//寻找树中key值相等的结点
18 else {
19 Node e = first; K k;
20 do {
21 if (e.hash == hash &&
22 ((k = e.key) == key || (key != null && key.equals(k)))) {
23 old = e;//寻找箱式链表中key值相等的结点
24 break;
25 }
26 ++binCount;
27 } while
28 }
29 }
30 if (old != null) {//寻找到key值相等的结点
31 V v;
32 if (old.value != null)//旧值不为null
33 v = remappingFunction.apply(old.value, value);//根据remappingFunction和旧value和参数中的value计算出新的value值
34 else
35 v = value;//旧值为null则新value=参数中的value
36 if (v != null) {
37 old.value = v;//计算出的新value值不为null则覆盖寻找到结点的value值
38 afterNodeAccess(old);
39 }
40
41 removeNode(hash, key, null, false, true);//计算出的新value值为null则移除找到的结点
42 return v;
43 }
44 if (value != null) {//没有寻找到key相等的结点
45 if (t != null)
46 t.putTreeVal(this, tab, hash, key, value);//树中新增结点
47 else {
48 tab[i] = newNode(hash, key, value, first);//新建结点插入到链表头部
49 if (binCount >= TREEIFY_THRESHOLD - 1)
50 treeifyBin(tab, hash);//新增结点后链表长度达到TREEIFY_THRESHOLD则转为树
51 }
52 ++modCount;//新增结点后执行
53 ++size;
54 afterNodeInsertion(true);
55 }
56 return value;
57 }
View Code
两个批量操作不难理解，同样要保证过程中没有其他线程修改了对象的元素个数
1 public void forEach(BiConsumer super K, ? super V> action) {
2 Node[] tab;
3 if (action == null)
4 throw new NullPointerException();
5 if (size
6 int mc = modCount;
7 for (int i = 0; i < tab.length; ++i) {
8 for (Node e = tab[i]; e != null; e = e.next)
9 action.accept(e.key, e.value);//对每个结点执行对应的操作
10 }
11 if (modCount != mc)
12 throw new ConcurrentModificationException();//有其他线程修改了HashMap中的元素个数时抛错
13 }
14 }
15 public void replaceAll(BiFunction super K, ? super
16 Node[] tab;
17 if (function == null)
18 throw new NullPointerException();
19 if (size > 0 && (tab = table) != null) {
20 int mc = modCount;
21 for (int i = 0; i < tab.length; ++i) {
22 for (Node e = tab[i]; e != null; e = e.next) {
23 e.value = function.apply(e.key, e.value);
24 }
25 }
26 if (modCount != mc)
27 throw new ConcurrentModificationException();
28 }
29 }
View Code
HashMap实现了clone方法，可以产生一个新的完全一样的HashMap
1 public Object clone() {
2 HashMap result;
3 try {
4 result = (HashMap)super.clone();//产生一个复制HashMap
5 } catch (CloneNotSupportedException e) {
6 // 因为HashMap支持clone方法，应该不会抛出这个错误
7 throw new InternalError(e);
8 }
9 result.reinitialize();//初始化参数值，所有集合数组都设为null
10 result.putMapEntries(this, false);//将原本集合中的键值对都插入到新产生的Map中
11 return result;
12 }
View Code
capacity这个方法先看table是否为null，不为null直接返回table.length。然后看threshold是否为0，不为0返回threshold否则返回默认容量16
1 final int capacity() {
2 return (table != null) ? table.length :
3 (threshold > 0) ? threshold :
4 DEFAULT_INITIAL_CAPACITY;
5 }
View Code
HashMap的序列化方法同样利用的是ObjectOutputStream
1 private
2 throws IOException {
3 int buckets = capacity();
4 // 先写入数组大小和集合内元素的个数
5 s.defaultWriteObject();
6 s.writeInt(buckets);
7 s.writeInt(size);
8 internalWriteEntries(s);
9 }
10 // 只有writeObject会调用这个方法
11 void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
12 Node[] tab;
13 if (size > 0 && (tab = table) != null) {
14 for (int
15 for (Node e = tab[i]; e != null; e = e.next) {
16 s.writeObject(e.key);
17 s.writeObject(e.value);
18 }
19 }
20 }
21 }
View Code
序列化输入是通过ObjectInputStreams，loadFactor一定会限制在0.25-4.0之间，而threshold是根据size/loadFactor + 1.0然后计算出大于等于该值的最小2的指数次幂。
1 private void readObject(java.io.ObjectInputStream s)
2 throws IOException, ClassNotFoundException {
3 // Read in the threshold (ignored), loadfactor, and any hidden stuff
4 s.defaultReadObject();
5 reinitialize();
6 if (loadFactor <= 0 || Float.isNaN(loadFactor))
7 throw new InvalidObjectException("Illegal load factor: " +
8 loadFactor);
9 s.readInt(); // 读取数组大小
10 int mappings = s.readInt(); // 读取元素个数
11 if (mappings < 0)
12 throw new InvalidObjectException("Illegal mappings count: " +
13 mappings);
14 else if (mappings > 0) { // (if zero, use defaults)
15 // loadFactor一定在0.25-4.0之间
16 float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
17 float fc = (float)mappings / lf + 1.0f;
18 int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
19 DEFAULT_INITIAL_CAPACITY :
20 (fc >= MAXIMUM_CAPACITY) ?
21 MAXIMUM_CAPACITY :
22 tableSizeFor((int)fc));//threshold的值在不超过范围的情况下设定为恰好大于等于size/loadFactor + 1的2的指数
23 float ft = (float)cap * lf;
24 threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
25 (int)ft : Integer.MAX_VALUE);
26 @SuppressWarnings({"rawtypes","unchecked"})
27 Node[] tab = (Node[])new Node[cap];
28 table = tab;
29
30 // Read the keys and values, and put the mappings in the HashMap
31 for (int i = 0; i < mappings; i++) {
32 @SuppressWarnings("unchecked")
33 K key = (K) s.readObject();
34 @SuppressWarnings("unchecked")
35 V value = (V) s.readObject();
36 putVal(hash(key), key, value, false, false);//从输入流中得去key和value值并通过putVal插入
37 }
38 }
39 }
View Code