WeakHashMap 和 HashMap 的区别是什么,何时使

2022-12-02  本文已影响0人  彭旭锐

前言

大家好,我是小彭。

在之前的文章里,我们聊到了 Java 标准库中 HashMapLinkedHashMap 的实现原理。HashMap 是一个标准的散列表数据结构,而 LinkedHashMap 是在 HashMap 的基础上实现的哈希链表。

今天,我们来讨论 WeakHashMap,其中的 “Weak” 是指什么,与前两者的使用场景有何不同?我们就围绕这些问题展开。

提示: 本文源码基于 JDK 1.2 WeakHashMap。

思维导图:


1. 回顾 HashMap 和 LinkedHashMap

其实,WeakHashMap 与 HashMap 和 LinkedHashMap 的数据结构大同小异,所以我们先回顾后者的实现原理。

1.1 说一下 HashMap 的实现结构

HashMap 是基于分离链表法解决散列冲突的动态散列表。

HashMap 实现示意图

1.2 说一下 LinkedHashMap 的实现结构

LinkedHashMap 是继承于 HashMap 实现的哈希链表。

LinkedHashMap 示意图


2. 认识 WeakHashMap

2.1 WeakReference 弱引用的特点

WeakHashMap 中的 “Weak” 指键 Key 是弱引用,也叫弱键。弱引用是 Java 四大引用类型之一,一共有四种引用类型,分别是强引用、软引用、弱引用和虚引用。我将它们的区别概括为 3 个维度:

感知垃圾回收示意图

提示: 关于 “Java 四种引用类型” 的区别,在小彭的 Java 专栏中深入讨论过 《说一下 Java 的四种引用类型》,去看看。

2.2 WeakHashMap 的特点

WeakHashMap 是使用弱键的动态散列表,用于实现 “自动清理” 的内存缓存。

WeakHashMap 示意图

自动清理数据

2.3 说一下 WeakHashMap 与 HashMap 和 LinkedHashMap 的区别?

WeakHashMap 与 HashMap 都是基于分离链表法解决散列冲突的动态散列表,两者的主要区别在 键 Key 的引用类型上:

WeakHashMap 与 LinkedHashMap 都有自动清理的能力,两者的主要区别在于 淘汰数据的策略上:

2.4 重建 Key 对象不等价的问题

WeakHashMap 的 Key 使用弱引用,也就是以 Key 作为清理数据的判断锚点,当 Key 变得不可达时会自动清理数据。此时,如果使用多个 equals 相等的 Key 对象访问键值对,就会出现第 1 个 Key 对象不可达导致键值对被回收,而第 2 个 Key 查询键值对为 null 的问题。 这说明 equals 相等的 Key 对象在 HashMap 等散列表中是等价的,但是在 WeakHashMap 散列表中是不等价的。

因此,如果 Key 类型没有重写 equals 方法,那么 WeakHashMap 就表现良好,否则会存在歧义。例如下面这个 Demo 中,首先创建了指向 image_url1 的图片 Key1,再重建了同样指向 image_url1 的图片 Key2。在 HashMap 中,Key1 和 Key2 等价,但在 WeakHashMap 中,Key1 和 Key2 不等价。

Demo

class ImageKey {
    private String url;

    ImageKey(String url) {
        this.url = url;
    }

    public boolean equals(Object obj) {
        return (obj instanceOf ImageKey) && Objects.equals(((ImageKey)obj).url, this.url);
    }
}

WeakHashMap<ImageKey, Bitmap> map = new WeakHashMap<>();
ImageKey key1 = new ImageKey("image_url1");
ImageKey key2 = new ImageKey("image_url2");
// key1 equalsTo key3
ImageKey key3 = new ImageKey("image_url1");

map.put(key1, bitmap1);
map.put(key2, bitmap2);

System.out.println(map.get(key1)); // 输出 bitmap1
System.out.println(map.get(key2)); // 输出 bitmap2
System.out.println(map.get(key3)); // 输出 bitmap1

// 使 key1 不可达,key3 保持
key1 = null;

// 说明重建 Key 与原始 Key 不等价
System.out.println(map.get(key1)); // 输出 null
System.out.println(map.get(key2)); // 输出 bitmap2
System.out.println(map.get(key3)); // 输出 null

默认的 Object#equals 是判断两个变量是否指向同一个对象:

Object.java

public boolean equals(Object obj) {
    return (this == obj);
}

2.5 Key 弱引用和 Value 弱引用的区别

不管是 Key 还是 Value 使用弱引用都可以实现自动清理,至于使用哪一种方法各有优缺点,适用场景也不同。

类型 优点 缺点 场景
Key 弱引用 外部不需要持有 Value 的强引用,使用更简单 重建 Key 不等价 未重写 equals
Value 弱引用 重建 Key 等价 外部需要持有 Value 的强引用 重写 equals

举例 1: 在 Android Glide 图片框架的多级缓存中,因为图片的 EngineKey 是可重建的,存在多个 EngineKey 对象指向同一个图片 Bitmap,所以 Glide 最顶层的活动缓存采用的是 Value 弱引用。

EngineKey.java

class EngineKey implements Key {

    // 重写 equals
    @Override
    public boolean equals(Object o) {
        if (o instanceof EngineKey) {
            EngineKey other = (EngineKey) o;
            return model.equals(other.model)
                && signature.equals(other.signature)
                && height == other.height
                && width == other.width
                && transformations.equals(other.transformations)
                && resourceClass.equals(other.resourceClass)
                && transcodeClass.equals(other.transcodeClass)
                && options.equals(other.options);
        }
        return false;
    }
}

