WeakHashMap源码分析

简介

基于哈希表的Map接口的实现，带有弱键。当集合中的键没有引用时，将会被垃圾回收器删除。

类继承关系

属性

	/**
     * 默认初始容量-必须为2的幂。
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * 最大容量
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认加载因子
     */
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * hash槽
     */
    Entry<K,V>[] table;

    /**
     * 键值对的数量
     */
    private int size;

    /**
     * 下次扩容的阈值
     */
    private int threshold;

    /**
     * 加载因子
     */
    private final float loadFactor;

    /**
     * 已清除虚键的队列
     */
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
    /**
     * 用来表示null键
     */
    private static final Object NULL_KEY = new Object();

内部类

// 继承了WeakReference 说明这个键是个虚键
// 并且实现了Entry节点 可以作为单链表
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    final int hash;
    Entry<K,V> next;

    /**
     * 内部节点值得注意的是这个构造方法
     * super(key, queue)调用父类构造 传入key和引用队列
     * 当GC回收了key的时候 会将这个Entry放到队列里面 就像是个回调
     * 这边发现队列有数据 就去清理一下（清理节点，key已经回收了）
     */
    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;
    }
}

构造

//构造一个空map，拥有默认的初始容量16,和加载因子0.75
public WeakHashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public WeakHashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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);
    //确定初始容量 寻找大于传入容量的最近 2的幂
    //这里循环判断是否大于初始容量 不大于 在翻一倍 直到找到那个数
    //注意这里算法和HashMap不一样 但是功能是一样的
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    table = newTable(capacity);
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
}

hash

final int hash(Object k) {
    int h = k.hashCode();
    // 此函数可确保在每个位位置仅
    //常数倍相差的hashCode具有
    //有限的冲突次数（默认负载因子约为8）
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

插入put

public V put(K key, V value) {
    Object k = maskNull(key);//如果key=null 使用默认全局nullKey表示
    int h = hash(k);
    Entry<K,V>[] tab = getTable();//获得table 这个函数里面先清除了一遍GC后的数据
    int i = indexFor(h, tab.length);//h & (length-1) 定位hash槽

    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);
    if (++size >= threshold)//如果数量到达阈值 就扩容一倍
        resize(tab.length * 2);
    return null;
}
private static Object maskNull(Object key) {
   return (key == null) ? NULL_KEY : key;
}

获取get

public V get(Object key) {
    Object k = maskNull(key);
    int h = hash(k);//计算hash码
    Entry<K,V>[] tab = getTable();//获取表
    int index = indexFor(h, tab.length);//定位 和插入规则一样
    Entry<K,V> e = tab[index];//找到所在hash槽 时间复杂度O(1)
    while (e != null) {
        if (e.hash == h && eq(k, e.get()))
            return e.value;
        e = e.next;
    }
    return null;
}

移除remove

public V remove(Object key) {
	//老规矩 计算hash码 获取tab表 定位hash槽
    Object k = maskNull(key);
    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--;
            //如果要删除的节点是第一个 那么直接把下一个节点放到hash槽就行了
            //否则将第一个节点指向下一个节点
            if (prev == e)
                tab[i] = next;
            else
                prev.next = next;
            return e.value;
        }
        prev = e;
        e = next;
    }

    return null;
}

扩容resize

void resize(int newCapacity) {
    Entry<K,V>[] oldTable = getTable();
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        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 {
        expungeStaleEntries();
        transfer(newTable, oldTable);
        table = oldTable;
    }
}

移除被GC的节点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;
            }
        }
    }
}