WeakHashMap原理分析

Posted by Codeboy on September 26, 2020

HashMap 是开发中经常使用到的集合类,Java中还有一个类似的类叫 WeakHashMap,本文来分析下 WeakHashMap 的实现原理。

原理

从key的存储上分析,在put操作时,如果不存在key值,则新建一个 Entry

public V put(K key, V value) {
        Object k = maskNull(key);
        int h = hash(k);
        Entry<K,V>[] tab = getTable();
        int i = indexFor(h, tab.length);
        // 如果有的话,则替换新
        for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
            if (h == e.hash && eq(k, e.get())) {
                V oldValue = e.value;
                if (value != oldValue)
                    e.value = value;
                return oldValue;
            }
        }

        // 创建新的key
        modCount++;
        Entry<K,V> e = tab[i];
        tab[i] = new Entry<>(k, value, queue, h, e);
        if (++size >= threshold)
            resize(tab.length * 2);
        return null;
    }

Entry 继承了 WeakReference ,这里就说明了put到 WeakHashMap 中的key是以 WeakReference 类型存储的:

 private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        V value;
        final int hash;
        Entry<K,V> next;

        /**
         * Creates new entry.
         */
        Entry(Object key, V value,
              ReferenceQueue<Object> queue,
              int hash, Entry<K,V> next) {
            super(key, queue);
            this.value = value;
            this.hash  = hash;
            this.next  = next;
        }
  // ...
  }

WeakReference 有两个构造方法,单独的key或者key和queue,两者的区别在于key在要引用的时候,后者将其加入到队列中:

public class WeakReference<T> extends Reference<T> {

    public WeakReference(T referent) {
        super(referent);
    }
 
    public WeakReference(T referent, ReferenceQueue<? super T> q) {
        super(referent, q);
    }

}

对于 WeakHashMap的key 清理,可以根据上文的queue进行处理,因为queue中的key都是没有引用的对象了(除queue引用), WeakHashMap 清理函数为 expungeStaleEntries,查看调用的地方:

private Entry<K,V>[] getTable() {
    expungeStaleEntries();
    return table;
}

public int size() {
    if (size == 0)
        return 0;
    expungeStaleEntries();
    return size;
}

void resize(int newCapacity) {
   // ...
    expungeStaleEntries();
    transfer(newTable, oldTable);
    table = oldTable;
}

在Map的基本操作get、put、remove等,都会触发上述方法的调用,进而达到清理失效key的效果;

使用场景

很多技术同学给出了Tomcat中的一个多级缓存使用的场景:

https://github.com/apache/tomcat/blob/trunk/java/org/apache/tomcat/util/collections/ConcurrentCache.java

其中二级缓存使用了 WeakHashMap,整体上是一个LRUCache,一级缓存保持固定的容量,超过最大容量后,将其移入二级缓存中,查找元素时,先从一级缓存中查找,不存在的时候,从二级缓存中查找,如果存在,则同时将其移入一级缓存中,实现LRU缓存,代码如下:

public final class ConcurrentCache<K,V> {

    private final int size;

    private final Map<K,V> eden;

    private final Map<K,V> longterm;

    public ConcurrentCache(int size) {
        this.size = size;
        this.eden = new ConcurrentHashMap<>(size);
        this.longterm = new WeakHashMap<>(size);
    }

    public V get(K k) {
        V v = this.eden.get(k);
        if (v == null) {
            synchronized (longterm) {
                v = this.longterm.get(k);
            }
            if (v != null) {
                this.eden.put(k, v);
            }
        }
        return v;
    }

    public void put(K k, V v) {
        if (this.eden.size() >= size) {
            synchronized (longterm) {
                this.longterm.putAll(this.eden);
            }
            this.eden.clear();
        }
        this.eden.put(k, v);
    }
}

Android同学经常会遇到持有相关对象,造成内存泄漏的问题,例如常用的全局listener,可以使用 WeakHashMap 便捷的解决问题,但是不完全能避免内存泄漏,因为其清理等待需要下一次操作之后,可能会有一个元素不能释放,可以使用 WeakReferenceHashMap 组合解决,构造 WeakReference 时不传入队列,在元素不使用后,直接由垃圾回收器回收。

小结

本文介绍了 WeakHashMap 的原理,对于需要频繁操作且内存有限的场景,可以尝试下。

如有任何知识产权、版权问题或理论错误,还请指正。

转载请注明原作者及以上信息。