美文网首页数据结构和算法分析程序员
Java集合源码分析-WeakHashMap

Java集合源码分析-WeakHashMap

作者: 宛丘之上兮 | 来源:发表于2018-11-20 12:05 被阅读1次

    这是分析Java的map类集合的最后一篇文章了,写完这一篇打算分析java.util.concurrent包下的并发集合源码。

    《淮南子•缪称训》:“欲知天道,察其数;欲行地道,物其树;欲知人道,从其欲”,所以想要清楚WeakHashMap的底层原理,首先要知道WeakHashMap上层应用的具体表现,如果都不知道WeakHashMap的上层表现,探究其实现原理还是需要点天赋的。

    举个例子:

        public static void main(String args[]) {
            Map<Object, Object> map = new HashMap<>();
            for(int i = 0;i < 10000;i++) {
                byte[] bytes = new byte[1024 * 1024];
                map.put(bytes, value);
            }
            System.out.println("map.size->" + map.size());
        }
    

    上面的代码意思是说向一个HashMap中添加10000(您可以适当改变这个数来触发OOM,比如1800)个数据,每个数据的key的大小是1M,也就是说试图分配10GB的内存,在我的电脑上运行的结果是(运行的时候最好加上调优参数-Xms -Xmx -Xss -Xmn来自定义heap的大小,否则可能会遇到一些麻烦)

    $ java -XX:+HeapDumpOnOutOfMemoryError  Test
    java.lang.OutOfMemoryError: Java heap space
    Dumping heap to java_pid16056.hprof ...
    Heap dump file created [1868282017 bytes in 56.761 secs]
    Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
            at Test.main(Test.java:80)
    

    运行时的参数-XX:+HeapDumpOnOutOfMemoryError表示当发生OOM的时候会自动拿到内存转储 引文,这个参数会在当前目录生成一个名字叫 java_pidXXX.hprof的文件。我的当前目录生成了一个名叫java_pid16056.hprof的大小为1.7G的文件(好大的文件,电脑卡了好久,麻烦就在此),用Eclipse Memory analyzer / MAT打开这个文件,文件的overview如图所示:

    上图可以看出java.lang.Thread @ 0x84602830 main自身占用的内存大小(即shadow size,不包括它引用的对象)只有120B,而retained size(Retained Size=当前对象大小+当前对象可直接或间接引用到的对象的大小总和)达到1.7GB,我们可以利用Histogram查看它引用的对象和大小。

    MAT提供了2个非常有用的功能: 1. Histogram列出了每个对象的名字、数量和大小; 2. Dominator Tree会将内存中的对象按大小进行排序,可以分析对象之间的引用链。
    首先看下Histogram,

    可以看到,byte[]的内存达到了1866519072个字节即1.7GB(

    如果把map的类型改为WeakHashMap(其余代码不变),运行结果是

    $ java -XX:+HeapDumpOnOutOfMemoryError  Test
    map.size->72
    

    可以看到并没有发生OOM,因此也不会进行内存转储,可以看到map中只有72个对象也就是最大分配72M。

    {\color{blue}{1\ WeakHashMap}} 类图

    可以看到WeakHashMap的类图很简单,跟HashMap不同的地方在于WeakHashMap没有实现Cloneable和Serializable。

    {\color{blue}{2\ WeakHashMap}}构造器和成员变量

        private static final int DEFAULT_INITIAL_CAPACITY = 16;
        private static final int MAXIMUM_CAPACITY = 1073741824;
        private static final float DEFAULT_LOAD_FACTOR = 0.75F;
        WeakHashMap.Entry<K, V>[] table;
        private int size;
        private int threshold;
        private final float loadFactor;
        private final ReferenceQueue<Object> queue;
        int modCount;
        private static final Object NULL_KEY = new Object();
        private transient Set<java.util.Map.Entry<K, V>> entrySet;
    

    和HashMap一样,WeakHashMap也定义了四个构造器:

        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);
            int capacity = 1;
            while (capacity < initialCapacity)
                capacity <<= 1;
            table = newTable(capacity);
            this.loadFactor = loadFactor;
            threshold = (int)(capacity * loadFactor);
        }
    
        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);
        }
    

    任何一个集合类,它的节点类都是很重要的,我们来看下WeakHashMap的节点类:

        private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
            V value;
            final int hash;
            Entry<K,V> next;
    
            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;
            }
    
            @SuppressWarnings("unchecked")
            public K getKey() {
                return (K) WeakHashMap.unmaskNull(get());
            }
    
            public V getValue() {
                return value;
            }
    
            public V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            public boolean equals(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                K k1 = getKey();
                Object k2 = e.getKey();
                if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                    V v1 = getValue();
                    Object v2 = e.getValue();
                    if (v1 == v2 || (v1 != null && v1.equals(v2)))
                        return true;
                }
                return false;
            }
    
            public int hashCode() {
                K k = getKey();
                V v = getValue();
                return Objects.hashCode(k) ^ Objects.hashCode(v);
            }
        }
    

    回顾下介绍HashMap的文章:Java集合源码分析-HashMap和IdentityHashMap,我们不难发现两者节点的不同:

    1. WeakHashMap的节点类继承自WeakReference
    2. WeakHashMap的节点类的key变成了弱引用,value保持不变

    所以,WeakHashMap底层的数据结构和HashMap是一样的,都是hash桶+链表,jdk1.8HashMap加入了红黑树的优化,不过WeakHashMap并没有采用红黑树。HashMap的1.7和1.8版本的代码差别非常大,WeakHashMap的1.7版本和1.8版本的代码基本一样的。

    由于节点类继承了弱引用,还有一个ReferenceQueue<Object>类型的成员变量queue,那么我们需要介绍下Java中的四种引用和引用队列ReferenceQueue,只有熟悉这两个东西才能搞懂WeakHashMap的工作原理。

    {\color{blue}{2.1\ Java}}中四种引用类型

    Java的引用类放在Java.lang.ref包中,这个包是Java 类库中比较特殊的,这个包在用来实现与缓存相关的应用时特别有用。同时该包也提供了在对象的“可达”性发生改变时,进行提醒的机制。

    先看下这个包下的类结构:

    Java开发者无需关心内存的申请、释放和垃圾回收,这些事情都由JVM处理,以我所知,JVM提供了Reference(引用)机制,让我们能够在应用的层次利用内存或者GC特性,从而更好的使用内存。

    • StrongReference(强引用)
      每当new一个对象出来,这种引用便是强引用。 JVM利用Finalizer来管理每个强引用对象 , 并将其被标记要清理时加入 ReferenceQueue, 并逐一调用该对象的 finalize() 方法。
    • SoftReference(软引用)
      当内存足够的时候,软引用所指向的对象没有其他强引用指向的话,GC的时候并不会被回收,当且只当内存不够时(Heap 内存是否临近阈值)才会被GC回收(调用finalize方法)。强度仅次于强引用; get()方法取得对象的强引用从而访问目标对象;当垃圾回收器决定对其回收时,会先清空它的 SoftReference,也就是说 SoftReference 的 get()方法将会返回 null,并在下一轮 GC 中调用对象的 finalize() 方法对其真正进行回收。
    • WeakReference(弱引用)
      基本与软引用相似,指向的对象没有任何强引用指向的话,GC的时候会进行回收,比SoftReference更容易被回收;get()方法取得对象的强引用从而访问目标对象。
    • PhantomReference(虚引用)
      虚引用在系统垃圾回收器开始回收对象时 , 将直接调用 finalize() 方法 , 但不会立即将其加入回收队列,只有在真正对象被 GC 清除时,才会将其加入引用队列中去。它类似强引用,不会自动根据内存情况自动对目标对象回收,在Heap里不断开辟新空间,当达到heap阈值时,系统报出 OOM异常。

    其实后三种我们都可以称之为“弱引用”,看下他们的源码。
    SoftReference的源码:

    public class SoftReference<T> extends Reference<T> {
        static private long clock;
        private long timestamp;
    
        public SoftReference(T referent) {
            super(referent);
            this.timestamp = clock;
        }
    
        public SoftReference(T referent, ReferenceQueue<? super T> q) {
            super(referent, q);
            this.timestamp = clock;
        }
    
        public T get() {
            T o = super.get();
            if (o != null && this.timestamp != clock)
                this.timestamp = clock;
            return o;
        }
    }
    

    WeakReference的源码:

    public class WeakReference<T> extends Reference<T> {
        public WeakReference(T referent) {
            super(referent);
        }
    
        public WeakReference(T referent, ReferenceQueue<? super T> q) {
            super(referent, q);
        }
    }
    

    PhantomReference的源码:

    public class PhantomReference<T> extends Reference<T> {
        public T get() {
            return null;
        }
    
        public PhantomReference(T referent, ReferenceQueue<? super T> q) {
            super(referent, q);
        }
    }
    

    在PhantomReference的源码中,get()方法永远返回null,所以无法获取对象也无法使用该对象,而且和其它两个“弱引用”不一样的是,PhantomReference只提供了一个构造器,而其它两个“弱引用”都有两个构造器,那么PhantomReference 到底什么用呢?
    首先一个知识点我们需要知道:虚引用的目标对象被回收前,它的引用会被放入一个 ReferenceQueue 对象中,这也是虚引用只提供一个构造器的原因(这个构造器的第二个参数就是引用队列)。因此虚引用主要被用来跟踪对象被垃圾回收的状态,通过查看引用队列中是否包含对象所对应的虚引用来判断它是否被被垃圾回收,从而做一些自己想做的东西或操作。虚引用对目标对象并不感兴趣也不想获取它的强引用,所以get()方法永远返回null。

    后三种引用被回收的时机以及用法各不相同,下面总结的表格参考自IBM的文章-深入探讨 java.lang.ref 包

    引用类型 取得目标对象方式 垃圾回收条件 是否可能内存泄漏
    强引用 直接调用 不回收 可能
    软引用 通过 get() 方法 视内存情况回收 不可能
    弱引用 通过 get() 方法 永远回收 不可能
    虚引用 无法取得 不回收 可能

    举个SoftReference的例子1:

        public static void main(String args[]) {//1
            String t = new String("T");//2
            ReferenceQueue<String> refQueue = new ReferenceQueue<String>();//3
            SoftReference<String> referent = new SoftReference<String>(new String("T"), refQueue);//4
            System.out.println(referent.get());//5
            System.gc();//6
            System.runFinalization();//7
            System.out.println(referent.get());//8
            Object pO = refQueue.poll();//9
            System.out.println(pO + "  " + (pO == referent));//10
        }
    

    要读懂上面的代码,您需要明白第6行和第7行的意思(我不知道怎么让代码显示行数,心碎)。System.gc()意思是告诉垃圾收集器打算进行垃圾收集,只是有了打算但不一定执行回收;System.runFinalization()必须在垃圾回收器有了回收垃圾的打算才有效,所以必须配合System.gc()使用,它会强制调用已经失去所有强引用的对象的finalize方法进行回收。
    第五行获取目标对象的强引用,所以打印T,经过第6行和第7行的操作,由于软引用回收的条件是目标对象没有强引用并且内存紧张,我写测试代码的时候电脑的内存足够的,所以引用不会被回收,引用队列也是空的,因此第8行打印T,第10行打印null false

    $ java -XX:+HeapDumpOnOutOfMemoryError  -Xms200m -Xmx200m  -Xss512k -Xmn2g Test
    T
    T
    null  false
    

    举个WeakReference的例子2:

        public static void main(String args[]) {//1
            String t = new String("T");//2
            ReferenceQueue<String> refQueue = new ReferenceQueue<String>();//3
            WeakReference<String> referent = new WeakReference<String>(new String("T"), refQueue);//4
            System.out.println(referent.get());//5
            System.gc();//6
            System.runFinalization();//7
            System.out.println(referent.get());//8
            Object pO = refQueue.poll();//9
            System.out.println(pO + "  " + (pO == referent));//10
        }
    

    第五行获取目标对象的强引用,所以打印T,经过第6行和第7行的操作,由于目标对象没有强引用,它的弱引用会放到引用队列中,所以第8行打印null,第10行打印java.lang.ref.WeakReference@1c20c684 true

    $ java -XX:+HeapDumpOnOutOfMemoryError -Xms200m -Xmx200m  -Xss512k -Xmn2g Test
    T
    null
    java.lang.ref.WeakReference@1c20c684  true
    

    举个PhantomReference的例子3:

        public static void main(String args[]) {//1
            String t = new String("T");//2
            ReferenceQueue<String> refQueue = new ReferenceQueue<String>();//3
            PhantomReference<String> referent = new PhantomReference<String>(new String("T"), refQueue);//4
            System.out.println(referent.get());//5
            System.gc();//6
            System.runFinalization();//7
            System.out.println(referent.get());//8
            Object pO = refQueue.poll();//9
            System.out.println(pO + "  " + (pO == referent));//10
        }
    

    第五行获取目标对象的强引用,所以打印null,经过第6行和第7行的操作,由于目标对象没有强引用,它的弱引用会放到引用队列中,所以第8行打印null,第10行打印java.lang.ref.WeakReference@1c20c684 true

    $ java -XX:+HeapDumpOnOutOfMemoryError -Xms200m -Xmx200m  -Xss512k -Xmn2g Test
    T
    null
    java.lang.ref.WeakReference@1c20c684  true
    

    前面写了三个例子,如果把每个例子的第4行构造器的第一个参数改为字符串常量"T"PhantomReference<String> referent = new PhantomReference<String>("T", refQueue);//4,您可以自己实验会发生什么结果。解释下,如果参数改成了字符串常量,那么它是存在强引用的,这个强引用就是第二行的t,因此对象不会被垃圾回收,您需要对字符串的常量池机制有所了解就会明白原因,没什么技术含量。

    {\color{blue}{2.2\ FinalReference}}以及{\color{blue}{Finalizer}}

    FinalReference 是java.lang.ref里的一个包权限的类,因此不能被开发者使用,Finalizer是它的子类并且是final类和包权限,它俩肯定只能被JVM调用,那么它俩什么作用呢?

    java.lang.ref包下并没有StrongReference这个类,那么强引用的概念怎么来的呀?其实FinalReference代表的正是强引用,如这样的代码 :String fs = new String("fsfss");JVM就给它创建一个看门狗(watchdog)来引用它,这个看门狗就是一个Finalizer实例, Finalizer在JVM中定义了一个FinalizerThread守护线程,JVM依靠这个线程的run方法对所有的解除了强引用内存进行清理。

    让我们来看看 Finalizer工作流程。Finalizer含有五个成员变量:

        private static ReferenceQueue<Object> queue = new ReferenceQueue<>();
        private static Finalizer unfinalized = null;
        private static final Object lock = new Object();
        private Finalizer next = null, prev = null;
    

    这个类有个static初始化块:

        static {
            ThreadGroup tg = Thread.currentThread().getThreadGroup();
            for (ThreadGroup tgn = tg;
                 tgn != null;
                 tg = tgn, tgn = tg.getParent());
            Thread finalizer = new FinalizerThread(tg);
            finalizer.setPriority(Thread.MAX_PRIORITY - 2);
            finalizer.setDaemon(true);
            finalizer.start();
        }
    

    这个初始化块声明并实例化一个FinalizerThread,将它设置为守护线程后,加入系统线程中去。在 GC 的过程中,当一个对象没了强引用(不包含Finalizer类的引用,这个引用是看门狗),垃圾收集器会标记该对象,然后会被加入到Finalizer对象中的static变量queue引用队列中去,FinalizerThread正在那里通过for死循环守株待兔地等着加入到引用队列的Finalizer实例,不信的话请看源码:

        private static class FinalizerThread extends Thread {
            private volatile boolean running;
            FinalizerThread(ThreadGroup g) {
                super(g, "Finalizer");
            }
            public void run() {
                // in case of recursive call to run()
                if (running)
                    return;
                // Finalizer thread starts before System.initializeSystemClass
                // is called.  Wait until JavaLangAccess is available
                while (!VM.isBooted()) {
                    // delay until VM completes initialization
                    try {
                        VM.awaitBooted();
                    } catch (InterruptedException x) {
                        // ignore and continue
                    }
                }
                final JavaLangAccess jla = SharedSecrets.getJavaLangAccess();
                running = true;
                for (;;) {
                    try {
                        Finalizer f = (Finalizer)queue.remove();
                        f.runFinalizer(jla);
                    } catch (InterruptedException x) {
                        // ignore and continue
                    }
                }
            }
        }
    

    上面的源码清晰地告诉我们:这个线程的run方法中有一个for死循环,每当引用队列里加入了一个对象,那么线程就取出来并调用对象的runFinalizer方法,看下runFinalizer源码:

        private void runFinalizer(JavaLangAccess jla) {
            synchronized (this) {
                if (hasBeenFinalized()) return;
                remove();
            }
            try {
                Object finalizee = this.get();
                if (finalizee != null && !(finalizee instanceof java.lang.Enum)) {
                    jla.invokeFinalize(finalizee);
                    /* Clear stack slot containing this variable, to decrease
                       the chances of false retention with a conservative GC */
                    finalizee = null;
                }
            } catch (Throwable x) { }
            super.clear();
        }
    

    上面的代码中调用了invokeFinalize方法。

    再来看下Finalizer的构造器:

        private Finalizer(Object finalizee) {
            super(finalizee, queue);
            add();
        }
    

    看到上面的代码,你有什么疑惑吗?这个构造器给我们留下三个疑问:首先,是谁调用了这个构造器,然后在什么时候调用的呢?最后,add方法干啥的?
    对于第一个疑问,有一点可以肯定的是,开发者无法主动调用构造器,那么只能是JVM调用了,Finalizer提供了一个register方法:

        static void register(Object finalizee) {
            new Finalizer(finalizee);
        }
    

    register方法中调用了构造器,JVM就是通过register方法来创建Finalizer对象的。

    第二个疑问,JVM什么时候调用register方法呢?这个疑问让我有点抓狂,网上看了一些分析,头大。
    对象的创建是分为很多步骤的,一步是先执行new分配好对象空间,一步是再执行invokespecial调用构造函数,jvm里其实可以让用户选择在这两个步骤中的任意一个将当前对象传递给Finalizer.register方法来注册。《JVM源码分析之Java对象的创建过程》一文中分析了Java对象创建的整个过程。另外需要提一点的是当通过clone的方式复制一个对象的时候,如果当前类是一个finalizer类,那么在clone完成的时候将调用Finalizer.register方法进行注册。
    一个构造函数执行的时候,会去调用父类的构造函数,主要是为了能对继承自父类的属性也能做初始化,那么任何一个对象的初始化最终都会调用到Object的空构造函数里,任何空的构造函数其实并不空,会含有三条字节码指令,如下:

    0: aload_0
    1: invokespecial #21                 // Method java/lang/Object."<init>":()V
    4: return
    

    为了不对所有的类的构造函数都做埋点调用Finalizer.register方法,hotspot的实现是在Object这个类在做初始化的时候将构造函数里的return指令替换为_return_register_finalizer指令,该指令并不是标准的字节码指令,是hotspot扩展的指令,这样在处理该指令的时候调用Finalizer.register方法,这样就在侵入性很小的情况下完美地在构造函数执行完毕后调用Finalizer.register。在JVM中通过JavaCalls::call触发register方法。

    需要注意的是我们的类在被加载过程中其实就已经被标记为需要注册了(遍历所有方法,包括父类的方法,只要有一个非空的参数为空返回void的finalize方法并且方法体不为空,那么就注册)。

    第三个疑问,add方法干啥的?看下源码:

        private void add() {
            synchronized (lock) {
                if (unfinalized != null) {
                    this.next = unfinalized;
                    unfinalized.prev = this;
                }
                unfinalized = this;
            }
        }
    

    代码很简单,其实就是插入到Finalizer双向链中,而且是从头部插入的;Finalizer双向链里的对象和Finalizer类静态相关联,言外之意是在这个链里的对象都无法被gc掉,除非将这种引用关系剥离掉(因为Finalizer类无法被unload)。

    那么问题来了,如何剥离Finalizer双向链呢?之前我们介绍了那个守护线程FinalizerThread,这个线程正在那里通过for死循环守株待兔地等着加入到引用队列的Finalizer实例,通过引用队列的remove方法将实例取出,并调用Finalizer实例的runFinalizer方法,这个方法源码在前面已经贴出来了,这里需要仔细分析下runFinalizer的源码,在源码中首先调用了remove方法,看下源码:

        private void remove() {
            synchronized (lock) {
                if (unfinalized == this) {
                    if (this.next != null) {
                        unfinalized = this.next;
                    } else {
                        unfinalized = this.prev;
                    }
                }
                if (this.next != null) {
                    this.next.prev = this.prev;
                }
                if (this.prev != null) {
                    this.prev.next = this.next;
                }
                this.next = this;   /* Indicates that this has been finalized */
                this.prev = this;
            }
        }
    

    这个代码是不是很熟悉呢?没错,就是双向链表的删除节点的操作,这就把Finalizer对象从Finalizer对象链里剥离出来即意味着下次gc发生的时候就可能将其关联的finalizer对象gc掉了。最后调用了invokeFinalize方法,这个方法其实调用的就是Object的finalize方法。

    如果在Finalizer对象的finalize方法里重新将当前对象赋值出去,变成可达对象,当这个Finalizer对象再次变成不可达的时候还会被执行finalize方法吗?答案是否定的,因为在执行完第一次finalize方法之后,这个finalizer对象已经和之前的Finalizer对象关系剥离了,也就是下次gc的时候不会再发现Finalizer对象指向该finalizer对象了,自然也就不会调用这个finalizer对象的finalize方法了。

    当gc发生的时候,gc算法会判断对象是不是只被看门狗引用(对象被看门狗引用,然后放到Finalizer对象链里),如果这个对象仅仅被看门狗引用的时候,说明这个对象在不久的将来会被回收了现在可以执行它的finalize方法了,于是会将这个对象的看门狗放到Finalizer类的ReferenceQueue里,但是这个对象其实并没有被回收,因为看门狗还对他们持有引用,在gc完成之前,JVM会调用ReferenceQueue里的lock对象的notify方法(当ReferenceQueue为空的时候,FinalizerThread线程会调用ReferenceQueue的lock对象的wait方法直到被jvm唤醒),此时就会执行上面FinalizeThread线程里看到的其它逻辑了。

    还有一个问题,护线程FinalizerThread在守株待兔地等着加入到引用队列的Finalizer实例,那么Finalizer实例是在什么情况下才会被插入到ReferenceQueue队列中?

    这要看Finalizer的祖父类Reference的源码,它中定义了ReferenceHandler线程,实现如下:

        private static class ReferenceHandler extends Thread {
    
            private static void ensureClassInitialized(Class<?> clazz) {
                try {
                    Class.forName(clazz.getName(), true, clazz.getClassLoader());
                } catch (ClassNotFoundException e) {
                    throw (Error) new NoClassDefFoundError(e.getMessage()).initCause(e);
                }
            }
    
            static {
                // pre-load and initialize InterruptedException and Cleaner classes
                // so that we don't get into trouble later in the run loop if there's
                // memory shortage while loading/initializing them lazily.
                ensureClassInitialized(InterruptedException.class);
                ensureClassInitialized(Cleaner.class);
            }
    
            ReferenceHandler(ThreadGroup g, String name) {
                super(g, name);
            }
    
            public void run() {
                while (true) {
                    tryHandlePending(true);
                }
            }
        }
    
        static boolean tryHandlePending(boolean waitForNotify) {
            Reference<Object> r;
            Cleaner c;
            try {
                synchronized (lock) {
                    if (pending != null) {
                        r = pending;
                        // 'instanceof' might throw OutOfMemoryError sometimes
                        // so do this before un-linking 'r' from the 'pending' chain...
                        c = r instanceof Cleaner ? (Cleaner) r : null;
                        // unlink 'r' from 'pending' chain
                        pending = r.discovered;
                        r.discovered = null;
                    } else {
                        // The waiting on the lock may cause an OutOfMemoryError
                        // because it may try to allocate exception objects.
                        if (waitForNotify) {
                            lock.wait();
                        }
                        // retry if waited
                        return waitForNotify;
                    }
                }
            } catch (OutOfMemoryError x) {
                // Give other threads CPU time so they hopefully drop some live references
                // and GC reclaims some space.
                // Also prevent CPU intensive spinning in case 'r instanceof Cleaner' above
                // persistently throws OOME for some time...
                Thread.yield();
                // retry
                return true;
            } catch (InterruptedException x) {
                // retry
                return true;
            }
    
            // Fast path for cleaners
            if (c != null) {
                c.clean();
                return true;
            }
    
            ReferenceQueue<? super Object> q = r.queue;
            if (q != ReferenceQueue.NULL) q.enqueue(r);
            return true;
        }
    

    这个线程在Reference类的static构造块中启动,并且被设置为高优先级Thread.MAX_PRIORITY和daemon状态。此线程要做的事情,是不断的检查pending 是否为null,如果pending不为null,则将pending进行enqueue,否则线程进入wait状态。当pending被设置时,会调用ReferenceQueue的enqueue方法把Finalizer对象插入到ReferenceQueue队列中,接着通过notifyAll方法唤醒FinalizerThread线程执行后续逻辑,实现如下:

        boolean enqueue(Reference<? extends T> r) { /* Called only by Reference class */
            synchronized (lock) {
                // Check that since getting the lock this reference hasn't already been
                // enqueued (and even then removed)
                ReferenceQueue<?> queue = r.queue;
                if ((queue == NULL) || (queue == ENQUEUED)) {
                    return false;
                }
                assert queue == this;
                r.queue = ENQUEUED;
                r.next = (head == null) ? r : head;
                head = r;
                queueLength++;
                if (r instanceof FinalReference) {
                    sun.misc.VM.addFinalRefCount(1);
                }
                lock.notifyAll();
                return true;
            }
        }
    

    那么问题来了,pending字段什么时候会被设置?

    在GC过程的引用处理阶段,通过oopDesc::atomic_exchange_oop方法把发现的引用列表设置在pending字段所在的地址:

    你可能还不太理解pending状态是什么意思,那么需要看下所有引用类的父类Reference,这个类包含四个状态:

    1. Active: queue = ReferenceQueue with which instance is registered,
      or ReferenceQueue.NULL if it was not registered with a queue; next = null.
    2. Pending: queue = ReferenceQueue with which instance is registered;
      next = Following instance in queue, or this if at end of list.
    3. Enqueued: queue = ReferenceQueue.ENQUEUED; next = Following instance
      in queue, or this if at end of list.
    4. Inactive: queue = ReferenceQueue.NULL; next = this.

    下面的表格引用自资料

    Reference State queue next discovered
    Active ReferenceQueue(registered)或ReferenceQueue.NULL(unregistered) NULL next element in a discovered reference list by GC(or this if last)
    Pending ReferenceQueue(registered) this next element in the pending list(or NULL if last)
    Enqueued ReferenceQueue.ENQUEUED next reference in queue(or this if last) NULL
    Inactive ReferenceQueue.NULL this NULL

    下面的图片同样引用自资料

    Reference状态转移图

    还有一点需要特别注意,那就是Finalizer的守护线程的优先级比主线程低,如果对象自己实现了finalize()方法,那么调用finalize()方法就会发生在主线程而非守护线程,主线程的操作会和我们的守护线程进行竞争,不过由于我们的守护线程的优先级较低,得到的CPU时间较少,因此它永远比主线程慢一个节拍,这时候主线程做了一些危险的操作就可能导致OOM。

    所以,这里给出一个启示录:当你考虑使用finalize()方法而不是使用常规的JVM的gc方式来清理对象的时候,最好三思而后行;你可能会因为覆盖了finalize()这样的奇技淫巧而沾沾自喜,但是不停增长的Finalizer队列也许会撑爆你的年老代区域(tenured space),你需要考虑一下重新设计你的方案。参考文献

    {\color{blue}{3\ WeakHashMap}}核心操作

    用WeakHashMap的get、put、remove方法都会有一个副作用,即通过方法expungeStaleEntries来清除无效key对应的Entry。

    {\color{blue}{3.1\ put}}

        public V put(K key, V value) {
            Object k = maskNull(key);
            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);
            if (++size >= threshold)
                resize(tab.length * 2);
            return null;
        }
    

    可以看到首先调用getTable方法获取原来的hash桶。有人会问,原来的hash桶不就是成员变量table吗,直接使用table不就行了吗?您说的没错,但是原来的table包含无效的key,那么就要先清理调。怎么清理呢?那么需要看下getTable的源码:

        private Entry<K,V>[] getTable() {
            expungeStaleEntries();
            return 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;
                    }
                }
            }
        }
    

    可以看到是使用expungeStaleEntries进行清理的,要读懂expungeStaleEntries()这个方法的源码,你必须明白引用队列queue的作用,所有的失效的key都会放到这个引用队列中,因此用一个for循环取出队列里的key对象e,利用这个key的hash计算它的桶位i,用一个while循环遍历桶位i里的链表,找到和对象e相等的key,删掉并size--;

    清理完无效的key,那么直接插入新的key就好了,这段插入的代码和Hashtable的代码是一模一样的,不清楚Hashtable的话可以看下这篇文章:Java集合源码分析-Hashtable,都是插入到链的头部,这和HashMap不太一样,HashMap是将新节点插入到链的尾部:Java集合源码分析-HashMap。插入完之后判断是否需要进行扩容,扩容是以2倍方式进行的,看下扩容方法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;
            }
        }
    

    源码中间有一段古怪的注释,注释前面的代码很好理解:首先以2倍容量新建一个数组newTable,然后通过transfer方法将老的hash桶的数据完全拷贝到新的hash桶newTable,通俗易懂。但是注释下面的ifelse代码是什么作用呢?这段代码是注释前面代码的逆操作,意思是说我后悔扩容了,为啥后悔了呢?跟size这个变量有关吧,我需要节省点内存,就改变阈值threshold,甚至如果size不太大就干脆反向操作不扩容了,这波操作666呀,代码还可以反悔(注释后面的代码含义是我的猜测)。

    {\color{blue}{3.2\ get}}

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

    对于get操作,需要注意的是调用了getTable方法进行无效key的清理。

    {\color{blue}{3.3\ remove}}

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

    对于remove操作,需要注意的是调用了getTable方法进行无效key的清理。

    {\color{blue}{4\ WeakHashMap}}遍历

    WeakHashMap提供了三个迭代器进行遍历KeyIterator、ValueIterator、EntryIterator,这三个迭代器有一个共同的基类:HashIterator,所以遍历操作都是HashIterator操作的,遍历是从hash桶的尾部向头部进行的,看下源码:

            public boolean hasNext() {
                Entry<K,V>[] t = table;
    
                while (nextKey == null) {
                    Entry<K,V> e = entry;
                    int i = index;
                    while (e == null && i > 0)
                        e = t[--i];
                    entry = e;
                    index = i;
                    if (e == null) {
                        currentKey = null;
                        return false;
                    }
                    nextKey = e.get(); // hold on to key in strong ref
                    if (nextKey == null)
                        entry = entry.next;
                }
                return true;
            }
    
            /** The common parts of next() across different types of iterators */
            protected Entry<K,V> nextEntry() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                if (nextKey == null && !hasNext())
                    throw new NoSuchElementException();
    
                lastReturned = entry;
                entry = entry.next;
                currentKey = nextKey;
                nextKey = null;
                return lastReturned;
            }
    

    有点不可思议的是,hasNext方法有两个while循环,nextEntry没有循环,这和我前面介绍的几个集合的遍历方式恰恰相反,比如HashMap的迭代器基类HashIterator,它的hasNext方法没有循环,nextNode只有一个while循环,由于HashMap的设计者极力保证链表的长度是1,所以这个while循环的时间复杂度可以认为是O(1),但是从源码上看,WeakHashMap遍历的时间复杂度有点复杂,如果遍历到链表的表尾(即(e = entry) == null),那么时间复杂度达到了恐怖的O(n^2)

    文章结束了,知识点有点多,有错误的地方希望指出。


    参考文献:
    深入分析Object.finalize方法的实现原理- 简书

    相关文章

      网友评论

        本文标题:Java集合源码分析-WeakHashMap

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