概述
本文是基于jdk8_271版本进行分析的。
HashMap是Map集合中使用最多的。底层是基于数组+链表实现的，jdk8开始底层是基于数组+链表/红黑树实现的。HashMap也会动态扩容，与ArrayList不同的是，HashMap有一个阈值字段，元素数量达到阈值之后就会进行扩容。HashMap允许key为null。同时HashMap也是线程不安全的。
数据结构
-
实现继承关系
1 public class HashMap<K,V> extends AbstractMap<K,V>
2 implements Map<K,V>, Cloneable, Serializable
-
静态变量
选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折中选择。加载因子过高虽然减少了空间开销，但同时也增加了查询成本；加载因子过低虽然可以减少查询时间成本，但是空间利用率很低。
根据泊松分布计算的链表元素数量出现的概率（源码注释中给出了元素数量1-8出现概率的对照表，是在加载因子为0.75基础上计算的），可以看到当链表上元素数量为8时概率为0.00000006，这已经是很小了，所以在jdk8中设置了链表元素数量大于8时会转成红黑树结构。
1 /**
2 * 默认初始化容量 16
3 */
4 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
5
6 /**
7 * MUST be a power of two <= 1<<30.
8 * 集合最大容量
9 */
10 static final int MAXIMUM_CAPACITY = 1 << 30; 11
12 /**
13 * 默认加载因子的值 14 */
15 static final float DEFAULT_LOAD_FACTOR = 0.75f; 16
17 /**
18 * 链表上元素个数概率 19 * 0: 0.60653066 20 * 1: 0.30326533 21 * 2: 0.07581633 22 * 3: 0.01263606 23 * 4: 0.00157952 24 * 5: 0.00015795 25 * 6: 0.00001316 26 * 7: 0.00000094 27 * 8: 0.00000006 28 * 当链表的值数量大于8时，会从链表转成红黑树 29 */
30 static final int TREEIFY_THRESHOLD = 8; 31
32 /**
33 * 当链表的值数量小于6时，会从红黑树转回链表 34 */
35 static final int UNTREEIFY_THRESHOLD = 6; 36
37 /**
38 * 当Map中数量超过这个值才会转成红黑树，否则优先进行扩容 39 */
40 static final int MIN_TREEIFY_CAPACITY = 64;
-
静态内部类
为什么Node和TreeNode这个类是静态的？答案是：这跟内存泄露有关，Node类和TreeNode是在HashMap类中的，也就是一个内部类，若不使用static修饰，那么Node和TreeNode就是一个普通的内部类，在java中，一个普通内部类在实例化之后，默认会持有外部类的引用，这就有可能造成内存泄露（内部类与外部类生命周期不一致时）。但使用static修饰过的内部类（称为静态内部类），就不会有这种问题。
非静态内部类会自动生成一个构造器依赖于外部类：也是内部类可以访问外部类的实例变量的原因。
静态内部类不会生成，访问不了外部类的实例变量，只能访问类变量。
1.Node
1 static class Node<K,V> implements Map.Entry<K,V> { 2 final int hash; // hash值
3 final K key; // key
4 V value; // value
5 Node<K,V> next; // 下一个节点
6
7 Node(int hash, K key, V value, Node<K,V> 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 return Objects.hashCode(key) ^ Objects.hashCode(value); 20 } 21
22 public final V setValue(V newValue) { 23 V oldValue = value; 24 value = newValue; 25 return oldValue; 26 } 27
28 public final boolean equals(Object o) { 29 if (o == this) 30 return true; 31 if (o instanceof Map.Entry) { 32 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 33 if (Objects.equals(key, e.getKey()) &&
34 Objects.equals(value, e.getValue())) 35 return true; 36 } 37 return false; 38 } 39 }
2.TreeNode
1 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 2 TreeNode<K,V> parent; // 父节点
3 TreeNode<K,V> left; // 左节点
4 TreeNode<K,V> right; //右节点
5 TreeNode<K,V> prev; // 上一个同级结点
6 boolean red; 7 TreeNode(int hash, K key, V val, Node<K,V> next) { 8 super(hash, key, val, next);
9 } 10 }
-
成员变量
1 transient Node<K,V>[] table;
2
3 /**
4 * for keySet() and values().
5 */
6 transient Set<Map.Entry<K,V>> entrySet; 7
8 /**
9 * 实际存放数据数量 10 */
11 transient int size; 12
13 /**
14 * 修改次数 15 */
16 transient int modCount; 17
18 /**
19 * 阈值。阈值=容量*加载因子；默认为16*0.75=12。当元素数量超过阈值便会触发扩容。 20 */
21 int threshold; 22
23 /**
24 * 加载因子，默认是0.75，一般使用默认值。 25 */
26 final float loadFactor;
-
构造方法
HashMap采用的是懒加载方式，在新建对象时候不会初始化数组，等使用时候才会去初始化。加载因子大多数情况都是使用默认值。容量值大小一定得是2的指数次幂，会根据传入的容量值调用tableSizeFor()方法重新计算容量值大小。
1 public HashMap(int initialCapacity, float loadFactor) { 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 // 阈值，初始化时候是没有*加载因子的。对给定的容量值重新计算，返回一个2的指数次幂的值。此时容量值大小为0。
12 this.threshold = tableSizeFor(initialCapacity); 13 } 14
15 public HashMap(int initialCapacity) { 16 this(initialCapacity, DEFAULT_LOAD_FACTOR); 17 } 18
19 public HashMap() { 20 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 21 // 此时阈值和容量值大小都为0
22 } 23
24 public HashMap(Map<? extends K, ? extends V> m) { 25 this.loadFactor = DEFAULT_LOAD_FACTOR; 26 putMapEntries(m, false); 27 }
主要方法解析
-
tableSizeFor–重新计算容量大小
1 /**
2 * 对于给定的目标容量，进行位运算。返回的值是2的指数幂（返回的是>=cap最小一个2的指数次幂）。
3 */
4 static final int tableSizeFor(int cap) { 5 int n = cap - 1;
6 n |= n >>> 1;
7 n |= n >>> 2;
8 n |= n >>> 4;
9 n |= n >>> 8; 10 n |= n >>> 16; 11 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 12 }
-
putMapEntries–添加一个map集合到该集合
1 /**
2 * Map.putAll，Map构造函数 会调用该方法
3 *
4 * @param m the map 5 * @param evict 初始化有参构造时为false，其他为true 6 */
7 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 8 int s = m.size(); 9 // 如果传入的集合大小=0不进行操作
10 if (s > 0) { 11 if (table == null) { // pre-size
12 float ft = ((float)s / loadFactor) + 1.0F; 13 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
14 (int)ft : MAXIMUM_CAPACITY); 15 if (t > threshold) 16 //
17 threshold = tableSizeFor(t); 18 } 19 else if (s > threshold) 20 // 如果table!=null && s>threshold，进行扩容处理
21 resize(); 22 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 23 K key = e.getKey(); 24 V value = e.getValue(); 25 putVal(hash(key), key, value, false, evict); 26 } 27 } 28 }
-
resize–扩容方法
1 final Node<K,V>[] resize() {
2 Node<K,V>[] oldTab = table; 3 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 原容量值
4 int oldThr = threshold; // 原阈值
5 int newCap, newThr = 0;
6 if (oldCap > 0) {
7 if (oldCap >= MAXIMUM_CAPACITY) { 8 // 原容量大小已达到最大值，不进行扩容。同时将阈值设置为Integer.MAX_VALUE
9 threshold = Integer.MAX_VALUE; 10 return oldTab; 11 } 12 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
13 oldCap >= DEFAULT_INITIAL_CAPACITY) 14 // newCap新容量扩容为老容量的2倍 15 // 如果原容量值大于等于默认值16，同时将新阈值扩容为原阈值的2倍
16 newThr = oldThr << 1; // double threshold
17 } 18 else if (oldThr > 0) // 如果原容量等于0，原阈值大于0；这种情况为有参构造创建的对象，还未添加数据 19 // 将原阈值（此时原阈值就是之前计算的容量大小）赋值给新容量值，新阈值大小会在下面统一计算（此时新阈值大小为0）。
20 newCap = oldThr; 21 else { // 如果原容量等于0，原阈值等于0；这种情况为无参构造创建的对象 22 // 则将新容量值大小设置为默认值16，新阈值大小设置为12
23 newCap = DEFAULT_INITIAL_CAPACITY; 24 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 25 } 26 if (newThr == 0) { 27 // 如果新阈值大小为0，则会通过 新容量值大小*加载因子 计算，如果新容量值大小或者新阈值大小超出最大容量值，则将新阈值设置为Integer.MAX_VALUE
28 float ft = (float)newCap * loadFactor; 29 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
30 (int)ft : Integer.MAX_VALUE); 31 } 32 threshold = newThr; 33 @SuppressWarnings({"rawtypes","unchecked"}) 34 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 35 table = newTab; 36 if (oldTab != null) { 37 for (int j = 0; j < oldCap; ++j) { 38 Node<K,V> e; 39 if ((e = oldTab[j]) != null) { 40 oldTab[j] = null; 41 if (e.next == null) // 桶内只有一个元素
42 newTab[e.hash & (newCap - 1)] = e; 43 else if (e instanceof TreeNode) // 桶内元素是红黑树结构，调用split方法，完成旧数组红黑树结构迁移到新数组中的工作
44 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 45 else { // 桶内元素是链表结构，利用高低位迁移
46 Node<K,V> loHead = null, loTail = null; 47 Node<K,V> hiHead = null, hiTail = null; 48 Node<K,V> next; 49 do { 50 next = e.next; 51 if ((e.hash & oldCap) == 0) { 52 if (loTail == null) 53 loHead = e; 54 else
55 loTail.next = e; 56 loTail = e; 57 } 58 else { 59 if (hiTail == null) 60 hiHead = e; 61 else
62 hiTail.next = e; 63 hiTail = e; 64 } 65 } while ((e = next) != null); 66 if (loTail != null) { 67 loTail.next = null; 68 newTab[j] = loHead; 69 } 70 if (hiTail != null) { 71 hiTail.next = null; 72 newTab[j + oldCap] = hiHead; 73 } 74 } 75 } 76 } 77 } 78 return newTab; 79 }
-
put–添加元素
jdk1.8之后是先插入元素，再判断是否需要扩容。
1 public V put(K key, V value) { 2 return putVal(hash(key), key, value, false, true);
3 }
4
5 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 6 boolean evict) { 7 Node<K,V>[] tab; Node<K,V> p; int n, i; 8 if ((tab = table) == null || (n = tab.length) == 0)
9 // 如果table为空，会先进行扩容
10 n = (tab = resize()).length; 11 if ((p = tab[i = (n - 1) & hash]) == null) // 如果要插入的key对应索引为空，直接新建一个节点
12 tab[i] = newNode(hash, key, value, null); 13 else { // 要插入的key对应索引不为空
14 Node<K,V> e; K k; 15 if (p.hash == hash &&
16 ((k = p.key) == key || (key != null && key.equals(k)))) // 该索引位头结点key与要插入key相等
17 e = p; 18 else if (p instanceof TreeNode) // 该索引位头结点与插入key不相等，并且桶内是红黑树结构，则进行红黑树方式插入
19 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 20 else { // 该索引位头结点与插入key不相等，并且桶内是链表结构
21 for (int binCount = 0; ; ++binCount) { 22 if ((e = p.next) == null) { // 头结点下一个节点为空，说明没有节点的key与要插入的key相等，直接新建一个节点
23 p.next = newNode(hash, key, value, null); 24 if (binCount >= TREEIFY_THRESHOLD - 1) // 链表长度大于8时，将链表转为红黑树（-1是因为binCount是从0开始计数的）
25 treeifyBin(tab, hash); // 如果容量小于64，会进行扩容处理。大于等于64才会转为红黑树
26 break; 27 } 28 if (e.hash == hash &&
29 ((k = e.key) == key || (key != null && key.equals(k)))) 30 break; 31 p = e; 32 } 33 } 34 if (e != null) { // e!=null，说明之前存在该key
35 V oldValue = e.value; 36 if (!onlyIfAbsent || oldValue == null) 37 e.value = value; 38 afterNodeAccess(e); 39 return oldValue; 40 } 41 } 42 ++modCount; 43 // 如果之前不存在该key，会判断元素数量是否达到阈值，如果达到阈值则进行扩容
44 if (++size > threshold) 45 resize(); 46 afterNodeInsertion(evict); 47 return null; 48 }
-
remove–删除元素
1 public V remove(Object key) { 2 Node<K,V> e; 3 return (e = removeNode(hash(key), key, null, false, true)) == null ?
4 null : e.value; 5 }
6
7 final Node<K,V> removeNode(int hash, Object key, Object value, 8 boolean matchValue, boolean movable) { 9 Node<K,V>[] tab; Node<K,V> p; int n, index; 10 if ((tab = table) != null && (n = tab.length) > 0 &&
11 (p = tab[index = (n - 1) & hash]) != null) { // 判断数组不为空，并且要删除key对应的索引位元素不为空
12 Node<K,V> node = null, e; K k; V v; 13 if (p.hash == hash &&
14 ((k = p.key) == key || (key != null && key.equals(k)))) // 该索引位头结点key与要删除的key相等
15 node = p; 16 else if ((e = p.next) != null) { // 该索引位头结点与插入key不相等 17 // 首先根据key获取节点
18 if (p instanceof TreeNode) 19 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); 20 else { 21 do { 22 if (e.hash == hash &&
23 ((k = e.key) == key ||
24 (key != null && key.equals(k)))) { 25 node = e; 26 break; 27 } 28 p = e; 29 } while ((e = e.next) != null); 30 } 31 } 32 // 如果获取到的节点不为空，并且与传入的值相等，进行删除操作
33 if (node != null && (!matchValue || (v = node.value) == value ||
34 (value != null && value.equals(v)))) { 35 if (node instanceof TreeNode) 36 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); 37 else if (node == p) 38 tab[index] = node.next; 39 else
40 p.next = node.next; 41 ++modCount; 42 --size; 43 afterNodeRemoval(node); 44 return node; 45 } 46 } 47 return null; 48 }
-
treeifyBin–链表树化，首先会判断容量大小是否达到64，如果小于会优先进行扩容处理
1 final void treeifyBin(Node<K,V>[] tab, int hash) { 2 int n, index; Node<K,V> e; 3 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 4 resize();
5 else if ((e = tab[index = (n - 1) & hash]) != null) {
6 TreeNode<K,V> hd = null, tl = null;
7 do { 8 TreeNode<K,V> 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); 19 } 20 }
-
split–负责完成旧数组红黑树结构迁移到新数组中的工作（静态内部类TreeNode内部方法）
1 final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { 2 TreeNode<K,V> b = this;
3 // Relink into lo and hi lists, preserving order
4 TreeNode<K,V> loHead = null, loTail = null;
5 TreeNode<K,V> hiHead = null, hiTail = null;
6 int lc = 0, hc = 0;
7 for (TreeNode<K,V> e = b, next; e != null; e = next) { 8 next = (TreeNode<K,V>)e.next;
9 e.next = null; 10 if ((e.hash & bit) == 0) { // 区分数链表的高低位。为0说明是低位
11 if ((e.prev = loTail) == null) // 如果低位尾部节点为空，说明此时低位链表为空，e为低位链表第一个节点
12 loHead = e; 13 else // 如果低位尾部节点不为空，说明此时低位链表不为空，此时e不为第一个。将之前的低位尾部节点下一个节点指向当前处理的节点e
14 loTail.next = e; 15 loTail = e; // 此时处理的节点e为低位的尾部节点
16 ++lc; 17 } 18 else { // 此时e为高位
19 if ((e.prev = hiTail) == null) // 如果高位尾部节点为空，说明此时高位链表为空，e为高位链表第一个节点
20 hiHead = e; 21 else // 如果高位尾部节点不为空，说明此时高位链表不为空，此时e不为第一个。将之前的高位尾部节点下一个节点指向当前处理的节点e
22 hiTail.next = e; 23 hiTail = e; // 此时处理的节点e为高位的尾部节点
24 ++hc; 25 } 26 } 27
28 if (loHead != null) { 29 if (lc <= UNTREEIFY_THRESHOLD) 30 // 如果计算的低位节点数量<=6，取消树状结构化，返回的是Node
31 tab[index] = loHead.untreeify(map); 32 else { 33 tab[index] = loHead; 34 if (hiHead != null) // 如果hiHead==null，说明只有一个树，树结构不变
35 loHead.treeify(tab); 36 } 37 } 38 if (hiHead != null) { 39 if (hc <= UNTREEIFY_THRESHOLD) 40 // 如果计算的高位节点数量<=6，取消树状结构化，返回的是Node
41 tab[index + bit] = hiHead.untreeify(map); 42 else { 43 tab[index + bit] = hiHead; 44 if (loHead != null) // 如果loHead==null，说明只有一个树，树结构不变
45 hiHead.treeify(tab); 46 } 47 } 48 }
-
treeify–链表树化（静态内部类TreeNode内部方法）
1 final void treeify(Node<K,V>[] tab) {
2 TreeNode<K,V> root = null;
3 for (TreeNode<K,V> x = this, next; x != null; x = next) { 4 next = (TreeNode<K,V>)x.next;
5 x.left = x.right = null;
6 if (root == null) {
7 x.parent = null;
8 x.red = false; // 根节点颜色为黑色
9 root = x; 10 } 11 else { 12 // x:当前要处理的节点
13 K k = x.key; 14 int h = x.hash; 15 Class<?> kc = null; 16 // 从根节点遍历红黑树
17 for (TreeNode<K,V> p = root;;) { 18 int dir, ph; 19 // p:遍历到的红黑树节点
20 K pk = p.key; 21 // 确定要插入的节点是树的左节点还是右节点
22 if ((ph = p.hash) > h) 23 dir = -1; 24 else if (ph < h) 25 dir = 1; 26 else if ((kc == null &&
27 (kc = comparableClassFor(k)) == null) ||
28 (dir = compareComparables(kc, k, pk)) == 0) 29 dir = tieBreakOrder(k, pk); 30
31 TreeNode<K,V> xp = p; 32 if ((p = (dir <= 0) ? p.left : p.right) == null) { 33 // 表示x节点找到了要插入的地方
34 x.parent = xp; 35 if (dir <= 0) // x插入在p节点的左边
36 xp.left = x; 37 else
38 xp.right = x; // x插入在p节点的右边
39 root = balanceInsertion(root, x); 40 break; 41 } 42 } 43 } 44 } 45 moveRootToFront(tab, root); 46 }
-
untreeify–取消树化（静态内部类TreeNode内部方法）
1 final Node<K,V> untreeify(HashMap<K,V> map) { 2 Node<K,V> hd = null, tl = null;
3 for (Node<K,V> q = this; q != null; q = q.next) { 4 Node<K,V> p = map.replacementNode(q, null);
5 if (tl == null)
6 // 如果尾部节点为空，说明当前节点是第一个处理的节点（头结点）
7 hd = p; 8 else
9 tl.next = p; // 如果尾部节点不为空，将之前尾部节点的下一个节点指向当前节点
10 tl = p; // 将当前节点设置为尾部节点
11 } 12 return hd; 13 }
附录
HashMap源码详细注释Github地址：https://github.com/y2ex/jdk-source/blob/jdk1.8.0_271/src/main/java/java/util/HashMap.java
jdk1.8源码Github地址：https://github.com/y2ex/jdk-source/tree/jdk1.8.0_271
作者： Yanci丶
出处：https://www.cnblogs.com/Y2EX/p/14786226.html
點擊查看更多內容
為 TA 點贊
評論
評論
共同學習，寫下你的評論
評論加載中...
作者其他優質文章
正在加載中
感謝您的支持，我會繼續努力的～
掃碼打賞，你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃，即可進行掃碼打賞哦