1、WeakHashMap-源码分析-底层数据结构

  1. 1、WeakHashMap-底层数据结构
  2.     1-1、WeakHashMap是哈希表，与HashMap区别不大，但是它的键是"弱键"。
  3.     1-2、故WeakHashMap底层数据结构=数组+链表(未进行链表和红黑树转换,得与HashMap区分)。
  5. 2、WeakHashMap-属性字段：
  6.     // 默认的初始容量是16，必须是2的幂。
  7.     private static final int DEFAULT_INITIAL_CAPACITY = 16;
  9.     // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
  10.     private static final int MAXIMUM_CAPACITY = 1 << 30;
  12.     // 默认加载因子
  13.     private static final float DEFAULT_LOAD_FACTOR = 0.75f;
  15.     // 存储数据的Entry数组，长度是2的幂。
  16.     // WeakHashMap是采用拉链法实现的，每一个Entry本质上是一个单向链表
  17.     private Entry[] table;
  19.     // WeakHashMap的大小，它是WeakHashMap保存的键值对的数量
  20.     private int size;
  22.     // WeakHashMap的阈值，用于判断是否需要调整WeakHashMap的容量（threshold = 容量*加载因子）
  23.     private int threshold;
  25.     // 加载因子实际大小
  26.     private final float loadFactor;
  28.     // queue保存的是“已被GC清除”的“弱引用的键”。
  29.     // 弱引用和ReferenceQueue 是联合使用的：如果弱引用所引用的对象被垃圾回收，Java虚拟机就会把这个弱引用加入到与之关联的引用队列中
  30.     private final ReferenceQueue<K> queue = new ReferenceQueue<K>();
  32.     // WeakHashMap被改变的次数
  33.     private volatile int modCount;
  35.     //创建一个大小为n的Entry数组
  36.     @SuppressWarnings("unchecked")
  37.     private Entry<K,V>[] newTable(int n) {
  38.         return (Entry<K,V>[]) new Entry<?,?>[n];
  39.     }
  41.     /**
  42.      * 表示表内的空键。
  43.      */
  44.     private static final Object NULL_KEY = new Object();

2、WeakHashMap-源码分析-构造方法

  1. 1、WeakHashMap-源码分析-构造方法：
  3.     //默认构造函数,默认的初始容量是16,默认加载因子0.75f
  4.     public WeakHashMap() {
  5.         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  6.     }
  8.     //指定"容量大小"的构造函数,自定义初始容量，默认加载因子0.75f
  9.     public WeakHashMap(int initialCapacity) {
  10.         this(initialCapacity, DEFAULT_LOAD_FACTOR);
  11.     }
  13.     //指定"容量大小"和"加载因子"的构造函数
  14.     public WeakHashMap(int initialCapacity, float loadFactor) {
  15.         //指定的初始容量必须大于0
  16.         if (initialCapacity < 0)
  17.             throw new IllegalArgumentException("Illegal Initial Capacity: "+
  18.                                                initialCapacity);
  19.         // WeakHashMap的最大容量只能是MAXIMUM_CAPACITY：必须是2的幂且小于2的30次方
  20.         if (initialCapacity > MAXIMUM_CAPACITY)
  21.             initialCapacity = MAXIMUM_CAPACITY;
  23.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
  24.             throw new IllegalArgumentException("Illegal Load factor: "+
  25.                                                loadFactor);
  26.         int capacity = 1;
  27.         while (capacity < initialCapacity)
  28.             capacity <<= 1;
  29.         // 创建Entry数组，用来保存数据
  30.         table = newTable(capacity);
  31.         this.loadFactor = loadFactor;
  32.         // 设置"WeakHashMap阈值"，当WeakHashMap中存储数据的数量达到threshold时，就需要将WeakHashMap的容量加倍。
  33.         threshold = (int)(capacity * loadFactor);
  34.     }
  36.     // 包含"子Map"的构造函数
  37.     public WeakHashMap(Map<? extends K, ? extends V> m) {
  38.         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
  39.                 DEFAULT_INITIAL_CAPACITY),
  40.              DEFAULT_LOAD_FACTOR);
  41.         putAll(m);
  42.     }

