• WeakHashMap 源码解析

    目录

    一. 前言

    二. 源码解析

    2.1. 类结构

    2.2. 成员变量

    2.3. 构造方法

    2.4. Entry

    2.5. 添加元素

    2.6. 扩容

    2.7. 删除元素

    2.8. 获取元素

    一. 前言

        WeakHashMap，从名字可以看出它是某种 Map。它的特殊之处在于 WeakHashMap 里的entry可能会被GC自动删除，即使程序员没有调用remove()或者clear()方法。

        更直观的说，当使用 WeakHashMap 时，即使没有显示的添加或删除任何元素，也可能发生如下情况：
    1. 调用两次size()方法返回不同的值；
    2. 两次调用isEmpty()方法，第一次返回false，第二次返回true；
    3. 两次调用containsKey()方法，第一次返回true，第二次返回false，尽管两次使用的是同一个key；
    4. 两次调用get()方法，第一次返回一个value，第二次返回null，尽管两次使用的是同一个对象。

        遇到这么奇葩的现象，你是不是觉得使用者一定会疯掉？其实不然，WeakHashMap 的这个特点特别适用于需要缓存的场景。在缓存场景下，由于内存是有限的，不能缓存所有对象；对象缓存命中可以提高系统效率，但缓存MISS也不会造成错误，因为可以通过计算重新得到。

        要明白 WeakHashMap 的工作原理，还需要引入一个概念：弱引用（WeakReference）。我们都知道Java中的内存是通过GC自动管理的，GC会在程序运行过程中自动判断哪些对象是可以被回收的，并在合适的时机进行内存释放。GC判断某个对象是否可被回收的依据是，是否有有效的引用指向该对象。如果没有有效引用指向该对象（基本意味着不存在访问该对象的方式），那么该对象就是可回收的。这里的有效引用并不包括弱引用。也就是说，虽然弱引用可以用来访问对象，但进行垃圾回收时弱引用并不会被考虑在内，仅有弱引用指向的对象仍然会被GC回收。

        WeakHashMap 内部是通过弱引用来管理entry的，弱引用的特性对应到 WeakHashMap 上意味着什么呢？将一对key, value放入到 WeakHashMap 里并不能避免该key值被GC回收，除非在 WeakHashMap 之外还有对该key的强引用。

    关于强引用，弱引用等概念请参见《Java 四种引用类型》。

    二. 源码解析

        如果你看过前几篇关于 Map 和 Set 的讲解，一定会问：既然有 WeakHashMap，是否有 WeekHashSet 呢？答案是没有。不过Java Collections工具类给出了解决方案，Collections.newSetFromMap(Map map) 方法可以将任何 Map包装成一个Set。通过如下方式可以快速得到一个 WeakHashSet：

    1. // 将WeakHashMap包装成一个Set
    2. Set weakHashSet = Collections.newSetFromMap(
    3.         new WeakHashMap());
    4.  
    5. // Collections.newSetFromMap()用于将任何Map包装成一个Set
    6. public static  Set newSetFromMap(Map map) {
    7.     return new SetFromMap<>(map);
    8. }
    9.  
    10. private static class SetFromMap extends AbstractSet
    11.     implements Set, Serializable
    12. {
    13.     private final Map m;  // The backing map
    14.     private transient Set s;       // Its keySet
    15.     SetFromMap(Map map) {
    16.         if (!map.isEmpty())
    17.             throw new IllegalArgumentException("Map is non-empty");
    18.         m = map;
    19.         s = map.keySet();
    20.     }
    21.     public void clear()               {        m.clear(); }
    22.     public int size()                 { return m.size(); }
    23.     public boolean isEmpty()          { return m.isEmpty(); }
    24.     public boolean contains(Object o) { return m.containsKey(o); }
    25.     public boolean remove(Object o)   { return m.remove(o) != null; }
    26.     public boolean add(E e) { return m.put(e, Boolean.TRUE) == null; }
    27.     public Iterator iterator()     { return s.iterator(); }
    28.     public Object[] toArray()         { return s.toArray(); }
    29.     public  T[] toArray(T[] a)     { return s.toArray(a); }
    30.     public String toString()          { return s.toString(); }
    31.     public int hashCode()             { return s.hashCode(); }
    32.     public boolean equals(Object o)   { return o == this || s.equals(o); }
    33.     public boolean containsAll(Collection c) {return s.containsAll(c);}
    34.     public boolean removeAll(Collection c)   {return s.removeAll(c);}
    35.     public boolean retainAll(Collection c)   {return s.retainAll(c);}
    36.     // addAll is the only inherited implementation
    37.     
    38.     // Override default methods in Collection
    39. 	@Override
    40. 	public void forEach(Consumersuper E> action) {
    41. 		s.forEach(action);
    42. 	}
    43. 	@Override
    44. 	public boolean removeIf(Predicatesuper E> filter) {
    45. 		return s.removeIf(filter);
    46. 	}
    47.  
    48. 	@Override
    49. 	public Spliterator spliterator() {return s.spliterator();}
    50. 	@Override
    51. 	public Stream stream()           {return s.stream();}
    52. 	@Override
    53. 	public Stream parallelStream()   {return s.parallelStream();}
    54.  
    55. 	private static final long serialVersionUID = 2454657854757543876L;
    56.  
    57. 	private void readObject(java.io.ObjectInputStream stream)
    58. 		throws IOException, ClassNotFoundException
    59. 	{
    60. 		stream.defaultReadObject();
    61. 		s = m.keySet();
    62. 	}
    63. }
      64.  

      2.1. 类结构
       

       

      从图中可以看出：WeakHashMap继承于AbstractMap，并且实现了Map接口。
       

      2.2. 成员变量
       

      1. // 默认的初始容量是16，必须是2的幂。
      2. private static final int DEFAULT_INITIAL_CAPACITY = 16;
      3.  
      4. // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
      5. private static final int MAXIMUM_CAPACITY = 1 << 30;
      6.  
      7. // 默认加载因子
      8. private static final float DEFAULT_LOAD_FACTOR = 0.75f;
      9.  
      10. // 存储数据的Entry数组，长度是2的幂。
      11. // WeakHashMap是采用拉链法实现的，每一个Entry本质上是一个单向链表
      12. private Entry[] table;
      13.  
      14. // WeakHashMap的大小，它是WeakHashMap保存的键值对的数量
      15. private int size;
      16.  
      17. // WeakHashMap的阈值，用于判断是否需要调整WeakHashMap的容量（threshold = 容量*加载因子）
      18. private int threshold;
      19.  
      20. // 加载因子实际大小
      21. private final float loadFactor;
      22.  
      23. // queue保存的是“已被GC清除”的“弱引用的键”。
      24. // 弱引用和ReferenceQueue 是联合使用的：如果弱引用所引用的对象被垃圾回收，Java虚拟机就会把这个弱引用加入到与之关联的引用队列中
      25. private final ReferenceQueue queue = new ReferenceQueue<>();
      26.  
      27. // WeakHashMap被改变的次数
      28. int modCount;
        29.  

        2.3. 构造方法
         

        1. // 指定“容量大小”和“加载因子”的构造函数
        2. public WeakHashMap(int initialCapacity, float loadFactor) {
        3. 	if (initialCapacity < 0)
        4. 		throw new IllegalArgumentException("Illegal Initial Capacity: "+
        5. 										   initialCapacity);
        6. 	// WeakHashMap的最大容量只能是MAXIMUM_CAPACITY
        7. 	if (initialCapacity > MAXIMUM_CAPACITY)
        8. 		initialCapacity = MAXIMUM_CAPACITY;
        9.  
        10. 	if (loadFactor <= 0 || Float.isNaN(loadFactor))
        11. 		throw new IllegalArgumentException("Illegal Load factor: "+
        12. 										   loadFactor);
        13. 	// 找出“大于initialCapacity”的最小的2的幂
        14. 	int capacity = 1;
        15. 	while (capacity < initialCapacity)
        16. 		capacity <<= 1;
        17. 	// 创建Entry数组，用来保存数据
        18. 	table = newTable(capacity);
        19. 	// 设置“加载因子”
        20. 	this.loadFactor = loadFactor;
        21. 	// 设置“WeakHashMap阈值”，当WeakHashMap中存储数据的数量达到threshold时，就需要将WeakHashMap的容量加倍。
        22. 	threshold = (int)(capacity * loadFactor);
        23. }
        24.  
        25. // 指定“容量大小”的构造函数
        26. public WeakHashMap(int initialCapacity) {
        27. 	this(initialCapacity, DEFAULT_LOAD_FACTOR);
        28. }
        29.  
        30. // 默认构造函数。
        31. public WeakHashMap() {
        32. 	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
        33. }
        34.  
        35. // 包含“子Map”的构造函数
        36. public WeakHashMap(Map m) {
        37. 	this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
        38.                 DEFAULT_INITIAL_CAPACITY),
        39.              DEFAULT_LOAD_FACTOR);
        40. 	// 将m中的全部元素逐个添加到WeakHashMap中
        41. 	putAll(m);
        42. }
        43.  
        44. private Entry[] newTable(int n) {
        45.     return (Entry[]) new Entry[n];
        46. }
         

        2.4. Entry
         

        1. private static class Entry extends WeakReference implements Map.Entry {
        2. 	V value;
        3. 	final int hash;
        4. 	Entry next;
        5.  
        6. 	/**
        7. 	 * Creates new entry.
        8. 	 */
        9. 	Entry(Object key, V value,
        10. 		  ReferenceQueue queue,
        11. 		  int hash, Entry next) {
        12. 		super(key, queue);
        13. 		this.value = value;
        14. 		this.hash  = hash;
        15. 		this.next  = next;
        16. 	}
        17.  
        18. 	@SuppressWarnings("unchecked")
        19. 	public K getKey() {
        20. 		return (K) WeakHashMap.unmaskNull(get());
        21. 	}
        22.  
        23. 	public V getValue() {
        24. 		return value;
        25. 	}
        26.  
        27. 	public V setValue(V newValue) {
        28. 		V oldValue = value;
        29. 		value = newValue;
        30. 		return oldValue;
        31. 	}
        32.  
        33. 	public boolean equals(Object o) {
        34. 		if (!(o instanceof Map.Entry))
        35. 			return false;
        36. 		Map.Entry e = (Map.Entry)o;
        37. 		K k1 = getKey();
        38. 		Object k2 = e.getKey();
        39. 		if (k1 == k2 || (k1 != null && k1.equals(k2))) {
        40. 			V v1 = getValue();
        41. 			Object v2 = e.getValue();
        42. 			if (v1 == v2 || (v1 != null && v1.equals(v2)))
        43. 				return true;
        44. 		}
        45. 		return false;
        46. 	}
        47.  
        48. 	public int hashCode() {
        49. 		K k = getKey();
        50. 		V v = getValue();
        51. 		return Objects.hashCode(k) ^ Objects.hashCode(v);
        52. 	}
        53.  
        54. 	public String toString() {
        55. 		return getKey() + "=" + getValue();
        56. 	}
        57. }
          58.  

          可以看到Entry是继承WeakReference的，我们结合WeakReference再看一下：
           

          1. public class WeakReference extends Reference {
          2.     /**
          3.      * Creates a new weak reference that refers to the given object.  The new
          4.      * reference is not registered with any queue.
          5.      * 创建一个新的弱应用给传入的对象，这个新的引用不注册任何队列
          6.      *
          7.      * @param referent object the new weak reference will refer to
          8.      */
          9.     public WeakReference(T referent) {
          10.         super(referent);
          11.     }
          12.  
          13.     /**
          14.      * Creates a new weak reference that refers to the given object and is
          15.      * registered with the given queue.
          16.      * 创建一个新的弱应用给传入的对象，这个新的引用注册给一个给定的队列
          17.      *
          18.      * @param referent object the new weak reference will refer to
          19.      * @param q the queue with which the reference is to be registered,
          20.      *          or null if registration is not required
          21.      */
          22.     public WeakReference(T referent, ReferenceQueuesuper T> q) {
          23.         super(referent, q);
          24.     }
          25. }
           

          我们发现在WeakHashMap中把key注册给了WeakReference，也就是说在WeakHashMap中key是一个弱引用。
           

          2.5. 添加元素
           

          1. public V put(K key, V value) {
          2.     // 如果key是null则给定一个空的对象进行修饰
          3.     Object k = maskNull(key);
          4.     // 计算key的hash
          5.     int h = hash(k);
          6.     // 获取table
          7.     Entry[] tab = getTable();
          8.     // 根据hash找到数组下标
          9.     int i = indexFor(h, tab.length);
          10.     // 找到链表中元素位置
          11.     for (Entry e = tab[i]; e != null; e = e.next) {
          12.         if (h == e.hash && eq(k, e.get())) {
          13.             V oldValue = e.value;
          14.             if (value != oldValue)
          15.                 e.value = value;
          16.             return oldValue;
          17.         }
          18.     }
          19.  
          20.     modCount++;
          21.     Entry e = tab[i];
          22.     tab[i] = new Entry<>(k, value, queue, h, e);
          23.     if (++size >= threshold) // 是否达到阀值达到阀值就扩容
          24.         resize(tab.length * 2);
          25.     return null;
          26. }
          27.  
          28. private Entry[] getTable() {
          29.     expungeStaleEntries();
          30.     return table;
          31. }
          32.  
          33. private void expungeStaleEntries() {
          34.     // 从 ReferenceQueue中拉取元素
          35.     for (Object x; (x = queue.poll()) != null; ) {
          36.         synchronized (queue) {
          37.             @SuppressWarnings("unchecked")
          38.                 Entry e = (Entry) x;
          39.             int i = indexFor(e.hash, table.length);
          40.  
          41.             Entry prev = table[i];
          42.             Entry p = prev;
          43.             while (p != null) {
          44.                 Entry next = p.next;
          45.                 if (p == e) {
          46.                     if (prev == e)
          47.                         table[i] = next;
          48.                     else
          49.                         prev.next = next;
          50.                     // Must not null out e.next;
          51.                     // stale entries may be in use by a HashIterator
          52.                     // 拿到entry的值赋值为null帮助GC
          53.                     e.value = null; // Help GC
          54.                     size--;
          55.                     break;
          56.                 }
          57.                 prev = p;
          58.                 p = next;
          59.             }
          60.         }
          61.     }
          62. }
           

          expungeStaleEntries 就是WeakHashMap的核心了，它承担着Map中死对象的清理工作。原理就是依赖WeakReference和ReferenceQueue的特性。在每个WeakHashMap都有个ReferenceQueue queue，在Entry初始化的时候也会将queue传给WeakReference，这样当某个key可以失去所有强引用之后，其key对应的WeakReference对象会被放到queue里，有了queue就知道需要清理哪些Entry了。
           

          这里也是整个WeakHashMap里唯一加了同步的地方。除了上文说的到resize中调用了expungeStaleEntries()，size()中也调用了这个清理方法。另外 getTable()也调了，这就意味着几乎所有其他方法都间接调用了清理。
           

          1. // 将"m"的全部元素都添加到WeakHashMap中
          2. public void putAll(Map m) {
          3. 	int numKeysToBeAdded = m.size();
          4. 	if (numKeysToBeAdded == 0)
          5. 		return;
          6.  
          7. 	// 计算容量是否足够，
          8. 	// 若“当前实际容量 < 需要的容量”，则将容量x2。
          9. 	if (numKeysToBeAdded > threshold) {
          10. 		int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
          11. 		if (targetCapacity > MAXIMUM_CAPACITY)
          12. 			targetCapacity = MAXIMUM_CAPACITY;
          13. 		int newCapacity = table.length;
          14. 		while (newCapacity < targetCapacity)
          15. 			newCapacity <<= 1;
          16. 		if (newCapacity > table.length)
          17. 			resize(newCapacity);
          18. 	}
          19.  
          20. 	// 将“m”中的元素逐个添加到WeakHashMap中。
          21. 	for (Map.Entryextends K, ? extends V> e : m.entrySet())
          22. 		put(e.getKey(), e.getValue());
          23. }
           

          2.6. 扩容
           

          1. // 重新调整WeakHashMap的大小，newCapacity是调整后的单位
          2. void resize(int newCapacity) {
          3. 	Entry[K, V] oldTable = getTable();
          4. 	int oldCapacity = oldTable.length;
          5. 	if (oldCapacity == MAXIMUM_CAPACITY) {
          6. 		threshold = Integer.MAX_VALUE;
          7. 		return;
          8. 	}
          9.  
          10. 	// 新建一个newTable，将“旧的table”的全部元素添加到“新的newTable”中，
          11. 	// 然后，将“新的newTable”赋值给“旧的table”。
          12. 	Entry[K, V] newTable = new Table(newCapacity);
          13. 	transfer(oldTable, newTable);
          14. 	table = newTable;
          15.  
          16. 	if (size >= threshold / 2) {
          17. 		threshold = (int)(newCapacity * loadFactor);
          18. 	} else {
          19. 		// 删除table中“已被GC回收的key对应的键值对”
          20. 		expungeStaleEntries();
          21. 		transfer(newTable, oldTable);
          22. 		table = oldTable;
          23. 	}
          24. }
          25.  
          26. // 将WeakHashMap中的全部元素都添加到newTable中
          27. private void transfer(Entry[] src, Entry[] dest) {
          28. 	for (int j = 0; j < src.length; ++j) {
          29. 		Entry e = src[j];
          30. 		src[j] = null;
          31. 		while (e != null) {
          32. 			Entry next = e.next;
          33. 			Object key = e.get();
          34. 			if (key == null) {
          35. 				e.next = null;  // Help GC
          36. 				e.value = null; //  "   "
          37. 				size--;
          38. 			} else {
          39. 				int i = indexFor(e.hash, dest.length);
          40. 				e.next = dest[i];
          41. 				dest[i] = e;
          42. 			}
          43. 			e = next;
          44. 		}
          45. 	}
          46. }
           

          2.7. 删除元素
           

          1. // 删除“键为key”元素
          2. public V remove(Object key) {
          3. 	Object k = maskNull(key);
          4. 	// 获取哈希值。
          5. 	int h = hash(k);
          6. 	Entry[] tab = getTable();
          7. 	int i = indexFor(h, tab.length);
          8. 	Entry prev = tab[i];
          9. 	Entry e = prev;
          10.  
          11. 	// 删除链表中“键为key”的元素
          12. 	// 本质是“删除单向链表中的节点”
          13. 	while (e != null) {
          14. 		Entry next = e.next;
          15. 		if (h == e.hash && eq(k, e.get())) {
          16. 			modCount++;
          17. 			size--;
          18. 			if (prev == e)
          19. 				tab[i] = next;
          20. 			else
          21. 				prev.next = next;
          22. 			return e.value;
          23. 		}
          24. 		prev = e;
          25. 		e = next;
          26. 	}
          27.  
          28. 	return null;
          29. }
          30.  
          31. // 删除“键值对”
          32. boolean removeMapping(Object o) {
          33. 	if (!(o instanceof Map.Entry))
          34. 		return false;
          35. 	Entry[] tab = getTable();
          36. 	Map.Entry entry = (Map.Entry)o;
          37. 	Object k = maskNull(entry.getKey());
          38. 	int h = hash(k);
          39. 	int i = indexFor(h, tab.length);
          40. 	Entry prev = tab[i];
          41. 	Entry e = prev;
          42.  
          43. 	// 删除链表中的“键值对e”
          44. 	// 本质是“删除单向链表中的节点”
          45. 	while (e != null) {
          46. 		Entry next = e.next;
          47. 		if (h == e.hash && e.equals(entry)) {
          48. 			modCount++;
          49. 			size--;
          50. 			if (prev == e)
          51. 				tab[i] = next;
          52. 			else
          53. 				prev.next = next;
          54. 			return e;
          55. 		}
          56. 		prev = e;
          57. 		e = next;
          58. 	}
          59.  
          60. 	return false;
          61. }
          62.  
          63. // 清空WeakHashMap，将所有的元素设为null
          64. public void clear() {
          65. 	while (queue.poll() != null)
          66. 		;
          67.  
          68. 	modCount++;
          69. 	Arrays.fill(table, null);
          70. 	size = 0;
          71.  
          72. 	while (queue.poll() != null)
          73. 		;
          74. }
           

          2.8. 获取元素
           

          1. // 获取key对应的value
          2. public V get(Object key) {
          3. 	Object k = maskNull(key);
          4. 	// 获取key的hash值。
          5. 	int h = hash(k);
          6. 	Entry[] tab = getTable();
          7. 	int index = indexFor(h, tab.length);
          8. 	Entry e = tab[index];
          9. 	// 在“该hash值对应的链表”上查找“键值等于key”的元素
          10. 	while (e != null) {
          11. 		if (e.hash == h && eq(k, e.get()))
          12. 			return e.value;
          13. 		e = e.next;
          14. 	}
          15. 	return null;
          16. }
          17.  
          18. // WeakHashMap是否包含key
          19. public boolean containsKey(Object key) {
          20. 	return getEntry(key) != null;
          21. }
          22.  
          23. // 返回“键为key”的键值对
          24. Entry getEntry(Object key) {
          25. 	Object k = maskNull(key);
          26. 	int h = hash(k);
          27. 	Entry[] tab = getTable();
          28. 	int index = indexFor(h, tab.length);
          29. 	Entry e = tab[index];
          30. 	while (e != null && !(e.hash == h && eq(k, e.get())))
          31. 		e = e.next;
          32. 	return e;
          33. }
           

          
                
                    
                

                
        58. 

                    相关阅读:
          
                    
qnx sh: rm: Arg list too long                            
          
写了这么久Java项目，是否还记得你的第一行Java代码                            
          
【精选】矩阵加速                            
          
centos 安装和卸载 webmin                            
          
HTML5 基础                            
          
vue3的单组件的编写(三）【响应式 API 之 toRef 与 toRefs】                            
          
史上最全SpringCloud微服务笔记,掌握已超过80%Java面试者                            
          
普冉PY32系列(五) 使用JLink RTT代替串口输出日志                            
          
第三套.py                            
          
dockerfile制作-pytoch+深度学习环境版                            
          
                              
                
          59. 
                
        59. 
                    原文地址：https://blog.csdn.net/mrluo735/article/details/134048651
                
          60.