亲宝软件园·资讯

展开

WeakHashMap 和 HashMap 区别及使用场景

彭旭锐 人气:1

引言

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

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

学习路线图:

1. 回顾 HashMap 和 LinkedHashMap

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

1.1 说一下 HashMap 的实现结构

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

散列表示意图

HashMap 实现示意图

1.2 说一下 LinkedHashMap 的实现结构

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

LinkedHashMap 示意图

FIFO 与 LRU 策略

2. 认识 WeakHashMap

2.1 WeakReference 弱引用的特点

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

维度 1 - 对象可达性状态的区别: 强引用指向的对象是强可达的,只有强可达的对象才会认为是存活的对象,才能保证在垃圾收集的过程中不会被回收;

维度 2 - 垃圾回收策略的区别: 不同的引用类型的回收激进程度不同,

维度 3 - 感知垃圾回收时机: 当引用对象关联的实际对象被垃圾回收时,引用对象会进入关联的引用队列,程序可以通过观察引用队列的方式,感知对象被垃圾回收的时机。

感知垃圾回收示意图

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

2.2 WeakHashMap 的特点

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

WeakHashMap 示意图

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

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

HashMap 会持有键 Key 的强引用,除非手动移除,否则键值对会长期存在于散列表中。而 WeakHashMap 只持有键 Key 的弱引用,当 Key 对象不再被外部持有强引用时,键值对会被自动被清理。

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

LinkedHashMap 会按照 FIFO 或 LRU 的策略 “尝试” 淘汰数据,需要开发者重写 removeEldestEntry() 方法实现是否删除最早节点的判断逻辑。而 WeakHashMap 会按照 Key 对象的可达性淘汰数据,当 Key 对象不再被持有强引用时,会自动清理无效数据。

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 弱引用: 以 Key 作为清理数据的判断锚点,当 Key 不可达时清理数据。优点是容器外不需要持有 Value 的强引用,缺点是重建的 Key 与原始 Key 不等价,重建 Key 无法阻止数据被清理;

Value 弱引用: 以 Value 作为清理数据的判断锚点,当 Value 不可达时清理数据。优点是重建 Key 与与原始 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;
    }
}

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> {
        // 与 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 个:

引用关系示意图

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

加载全部内容

相关教程
猜你喜欢
用户评论