JAVA基础 JAVA集合

WeakHashMap源码分析

王守钰 2020-03-10 10:03:02

简介

WeakHashMap是一种弱引用map，内部的key会存储为弱引用，当jvm gc的时候，如果这些key没有强引用存在的话，会被gc回收掉，下一次当我们操作map的时候会把对应的Entry整个删除掉，基于这种特性，WeakHashMap特别适用于缓存处理。

WeakHashMap继承体系

WeakHashMap没有实现Clone和Serializable接口，所以不具有克隆和序列化的特性。

image

存储结构

WeakHashMap因为gc的时候会把没有强引用的key回收掉，所以注定了它里面的元素不会太多，因此也就不需要像HashMap那样元素多的时候转化为红黑树来处理了。因此，WeakHashMap的存储结构只有（数组 + 链表）。

属性

// 默认初始容量为16
private static final int DEFAULT_INITIAL_CAPACITY = 16;

// 最大容量为2的30次方
private static final int MAXIMUM_CAPACITY = 1 << 30;
 
// 默认装载因子
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
// 桶
Entry<K,V>[] table;
 
// 元素个数
private int size;
 
// 扩容门槛，等于capacity * loadFactor
private int threshold;
 
// 装载因子
private final float loadFactor;
 
// 引用队列，当弱键失效的时候会把Entry添加到这个队列中
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

Entry内部类

WeakHashMap内部的存储节点, 没有key属性。

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    // 可以发现没有key, 因为key是作为弱引用存到Referen类中
    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) {
        // 调用WeakReference的构造方法初始化key和引用队列
        super(key, queue);
        this.value = value;
        this.hash  = hash;
        this.next  = next;
    }
}

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

    // 调用Reference的构造方法初始化key和引用队列
    public WeakReference(T referent, ReferenceQueue<? super T> q) {
        super(referent, q);
    }

}

public abstract class Reference<T> {

    // 实际存储key的地方
    private T referent;         /* Treated specially by GC */

    // 引用队列
    volatile ReferenceQueue<? super T> queue;

    Reference(T referent, ReferenceQueue<? super T> queue) {
        this.referent = referent;
        this.queue = (queue == null) ? ReferenceQueue.NULL : queue;
    }
}

从Entry的构造方法我们知道，key和queue最终会传到到Reference的构造方法中，这里的key就是Reference的referent属性，它会被gc特殊对待，即当没有强引用存在时，当下一次gc的时候会被清除。

构造方法

public WeakHashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Initial Capacity: "+
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;

    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load factor: "+
                                           loadFactor);
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    table = newTable(capacity);
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
}

public WeakHashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public WeakHashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public WeakHashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
            DEFAULT_INITIAL_CAPACITY),
         DEFAULT_LOAD_FACTOR);
    putAll(m);
}

构造方法与HashMap基本类似，初始容量为大于等于传入容量最近的2的n次方，扩容门槛threshold等于capacity * loadFactor。

put

public V put(K key, V value) {
    // 校验key是否为空，为空的话创建一个Object对象
    Object k = maskNull(key);
    // 获取key的hash值
    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;
        }
    }

    modCount++;
    // 如果没找到就把新值插入到链表的头部
    Entry<K,V> e = tab[i];
    tab[i] = new Entry<>(k, value, queue, h, e);
    // 如果插入元素后数量达到了扩容门槛就把桶的数量扩容为2倍大小
    if (++size >= threshold)
        resize(tab.length * 2);
    return null;
}
  • 计算hash：与HashMap有所不同，HashMap中如果key为空直接返回0，这里是用空对象来计算的。另外打散方式也不同，HashMap只用了一次异或，这里用了四次，HashMap给出的解释是一次够了，而且就算冲突了也会转换成红黑树，对效率没什么影响。
  • 计算在哪个桶
  • 遍历桶对应的链表
  • 如果找到元素就用新值替换旧值，并返回旧值
  • 如果没找到就在链表头部插入新元素，HashMap就插入到链表尾部。
  • 如果元素数量达到了扩容门槛，就把容量扩大到2倍大小；HashMap中是大于threshold才扩容，这里等于threshold就开始扩容了。

resize扩容

