Java 8 容器源码-WeakHashMap

扫码关注公众号:Java 技术驿站

发送:vip
将链接复制到本浏览器,永久解锁本站全部文章

【公众号:Java 技术驿站】 【加作者微信交流技术,拉技术群】

作者:潘威威 出处:https://blog.csdn.net/panweiwei1994


WeakHashMap和HashMap相似,也是哈希表的实现,以键值对的形式存储数据,key和value都可以为null。不同的是WeakHashMap的键为“弱键”。什么是“弱键”?弱键会对WeakHashMap产生什么影响?“弱键”是如何实现的?本文会通过源码来一一解答。

部分顶部注释

Hash table based implementation of the Map interface, with weak keys. An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use. More precisely, the presence of a mapping for a given key will not prevent the key from being discarded by the garbage collector, that is, made finalizable, finalized, and then reclaimed. When a key has been discarded its entry is effectively removed from the map, so this class behaves somewhat differently from other Map implementations.

WeakHashMap是Map接口的基于弱键的哈希表实现。当一个键不再正常使用,键对应的键值对将自动从WeakHashMap中删除。更严谨的说法是,键对应的键值对的存在并不阻止key被垃圾回收期回收,这就使该键称为可被终止的,最终被终止,被回收。当某个键被回收,它对应的键值对也就被从map中有效地删除了。所以WeakHashMap类表现地有些和其他的Map接口实现不同。

Both null values and the null key are supported. This class has performance characteristics similar to those of the HashMap class, and has the same efficiency parameters of initial capacity and load factor.

WeakHashMap特性与HashMap相似,WeakHashMap同样支持key和value为null,也有初始化容量和负载因子等参数。

Like most collection classes, this class is not synchronized. A synchronized WeakHashMap may be constructed using the Collections.synchronizedMap method.

像大多的集合类一样,WeakHashMap是非同步的。可以使用Collections.synchronizedMap来构造同步的WeakHashMap。

下面还有很多,不翻译了。

从以上的内容中我们可以总结出WeakHashMap的特点

  1. WeakHashMap特性与HashMap相似,也是哈希表的实现,以键值对的形式存储数据,同样支持key和value为null,也有初始化容量和负载因子等参数,也是非同步的。
  2. WeakHashMap的键为“弱键”。

类层次结构图

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

  • WeakHashMap<K,V>:HashMap是以key-value形式存储数据的
  • extends AbstractMap<K,V>:继承了AbstractMap,大大减少了实现Map接口的工作量。
  • implements Map<K,V>:实现了Map。AbstractMap已经继承了Map接口,为什么WeakHashMap还要实现Map接口呢?仔细看过Java容器其他源码的朋友会发现,不仅仅WeakHashMap这样做,其他实现类也经常这样做。网上的一些看法是这样做可以直观地表达出WeakHashMap实现了Map。如果大家有其他看法,欢迎留言。

说到直观地展示出一个类的继承实现结构,eclipse的类层次结构图就可以实现这个功能。下图是WeakHashMap类结构层次图

MarkdownPhotos/master/CSDNBlogs/container/WeakHashMap/WeakHashMapTH.jpg

与HashMap相比

MarkdownPhotos/master/CSDNBlogs/container/HashMap/HashMapTH.jpg

我们发现WeakHashMap并没有实现Cloneable和Serializable接口。

全局变量

静态全局变量

    /**
     * 默认初始化容量,值为16
     * 必须是2的n次幂.
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * 最大容量, 如果一个更大的值在构造函数总被指定,将被MAXIMUM_CAPACITY 替换.
     * 必须是2的倍数。最大容量为1<<30,即2的30次方。
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

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

与HashMap相比,缺少了TREEIFY_THRESHOLD 、UNTREEIFY_THRESHOLD、MIN_TREEIFY_CAPACITY三个静态全局变量,而这三个静态全局变量是针对红黑树与链表的转换的。从这里可以验证WeakHashMap的数据结构为哈希表+链表。

普通全局变量

    /**
     * 存储键值对的数组,一般是2的幂
     */
    Entry<K,V>[] table;

    /**
     * 键值对的实际个数
     */
    private int size;

    /**
     * 扩容的临界值,通过capacity * load factor可以计算出来。超过这个值HashMap将进行扩容
     * @serial
     */
    private int threshold;

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

    /**
     * 会保存被GC回收的“弱键”的队列
     */
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

    /**
     * 记录HashMap被修改结构的次数。
     * 修改包括改变键值对的个数或者修改内部结构,比如rehash
     * 这个域被用作HashMap的迭代器的fail-fast机制中(参考ConcurrentModificationException)
     */
    int modCount;