举例 2: 在 ThreadLocal 的 ThreadLocalMap 线程本地存储中,因为 ThreadLocal 没有重写 equals,不存在多个 ThreadLocal 对象指向同一个键值对的情况,所以 ThreadLocal 采用的是 Key 弱引用。

ThreadLocal.java

static class Entry extends WeakReference<ThreadLocal<?>> {
    /** The value associated with this ThreadLocal. */
    Object value;

    Entry(ThreadLocal<?> k, Object v) {
        super(k);
        value = v;
    }
    
    // 未重写 equals
}

3. WeakHashMap 源码分析

这一节,我们来分析 WeakHashMap 中主要流程的源码。

事实上,WeakHashMap 就是照着 Java 7 版本的 HashMap 依葫芦画瓢的,没有树化的逻辑。考虑到我们已经对 HashMap 做过详细分析,所以我们没有必要重复分析 WeakHashMap 的每个细节,而是把重心放在 WeakHashMap 与 HashMap 不同的地方。

3.1 WeakHashMap 的属性

先用一个表格整理 WeakHashMap 的属性:

版本 数据结构 节点实现类 属性
Java 7 HashMap 数组 + 链表 Entry(单链表) 1、table(数组)
2、size(尺寸)
3、threshold(扩容阈值)
4、loadFactor(装载因子上限)
5、modCount(修改计数)
6、默认数组容量 16
7、最大数组容量 2^30
8、默认负载因子 0.75
WeakHashMap 数组 + 链表 Entry(单链表,弱引用的子类型) 9、queue(引用队列)

WeakHashMap.java

public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {

    // 默认数组容量
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 数组最大容量:2^30(高位 0100,低位都是 0)
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    // 默认装载因子上限:0.75
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 底层数组
    Entry<K,V>[] table;

    // 键值对数量
    private int size;

    // 扩容阈值(容量 * 装载因子)
    private int threshold;

    // 装载因子上限
    private final float loadFactor;

    // 引用队列
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

    // 修改计数
    int modCount;

    // 链表节点(一个 Entry 等于一个键值对)
    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        // Key:与 HashMap 和 LinkedHashMap 相比,少了 key 的强引用
        // final K key;
        // Value(强引用)
        V value;
        // 哈希值
        final int hash;
        Entry<K,V> next;

        Entry(Object key, V value, ReferenceQueue<Object> queue, int hash, Entry<K,V> next) {
            super(key /*注意:只有 Key 是弱引用*/, queue);
            this.value = value;
            this.hash  = hash;
            this.next  = next;
        }
    }
}

WeakHashMap 与 HashMap 的属性几乎相同,主要区别有 2 个:

引用关系示意图

不出意外的话又有小朋友出来举手提问了🙋🏻♀️

ReferenceQueue 与 Reference 配合能够实现感知对象被垃圾回收的能力。在创建引用对象时可以关联一个实际对象和一个引用队列,当实现对象被垃圾回收后,引用对象会被添加到这个引用队列中。在 WeakHashMap 中,就是根据这个引用队列来自动清理无效键值对。

首先,Entry 一定要持有强引用,而不能持有弱引用。这是因为 Entry 是 WeakHashMap 内部维护数据结构的实现细节,并不会暴露到 WeakHashMap 外部,即除了 WeakHashMap 本身之外没有其它地方持有 Entry 的强引用。所以,如果持有 Entry 的弱引用,即使 WeakHashMap 外部依然在使用 Key 对象,WeakHashMap 内部依然会回收键值对,这与预期不符。

其次,不管是 Key 还是 Value 使用弱引用都可以实现自动清理。至于使用哪一种方法各有优缺点,适用场景也不同,这个在前文分析过了。

3.2 WeakHashMap 如何清理无效数据?

在通过 put / get /size 等方法访问 WeakHashMap 时,其内部会调用 expungeStaleEntries() 方法清理 Key 对象已经被回收的无效键值对。其中会遍历 ReferenceQueue 中持有的弱引用对象(即 Entry 节点),并将该结点从散列表中移除。

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

// 添加键值对
public V put(K key, V value) {
    ...
    // 间接 expungeStaleEntries()
    Entry<K,V>[] tab = getTable();
    ...
}

// 扩容
void resize(int newCapacity) {
    // 间接 expungeStaleEntries()
    Entry<K,V>[] oldTable = getTable();
    ...
}

// 获取键值对
public V get(Object key) {
    ...
    // 间接 expungeStaleEntries()
    Entry<K,V>[] tab = getTable();
    ...
}

private Entry<K,V>[] getTable() {
    // 清理无效键值对
    expungeStaleEntries();
    return table;
}

// ->清理无效键值对
private void expungeStaleEntries() {
    // 遍历引用队列
    for (Object x; (x = queue.poll()) != null; ) {
        // 疑问 3:既然 WeakHashMap 不考虑线程同步,为什么这里要做加锁,岂不是突兀?
        synchronized (queue) {
            Entry<K,V> e = (Entry<K,V>) x;
            // 根据散列值定位数组下标
            int i = indexFor(e.hash /*散列值*/, table.length);
            // 遍历桶寻找节点 e 的前驱结点
            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {
                Entry<K,V> next = p.next;
                if (p == e) {
                    // 删除节点 e
                    if (prev == e)                  
                        // 节点 e 是根节点
                        table[i] = next;
                    else
                        // 节点 e 是中间节点
                        prev.next = next;
                    // Must not null out e.next;
                    // stale entries may be in use by a HashIterator
                    e.value = null; // Help GC
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

4. 总结

上一篇 下一篇

猜你喜欢

热点阅读