计算机基础数据结构与算法 HashMap源码解读

🎄HashMap所用数据结构

在JDK1.7及之前 HashMap的实现是数组 + 链表

在JDK1.8及之后 HashMap的实现是数组 + 链表 + 红黑树

🎄扩容源码分析

🍭JDK1.7的扩容源码

📑概述

在JDK1.7中 HashMap的底层数据结构是Entry数组 + Entry链表在扩容的时候基本逻辑是直接把所有元素的key经过hash()函数重新计算hash值并填充到新存储桶实现处理逻辑相比于JDK1.8的实现更简单

📑源码解读

当size的大小超过阈值（阈值 = 当前容量 * 加载因子）就会执行resize方法进行扩容操作

在下面的代码中可以看到JDK1.7的实现是默认🎯把null元素存储在下标为0的位置的

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 当size的大小超过阈值（阈值 = 当前容量 * 加载因子）
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        // 默认把null元素存储在下标为0的位置
        hash = (null != key) ? hash(key) : 🎯0;
        bucketIndex = indexFor(hash, table.length);
    }
    ...
}

resize方法的解读如下

/**
 * 根据新的容量扩容原HashMap
 * @param newCapacity
 */
void resize(int newCapacity) {
    // 获取原存储桶
    HashMap.Entry[] oldTable = table;
    // 获取原存储桶的容量
    int oldCapacity = oldTable.length;
    // 如果原先的容量已经达到最大 则更新扩容阈值并返回
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 如果原容量并没有达到最大值 则根据newCapacity新建一个存储桶
    HashMap.Entry[] newTable = new HashMap.Entry[newCapacity];
    // 这个转换函数负责将旧的哈希表的元素全部移到新的哈希表（中间会设计重新计算元素的hash值）
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 转换函数执行后 更新存储桶
    table = newTable;
    // 更新新的扩容阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

重要的扩容细节必然在transfer函数中呈现我们来看这个函数

/**
 * 将旧存储桶的元素全部移动到新存储桶
 * @param newTable      新的存储桶
 * @param rehash        哈希掩码是否更更新 -> 与哈希码的生成有关
 */
void transfer(HashMap.Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    // 遍历旧的table的元素
    for (HashMap.Entry<K,V> e : table) {
        // 处理当前e对应的链表
        while(e != null) {
            // 暂存链表的next元素
            HashMap.Entry<K,V> next = e.next;
            // 是否需要更新元素的hash值
            if (rehash) {
                // 处理key为null的元素hash码为0 非null的元素用hash()函数进行计算
                e.hash = (null == e.key) ? 0 : hash(e.key);
            }
            // 获取要移到新table的哪一个下标位置
            int i = indexFor(e.hash, newCapacity);

            // 这一步赋值的时候 用的是⚡头插法
            e.next = newTable[i];
            newTable[i] = e;

            // 更新正在遍历的元素 直到e为null 当前的链表则处理完
            e = next;
        }// while退出 遍历数组中下一个Entry
    }
}

transfer函数中使用了一个indexFor函数其作用是获取当前的e元素应该放在新存储的哪一个下标来看一下这个函数

/**
 * 这个函数很简单 实际上就是用元素的新hashCode经过与运算计算得到下标 等价于取余运算
 * @param h             e元素的hashCode
 * @param length        新容量 这个容量是2的整数次幂
 * @return
 */
static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1); // 等价于取余运算
}

20231013 更新

🍭JDK1.8的扩容源码

📑概述

在JDK1.8中，数组仍然是哈希表的主要结构，每个数组位置被称为一个桶（bucket），每个桶可以存放多个元素。每个桶被实现为一个单向链表（LinkedList），当链表长度超过阈值（8）时，将链表转换为红黑树（Red-Black Tree）。

扩容的触发条件是：当哈希表中元素数量大于当前数组容量与负载因子（默认为0.75）的乘积时，就会触发扩容操作。

扩容的具体过程如下：

创建一个新的两倍大小的数组，将原先的数组中的元素一一重新哈希到新的数组中。