与HashMap相比,WeakHashMap缺少了

    /**
     * 键值对缓存,它们的映射关系集合保存在entrySet中。即使Key在外部修改导致hashCode变化,缓存中还可以找到映射关系
     */
    transient Set<Map.Entry<K,V>> entrySet;

多了queue这个成员。

构造方法

WeakHashMap有四个构造方法:

  1. 用指定的初始化容量initial capacity 和负载因子load factor构造一个空WeakHashMap。
  2. 使用指定的初始化容量initial capacity和默认负载因子DEFAULT_LOAD_FACTOR(0.75)构造一个空WeakHashMap。
  3. 使用指定的初始化容量(16)和默认负载因子DEFAULT_LOAD_FACTOR(0.75)构造一个空WeakHashMap。
  4. 使用指定map构造新的WeakHashMap。使用指定的初始化容量(16)和默认负载因子DEFAULT_LOAD_FACTOR(0.75)。

WeakHashMap( int initialCapacity, float loadFactor)

    @SuppressWarnings("unchecked")
    private Entry<K,V>[] newTable(int n) {
        return (Entry<K,V>[]) new Entry<?,?>[n];
    }

    /**
     * 使用指定的初始化容量initial capacity 和负载因子load factor构造一个空WeakHashMap
     *
     * @param  initialCapacity 初始化容量
     * @param  loadFactor      负载因子
     * @throws IllegalArgumentException 如果指定的初始化容量为负数或者加载因子为非正数。
     */
    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);
    }

WeakHashMap( int initialCapacity)

    /**
     * 使用指定的初始化容量initial capacity和默认负载因子DEFAULT_LOAD_FACTOR(0.75)构造一个空WeakHashMap
     *
     * @param  initialCapacity 初始化容量
     * @throws IllegalArgumentException 如果指定的初始化容量为负数
     */
    public WeakHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

WeakHashMap()

    /**
     * 使用指定的初始化容量(16)和默认负载因子DEFAULT_LOAD_FACTOR(0.75)构造一个空WeakHashMap
     */
    public WeakHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

