Java集合 - HashMap

2022-12-31  本文已影响0人  真正的飞鱼

介绍 HashMap

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

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

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

1638547825959-e25260c0-b272-40f0-8fb8-036b2582db3d.png

HashMap 的新增操作

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

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


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

// 向 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() 方法的处理逻辑如下:

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

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

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

HashMap 的容量大小问题

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

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


HashMap 设计的非常巧妙:

HashMap 的死循环问题

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

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

上一篇 下一篇

猜你喜欢

热点阅读