美文网首页
Java集合(七)--WeakHashMap简析

Java集合(七)--WeakHashMap简析

作者: swz_android | 来源:发表于2019-01-02 21:12 被阅读0次

    WeakHashMap是一个带有弱键的Map,即当某个键不再正常使用的时候,这个键就会被移除,它所对应的键值对也就被移除了。该类支持空键和空值,具有与HashMap相似的性能特征,有与初始容量和负载因子。WeakHashMap是非同步的。

    WeakHashMap的定义及说明

    定义如下:

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

    WeakHashMap的定义还是比较简单的,就是继承了AbstractMap,实现了Map。即拥有Map基本的属性和方法。

    构造方法

    构造方法如下:

    //最大的容量,如果具有参数的任一构造函数隐式指定较高值,则使用最大容量
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    
    //默认的初始容量,必须是2的次方
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    
    //默认的加载因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    //数组类型,实际是一个单链表,数组长度必须是2的次方
    Entry<K,V>[] table;
    
    //阈值(容量*loadFaactor)
    private int threshold;
    
    //加载因子
    private final float loadFactor;
    
    //WeakHashMap中包含的键值的数量
    private int size;
    
    //使用给定的初始容量和给定的加载因子构造一个新的空WeakHashMap。
    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);
            //计算初始容量(找到大于initialCapacity的最小的2的次方)
            int capacity = 1;
            while (capacity < initialCapacity)
                capacity <<= 1;
            //新建一个空数组
            table = newTable(capacity);
            this.loadFactor = loadFactor;
            threshold = (int)(capacity * loadFactor);
        }
    
    //使用给定的初始容量和默认加载因子(0.75)构造一个新的空WeakHashMap。
    public WeakHashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
    //使用默认初始容量(16)和加载因子(0.75)构造一个新的空WeakHashMap
    public WeakHashMap() {
            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
        }
    
    //使用与指定映射相同的映射构造一个新的WeakHashMap。 使用默认加载因子(0.75)创建WeakHashMap,且初始容量要足以保存指定映射中的映射。
    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。可以看到它与HashMap相类似,都有容量、加载因子、阈值以及都是单链表结构。怎么看出是一个单链表?看一下Entry就了然了:

    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
            //值
            V value;
            //hash值
            final int hash;
            //下个节点
            Entry<K,V> next;
    
            Entry(Object key, V value,
                  ReferenceQueue<Object> queue,
                  int hash, Entry<K,V> next) {
                 //通过WeakReference调用Reference的方法,使key注册到queue中,并且,key为弱引用
                super(key, queue);
                this.value = value;
                this.hash  = hash;
                this.next  = next;
            }
    
    }
    

    其中ReferenceQueue是一个引用队列,在检测到可到达性更改后,垃圾回收器将已注册的引用对象添加到队列中,主要是用于监听Reference所指向的对象是否已经被垃圾回收。通过"super(key, queue)"方法及其调用方法,使key成为一个弱引用对象,并将其注册到queue中,以便在key被GC的时候可以添加到queue中去。

    源码简析

    我们还是从put()方法入手,分析一下它的实现原理:

    //已清除的Entries的引用队列
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
    
    public V put(K key, V value) {
            //判断key是否为空
            Object k = maskNull(key);
            //获取key经过处理后的hashCode
            int h = hash(k);
            //获取当前(清除了被GC了的key所对应的映射) 的表
            Entry<K,V>[] tab = getTable();
            //返回哈希码h在数组中对应的索引
            int i = indexFor(h, tab.length);
            //获取i对应的索引位置的链表的首节点并遍历链表
            for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
                //判断hash值是否相等
                if (h == e.hash && eq(k, e.get())) {
                    //获取当前位置的旧值
                    V oldValue = e.value;
                    //新旧值不相等,则新值覆盖旧值
                    if (value != oldValue)
                        e.value = value;
                    //返回旧值,结束后面的操作
                    return oldValue;
                }
            }
           
            //修改次数加1
            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;
        }
    
    //对key的hashCode做处理
    final int hash(Object k) {
            //获取k的hashCode
            int h = k.hashCode();
            //hashCode混淆
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }
    
    //首次删除过时条目后返回表
    private Entry<K,V>[] getTable() {
            expungeStaleEntries();
            return table;
        }
    
    //从表中清除过时的条目
    private void expungeStaleEntries() {
            //遍历queue中的key(已被GC)
            for (Object x; (x = queue.poll()) != null; ) {
                synchronized (queue) {
                    @SuppressWarnings("unchecked")
                    //取出queue中的当前位置的元素    
                    Entry<K,V> e = (Entry<K,V>) x;
                    //获取该key在数组中的所对应的索引
                    int i = indexFor(e.hash, table.length);
                    //将当前key赋值与prev
                    Entry<K,V> prev = table[i];
                    Entry<K,V> p = prev;
                    //遍历索引i对应的链表
                    while (p != null) {
                        //获取p的下一个元素并赋值给next
                        Entry<K,V> next = p.next;
                        //判断p是否等于e(除了第一次轮询以外,其他情况下p = prev.next())
                        if (p == e) {
                            //判断prev是否等于e
                            if (prev == e)
                                //p和prev都等于e,则直接将数组索引为i的链表的首节点替换为next
                                table[i] = next;
                            else
                                //只有p等于e,则改变prev的下一个元素的指向,将其变为p的下一个元素,即删除p
                                prev.next = next;
                            //不得将e.next归零; 旧的条目可能被HashIterator使用
                            //置为空以方便GC回收
                            e.value = null;
                            //数组长度减一
                            size--;
                            break;
                        }
                        //重新赋值,以便再次循环
                        prev = p;
                        p = next;
                    }
                }
            }
        }
    
    
    //返回哈希码h对应的索引
    private static int indexFor(int h, int length) {
            return h & (length-1);
        }
    
    //调整数组大小
    void resize(int newCapacity) {
            //获取当前table数组
            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指向新数组
            table = newTable;
    
            //判断数组长度是否大于等于阈值的1/2
            if (size >= threshold / 2) {
                //重新计算阈值
                threshold = (int)(newCapacity * loadFactor);
            } else {
                //从表中清除过时的条目
                expungeStaleEntries();
                //将新元素移入旧的数组
                transfer(newTable, oldTable);
                //将table指向旧数组
                table = oldTable;
            }
        }
    
    //将所有条目从src传输到dest
    private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
            for (int j = 0; j < src.length; ++j) {
                //获取src指定位置的元素
                Entry<K,V> e = src[j];
                src[j] = null;
                //遍历指定索引下的链表
                while (e != null) {
                    Entry<K,V> next = e.next;
                    //获取key
                    Object key = e.get();
                    if (key == null) {
                        //key为null则将其next和value置为空,且数组长度减一
                        e.next = null;
                        e.value = null;
                        size--;
                    } else {
                        //获取e在dest数组中所对应的索引,并赋值
                        int i = indexFor(e.hash, dest.length);
                        e.next = dest[i];
                        dest[i] = e;
                    }
                    //赋值并重新开始循环
                    e = next;
                }
            }
        }
    
    

    从上面的分析中我们可以看出,WeakHashMap每次put一个元素,都会先删除table中不再正常使用的元素。然后再判断当前已有元素中的key是否有与要添加元素的key相同的,相同则覆盖其值,不同则将新元素添加如数组中。在这个过程中不再正常使用的键的原理为:当WeakHashMap中的键(弱引用)被GC回收时,该键会被添加到queue中。然后,在put过程中会执行expungeStaleEntries()方法,该方法会遍历queue中的key并删除WeakHashMap中与其key对应的键值对。

    在expungeStaleEntries()方法中,有一个queue.poll()方法,它是ReferenceQueue类中的方法,具体如下:

    
    //ReferenceQueue的队首
    private Reference<? extends T> head = null;
    
    //ReferenceQueue的队尾
    private Reference<? extends T> tail = null;
    
    //判断队列中是否为空,如果不为空,则取出链表中head位置的元素
    public Reference<? extends T> poll() {
            synchronized (lock) {
                if (head == null)
                    return null;
                return reallyPollLocked();
            }
        }
    
    //Reference.queueNext将设置为sQueueNextUnenqueued,以指示何时将引用放入队列并从队列中删除。
    private static final Reference sQueueNextUnenqueued = new PhantomReference(null, null);
    
    private Reference<? extends T> reallyPollLocked() {
            
            if (head != null) {
                Reference<? extends T> r = head;
                if (head == tail) {
                    tail = null;
                    head = null;
                } else {
                    head = head.queueNext;
                }
                //更新queueNext以指示引用已入队,但现在已从队列中删除。
                r.queueNext = sQueueNextUnenqueued;
                return r;
            }
    
            return null;
        }
    

    作用就是取出queue中的key,以方便从数组中删除。

    好了,本文到此结束。

    感觉自己博客写的好乱!!!后期要整理一下。

    相关文章

      网友评论

          本文标题:Java集合(七)--WeakHashMap简析

          本文链接:https://www.haomeiwen.com/subject/wumtrqtx.html