**WeakHashMap( Map m)** ```java /** 使用指定Map m构造新的HashMap。使用指定的初始化容量(16)和默认负载因子DEFAULT_LOAD_FACTOR(0.75) * @param m 指定的map * @throws NullPointerException 如果指定的map是null * @since 1.3 */ public WeakHashMap(Map m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAll(m); } ``` ## 私有方法 ```java /** * 当key为null时,NULL_KEY表示key */ private static final Object NULL_KEY = new Object(); ``` **maskNull( Object key)** ```java /** * 当key为null时,使用NULL_KEY表示key */ private static Object maskNull(Object key) { return (key == null) ? NULL_KEY : key; } ``` **unmaskNull( Object key)** ```java /** * 将key为NULL_KEY时,将key表示为null */ static Object unmaskNull(Object key) { return (key == NULL_KEY) ? null : key; } ``` **eq( Object x, Object y)** ```java /** * 判断两个非null对象是否相等 */ private static boolean eq(Object x, Object y) { return x == y || x.equals(y); } ``` **hash( Object k)** ```java /** * 计算key的哈希值 */ final int hash(Object k) { int h = k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } ``` **indexFor( int h, int length)** ```java /** * 返回哈希值对应的index */ private static int indexFor(int h, int length) { return h & (length-1); } ``` **expungeStaleEntries()** 文章开始提了一个问题:“弱键”是如何实现的?下面这个方法就是弱键实现的关键。 expungeStaleEntries方法会在引用队列queue中寻找是否有被回收的entry,如果有则在table中找到其映射,并将value置为null,next指针也置为null。 一旦垃圾收集器把某个key回收了,那么该key对应的entry就会被自动添加到这个队列里面,何时添加,如何添加,这些操作对WeakHashMap是透明的。 ```java /** * 从哈希表中删除被回收的key的映射 */ private void expungeStaleEntries() { //遍历队列 for (Object x; (x = queue.poll()) != null; ) { synchronized (queue) { @SuppressWarnings("unchecked") //由此可以看出队列中的元素是Entry Entry e = (Entry) x; //获取entry对应桶的index int i = indexFor(e.hash, table.length); //根据index获取table中对应的桶 Entry prev = table[i]; Entry p = prev; //如果桶不为null,遍历桶中节点,找到并删除与e相等的节点 while (p != null) { Entry next = p.next; //这段没看懂 if (p == e) { if (prev == e) table[i] = next; else prev.next = next; e.value = null; // 将e的value置为null size--;//table大小减1 break;//跳出循环 } //准备遍历下个节点 prev = p; p = next; } } } } ``` **getTable()** ```java /** * 从哈希表中删除被回收的key的映射后返回新的哈希表 */ private Entry[] getTable() { expungeStaleEntries(); return table; } ``` ## 常用方法 **size()** ```java /** * 从哈希表中删除被回收的key的映射后返回新的哈希表的大小 */ public int size() { if (size == 0) return 0; expungeStaleEntries(); return size; } ``` **isEmpty()** ```java /** * 判断哈希表大小是否为0 */ public boolean isEmpty() { return size() == 0; } ``` **get( Object key)** ```java /** * 返回指定的key对应的value,如果value为null,则返回null * * @see #put(Object, Object) */ public V get(Object key) { Object k = maskNull(key); int h = hash(k); Entry[] tab = getTable(); //获取桶在table中的index int index = indexFor(h, tab.length); //获取桶 Entry e = tab[index]; //遍历桶中节点 while (e != null) { if (e.hash == h && eq(k, e.get())) return e.value; e = e.next; } return null; } ``` 从遍历桶中节点的方式中可以看出,桶中节点为链表,并没有红黑树。 **containsKey( Object key)** ```java /** * 如果map中含有key为指定参数key的键值对,返回true * * @param key 指定参数key * @return 如果map中含有key为指定参数key的键值对,返回true */ public boolean containsKey(Object key) { return getEntry(key) != null; } /** * 根据key获取对应的节点 * * @param key 指定参数key * @return 返回node,如果没有则返回null */ Entry getEntry(Object key) { Object k = maskNull(key); int h = hash(k); Entry[] tab = getTable(); int index = indexFor(h, tab.length); Entry e = tab[index]; while (e != null && !(e.hash == h && eq(k, e.get()))) e = e.next; return e; } ``` **put( K key, V value)** ```java /** * 将指定参数key和指定参数value插入map中,如果key已经存在,那就替换key对应的value * * @param key 指定key * @param value 指定value * @return 如果value被替换,则返回旧的value,否则返回null。当然,可能key对应的value就是null。 */ public V put(K key, V value) { Object k = maskNull(key); int h = hash(k); Entry[] tab = getTable(); int i = indexFor(h, tab.length); for (Entry 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 e = tab[i]; tab[i] = new Entry<>(k, value, queue, h, e); if (++size >= threshold) resize(tab.length * 2); return null; } ``` **resize( int newCapacity)** ```java /** * * 扩容,并将旧的map中的键值对插入到新的table中。当map大小超过threshold时,方法会自动调用。 * 如果现在的容量为MAXIMUM_CAPACITY,方法不会扩容,但会设置threshold为Integer.MAX_VALUE。 * * @param newCapacity 新的容量,大小为2的幂。必须大于现在的容量,除非现在的容量为MAXIMUM_CAPACITY 。 */ void resize(int newCapacity) { Entry[] oldTable = getTable(); //记录table大小 int oldCapacity = oldTable.length; //如果table大小为MAXIMUM_CAPACITY,就将threshold调整为Integer.MAX_VALUE,终止执行 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 新建newTable Entry[] newTable = newTable(newCapacity); //将旧的table中的键值对复制到newTable中 transfer(oldTable, newTable); //使用newTable替换旧table 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. */ //如果table大小大于等于threshold / 2 if (size >= threshold / 2) { //重新计算threshold threshold = (int)(newCapacity * loadFactor); } else {//如果table小于threshold / 2 //没看懂为什么要这么做 expungeStaleEntries(); transfer(newTable, oldTable); table = oldTable; } } ``` **transfer( Entry\[\] src, Entry\[\] dest)** ```java /** Transfers all entries from src to dest tables */ /** * 将src的所有键值对复制到dest中。 */ private void transfer(Entry[] src, Entry[] dest) { for (int j = 0; j < src.length; ++j) { Entry e = src[j]; src[j] = null; while (e != null) { Entry next = e.next; Object key = e.get(); 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; } } } ``` **putAll(Map m)** ```java /** * 复制参数m中所有的键值对到weakHashMap中 * * @param m the map * @param evict 初始化map时使用false,否则使用truenull. */ public void putAll(Map m) { int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; /* * Expand the map if the map if the number of mappings to be added * is greater than or equal to threshold. This is conservative; the * obvious condition is (m.size() + size) >= threshold, but this * condition could result in a map with twice the appropriate capacity, * if the keys to be added overlap with the keys already in this map. * By using the conservative calculation, we subject ourself * to at most one extra resize. */ if (numKeysToBeAdded > threshold) { int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); if (targetCapacity > MAXIMUM_CAPACITY) targetCapacity = MAXIMUM_CAPACITY; int newCapacity = table.length; while (newCapacity < targetCapacity) newCapacity <<= 1; if (newCapacity > table.length) resize(newCapacity); } for (Map.Entry e : m.entrySet()) put(e.getKey(), e.getValue()); } ``` **remove( Object key)** ```java /** * 删除weakHashMap中key为参数key的键值对 * * @param key 参数key * @return 如果没有对应的键值对,返回null,否则返回对应的value。 */ public V remove(Object key) { Object k = maskNull(key); int h = hash(k); Entry[] tab = getTable(); int i = indexFor(h, tab.length); Entry prev = tab[i]; Entry e = prev; while (e != null) { Entry 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; } ``` **removeMapping( Object o)** ```java /** * 删除weakHashMap中为值为o的entry */ boolean removeMapping(Object o) { if (!(o instanceof Map.Entry)) return false; Entry[] tab = getTable(); Map.Entry entry = (Map.Entry)o; Object k = maskNull(entry.getKey()); int h = hash(k); 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 && e.equals(entry)) {
            modCount++;
            size--;
            if (prev == e)
                tab[i] = next;
            else
                prev.next = next;
            return true;
        }
        prev = e;
        e = next;
    }

    return false;
}

