本篇文章将从源码的角度去分析 HashMap 的 put，resize，get 流程。如果只想了解这三个方法的原理的小伙伴，可以只看这三个方法末尾的总结部分。

部分变量说明

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
/** 
* 1.默认初始化容量，默认是16 
* 2.必须是2的幂次方，便于通过位运算 (n - 1) & hash 快速定位桶索引。较小的初始容量平衡了内存占用和哈希* 碰撞概率。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/*** 最大容量，2的30次方 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/*** 装载因子，0.75是统计出来的，能够平衡时间和空间成本 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/*** 由链表转成红黑树的阈值，即当链表的长度 >= 8的时候触发 */
static final int TREEIFY_THRESHOLD = 8;

/*** 由红黑树退化成链表的阈值，当树节点 <= 6的时候触发 */
static final int UNTREEIFY_THRESHOLD = 6;

/*** 允许树化的最小哈希表容量，当表容量 < 64时，优先扩容而非树化。 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * 1.存储节点的数组，在首次被使用的时候才初始化（第一次put）
 * 2.长度总是2的次方
 */
transient Node<K,V>[] table;

初始化流程

构造方法

  1. JDK8 的 HashMap 提供多个构造方法，平时常用的无参构造方法如下，这里只是简单的给装载因子取默认值：

    1
    2
    3
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

  2. 构造方法并没有直接创建存储数组，而是在首次调用 put 时才会初始化（table == null 时触发）。

put 流程

入口方法

1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

核心逻辑（putVal）

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
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) {
        // 首次 put 时初始化数组，在 resize() 中实现
        n = (tab = resize()).length;
    }
    if ((p = tab[i = (n - 1) & hash]) == null) {
       // 数组下标不存在节点，则直接填入 
       tab[i] = newNode(hash, key, value, null); 
    } else {
        // 处理哈希冲突
        Node<K,V> e; K k;
        // 检查第一个节点和将要插入的节点是否相等，如果相等，则赋值给局部变量e
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
            e = p;
        } else if (p instanceof TreeNode) {
            // 如果是树节点，调用红黑树插入逻辑
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        } else {
            // 遍历链表
            for (int binCount = 0; ; ++binCount) {
                // 插入到链表尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表长度超过 8 转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) {
                        treeifyBin(tab, hash);
                    }
                    break;
                }
                // hash值相等并且键值地址相等 或 键equals。这里可以保证 key 的唯一性
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                    // 当前的 e 的 key 与要新插入的 node 的 key 相等
                    break;
                }     
                p = e;
            }
        }
        // e 不为空的情况，即存在 key 相等的旧node
        if (e != null) {
            V oldValue = e.value;
            // 是否覆盖旧值
            if (!onlyIfAbsent || oldValue == null) {
                e.value = value;
            }
            // 给LinkHashMap的回调方法
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 检查扩容
    if (++size > threshold) {
        resize();
    }
    // 给LinkHashMap的回调方法
    afterNodeInsertion(evict);
    return null;
}

putVal 流程总结

  1. 哈希计算：入口方法中，通过 hash(key) 得出hash值。
  2. 判断链表数组是否被初始化过，如果没有则初始化，默认长度是16。
  3. 通过hash值定位数组下标：(n - 1) & hash。
  4. 处理哈希冲突：
    • 链表插入：遍历链表直到找到空节点或相同 key。
    • 树化：链表长度 ≥8 时转红黑树（需数组长度 ≥64，否则优先扩容）。
  5. 扩容检查：元素总数超过阈值 threshold（容量 × 装载因子）时触发 resize()。

扩容（resize）

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
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        // 已经达到最大容量，不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY) {
            // 新阈值翻倍，上面处理newCap = oldCap << 1，表示容量也翻倍
            newThr = oldThr << 1; 
        }
    } else if (oldThr > 0) {
        // 未初始化的情况，使用带初始容量的构造器创建
        newCap = oldThr;
    } else {               
        // 默认初始化情况，容量取默认值16
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 阈值为装载因子 * 容量值，即 0.75 * 16 = 12
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    } 
    // 当新阈值未被设置时，根据新容量和负载因子计算新阈值。
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 创建新的哈希表，准备把旧表的值复制到新表中
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null) {
                    // Node节点只有一个的情况，直接计算新的下表放入新表
                    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 {
                        next = e.next;
                        // 由于是2的次方数，这里利用哈希值与旧容量的按位与运算结果判断节点应该留在原位还是移动到新位置。
                        if ((e.hash & oldCap) == 0) {
                            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);
                    // 放入低位链表
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 放入高位链表
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 将高位链表放在新表的"原索引+旧容量"的位置(j + oldCap)
                        // 因为新容量是旧容量的2倍，所以高位链表的新位置就是原位置加上旧容量
                        // 例如：旧容量16，节点原在索引5，则新位置可能是5或21(5+16)
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

resize 流程总结

  1. 元素数量达到扩容阈值时触发扩容（装载因子 * 数组容量）。
  2. 新建一个链表数组，新长度和新扩容阈值都是旧链表数组的两倍。
  3. 把旧表的数据复制到新表中，采用了高低位链表法避免了重新哈希。
  4. 由于扩容需要把元素重新放入到新表，并且需要遍历一次链表，所以扩容的时间复杂度是O(n)。

get 流程

入口方法

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

核心逻辑（getNode）

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
final Node<K,V> getNode(Object key) {
    // 链表数组
    Node<K,V>[] tab; 
    // first：头节点；e：暂存遍历的节点
    Node<K,V> first, e; 
    // 数组容量 和 通过hash函数计算出的hash值
    int n, hash; 
    // 暂存遍历节点的 key 值
    K k;
    
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) {
        
        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 {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                    return e;
                }
            } while ((e = e.next) != null);
        }
    }
    return null;
}

get流程总结

getNode 的流程比较简单，先是计算出数组的下标，然后通过遍历链表/红黑树比较key值来获取元素。总结如下：

  1. 哈希定位：(n - 1) & hash 快速找到数组下标。
  2. 节点查找：
    1. 链表遍历时间复杂度O(n)。
    2. 红黑树查找时间复杂度O(log n)。

总结

操作 时间复杂度 核心逻辑
初始化 O(1) 延迟初始化，容量为 2 的幂次方
put O(1)~O(log n) 哈希定位 → 链表/树插入 → 扩容检查
get O(1)~O(log n) 哈希定位 → 链表/树遍历
resize O(n) 容量翻倍 → 数据迁移优化