🌑

Shawn Fux

Home Tags Archive About

从源码角度分析HashMap

本文主要从源码角度分析 JDK1.8 HashMap 的 put get 方法的底层实现原理，以及 HashMap 的扩容机制实现。

前置知识

在分析 HashMap 源码之前，先理解一些 HashMap 的概念，在 HashMap 底层使用的数据结构是基于数组来实现的，这个数组一般称为哈希数组或者哈希桶数组，通过 Key 的 HashCode 计算出数组所在的索引下标位置，但是即使是不同的 HashCode 值计算出来的索引下标也有可能会一样，这时就发生哈希冲突了，那怎么解决了？HashMap 使用链地址法来解决哈希冲突，简单来说就是将冲突的元素用链表连接。由于我们知道数组一旦创建长度就固定了，所以这时候就需要对哈希数组进行扩容，通常来说就是创建一个更大的数组，然后将旧数组的元素复制过去以此来完成扩容，那么在扩容的时候有一些参数会影响到我们的扩容时机。


/**
 * 扩容阈值，当 HashMap 集合内的元素数量达到该阈值发生扩容
 * threshold = 容量 * loadFactor
 */
int threshold;

/**
 * 负载因子：默认0.75f
 */
final float loadFactor;

构造函数

  • 参数为另一个HashMap
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 通过构造函数把另一个 Map 集合合并到自身
    // 内部实现就是遍历参数 Map 集合
    // 然后调用 putVal 方法挨个添加
    putMapEntries(m, false);
}
  • 无参的构造函数
// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}
  • 可以指定容量的构造函数
// initialCapacity 指定 HashMap 容量
public HashMap(int initialCapacity) {
    // 可以看到实际上是调用了另一个构造函数,然后负载因子为默认的0.75f
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
  • 可以指定容量和负载因子的构造函数
public HashMap(int initialCapacity, float loadFactor) {
    // 参数容量不能小于0，但是可以等于0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 判断参数容量是否达到最大
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 参数负载因子不能小于等于0
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // 设置负载因子
    this.loadFactor = loadFactor;
    // 设置初始容量
    // 返回大于输入参数且最近的2的整数次幂的数。比如10，则返回16
    this.threshold = tableSizeFor(initialCapacity);
}

put方法

Put方法源码

public V put(K key, V value) {
    // onlyIfAbsent 表示当Key一样冲突时，是否决定覆盖
    // evict 这个参数 HashMap 并没有使用到，是留给子类如 LinkedHashMap 使用的
    return putVal(hash(key), key, value, false, true);
}

我们点进去 put 方法查看源码，会发现它间接调用了 putVal 这个方法来实现对实现数据的添加。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; // 临时变量引用哈希数组
    Node<K,V> p; // 临时变量引用当前节点对象
    int n, i; // n=临时变量哈希数组长度 i=临时变量当前节点哈希数组索引位置
    if ((tab = table) == null || (n = tab.length) == 0)
        // 如果哈希数组等于空或者哈希数组长度为0，则进行扩容初始化
        // 注意这里已经完成了对临时变量 tab n 的赋值
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 计算哈希索引位置并完成 p i 的赋值
        // 如果发现当前位置为 null，说明没有发生冲突
        // 直接创建一个新节点保存到当前位置
        tab[i] = newNode(hash, key, value, null);
    else {
        // 如果代码运行到这里，说明该哈希数组位置已经有值，可能发生冲突，也有可能会发生覆盖
        Node<K,V> e; // 临时变量引用Key一样的节点
        K k; // 临时变量引用已存在的节点 Key
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 如果hash一致 并且 key 的 equals 方法也一致，则认为这是同一个 key
            e = p;
        else if (p instanceof TreeNode)
            // 冲突节点是红黑树，将节点强制转换成红黑树后调用 putTreeVal 方法进行插入
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 冲突的节点是一个链表
            for (int binCount = 0; ; ++binCount) { // binCount 统计当前的链表长度
                if ((e = p.next) == null) {
                    // 获取节点的下一个节点，如果等null，这就是新节点保存的位置
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash); // 如果链表长度超过8 转红黑树
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 如果hash一致 并且 key 的 equals 方法也一致，则认为这是同一个 key
                // 跳出循环，已经找到要保存的位置
                p = e;
            }
        }
        if (e != null) {
            // 通常来说，当 e 不等于 null 的时候
            // 就是新加入的 key 找到了与已存在的 key 一样的节点
            // 可能需要发生值覆盖的情况
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                // 只有当 onlyIfAbsent 等于 flase 或者旧值等于 null 的时候才会发生覆盖
                e.value = value;
            afterNodeAccess(e); // 留给子类重写的扩展机制
            // 结束返回旧值
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        // 最后对Map集合元素数量加一，判断是否达到了扩容阈值
        resize();
    afterNodeInsertion(evict);// 留给子类重写的扩展机制
    return null;
}

Put方法流程图

, , — Nov 24, 2022