**clear()** ```java /** * 删除weakHashMap中所有的键值对 */ public void clear() { // clear out ref queue. We don't need to expunge entries // since table is getting cleared. while (queue.poll() != null) ; modCount++; Arrays.fill(table, null); size = 0; // Allocation of array may have caused GC, which may have caused // additional entries to go stale. Removing these entries from the // reference queue will make them eligible for reclamation. while (queue.poll() != null) ; }

containsValue( Object value)

    /**
     * 如果weakHashMap中的键值对有一对或多对的value为参数value,返回true
     *
     * @param value 参数value
     * @return 如果weakHashMap中的键值对有一对或多对的value为参数value,返回true
     */
    public boolean containsValue(Object value) {
        if (value==null)
            return containsNullValue();

        Entry<K,V>[] tab = getTable();
        for (int i = tab.length; i-- > 0;)
            for (Entry<K,V> e = tab[i]; e != null; e = e.next)
                if (value.equals(e.value))
                    return true;
        return false;
    }

containsNullValue()

    /**
     * 如果weakHashMap中的键值对有一对或多对的value为null,返回true
     *
     * @return 如果weakHashMap中的键值对有一对或多对的value为null,返回true
     */
    private boolean containsNullValue() {
        Entry<K,V>[] tab = getTable();
        for (int i = tab.length; i-- > 0;)
            for (Entry<K,V> e = tab[i]; e != null; e = e.next)
                if (e.value==null)
                    return true;
        return false;
    }

总结

WeakHashMap与HashMap比较

不同点

不同点 HashMap WeakHashMap
数据结构 数组+链表+红黑树 数组+链表+队列
强引用 弱引用
是否实现Cloneable和Serializable

相同点

  • 都是基于哈希表的实现。
  • 都以键值对的形式存储数据。
  • 都继承了AbstractMap,实现了Map接口。
  • 都支持key和value为null。
  • 都是非同步的。
  • 都是无序的。

什么是“弱键”?

先了解下什么是“弱引用”

弱引用, 在进行垃圾回收时,无论当前内存是否足够,都会回收掉只被弱引用关联着的对象,因此其生命周期只存在于一个垃圾回收周期内。

WeakHashMap的键就是弱引用。当某个键不再正常使用时,便自动移除其条目。

“弱键”会对WeakHashMap产生什么影响?

当一个键不再正常使用,键对应的键值对将自动从WeakHashMap中删除。键对应的键值对的存在并不阻止key被垃圾回收期回收,这就使该键称为可被终止的,最终被终止,被回收。当某个键被回收,它对应的键值对也就被从map中有效地删除了。所以WeakHashMap类表现地有些和其他的Map接口实现不同。

“弱键”是如何实现的?

WeakHashMap 中的Entry对象继承了 WeakReference,它把key封装成一个弱引用对象。

WeakHashMap .Entry

    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;
        }
        ...
        ...
        ...

HashMap.Node

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        ...
        ...
        ...

对比从上面WeakHashMap和HashMap节点类的实现可以看出,WeakHashMap把key封装成一个弱引用对象。

想深入了解WeakHashMap的弱键,那么就必须先了解 ReferenceQueue 和 WeakReference。文章篇幅有限,不多做讲解,有兴趣的朋友可以自己研究。

赞(0) 打赏
版权归原创作者所有,任何形式的转载请联系博主:daming_90:Java 技术驿站 » Java 8 容器源码-WeakHashMap

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