HashMap怎么学（二）数组扩展&链表生成 代码案例 代码

发表于

上一篇HashMap怎么学（一）我们通过一个简单的例子解释了HashMap的内部结构。

这篇文章我们会在上一篇的例子基础上改进下，给大家解释HashMap的内部数组是怎么扩展的，以及其内部是如何生成链表的。

代码案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
arduino复制代码public static void part2_1() {
		// 步骤一，初始化代码，插入部分12条数据
		Map<Integer, Integer> map = new HashMap<>(20);
		for (int i = 0; i < 12; i++) {
			map.put(i, i);
		}

		// 步骤二，插入第13条数据，触发内部数组长度扩展
		map.put(12, 12);

		// 步骤三，插入特定hash值，触发hash碰撞，生成链表
		for (int i = 1; i < 5; i++) {
			map.put(32 * i, 32 * i);
		}
}

执行完上述代码后HashMap的内部结构变化如图：

HashMap内部结构图2-1

代码解释

  • 步骤一执行完后，HashMap内部会生成一个长度为16的数组，数组的前12位的Node对象的key-value值和数组index值相同（HashMap内key-value键值对数量为12）。
  • 步骤二执行完后，HashMap的内部数组长度变成原来的2倍（32），并且第12位的Node对象的key-value值也为12。这里涉及到HashMap内部数组的扩张机制：

DEFAULT_LOAD_FACTOR默认值是0.75（也可以通过HashMap构造函数传递），表示当HashMap内key-value键值对数量超过内部数组长度0.75时，对内部数组进行扩张。

执行完步骤一后，内部数组长度为16，当key-value键值对数量超过16×0.75=12时内部数组会进行扩张，下面为HashMap部分源码。

1
2
3
4
arduino复制代码    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

内部数组长度扩展的长度是原值左移一位，也就是乘以2（newCap = oldCap << 1），下面为HashMap部分源码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ini复制代码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)
                newThr = oldThr << 1; // double threshold
        }
  ......
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
  ......
  • 步骤三执行完后，原内部数组index为0的Node对象变成了一个链表的头结点。

HashMap是通过tab[i = (n - 1) & hash]来定位新的key-value键值对要插入到内部数组的哪个位置的，这时n为内部数组长度32，n-1对应到二进制为00011111，Integer的hashcode值就是它本身的int值，这时hashcode就发生冲突了，都插入到了index为0的位置，组成了一个链表：

00011111&00000000=0

00011111&00100000（32）=0

00011111&01000000（64）=0

00011111&10000000（128）=0

下面为HashMap部分源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
ini复制代码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)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        ........
          for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
         .......

这篇文章就分享到这里，后续还有HashMap其他文章会陆续发布。

大家如果有问题欢迎在评论区留言一起探讨，同时也可以关注收藏“小西学JAVA”和同名公众号，有文章更新会及时收到通知。

Demo代码位置

gitee.com/xiaoxijava/…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%