投稿
  1. 首页
  2. 随笔

【Java】WeakHashMap源码阅读笔记

周迅个人资料 • 2022-12-14 • 随笔 • 阅读 18

【Java】WeakHashMap源码阅读笔记,第1张

【Java】WeakHashMap源码阅读笔记

HashMap中如果一个键指向的对象没有其他任何引用指向它，也不会被GC回收，被map的桶接管了，存在强引用，只能手动remove。如果想要这种键值对被自动回收怎么办？带着问题看一下WeakHashMap的源码

WeakHashMap的属性

和HashMap中基本一样，不过WeakHashMap没有红黑树相关 *** 作，还多了个ReferenceQueue。

ReferenceQueue存的是什么呢？这里可以推出是那些指向被回收的对象的弱引用。

    
    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;

    
    Entry[] table;

    
    private int size;

    
    private int threshold;

    
    private final float loadFactor;

    
    private final ReferenceQueue queue = new ReferenceQueue<>();

    
    int modCount;
 

这里主要要看一下Entry[] table，注释中写的是The table, resized as necessary.明显是桶数组。其中的每个元素都是Entry类型的，也就是说链表的节点就是Entry类型的。
 

看一下Entry的定义：
 

    
    private static class Entry extends WeakReference implements Map.Entry {
        V value;
        final int hash;
        Entry next;

        
        Entry(Object key, V value,
              ReferenceQueue queue,
              int hash, Entry 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);
        }

        public String toString() {
            return getKey() + "=" + getValue();
        }
    }
 

分析出几点：
 

  1. Entry extends WeakReference说明Entry本身是一个弱引用，那它的构造函数一定能返回一个弱引用，指向的是传给父类构造函数的第一个参数。同时绑定了一个引用队列。当指向的对象被回收后，弱引用就入队。
  2. Entry 中包含一个属性Entry next，next指向的是下一个Entry对象，符合链表的定义。
  3. 第一次见到引用自身还能携带属性的，其中一个属性next又指向了同类的另一个引用，感觉有点绕。
 

偷来别人的图看一下：
 

 
WeakHashMap的构造函数 

有两个参数，table的初始容量，加载因子，生成了table数组，元素类型是Entry。
 

一般情况下用无参构造就行了。
 

    
    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(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public WeakHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    private Entry[] newTable(int n) {
        return (Entry[]) new Entry[n];
    }

 
WeakHashMap的一些工具方法 

    private static final Object NULL_KEY = new Object();
    private static Object maskNull(Object key) {
        return (key == null) ? NULL_KEY : key;
    }
    static Object unmaskNull(Object key) {
        return (key == NULL_KEY) ? null : key;
    }


    private static boolean eq(Object x, Object y) {
        return x == y || x.equals(y);
    }

    
    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 static int indexFor(int h, int length) {
        return h & (length-1);
    }

 

关键方法expungeStaleEntries，作用是移除Entry。
 

这些Entry有一个共同的特征：
 

    
    private void expungeStaleEntries() {
        //取出已经入队的弱引用x (Entry x)
        for (Object x; (x = queue.poll()) != null; ) {
            //一整个是一个同步块
            synchronized (queue) {
                @SuppressWarnings("unchecked")
                //现在e是出队的那个弱引用，指向的是一个原本有强引用key指向的对象
                    Entry e = (Entry) x;
                //e里面的属性hash配合table的长度来确定e当前在哪个桶
                int i = indexFor(e.hash, table.length);

                //prev是桶的第一个元素
                Entry prev = table[i];
                //经典的链表双指针遍历法
                Entry p = prev;
                //p往前走，prev跟在后面，直到p==e为止
                while (p != null) {
                    Entry next = p.next;
                    //找到了等于e的那个节点p
                    if (p == e) {
                        //这里说明e就是桶里的第一个元素
                        if (prev == e)
                            //直接置为next，e就从map中移除了
                            table[i] = next;
                        else
                            //不是第一个元素，跳过e
                            prev.next = next;
                        // Must not null out e.next;
                        // stale entries may be in use by a HashIterator
                        //到上面为止就已经完成了移除e
                        e.value = null; // Help GC
                        size--;
                        break;
                    }
                    prev = p;
                    p = next;
                }
            }
        }
    }

 

e这个东西是从引用队列里拿出来的，是一个弱引用，是对原本key指向的实际对象的一个弱引用。正是由于实际对象只剩这一个弱引用才会被GC回收。
 

然后e又是map中的一个元素，它本身是被强引用的，所以才有expungeStaleEntries()方法来从map中删除它的一个过程。
 

这里留了两个问题想不清楚：
 

  1. Must not null out e.next 是什么意思
  2. e.value = null; // Help GC 为什么要这样写
 
WeakHashMap的基 ***  
PUT 

    public V put(K key, V value) {
        //null也可以存进来
        Object k = maskNull(key);
        //计算key的hash
        int h = hash(k);
        //getTable()返回table，返回之前要expungeStaleEntries
        Entry[] tab = getTable();
        //计算出table中的下标
        int i = indexFor(h, tab.length);

        //遍历链表，如果找到key一样的，并且值不相等的，给新值
        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];
        //插在了链表头，next指向原来的第一个元素
        tab[i] = new Entry<>(k, value, queue, h, e);
        //判断size是否达到扩容条件
        if (++size >= threshold)
            resize(tab.length * 2);
        return null;
    }

    private Entry[] getTable() {
        expungeStaleEntries();
        return table;
    }

 
