2023-01-14  阅读(242)
原文作者: HelloWorld_EE 原文地址:https://blog.csdn.net/u010412719/category_6159934_2.html

《Java源码分析》:WeakHashMap

这篇博文就来看下WeakHashMap这个类的源码。博文的思路也是从继承结构、构造方法、常见的方法这些方面来分析WeakHashMap这个类的源码。

说明:WeakHashMap也是一个“数组和链表”的结合体

1、WeakHashMap的继承结构

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

WeakHashMap与HashMap一样,都是继承AbstractMap并实现了Map接口。与HashMap的区别在于并没有实现Cloneable和Serializable接口,这就导致WeakHashMap对象不能被克隆和序列化。

2、WeakHashMap的主要属性

源码中对这些属性的注释写的清晰好懂,我都舍不得对她进行翻译,怕对其都是一种践踏。因此,这里源码我就直接贴出来了。

想了想,这里还是对其进行说明下:

1、DEFAULT_INITIAL_CAPACITY=16:为默认容量

2、MAXIMUM_CAPACITY = 1 << 30;表示WeakHashMap所能分配空间的最大容量

3、DEFAULT_LOAD_FACTOR = 0.75f;默认加载因子

4、Entry

            /**
             * The default initial capacity -- MUST be a power of two.
             */
            private static final int DEFAULT_INITIAL_CAPACITY = 16;
    
            /**
             * The maximum capacity, used if a higher value is implicitly specified
             * by either of the constructors with arguments.
             * MUST be a power of two <= 1<<30.
             */
            private static final int MAXIMUM_CAPACITY = 1 << 30;
    
            /**
             * The load factor used when none specified in constructor.
             */
            private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
            /**
             * The table, resized as necessary. Length MUST Always be a power of two.
             */
            Entry<K,V>[] table;
    
            /**
             * The number of key-value mappings contained in this weak hash map.
             */
            private int size;
    
            /**
             * The next size value at which to resize (capacity * load factor).
             */
            private int threshold;
    
            /**
             * The load factor for the hash table.
             */
            private final float loadFactor;
    
            /**
             * Reference queue for cleared WeakEntries
             */
            private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

2、WeakHashMap的构造函数

下面这个构造函数和HashMap的构造函数基本一模一样。构造函数所做的事又如下两点:1)先对容量进行了有效性检查,如果有效,则开辟一个2的幂次方大小的数组空间,其中这个2的幂次方大于等于initialCapacity。

源码如下:(添加了一点注释)

        /*
            其它的构造方法都是调用此构造方法
            参数说明:
            initialCapacity:容量大小,默认值为 16
            loadFactor:加载因此,默认值为0.75
        */
        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;
            //保证容量为2的幂次方
            while (capacity < initialCapacity)
                capacity <<= 1;
            //分配数组空间
            table = newTable(capacity);
            this.loadFactor = loadFactor;
            //扩容门限有容量和加载因子的乘积决定
            threshold = (int)(capacity * loadFactor);
        }
    
    
        private Entry<K,V>[] newTable(int n) {
            return (Entry<K,V>[]) new Entry<?,?>[n];
        }

3、WeakHashMap中常见的一些方法介绍

对于所有的容器,添加元素和取得元素是两个最基本的方法。因此,这是我们研究的重点。对于WeakHashMap,添加元素的方法为:V put(K key, V value);根据key取得元素的方法为:V get(Object key)。

下面我们将分别详细的介绍这两个方法的原理。

3.1、put(K key, V value)介绍

此方法的功能为:向WeakHashMap中添加键值对

由于WeakHashMap与HashMap基本类似,因此,put方法的思路也基本一致。

具体如下:

第一步:检查key是否为null,如果为null,则将key用一个Object常量代替:NULL_KEY。在HashMap中是没有进行这样一个替代转换的,而是直接用null作为key存在在HashMap对象中。这是他们其中的一个区别

第二步:取得key的hash值,

第三步:根据hash值找到其在table的存储位置 i 。

第四步:由于table的每个位置存储的可能是一个链表,因此,在此位置 i处的链表中检测是否有此key存在,如果有,则更新其key所对应的value即可。如果没有此key,则将此节点加入到此链表的头结点位置。

在进行上面的4个步骤中,在第四步之前涉及到一个expunge Stale
Entries in table(翻译:在table中删除过时的条目)的一个处理。这个是在HashMap中没有的。

put方法(包括此方法中调用方法)源码如下:(添加了相关的注释)

        public V put(K key, V value) {
            /*
                第一步:对key进行是否为null的检测,如果为null,
                        则将key用一个Object常量代替:NULL_KEY
            */
            Object k = maskNull(key);
            /*
                第二步:取得key的hash值
            */
            int h = hash(k);
            Entry<K,V>[] tab = getTable();
            //第三步:根据key的hash值算出其在数组table中的存储位置i
            int i = indexFor(h, tab.length);
    
            /*
                第四步:检测存储位置中已存在的节点中是否已经此key了,
                        如果有,则更新value即可
                        如果没有,则把此节点添加在此位置的链表头
    
            */
            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++;
            //由于每个位置可能是一个链表,因此,将新节点加入到此位置的head位置
            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 final Object NULL_KEY = new Object();
    
        /**
         * Use NULL_KEY for key if it is null.
         */
        private static Object maskNull(Object key) {
            return (key == null) ? NULL_KEY : 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);
        }
        private Entry<K,V>[] getTable() {
            expungeStaleEntries();
            return table;
        }
        /**
         * Expunges stale entries from the table.
         *翻译:删除过时的条目,即将ReferenceQueue队列中的对象引用全部在table中给删除掉
         *思路:如何删除一个table的节点e,方法为:首先计算e的hash值,接着根据hash值找到其在table的位置,然后遍历链表即可。
         */
        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;
                    }
                }
            }
        }
    
        private static int indexFor(int h, int length) {
            return h & (length-1);//当length为2的幂次方时,等价于h%length
        }