3、WeakHashMap-源码分析-Entry类

  1. 1、WeakHashMap中的核心角色--Entry，Entry继承了WeakReference，实现了Map.Entry类
  2.     1-1、Entry继承自WeakReference，也就是弱引用，所以就具有了弱引用的特点。
  3.     1-2、实现了Map.Entry类，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()等这些函数。
  4.     1-3、其他WeakHashMap中的Entry最大的不同就是继承自WeakReference，并把key保存在了WeakReference中。
  6. 2、Entry类源代码：
  7.     //Entry是单向链表。
  8.     private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
  9.         V value;
  10.         final int hash;
  11.         Entry<K,V> next; // 指向下一个节点
  13.         /**
  14.          * 构造函数，创建一个新Entry实例
  15.          * queue是用来存放那些，被jvm清除的entry的引用，因为WeakHashMap使用的是弱引用，所以一旦gc，就会有key键被清除，所以会把entry加入到queue中。
  16.          * 就是为.expungeStaleEntries()方法所用。
  17.          */
  18.         Entry(Object key, V value, ReferenceQueue<Object> queue, int hash, Entry<K,V> next) {
  19.             //它调用了父类的构造函数,调用的WeakReference的构造函数，将key传入Reference中，保存在referent成员变量中
  20.             super(key, queue);
  21.             this.value = value;
  22.             this.hash  = hash;
  23.             this.next  = next;
  24.         }
  26.         @SuppressWarnings("unchecked")
  27.         public K getKey() {
  28.             // 这里调用了Reference的get方法，从中取出referent对象
  29.             // WeakHashMap中，key如果为null会使用NULL_KEY来替代
  30.             return (K) WeakHashMap.unmaskNull(get());
  31.         }
  33.         public V getValue() {
  34.             return value;
  35.         }
  37.         public V setValue(V newValue) {
  38.             V oldValue = value;
  39.             value = newValue;
  40.             return oldValue;
  41.         }
  43.         public boolean equals(Object o) {
  44.             if (!(o instanceof Map.Entry))
  45.                 return false;
  46.             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  47.             K k1 = getKey();
  48.             Object k2 = e.getKey();
  49.             if (k1 == k2 || (k1 != null && k1.equals(k2))) {
  50.                 V v1 = getValue();
  51.                 Object v2 = e.getValue();
  52.                 if (v1 == v2 || (v1 != null && v1.equals(v2)))
  53.                     return true;
  54.             }
  55.             return false;
  56.         }
  58.         public int hashCode() {
  59.             K k = getKey();
  60.             V v = getValue();
  61.             //把key和value的hashcode做一个异或处理
  62.             return Objects.hashCode(k) ^ Objects.hashCode(v);
  63.         }
  65.         public String toString() {
  66.             return getKey() + "=" + getValue();
  67.         }
  68.     }
  70. 2、构造方法调用其他方法：
  71.         //.unmaskNull()方法
  72.         //调用这个方法，因为WeakHashMap中对key为null时的特殊处理，会将其指向一个特殊的内部变量：
  73.         //private static final Object NULL_KEY = new Object();
  74.         static Object unmaskNull(Object key) {
  75.             return (key == NULL_KEY) ? null : key;
  76.         }
  78.         //处理null值, WeakHashMap中对key为null时的特殊处理，会将其指向一个特殊的内部变量：
  79.         //private static final Object NULL_KEY = new Object();
  80.         private static Object maskNull(Object key) {
  81.             return (key == null) ? NULL_KEY : key;
  82.         }