void resize(int newCapacity) {
    // 定义原桶
    Entry<K,V>[] oldTable = getTable();
    // 获取桶的大小
    int oldCapacity = oldTable.length;
    // 判断桶容量是否到达了最大容量
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // 到达最大容量设置为Integer的最大值
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 新桶
    Entry<K,V>[] newTable = newTable(newCapacity);
    // 把元素从旧桶转移到新桶
    transfer(oldTable, newTable);
    // 把新桶赋值桶变量
    table = newTable;

    /*
     * If ignoring null elements and processing ref queue caused massive
     * shrinkage, then restore old table.  This should be rare, but avoids
     * unbounded expansion of garbage-filled tables.
     */
     // 如果元素个数大于扩容门槛的一半，则使用新桶和新容量，并计算新的扩容门槛
    if (size >= threshold / 2) {
        threshold = (int)(newCapacity * loadFactor);
    } else {
        // 否则把元素再转移回旧桶，还是使用旧桶
        // 因为在transfer的时候会清除失效的Entry，所以元素个数可能没有那么大了，就不需要扩容了
        expungeStaleEntries();
        transfer(newTable, oldTable);
        table = oldTable;
    }
}
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
    // 遍历桶
    for (int j = 0; j < src.length; ++j) {
        Entry<K,V> e = src[j];
        src[j] = null;
        while (e != null) {
            Entry<K,V> next = e.next;
            Object key = e.get();
            // 如果key等于了null就清除，说明key被gc清理掉了，则把整个Entry清除
            if (key == null) {
                e.next = null;  // Help GC
                e.value = null; //  "   "
                size--;
            } else {
                // 否则就计算在新桶中的位置并把这个元素放在新桶对应链表的头部
                int i = indexFor(e.hash, dest.length);
                e.next = dest[i];
                dest[i] = e;
            }
            e = next;
        }
    }
}
  • 判断旧容量是否达到最大容量；
  • 新建新桶并把元素全部转移到新桶中；
  • 如果转移后元素个数不到扩容门槛的一半，则把元素再转移回旧桶，继续使用旧桶，说明不需要扩容；
  • 否则使用新桶，并计算新的扩容门槛；
  • 转移元素的过程中会把key为null的元素清除掉，所以size会变小；

get元素

public V get(Object key) {
    Object k = maskNull(key);
    // 计算hash
    int h = hash(k);
    Entry<K,V>[] tab = getTable();
    int index = indexFor(h, tab.length);
    Entry<K,V> e = tab[index];
    // 遍历链表，找到了就返回
    while (e != null) {
        if (e.hash == h && eq(k, e.get()))
            return e.value;
        e = e.next;
    }
    return null;
}
  • 计算hash值；
  • 遍历所在桶对应的链表；
  • 如果找到了就返回元素的value值；
  • 如果没找到就返回空；

remove元素

public V remove(Object key) {
    Object k = maskNull(key);
    // 计算hash
    int h = hash(k);
    Entry<K,V>[] tab = getTable();
    int i = indexFor(h, tab.length);
    // 元素所在的桶的第一个元素
    Entry<K,V> prev = tab[i];
    Entry<K,V> e = prev;

    // 遍历链表
    while (e != null) {
        Entry<K,V> next = e.next;
        if (h == e.hash && eq(k, e.get())) {
            // 如果找到了就删除元素
            modCount++;
            size--;

            if (prev == e)
                // 如果是头节点，就把头节点指向下一个节点
                tab[i] = next;
            else
                // 如果不是头节点，删除该节点
                prev.next = next;
            return e.value;
        }
        prev = e;
        e = next;
    }

    return null;
}
  • 计算hash；
  • 找到所在的桶；
  • 遍历桶对应的链表；
  • 如果找到了就删除该节点，并返回该节点的value值；
  • 如果没找到就返回null；

expungeStaleEntries

private void expungeStaleEntries() {
    // 遍历引用队列
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) x;
            int i = indexFor(e.hash, table.length);
            // 找到所在的桶
            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            // 遍历链表
            while (p != null) {
                Entry<K,V> next = p.next;
                // 找到该元素
                if (p == e) {
                    // 删除该元素
                    if (prev == e)
                        table[i] = next;
                    else
                        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;
            }
        }
    }
}
  • 当key失效的时候gc会自动把对应的Entry添加到这个引用队列中；
  • 所有对map的操作都会直接或间接地调用到这个方法先移除失效的Entry，比如getTable()、size()、resize()；
  • 这个方法的目的就是遍历引用队列，并把其中保存的Entry从map中移除掉，具体的过程请看类注释；
  • 从这里可以看到移除Entry的同时把value也一并置为null帮助gc清理元素，防御性编程。

使用案例

public class TestWeakHashMap {

    public static void main(String[] args) {
        Map<String, Object> map = new WeakHashMap<>(3);
        map.put(new String("1"),"1");
        map.put(new String("2"),"2");
        map.put(new String("3"),"3");
        System.out.println(map);
        String key = null;
        for (String k : map.keySet()){
            if(k.equals("3")){
                key = k;
            }
        }
        map.put("6","6");
        System.gc();
        System.out.println(map);
        key = null;
        System.gc();
        System.out.println(map);
    }
}
{1=1, 2=2, 3=3}
{6=6, 3=3}
{6=6}

在这里通过new String()声明的变量才是弱引用，使用"6"这种声明方式会一直存在于常量池中，不会被清理，所以"6"这个元素会一直在map里面，其它的元素随着gc都会被清理掉。

  • WeakHashMap使用（数组 + 链表）存储结构；
  • WeakHashMap中的key是弱引用，gc的时候会被清除；
  • 每次对map的操作都会剔除失效key对应的Entry；
  • 使用String作为key时，一定要使用new String()这样的方式声明key，才会失效，其它的基本类型的包装类型是一样的；
  • WeakHashMap常用来作为缓存使用；
目录
    标签列表
    Nacos 7 SpringCloud 7 CPU飚高 1 Redis 1 CacheEvict 1 OOM 1 JVM 2 Feign 12 hystrix 10 高可用 11 Mybatis 1 高并发 1 分布式锁 1 事务 2 Spring 2 TreeMap 4 数据库 1 Mysql 1 数据结构 5 红黑树 5 SpringMvc 1 构建工具 1 Maven 1 JUC 5 JAVA集合 13 JAVA基础 13