本文将通过如下简单的代码来分析 HashMap 的内部数据结构的变化过程。

public static void main(String[] args) {
    Map<String, String> map = new HashMap<>();
    for (int i = 0; i < 50; i++) {
        map.put("key" + i, "value" + i);
    }
}
复制代码

1 数据结构说明

HashMap 中本文需要用到的几个字段如下:

下面说明一下几个字段的含义

1)table

// HashMap 内部使用这个数组存储所有键值对
transient Node<K,V>[] table;
复制代码

Node 的结构如下:

可以发现,Node 其实是一个链表,通过 next 指向下一个元素。

2)size

记录了 HashMap 中键值对的数量

3)modCount

记录了 HashMap 在结构上更改的次数,包括可以更改键值对数量的操作,例如 put、remove,还有可以修改内部结构的操作,例如 rehash。

4)threshold

记录一个临界值,当已存储键值对的个数大于这个临界值时,需要扩容。

5)loadFactor

负载因子,通常用于计算 threshold,threshold= 总容量 *loadFactor。

2.new HashMap

new HashMap 的源码如下:

/**
* The load factor used when none specified in constructor.
* 负载因子,当 已使用容量 > 总容量 * 负载因子 时,需要扩容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

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

复制代码

此时,HashMap 只初始化了负载因子(使用默认值 0.75),并没有初始化 table 数组。 其实 HashMap 使用的是延迟初始化策略,当第一次 put 的时候,才初始化 table(此时 table 是 null)。

3.table 数组的初始化

当第一次 put 的时候,HashMap 会判断当前 table 是否为空,如果是空,会调用 resize 方法进行初始化。 resize 方法会初始化一个容量大小为 16 的数组,并赋值给 table。 并计算 threshold=16*0.75=12。 此时 table 数组的状态如下:

4.put 过程

map.put("key0", "value0");
复制代码

首先计算 key 的 hash 值,hash("key0") = 3288451 计算这次 put 要存入数组位置的索引值:index=(数组大小 - 1) & hash = 3 判断 if (table[index] == null) 就 new 一个 Node 放到这里,此时为 null,所以直接 new Node 放到 3 上,此时 table 如下:

然后判断当前已使用容量大小 (size) 是否已经超过临界值 threshold,此时 size=1,小于 12,不做任何操作,put 方法结束(如果超过临界值,需要 resize 扩容)。

继续 put。。。

map.put("key1", "value1");
复制代码

map.put("key1", "value1");
map.put("key2", "value2");
map.put("key3", "value3");
map.put("key4", "value4");
map.put("key5", "value5");
map.put("key6", "value6");
map.put("key8", "value7");
map.put("key9", "value9");
map.put("key10", "value10");
map.put("key11", "value11");
复制代码

此时 size=12,下一次 put 后 size 为 13,大于当前 threshold,将触发扩容(resize)

map.put("key12", "value12");
复制代码

计算 Key 的 hash 值,hash("key12")=101945043,计算要存入 table 位置的索引值 = (总大小 - 1) & hash = (16 - 1) & 101945043 = 3 从目前的 table 状态可知,table[3] != null,但此时要 put 的 key 与 table[3].key 不相等,我们必须要把他存进去,此时就产生了哈希冲突(哈希碰撞)。

这时链表就派上用场了,HashMap 就是通过链表解决哈希冲突的。 HashMap 会创建一个新的 Node,并放到 table[3] 链表的最后面。 此时 table 状态如下:

5.resize 扩容

此时 table 中一共有 13 个元素,已经超过了 threshold(12),需要对 table 调用 resize 方法扩容。 HashMap 会创建一个容量为之前两倍 (162=32)的 table,并将旧的 Node 复制到新的 table 中,新的临界值 (threshold) 为 24(320.75)。

下面主要介绍一下复制的过程(并不是原封不动的复制,Node 的位置可能发生变化)

先来看源码:

for (int j = 0; j < oldCap; ++j) { // oldCap:旧 table 的大小 =16
    Node<K,V> e;
    if ((e = oldTab[j]) != null) { // oldTab:旧 table 的备份
        oldTab[j] = null;
        // 如果数组中的元素没有后继节点,直接计算新的索引值,并将 Node 放到新数组中
        if (e.next == null)
            newTab[e.hash & (newCap - 1)] = e;
        // 忽略这个 else if。其实,如果链表的长度超过 8,HashMap 会把这个链表变成一个树结构,树结构中的元素是 TreeNode
        else if (e instanceof TreeNode)
            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        // 有后继节点的情况
        else { // preserve order
            Node<K,V> loHead = null, loTail = null;
            Node<K,V> hiHead = null, hiTail = null;
            Node<K,V> next;
            do {
                next = e.next;
                // 【说明 1】
                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;
                //【说明 2】
                newTab[j + oldCap] = hiHead;
            }
        }
    }
}
复制代码

【说明 1】遍历链表,计算链表每一个节点在新 table 中的位置。

计算位置的方式如下:

1)如果节点的 (hash & oldCap) == 0,那么该节点还在原来的位置上,为什么呢?

因为 oldCap=16,二进制的表现形式为 0001 0000,任何数 &16,如果等于 0,那么这个数的第五个二进制位必然为 0。

以当前状态来说,新的容量是 32,那么 table 的最大 index 是 31,31 的二进制表现形式是 00011111。 计算 index 的方式是 hash & (容量 - 1),也就是说,新 index 的计算方式为 hash & (32 - 1) 假设 Node 的 hash = 01101011,那么

  01101011
& 00011111
----------
  00001011 = 11
复制代码

2)下面再对比 (hash & oldCap) != 0 的情况

如果节点的 (hash & oldCap) != 0,那么该节点的位置 = 旧 index + 旧容量大小

假设 Node 的 hash = 01111011,那么

  01111011
& 00011111
----------
  00011011 = 27
复制代码

上一个例子的 hash 值 01101011 跟这个例子的 hash 值 01111011 只是在第 5 位二进制上不同,可以发现,这两个值在旧的 table 中,是在同一个 index 中的,如下:

  01101011
& 00001111
----------
  00001011 = 11
复制代码
  01111011
& 00001111
----------
  00001011 = 11
复制代码

由于扩容总是以 2 倍的方式进行,也就是:旧容量 << 1,这也就解释了【说明 2】,当 (hash & oldCap) != 0 时,这个 Node 的新 index = 旧 index + 旧容量大小。

扩容后,table 状态如下所示:

最终,重新分配完所有的 Node 后,扩容结束。

  • Java

    Java,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台的总称。用 Java 实现的 HotJava 浏览器(支持 Java applet)显示了 Java 的魅力:跨平台、动态的…

    380 引用 • 6 回帖
感谢    赞同    分享    收藏    关注    反对    举报    ...