4、WeakHashMap-源码分析-添加元素

  1. 1、添加元素：.put()方法
  2. 2、源代码：
  3.     public V put(K key, V value) {
  4.         //key为null值处理
  5.         Object k = maskNull(key);
  6.         //计算hash值
  7.         int h = hash(k);
  8.         //获取table
  9.         Entry<K,V>[] tab = getTable();
  10.         //计算下标
  11.         int i = indexFor(h, tab.length);
  13.         for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
  14.             if (h == e.hash && eq(k, e.get())) {
  15.                 V oldValue = e.value;
  16.                 if (value != oldValue)
  17.                     e.value = value;
  18.                 return oldValue;
  19.             }
  20.         }
  22.         modCount++;
  23.         Entry<K,V> e = tab[i];
  24.         tab[i] = new Entry<>(k, value, queue, h, e);
  25.         //如果元素个数超过阈值，则进行扩容
  26.         if (++size >= threshold)
  27.             //进行扩容
  28.             resize(tab.length * 2);
  29.         return null;
  30.     }
  32.     //处理null值, WeakHashMap中对key为null时的特殊处理，会将其指向一个特殊的内部变量：
  33.     //private static final Object NULL_KEY = new Object();
  34.     private static Object maskNull(Object key) {
  35.         return (key == null) ? NULL_KEY : key;
  36.     }
  38.     //计算hash值
  39.     final int hash(Object k) {
  40.         int h = k.hashCode();
  41.         //做了二次散列，来扩大低位的影响。
  42.         //h >>> 20 = h*2^20、h >>> 12 = h*2^12
  43.         h ^= (h >>> 20) ^ (h >>> 12);
  44.         return h ^ (h >>> 7) ^ (h >>> 4);
  45.     }
  47.     /**
  48.      * 根据hashcode值，计算下标
  49.      * 将数组长度减1后与hashcode做一个位与操作，因为length必定是2的幂，所以减1后就变成了掩码，再进行与操作就能直接得到hashcode mod length的结果。
  50.      * h & (length-1) = h/length
  51.      */
  52.     private static int indexFor(int h, int length) {
  53.         return h & (length-1);
  54.     }
  56.     //获取table
  57.     /**
  58.      * 返回第一次清除过时项后的表。
  59.      */
  60.     private Entry<K,V>[] getTable() {
  61.         expungeStaleEntries();
  62.         return table;
  63.     }
  65.     /**
  66.      * 从表中删除过时的条目：都会将table中key已经被回收掉的Entry移除掉(将对应的value置为null)。
  67.      */
  68.     private void expungeStaleEntries() {
  69.         for (Object x; (x = queue.poll()) != null; ) {
  70.             synchronized (queue) {
  71.                 @SuppressWarnings("unchecked")
  72.                 Entry<K,V> e = (Entry<K,V>) x;
  73.                 // 查找对应的位置
  74.                 int i = indexFor(e.hash, table.length);
  76.                 // 找到之前的Entry
  77.                 Entry<K,V> prev = table[i];
  78.                 Entry<K,V> p = prev;
  79.                 // 在链表中寻找
  80.                 while (p != null) {
  81.                     Entry<K,V> next = p.next;
  82.                     if (p == e) {
  83.                         if (prev == e)
  84.                             table[i] = next;
  85.                         else
  86.                             prev.next = next;
  87.                         // 将对应的value置为null，帮助GC回收
  88.                         e.value = null; // Help GC
  89.                         size--;
  90.                         break;
  91.                     }
  92.                     prev = p;
  93.                     p = next;
  94.                 }
  95.             }
  96.         }
  97.     }

