WeakHashMap分析
2020-09-04 本文已影响0人
竖起大拇指
简介
WeakHashMap是一种弱引用map，内部的key会存储为弱引用，当gc的时候，如果这些key没有强引用存在，会被gc回收掉，下一次当我们操作的时候会把对应的Entry整体删除掉，基于这种特性，WeakHashMap特别使用于缓存处理。
存储结构
WeakHashMap因为gc的时候会把没有强引用的key回收掉，所以注定了它里面的元素不会太多，因此也就不需要像HashMap那样元素多的时候转化为红黑树来处理了。因此，WeakHashMap的存储结构只有(数组+链表)。
源码解析
属性分析
public class WeakHashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V> {
//默认初始容量16
private static final int DEFAULT_INITIAL_CAPACITY = 16;
//最大容量为2的30次方
private static final int MAXIMUM_CAPACITY = 1 << 30;
//默认装载因子
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
//桶
Entry<K,V>[] table;
//元素个数
private int size;
//扩容门槛
private int threshold;
//装载因子
private final float loadFactor;
//引用队列，当弱键失效的时候会把Entry添加到这个队列中
//当下次访问map的时候会把失效的Entry清除掉
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
}
Entry内部类
没有key属性
//Entry内部类
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
//可以发现没有key，因为key是作为弱引用存在Refresh类中
V value;
final int hash;
Entry<K,V> next;
/**
* Creates new entry.
*/
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);
}
public String toString() {
return getKey() + "=" + getValue();
}
}
public class WeakReference<T> extends Reference<T> {
/**
* Creates a new weak reference that refers to the given object. The new
* reference is not registered with any queue.
*
* @param referent object the new weak reference will refer to
*/
public WeakReference(T referent) {
super(referent);
}
/**
* Creates a new weak reference that refers to the given object and is
* registered with the given queue.
*
* @param referent object the new weak reference will refer to
* @param q the queue with which the reference is to be registered,
* or <tt>null</tt> if registration is not required
*/
public WeakReference(T referent, ReferenceQueue<? super T> q) {
super(referent, q);
}
}
public abstract class Reference<T> {
...................省略..............
//实际存储key的地方
volatile T referent;
//引用队列
final ReferenceQueue<? super T> queue;
Reference(T referent) {
this(referent, null);
}
Reference(T referent, ReferenceQueue<? super T> queue) {
this.referent = referent;
this.queue = queue;
}
}
从Entry的构造方法我们知道，key和queue最终会传到Reference的构造方法中，这里的key就是Reference的referent属性，它会被gc特殊对待，即当没有强引用存在时，当下一次gc的时候会被清除。
put(K key,V value)方法
添加元素的方法。
public V put(K key, V value) {
//如果key为空，则将key用一个Object常量代替：NULL_KEY
Object k = maskNull(key);
//计算key的hash值
int h = hash(k);
//获取桶
Entry<K,V>[] tab = getTable();
//计算元素在数组中的索引 h&(length-1)
int i = indexFor(h, tab.length);
//遍历桶对应的链表，检测存储位置中是否已存在此key
//如果有，则更新value即可 如果没有 则把此节点添加到此位置的链表头
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);
// 如果插入元素后数量达到扩容阈值就把桶的容量扩容为2倍大小
if (++size >= threshold)
resize(tab.length * 2);
return null;
}
private static final Object NULL_KEY = new Object();
/**
* Use NULL_KEY for key if it is null.
*/
private static Object maskNull(Object key) {
return (key == null) ? NULL_KEY : key;
}
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 Entry<K,V>[] getTable() {
expungeStaleEntries();
return table;
}
/**
* Expunges stale entries from the table.
*翻译：删除过时的条目，即将ReferenceQueue队列中的对象引用全部在table中给删除掉
*思路：如何删除一个table的节点e，方法为：首先计算e的hash值，接着根据hash值找到其在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;
}
}
}
}
private static int indexFor(int h, int length) {
return h & (length-1);//当length为2的幂次方时，等价于h%length
}
由于WeakHashMap与HashMap基本类似，因此，put方法的思路也基本一致。
具体如下：
- 检查key是否为null，如果为null，则将key用一个Object常量代替：NULL_KEY。
在HashMap中是没有进行这样一个替代转换的,而是直接用null作为key存在在HashMap对象中。这是他们其中的一个区别 - 取得key的hash值，
- 根据hash值找到其在table的存储位置 i 。
- 由于table的每个位置存储的可能是一个链表，因此，在此位置 i处的链表中检测是否有此key存在，如果有，则更新其key所对应的value即可。如果没有此key，则将此节点加入到此链表的头结点位置。
在进行上面的4个步骤中，在第四步之前涉及到一个expunge Stale
Entries in table(翻译：在table中删除过时的条目)的一个处理。这个是在HashMap中没有的。
resize(int newCapacity)方法
扩容方法。
void resize(int newCapacity) {
//获取原理旧的数组 getTable()的时候会剔除失效的Entry
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变量
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 {
//否则把元素再转移回旧桶 还是使用旧桶
//因为在transfer的时候会清除失效的Entry，所以元素个数可能没有那么大了 就不需要扩容了。
expungeStaleEntries();
transfer(newTable, oldTable);
table = oldTable;
}
}
/** Transfers all entries from src to dest tables */
private void transfer(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();
//如果key等于null就清除，说明key被gc清理掉了
//则把整个Entry清除
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;
}
}
}
get(Object key)方法
获取元素。
public V get(Object key) {
Object k = maskNull(key);
//计算hash
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;
}
remove(Object key)方法
移除元素。
public V remove(Object key) {
Object k = maskNull(key);
//计算hash值
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;
}
size()
public int size() {
if (size == 0)
return 0;
expungeStaleEntries();
return size;
}
/**
* Returns <tt>true</tt> if this map contains no key-value mappings.
* This result is a snapshot, and may not reflect unprocessed
* entries that will be removed before next attempted access
* because they are no longer referenced.
*/
public boolean isEmpty() {
return size() == 0;
}
这个方法与HashMap方法中size()不一样。在HashMap中的size()方法中，仅仅是返回数组table中存储数据的长度，而这里的size()方法在返回长度之前做了一个：”删除table中过时的数据”这里一个操作，然后才返回数组存储数据的长度的，即返回的是table中真正有意义的数据。这也是HashMap与WeakHashMap的区别之一 。
总结
WeakHashMap和HashMap一样，WeakHashMap也是一个散列表，它存储的内容也是键值对(key-value)映射，而且键和值都可以为null。不过WeakHashMap的键时“弱键”，当WeakHashMap某个键不再正常使用时，会被从WeakHashMap自动删除。更精确的说，对于一个给定的键，其映射的存在并不能阻止垃圾回收器对该键的丢弃，这就使该键称为被终止的，被终止，然后被回收，这样，这就可以认为该键值对应该被WeakHashMap删除。因此，WeakHashMap使用了弱引用作为内部数据的存储方案，，WeakHashMap可以作为简单缓存表的解决方案，当系统内存不足时，垃圾收集器会自动的清除没有在任何其他地方被引用的键值对。如果需要用一张很大的Map作为缓存表时，那么可以考虑使用WeakHashMap。