3.1.1、resize(int newCapacity)介绍

对于任何容器,当存储数据的空闲位置到达门限时,都会进行扩容,WeakHashMap也不例外,因此,也有必要分析下此类的resize()方法。

扩容其实思想特简单,就是分配一个是原来空间的2倍的数组空间,接着进行一个数组的拷贝即可。其中,在进行上面步骤的过程中,涉及到一个特殊情况的处理。

方法的源码如下:(有一点主要注意:在tranfer方法中用到了Entry类的get方法,这个方法是WeakReference的父类Reference中的方法,此方法的功能是:获得该引用所指示的对象)

       /*
            函数的功能:扩容
    
        */
        void resize(int newCapacity) {
            Entry<K,V>[] oldTable = getTable();
            int oldCapacity = oldTable.length;
            //如果table所分配的空间已经是最大值,则还继续使用,不进行扩容
            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;
            }
        }
    
        /** Transfers all entries from src to dest tables */
        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();//得到引用对象WeakReference所指示的对象
                    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;
                }
            }
        }

3.2、get(Object key)介绍

上面介绍了put方法的思想,get方法实现的思想就相当简单了,get方法是想的思想具体如下:

get方法实现的思想与put的前3不是一模一样的。

第一步:检查key是否为null,如果为null,则将key用一个Object常量代替:NULL_KEY。在HashMap中是没有进行这样一个替代转换的,而是直接用null作为key存在在HashMap对象中。这是他们其中的一个区别

第二步:取得key的hash值,

第三步:根据hash值找到其在table的存储位置 i 。

第四步:由于table的每个位置存储的可能是一个链表,因此,在此位置 i处的链表中检测是否有此key存在,如果有,则取出其对应的value并返回即可。如果没有此key,则返回null。

源码如下:(有了上面put方法的思想,理解下面的源码就比较简单了,这里就没有写注释,如果不懂,可以参考put方法中详细的注释)

        public V get(Object key) {
            Object k = maskNull(key);
            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;
        }

3.3、containsKey(Object key)介绍

这里的containKey方法与上面介绍的get、put方法的实现思想类似。

源码如下:

        public boolean containsKey(Object key) {
            return getEntry(key) != null;
        }
    
        /**
         * Returns the entry associated with the specified key in this map.
         * Returns null if the map contains no mapping for this key.
         */
        Entry<K,V> getEntry(Object key) {
            Object k = maskNull(key);
            int h = hash(k);
            Entry<K,V>[] tab = getTable();
            int index = indexFor(h, tab.length);
            Entry<K,V> e = tab[index];
            while (e != null && !(e.hash == h && eq(k, e.get())))
                e = e.next;
            return e;
        }

3.4、remove(Object key)

remove方法也是我们在使用容器过程中,用的相当多的方法之一。因此也要必要进行介绍。

remove方法的思想:先根据key找到其在table的位置,然后就转换为了一个在链表中删除某一个节点的问题了。

具体思想描述如下:

第一步:检查key是否为null,如果为null,则将key用一个Object常量代替:NULL_KEY。在HashMap中是没有进行这样一个替代转换的,而是直接用null作为key存在在HashMap对象中。这是他们其中的一个区别

第二步:取得key的hash值,

第三步:根据hash值找到其在table的存储位置 i 。

第四步:由于table的每个位置存储的可能是一个链表,因此就转化为了一个在删除链表中某一个节点的问题了。

        public V remove(Object key) {
            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--;
                    if (prev == e)
                        tab[i] = next;
                    else
                        prev.next = next;
                    return e.value;
                }
                prev = e;
                e = next;
            }
    
            return null;
        }

3.5、其它方法介绍

下面是size()方法与之所以拿出来分析下,是因为,这个方法与HashMap方法中size()不一样。在HashMap中的size()方法中,仅仅是返回数组table中存储数据的长度,而这里的size()方法在返回长度之前做了一个:”删除table中过时的数据”这里一个操作,然后才返回数组存储数据的长度的,即返回的是table中真正有意义的数据。这也是HashMap与WeakHashMap的区别之一

        public int size() {
            if (size == 0)
                return 0;
            expungeStaleEntries();
            return size;
        }
    
        /**
         * Returns <tt>true</tt> if this map contains no key-value mappings.
         * This result is a snapshot, and may not reflect unprocessed
         * entries that will be removed before next attempted access
         * because they are no longer referenced.
         */
        public boolean isEmpty() {
            return size() == 0;
        }

总结

WeakHashMap和HashMap一样,WeakHashMap也是一个散列表,它存储的内容也是键值对(key-value)映射,而且键和值都可以为null。不过WeakHashMap的键时“弱键”,当WeakHashMap某个键不再正常使用时,会被从WeakHashMap自动删除。更精确的说,对于一个给定的键,其映射的存在并不能阻止垃圾回收器对该键的丢弃,这就使该键称为被终止的,被终止,然后被回收,这样,这就可以认为该键值对应该被WeakHashMap删除。因此,WeakHashMap使用了弱引用作为内部数据的存储方案,,WeakHashMap可以作为简单缓存表的解决方案,当系统内存不足时,垃圾收集器会自动的清除没有在任何其他地方被引用的键值对。如果需要用一张很大的Map作为缓存表时,那么可以考虑使用WeakHashMap。

关于WeakHashMap与HashMap的更多区别请看下篇博文。

阅读全文
  • 点赞