5、WeakHashMap-源码分析-扩容

  1. 1、扩容：.resize()方法
  3. 2、源代码：
  5.     void resize(int newCapacity) {
  6.         //获取当前table
  7.         Entry<K,V>[] oldTable = getTable();
  8.         int oldCapacity = oldTable.length;
  9.         if (oldCapacity == MAXIMUM_CAPACITY) {
  10.             threshold = Integer.MAX_VALUE;
  11.             return;
  12.         }
  13.         //新建一个table
  14.         Entry<K,V>[] newTable = newTable(newCapacity);
  15.         transfer(oldTable, newTable);
  16.         table = newTable;
  18.         /*
  19.          * If ignoring null elements and processing ref queue caused massive
  20.          * shrinkage, then restore old table.  This should be rare, but avoids
  21.          * unbounded expansion of garbage-filled tables.
  22.          */
  23.         if (size >= threshold / 2) {
  24.             threshold = (int)(newCapacity * loadFactor);
  25.         } else {
  26.             //从表中删除过时的条目：都会将table中key已经被回收掉的Entry移除掉。
  27.             expungeStaleEntries();
  28.             // 将旧table中的内容复制到新table中
  29.             transfer(newTable, oldTable);
  30.             table = oldTable;
  31.         }
  32.     }
  34.     // 新建Entry数组
  35.     private Entry<K,V>[] newTable(int n) {
  36.         return (Entry<K,V>[]) new Entry<?,?>[n];
  37.     }
  39.     /** 
  40.         Transfers all entries from src to dest tables 
  41.         将旧table中的内容复制到新table中
  42.     */
  43.     private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
  44.         for (int j = 0; j < src.length; ++j) {
  45.             Entry<K,V> e = src[j];
  46.             src[j] = null;
  47.             while (e != null) {
  48.                 Entry<K,V> next = e.next;
  49.                 Object key = e.get();
  50.                 if (key == null) {
  51.                     e.next = null;  // Help GC
  52.                     e.value = null; //  "   "
  53.                     size--;
  54.                 } else {
  55.                     int i = indexFor(e.hash, dest.length);
  56.                     e.next = dest[i];
  57.                     dest[i] = e;
  58.                 }
  59.                 e = next;
  60.             }
  61.         }
  62.     }

6、WeakHashMap-源码分析-获取元素

  1. 1、获取元素：.get()方法
  3. 2、源代码：
  4.     public V get(Object key) {
  5.         // 对null值特殊处理
  6.         Object k = maskNull(key);
  7.         // 取key的hash值
  8.         int h = hash(k);
  9.         // 取当前table
  10.         Entry<K,V>[] tab = getTable();
  11.         // 获取下标
  12.         int index = indexFor(h, tab.length);
  13.         Entry<K,V> e = tab[index];
  14.         // 链表中查找元素
  15.         while (e != null) {
  16.             if (e.hash == h && eq(k, e.get()))
  17.                 return e.value;
  18.             e = e.next;
  19.         }
  20.         return null;
  21.     }

7、WeakHashMap-源码分析-删除元素

  1. 1、删除元素：.remove()方法
  3. 2、源代码：
  4.     public V remove(Object key) {
  5.         // 对null值特殊处理
  6.         Object k = maskNull(key);
  7.         // 取key的hash
  8.         int h = hash(k);
  9.         // 取当前table
  10.         Entry<K,V>[] tab = getTable();
  11.         // 计算下标
  12.         int i = indexFor(h, tab.length);
  13.         Entry<K,V> prev = tab[i];
  14.         Entry<K,V> e = prev;
  16.         while (e != null) {
  17.             Entry<K,V> next = e.next;
  18.             // 查找对应Entry
  19.             if (h == e.hash && eq(k, e.get())) {
  20.                 modCount++;
  21.                 size--;
  22.                 if (prev == e)
  23.                     tab[i] = next;
  24.                 else
  25.                     prev.next = next;
  26.                 // 如果找到，返回对应Entry的value
  27.                 return e.value;
  28.             }
  29.             prev = e;
  30.             e = next;
  31.         }
  33.         return null;
  34.     }

