Java集合 - HashMap

时间:2023-01-01 15:06:34

Map 是一种存储键值对的集合。Map 集合可以根据 key 快速查找对应的 value 值。HashMap 是 Map 类型的一中。

HashMap 的底层存储结构是:数组 + 链表 + 红黑树。

下面我们通过 HashMap 的新增操作、查找操作来看 HashMap 的底层存储结构。

Java集合 - HashMap

HashMap 的新增操作

当调用 HashMap 的 put() 方法时,put() 方法的处理逻辑如下:

  • 首先,它会调用 hash() 方法根据 key 计算出 hash 值,然后根据计算出的 hash 值计算出 key 对应的数组索引 i:

  • 计算出 key 对应的数组索引 i 之后,它根据数组在索引 i 上的值进行处理:

    • 如果数组在索引 i 上的值为 null,则直接生成一个新的节点,并让 tab[i] 指向该节点;
    • 如果数组在索引 i 上的值不为 null,则意味着需要解决 hash 冲突问题。
  • 接上一步骤,如果数组在索引 i 上的值不为 null。

    • 如果索引 i 上的结构是普通链表,则把新生成的节点加到链表的末尾
    • 如果索引 i 上的结构是红黑树,则使用红黑树方式新增
  • 接上一步骤,如果索引 i 上的结构是普通链表,则把新生成的节点加到链表的末尾之后,需要判断是否需要将链表转为红黑树:

    • 如果链表的长度大于等于 8,并且数组的长度大于等于 64,则调用 treeifyBin() 将链表转为红黑树;
    • 如果链表的长度大于等于 8,但是数组的长度小于 64,则调用 resize() 方法执行扩容操作;
    • 当红黑树中的节点个数小于等于 6 时,红黑树会转为链表。
  • 将节点加入 HashMap 集合之后,put() 方法的最后一步,如果 HashMap 中元素的数量超过了扩容的阈值(threshold),那么它会调用 resize() 方法执行扩容操作。

当调用 HashMap 的 put() 方法时,如果 HashMap 中已经存在要新增的 key,并且方法的入参 onlyIfAbsent 为 false,则替换旧值,并返回旧值。


HashMap 中调用 hash() 方法根据 key 计算出 hash 值的规则是:

  • 如果 key 为 null,则计算出的 hash 值为 0
  • 如果 key 不为 null,则 hash 值的计算公式为 hash = key.hashCode() ^ (key.hashCode() >>> 16)。先将 key 的 hashCode 值无符号右移 16 位,然后再和 key 的 hashCode 值做 异或 运算,使 key 的 hashCode 值高 16 位的变化映射到低 16 位中,使 hashCode 值高 16 位也参与后续索引 i 的计算(i = hash & (n - 1))。减少了碰撞的可能性。
// 向 HashMap 集合中新增键值对
// 如果 HashMap 集合中已经存在该键,那么旧的值将被替换
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap 的扩容机制

当调用 HashMap 的 put() 方法时,将节点加入 HashMap 集合之后,如果 HashMap 中元素的数量超过了扩容的阈值(threshold),那么它会调用 resize() 方法执行扩容操作。

HashMap 的扩容机制是扩容为原来容量的 2 倍。resize() 方法会重新计算每个元素的 hash 值,将元素重新放入新的位置,并更新下次扩容的阈值(threshold 成员变量)为原来阈值的 2 倍。初始扩容阈值 threshold = loadFactor * 数组的长度。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {

    // 将节点加入 HashMap 集合

    ++modCount;
    if (++size > threshold) {
        // 执行扩容操作
        resize();
    }
    afterNodeInsertion(evict);
    return null;
}

HashMap 的查找操作

当调用 HashMap 的 get() 方法时,get() 方法的处理逻辑如下:

  • 首先,它会根据传入的 key 计算出 hash 值;然后根据计算出的 hash 值计算出 key 对应的数组索引 i
  • 计算出 key 对应的数组索引 i 之后,根据存储位置,从数组中取出对应的 Entry,然后通过 key 对象的 equals() 方法判断传入的 key 和 Entry 中的 key 是否相等:
    • 如果传入的 key 和 Entry 中的 key 相等,则查找操作完成,返回 Entry 中的 value;
    • 如果传入的 key 和 Entry 中的 key 不相等,判断数组在索引 i 上的结构是链表 还是 红黑树,然后调用相应的查找数据的方法。直到找到相等的 Entry 或者没有下一个 Entry 为止。

自定义类型作为 Map 的 key,注意事项

面试中如何通过 HashMap 展示你在数据结构方面的功底?-极客时间 (geekbang.org)

当 HashMap 的 key 为自定义类型时,我们需要重写(Override)该类的 equals() 方法和 hashCode() 方法。因为:

  • 重写 equals() 方法的原因:HashMap 的查找操作需要使用 key 对象的 equals() 方法判断传入的 key 和 Entry 中的 key 是否相等。我们需要保证逻辑上相同的对象,使用 equals() 方法判断时结果为 true。
  • 重写 hashCode() 方法的原因:HashMap 在使用哈希函数计算 key 的 hash 值时,需要使用 key 对象的 hashCode() 方法。我们需要保证逻辑上相同的对象,hashCode() 方法的返回值也相同。

HashMap 的容量大小问题

HashMap 的数组长度总是为 2 的幂次方。不论传入的初始容量是否为 2 的幂次方,最终都会转化为 2 的幂次方。

HashMap 中根据 key 计算出 hash 值,然后根据计算出的 hash 值计算出 key 对应的数组索引 i 时,通过 hash 值 和 数组的长度 - 1 做与运算获得 key 对应的数组索引 i ,即 i = hash & (n - 1)


HashMap 设计的非常巧妙:

  • 在计算 hash 值时,它先将 key 的 hashCode 值无符号右移 16 位,然后再和 key 的 hashCode 值做 异或 运算,使 key 的 hashCode 值高 16 位的变化映射到低 16 位中,使 hashCode 值高 16 位也参与后续索引 i 的计算(i = hash & (n - 1))。减少了碰撞的可能性。
  • 在根据 hash 值计算 key 对应的数组索引 i 时,它将 hash 值 和 数组的长度 - 1 做与运算获得 key 对应的数组索引 i,即 i = hash & (n - 1)。由于数组的长度 n 是 2 的幂次方,n - 1 可以保证它的二进制的后几位都是 1,n 的这一位及之前的位都是 0。因此,计算出的数组索引 i 和 hash 值的二进制表示中后几位有关,而与前面的二进制位无关
  • 当 b 是 2 的幂次方时,a % b == a & (b - 1)。CPU 处理位运算比处理数学运算的速度更快,效率更高。

HashMap 的死循环问题

HashMap 的死循环问题说的是,多个线程同时操作一个 HashMap,当 HashMap 中的键值对数量达到一定程度需要进行扩容操作时,HashMap 有可能会进入一个无限循环,导致程序无法正常执行。

这是因为多个线程同时操作一个 HashMap,多个线程调用 HashMap 的 resize() 执行扩容操作,HashMap 中的链表有可能成环,程序无法从遍历链表中退出,从而导致程序进入死循环。