RESIZE 

    void resize(int newCapacity) {
        //拿到老表
        Entry[] oldTable = getTable();
        //老表长度看一下
        int oldCapacity = oldTable.length;
        //如果老表长度等于最大容量
        if (oldCapacity == MAXIMUM_CAPACITY) {
            //门槛设置为最大，这样put *** 作就不会总是进resize方法了
            threshold = Integer.MAX_VALUE;
            //扩不了了，结束
            return;
        }

        //来张新表
        Entry[] newTable = newTable(newCapacity);
        //元素迁移
        transfer(oldTable, newTable);
        table = newTable;

        
        //完成扩容之后，如果size大于门槛的1/2，门槛就按正常的设置为新的门槛
        //如果size不大于门槛的1/2，（size明显缩水了，可能是其他 *** 作中的
        //expungeStaleEntries导致的，transfer里面也可能导致size缩水
        if (size >= threshold / 2) {
            threshold = (int)(newCapacity * loadFactor);
        } else {
            expungeStaleEntries();
            transfer(newTable, oldTable);
            table = oldTable;
        }
    }


 
TRANSFER 

    private void transfer(Entry[] src, Entry[] dest) {
        //老表中的所有元素搬到新表
        for (int j = 0; j < src.length; ++j) {
            //j号桶的第一个元素
            Entry e = src[j];
            //老表的j号桶直接清空
            src[j] = null;
            while (e != null) {
                //拿到e的下一个元素
                Entry next = e.next;
                //对e做一些处理，e.get返回弱引用指向的实际对象，也就是key
                Object key = e.get();
                //如果key什么都没拿到
                if (key == null) {
                    //e不要了，把它的next和value都给null size--
                    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;
            }
        }
    }

 

这里又出现了Help GC的问题，不是很懂。
 

为什么这里可以写e.next = null了？而expungeStaleEntries方法里不写呢（Must not null out e.next说的是不是e.next不可以为null？）
 
containsValue 

    public boolean containsValue(Object value) {
        if (value==null)
            return containsNullValue();
        //主要看一下遍历方式：先数组，再链表
        Entry[] tab = getTable();
        for (int i = tab.length; i-- > 0;)
            for (Entry e = tab[i]; e != null; e = e.next)
                if (value.equals(e.value))
                    return true;
        return false;
    }

 
get 

    public V get(Object key) {
        //key为null也能查出来，NULL_KEY是一个 static final，计算出的hash总是一样
        Object k = maskNull(key);
        int h = hash(k);
        Entry[] tab = getTable();
        int index = indexFor(h, tab.length);
        Entry e = tab[index];
        //找到对应的桶，走一下链表
        while (e != null) {
            //看一下这里是怎么拿到key的，key不是e的属性，而是e弱引用的对象，直接get
            if (e.hash == h && eq(k, e.get()))
                return e.value;
            e = e.next;
        }
        return null;
    }

 
总结 

  1. 关键是理解Entry的结构，WeakHashMap的用法。
  2. 理清引用关系很重要。
  3. 留下了一个问题：expungeStaleEntries()里面e.value = null; // Help GC是如何help GC的？为什么不能e.next=null?（猜测可能和stale entries may be in use by a HashIterator这一句有关）
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5563023.html

					

				
								

										
										
										
										
										
									

								

					
						
							
						 赞
						(0)
					
					

						
							 打赏
						
							
								微信扫一扫 微信扫一扫
							
							
								支付宝扫一扫 支付宝扫一扫
							
						
					

				

				

					

						

							
								周迅个人资料
								周迅个人资料
								一级用户组
							
						

						

							

								
									
										
									
									0
								
								
									
										
									
									0
								
							

							
							

								
									
										
									
								
							

						

					

				

			
			
            

            	            

            
			

								

					
					

         				
							
								
							 上一篇
						
						2022-12-14
					

				

												

					
					

         				
							下一篇 
           						
							
						
						2022-12-14
					

				

							


			
			

				

					

						发表评论
					

										

						
						

							

								登录后才能评论
							

							
						

					

									

								
 评论列表（0条）

				
    
									

				
											

		

	

	





	


	

		

			

			

				
				

					

						Copyright © 2022 内存溢出 版权所有
						
							湘ICP备2022025235号						
						Powered by
						
							outofmemory.cn
						
					
					

				

			

			

				

					
					
						
						
					
					
						
					
				

			

		

	




























    
    

    

        
            保存