8、WeakHashMap-源码分析-举例使用-Demo

  2. public class WeakHashMapTest {
  3.     public static void main(String[] args){
  4.         testWeakHashMap();
  5.     }
  7.     private static void testWeakHashMap() {
  8.         // 创建3个String对象用来做key
  9.         String w1 = new String("key1");
  10.         String w2 = new String("key2");
  11.         String w3 = new String("key3");
  13.         // 新建WeakHashMap
  14.         Map weakHashMap = new WeakHashMap();
  16.         // 添加键值对
  17.         weakHashMap.put(w1, "v1");
  18.         weakHashMap.put(w2, "v2");
  19.         weakHashMap.put(w3, "v3");
  21.         // 打印出weakHashMap
  22.         System.out.printf("weakHashMap:%s\n", weakHashMap); //{key1=w1, key2=w2, key3=w3}
  24.         // containsKey(Object key) :是否包含键key
  25.         System.out.printf("contains key key1 : %s\n",weakHashMap.containsKey("key1"));//true
  26.         System.out.printf("contains key key4 : %s\n",weakHashMap.containsKey("key4"));//false
  28.         // containsValue(Object value) :是否包含值value
  29.         System.out.printf("contains value v1 : %s\n",weakHashMap.containsValue("v1"));//true
  30.         System.out.printf("contains value 0 : %s\n",weakHashMap.containsValue(0));//false
  32.         // remove(Object key) ： 删除键key对应的键值对
  33.         weakHashMap.remove("three");
  35.         System.out.printf("weakHashMap: %s\n", weakHashMap);{key1=w1, key2=w2, key3=w3}
  38.         // ---- 测试 WeakHashMap 的自动回收特性 ----
  40.         // 将w1设置null。
  41.         // 这意味着“弱键”w1再没有被其它对象引用，调用gc时会回收WeakHashMap中与“w1”对应的键值对
  42.         w1 = null;
  44.         // 内存回收。这里，会回收WeakHashMap中与“w1”对应的键值对
  45.         System.gc();
  47.         // 遍历WeakHashMap
  48.         Iterator iter = weakHashMap.entrySet().iterator();
  49.         while (iter.hasNext()) {
  50.             Map.Entry en = (Map.Entry)iter.next();
  51.             /**
  52.                 next : key2 - w2
  53.                 next : key3 - w3
  54.             */
  55.             System.out.printf("next : %s - %s\n",en.getKey(),en.getValue());
  56.         }
  57.         // 打印WeakHashMap的实际大小
  58.         // after gc WeakHashMap size:2
  59.         System.out.printf("after gc WeakHashMap size:%s\n", weakHashMap.size());
  60.     }
  61. }

9、WeakHashMap-源码分析-应用场景-Demo

  1. 1、应用场景
  2.     1-1、由于WeakHashMap可以自动清除Entry，所以比较适合用于存储非必需对象，用作缓存非常合适。
  3.     1-2、配合事务进行使用，存储事务过程中的各类信息，结构：
  4.         WeakHashMap<String,Map<K,V>> transactionCache;
  5.         1-2-1、key为String类型，可以用来标志区分不同的事务，起到一个事务id的作用。value是一个map，可以是一个简单的HashMap或者LinkedHashMap，用来存放在事务中需要使用到的信息。
  6.         1-2-2、在事务开始时创建一个事务id，并用它来作为key，事务结束后，将这个强引用消除掉，这样既能保证在事务中可以获取到所需要的信息，又能自动释放掉map中的所有信息。
  8. 2、应用Demo-在Tomcat的工具类里，有这样一种实现。基于LRU策略。
  9.     package org.apache.tomcat.util.collections;
  11.     public final class ConcurrentCache<K,V> {
  12.         private final int size;
  13.         private final Map<K,V> eden;
  14.         private final Map<K,V> longterm;
  16.         public ConcurrentCache(int size) {
  17.             this.size = size;
  18.             this.eden = new ConcurrentHashMap<>(size);
  19.             this.longterm = new WeakHashMap<>(size);
  20.         }
  22.         public V get(K k) {
  23.             V v = this.eden.get(k);
  24.             if (v == null) {
  25.                 synchronized (longterm) {
  26.                     v = this.longterm.get(k);
  27.                 }
  28.                 if (v != null) {
  29.                     this.eden.put(k, v);
  30.                 }
  31.             }
  32.             return v;
  33.         }
  35.         public void put(K k, V v) {
  36.             if (this.eden.size() >= size) {
  37.                 synchronized (longterm) {
  38.                     this.longterm.putAll(this.eden);
  39.                 }
  40.                 this.eden.clear();
  41.             }
  42.             this.eden.put(k, v);
  43.         }
  44.     }