如果哈希冲突的元素太多，即一个桶中的元素超过一定数量（默认为8）时，将该桶中的元素转换为红黑树，以提高查找、插入和删除的性能。

新的数组中，每个桶的顺序与原先相同，但桶中的元素顺序可能发生变化。

当扩容完成后，新的数组将替换掉旧的数组，成为哈希表的存储结构。

通过链表和红黑树相结合的扩容思路，JDK1.8在处理哈希冲突时提高了性能，并且在一定程度上减少了因哈希冲突而导致的链表过长的问题，提高了哈希表的操作效率。

📑源码解读

JDK1.8 HashMap的重要变量域

// 默认初始化容量 必须是2的整数次幂 -> 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 扩容的阈值 一旦在一次put操作中发现 需要的容量大于threshold 就会触发扩容
int threshold; // threshold = capacity * loadFactor
// 加载因子(非常重要的默认域 0.75是经过验证的合理的值)
final float loadFactor = 0.75;

扩容在哪里进行触发？在put值的时候触发见下面的putVal函数

在下面的代码中只关心有注释的部分其他参数涉及到HashMap实现的其他逻辑暂不关注

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;
    // 声明一个新的Node 用于put到哈希表
    Node<K,V> p; 
    int n, i;
    
    /************************* 下面分两种情况 *********************/
    
    // 1️⃣如果哈希表为空 则先初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // 初始化哈希表table
        n = (tab = resize()).length;
    // 2️⃣1️⃣如果要插入的表的下标目前还没有元素 则在下标位置创建一个新的Node
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    /**
     * 2️⃣2️⃣其他情况 -> 目前要添加的位置下标已经存在元素 -> 存在哈希冲突 这个时候的处理就是核心了 
     *   需要进一步分情况处理
     */
    else {
        Node<K,V> e; K k;
        // 2️⃣2️⃣1️⃣ 第一种情况是当前要添加的元素的key（就是当前的p结点）之前已经存在 这个时候 只需要把原来的 p结点赋值给e
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; 
        // 2️⃣2️⃣2️⃣ 第二种情况 头元素不是要添加的key 这个时候就需要往后面（后面的元素可能位于链表 也可能位于红黑树）去查找要添加的key是不是已经存在 先判断头结点是不是红黑树结点
        else if (p instanceof TreeNode)
            // 如果是红黑树 则交给putTreeVal函数去处理添加的操作
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 2️⃣2️⃣3️⃣ 第三种情况 p是链表头 -> 在链表中put元素key value
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 插入到链表的尾部
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;
                p = e;
            }
        }
        // 如果要添加的元素存在冲突 并且e接收了原来的旧的元素 则返回旧的元素 程序结果
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null) e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 添加元素完成
    ++modCount;
    // ⚡扩容判断
    if (++size > threshold) resize();
    afterNodeInsertion(evict);
    // 添加元素无冲突 返回null
    return null;
}

接下来看到扩容函数resize

final HashMap.Node<K,V>[] resize() {
    ...初始化代码省略...
    // 创建一个新的table -> 扩容后的tabele
    HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
    table = newTab;
    if (oldTab != null) {
        /******* 遍历旧的table的所有元素 并把元素挪到新的table中 *******/
        for (int j = 0; j < oldCap; ++j) {
            HashMap.Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 1️⃣ 如果新table的j下标位置目前还没有元素 则直接把e赋给即可
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 2️⃣ 如果头结点是树结点 则调用split函数进行添加元素
                else if (e instanceof HashMap.TreeNode)
                    ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 3️⃣ 如果头结点是链表结点 则根据链表的拆分策略 将其挪动到新的table对应的下标
                else { // preserve order
                    // 具体逻辑可见【数据结构与算法 哈希表模拟实现】一文
                    // 链表的拆分策略 大致是把原链表均分为两部分 第一部分还是在原来的位置 第二部分放在newTab[j + oldCap]的位置
                }
            }
        }
    }
    return newTab;
}

在resize函数中当挪动元素的时候遇到树节点需要用split函数进行拆分这个地方TreeNode结点是红黑树结构处理相对复杂来看到它的源码如下（20231013更新 split函数暂未解读）：

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}