WeakHashMap源码分析

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

WeakHashMap与HashMap有些类似，但也有很多地方不同。它们设置了相同的负载因子和初始容量，但是前者的数据结构只使用了数组+链表，并没有用到红黑树，

在这里，与HashMap重复且设置值一致的变量就不重复介绍了，只简单说下不同的地方。

代表空Key

privatestaticfinal Object NULL_KEY = new Object();
复制代码

保存GC后被清除的WeakEntries

privatefinal ReferenceQueue<Object> queue = new ReferenceQueue<>();
复制代码

Entry: 数组存放节点

privatestaticclassEntry<K,V> extendsWeakReference<Object> implementsMap.Entry<K,V> {
        V value;
finalint 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;  } 复制代码

我们可以发现Entry继承了WeakReference，在其构造函数中，会创建一个新的弱引用指向给定的key。

WeakHashMap构造函数

publicWeakHashMap(int initialCapacity, float loadFactor){
// 部分代码删除
int capacity = 1;
while (capacity < initialCapacity)
            capacity <<= 1;
 table = newTable(capacity); this.loadFactor = loadFactor;  threshold = (int)(capacity * loadFactor);  } 复制代码

在构造函数中，它会将数组容量大小设置为输入值的最接近的2的n次方；并调用newTable初始化数组。

接下来来分析几个重要的方法。

Put()方法

public V put(K key, V value){
// 当Key为null时会返回一个名字为NULL_KEY的Object对象，表明Key支持Null
        Object k = maskNull(key);
int h = hash(k);
// 将过期的Entry删除掉
 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); returnnull;  } 复制代码

expungeStaleEntries()方法

在调用get()、replaceAll()、containsNullValue()、forEach()、removeMapping()、remove()、resize()、put()等方式时再获取table数组时，不是直接返回table数组，而是通过getTable方法先把数组中key为null的Entry删除掉，再返回。

private Entry<K,V>[] getTable() {
        expungeStaleEntries();
return table;
    }
复制代码

privatevoidexpungeStaleEntries(){
// 从ReferenceQueue中取出过期的节点
for (Object x; (x = queue.poll()) != null; ) {
// 锁住ReferenceQueue
synchronized (queue) {
@SuppressWarnings("unchecked")  Entry<K,V> e = (Entry<K,V>) x; // 为了方面，插入indexFor的代码/**  * private static int indexFor(int h, int length) {  return h & (length-1);  }  **/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; // 将前驱节点的next指向它的下一个节点，即把该节点从链表中去除else prev.next = next; // 将该节点的value设置为null，帮助gc e.value = null; // Help GC size--; break;  }  prev = p;  p = next;  }  }  }  } 复制代码

Resize()扩容

在扩容前，先删除过期的Entry，然后新建一个容量是原来2倍的数组；之后调用transfer方法进行扩容。如果扩容后size大小大于等于阈值的一半，则更新阈值；如果小于阈值的一半，则再调用一次expungeStaleEntries方法，再从新表转化到原来的旧表中。

voidresize(int newCapacity){
// 在扩容前先删除过期的Entry
        Entry<K,V>[] oldTable = getTable();
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
 threshold = Integer.MAX_VALUE; return;  } // 扩容为原来的2倍 Entry<K,V>[] newTable = newTable(newCapacity);  transfer(oldTable, newTable);  table = newTable; // 如果忽略null元素并处理ref队列导致大量收缩，则还原旧表// 这应该很少见，但是可以避免垃圾填表的无限扩展。if (size >= threshold / 2) {  threshold = (int)(newCapacity * loadFactor);  } else {  expungeStaleEntries();  transfer(newTable, oldTable);  table = oldTable;  }  } 复制代码

transfer()方法

遍历旧数组，如果key为null，则设置其Entry的next和value都为null，帮助gc；如果不为null，则计算该Entry在新数组中的位置，利用头插法进行插入。

privatevoidtransfer(Entry<K,V>[] src, Entry<K,V>[] dest){
for (int j = 0; j < src.length; ++j) {
            Entry<K,V> e = src[j];
            src[j] = null;
while (e != null) {
 Entry<K,V> next = e.next;  Object key = e.get(); if (key == null) {  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;  }  }  }

以上是 WeakHashMap源码分析 的全部内容， 来源链接： utcz.com/z/518237.html

回到顶部