java.uitl.WeakHashMap
程序员文章站
2022-05-14 20:02:07
...
在上篇文章中我提到过java.lang.ref.Reference类，这个东西有点用。
http://wangxinchun.iteye.com/blog/1954187
今天我就介绍下jdk中关于这块的一个应用：WeakHashMap，一个永不满的hashmap,一个和垃圾回收器相依相偎的缓存Map。
先看一个例子：
在这个例子中，无限分配1M的内存，并存入WeakHashMap，程序运行多久都不会内存溢出。
要问原理，请参看链接：
http://wangxinchun.iteye.com/blog/1954187
本文重点关注WeakHashMap的实现。
介绍：
首先，WeakHashMap 是一个map，具有map的一般实现。
其次，它很大程度上实现和HashMap极为相似。负载因子，Entry数组，默认大小等等。
独特处是 它的实现依赖了 ReferenceQueue 和 WeakReference，这也是WeakHashMap 和HashMap的特性差异所依赖的底层技术。
下面简单分析下WeakHashMap 的部分源码，和HashMap相似的请查看
http://wangxinchun.iteye.com/blog/1872356
以上是我的分析，如有错误，请指正～
http://wangxinchun.iteye.com/blog/1954187
今天我就介绍下jdk中关于这块的一个应用：WeakHashMap，一个永不满的hashmap,一个和垃圾回收器相依相偎的缓存Map。
先看一个例子：
package com.qunar.flight.tts.policy.client.validator.impl;
import java.util.WeakHashMap;
public class Test {
public static void main(String[] args) throws Exception {
WeakHashMap<byte[][], byte[][]> map = new WeakHashMap<byte[][], byte[][]>();
for (int i = 0; i < 10000000; i++) {
map.put(new byte[1000][1000], new byte[1000][1000]);
System.err.println(map.size());
}
}
}
在这个例子中，无限分配1M的内存，并存入WeakHashMap，程序运行多久都不会内存溢出。
要问原理，请参看链接：
http://wangxinchun.iteye.com/blog/1954187
本文重点关注WeakHashMap的实现。
介绍：
首先，WeakHashMap 是一个map，具有map的一般实现。
其次，它很大程度上实现和HashMap极为相似。负载因子，Entry数组，默认大小等等。
独特处是 它的实现依赖了 ReferenceQueue 和 WeakReference，这也是WeakHashMap 和HashMap的特性差异所依赖的底层技术。
下面简单分析下WeakHashMap 的部分源码，和HashMap相似的请查看
http://wangxinchun.iteye.com/blog/1872356
public class WeakHashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V> {
/**
* 默认Map内的Entry数字的默认大小
*/
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;
/**
map所依赖的底层数组，业界文章多称之概念为：桶
*/
private Entry[] table;
/**
* 现有的记录数量
*/
private int size;
/**
* 下一次resize 增长的值（capacity * load factor）
*/
private int threshold;
/**
* 负载因子
*/
private final float loadFactor;
/**
* Reference queue for cleared WeakEntries
这个queue主要用于保存被垃圾回收器回收后的key对应的引用
*/
private final ReferenceQueue<K> queue = new ReferenceQueue<K>();
/**
* 详细 请查看ConcurrentHashMap 的分析。
*/
private volatile int modCount;
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 = new Entry[capacity];
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
}
public WeakHashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
DEFAULT_LOAD_FACTOR);
putAll(m);
}
/**
* 用来代替key = null的 记录的key
*/
private static final Object NULL_KEY = new Object();
/**
* 把null转为 NULL_KEY
*/
private static Object maskNull(Object key) {
return (key == null ? NULL_KEY : key);
}
/**
*maskNull 的反模式
*/
private static <K> K unmaskNull(Object key) {
return (K) (key == NULL_KEY ? null : key);
}
/**
* Checks for equality of non-null reference x and possibly-null y. By
* default uses Object.equals.
*/
static boolean eq(Object x, Object y) {
return x == y || x.equals(y);
}
/**
* 定位h所在桶的位置
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
/**
* 清理陈旧的Entry，这个方法很早很重要，也是WeakHashMap实现的核心方法之一
*/
private void expungeStaleEntries() {
Entry<K,V> e;
while ( (e = (Entry<K,V>) queue.poll()) != null) { //queue.poll() 能取出的对象都是被垃圾回收器回收过的，while循环可以保证清理掉所有被回收过的对象
int h = e.hash;
int i = indexFor(h, 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) { //一直找到一个对象，是 queue.poll()，准备对其进行回收
if (prev == e) //此种情况：只有e出现在了桶的第一个位置
table[i] = next;
else //如果没有出现在桶的第一个位置，那么要保证e.prev.next=e.next ，这个很重要！否则回去丢失数据
prev.next = next;
e.next = null; // Help GC 让当前e对象不要引用e.next，让GC回收
e.value = null; // 清理value值
size--; //数量也要减1
break;退出
}
prev = p; //记录上一个
p = next; //继续寻找等于queue.poll() 的Entry对象
}
}
}
/**
* 每次获取桶会清理已经被垃圾回收器回收的数据
*/
private Entry[] getTable() {
expungeStaleEntries();
return table;
}
/**
* 每次取size之前会清理已经被垃圾回收器回收的数据
*/
public int size() {
if (size == 0)
return 0;
expungeStaleEntries();
return size;
}
/
public boolean isEmpty() {
return size() == 0;
}
/**
* 获取一个对象，和普通的HashMap没有区别
*/
public V get(Object key) {
Object k = maskNull(key); //如果key =null，需要做特殊处理。
int h = HashMap.hash(k.hashCode());
Entry[] 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())) //注意：e.get() 返回的引用的值，如果值已经失效，那么e.get() 返回null。这也是不能使用Null为key的原因！！！
return e.value;
e = e.next;
}
return null;
}
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
/**
同get 方法
*/
Entry<K,V> getEntry(Object key) {
Object k = maskNull(key);
int h = HashMap.hash(k.hashCode());
Entry[] tab = getTable();
int index = indexFor(h, tab.length);
Entry<K,V> e = tab[index];
while (e != null && !(e.hash == h && eq(k, e.get())))
e = e.next;
return e;
}
/** 添加记录*/
public V put(K key, V value) {
K k = (K) maskNull(key); // null ->NULL_KEY 的转换
int h = HashMap.hash(k.hashCode());
Entry[] 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,V>(k, value, queue, h, e); //注意：queue：如果k失效，那么会添加以key为值的WeakReference到queue ，h：key的hash值
if (++size >= threshold)
resize(tab.length * 2);
return null;
}
/**
扩容 （和hashmap 没有区别）
*/
void resize(int newCapacity) {
Entry[] oldTable = getTable();
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(oldTable, newTable);
table = newTable;
if (size >= threshold / 2) {
threshold = (int)(newCapacity * loadFactor);
} else {
expungeStaleEntries();
transfer(newTable, oldTable);
table = oldTable;
}
}
/** 扩容的时候，数据的处理 */
private void transfer(Entry[] src, Entry[] 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) { //扩容的时候，发现了key 已经被垃圾回收器回收，那么做引用的处理。
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;
}
}
}
public void putAll(Map<? extends K, ? extends V> m) {
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
/**删除一个记录
*/
public V remove(Object key) {
Object k = maskNull(key);
int h = HashMap.hash(k.hashCode());
Entry[] 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; //循环桶进入下一轮寻找key
e = next;
}
return null;
}
/** Special version of remove needed by Entry set
同上
*/
Entry<K,V> removeMapping(Object o) {
if (!(o instanceof Map.Entry))
return null;
Entry[] tab = getTable();
Map.Entry entry = (Map.Entry)o;
Object k = maskNull(entry.getKey());
int h = HashMap.hash(k.hashCode());
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 && e.equals(entry)) {
modCount++;
size--;
if (prev == e)
tab[i] = next;
else
prev.next = next;
return e;
}
prev = e;
e = next;
}
return null;
}
/**
* 清空
*/
public void clear() {
// 先清理已经被垃圾回收器处理过的记录
while (queue.poll() != null)
;
modCount++;
Entry[] tab = table;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
size = 0;
//再次处理被垃圾回收器处理过的记录
while (queue.poll() != null)
;
}
/**
*是否包含
*/
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) //e != null ，但是e.value 可能被回收过的。
if (value.equals(e.value))
return true;
return false;
}
/**
同上
*/
private boolean containsNullValue() {
Entry[] tab = getTable();
for (int i = tab.length ; i-- > 0 ;)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (e.value==null)
return true;
return false;
}
/**
* Entry继承了WeakReference，
*/
private static class Entry<K,V> extends WeakReference<K> implements Map.Entry<K,V> {
private V value;
private final int hash; //这个值用在 Map.put 方法里面，判断key是否一致。
private Entry<K,V> next;
/**
* Creates new entry.
*/
Entry(K key, V value,
ReferenceQueue<K> queue,
int hash, Entry<K,V> next) {
super(key, queue); //这里指定了queue 来跟踪key的被垃圾回收器回收的时机
this.value = value;
this.hash = hash; //entry的hash 是 key的hash值
this.next = next;
}
public K getKey() {
return WeakHashMap.<K>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;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) { //key相等
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2))) //并且值相等
return true;
}
return false;
}
public int hashCode() {
Object k = getKey();
Object v = getValue();
return ((k==null ? 0 : k.hashCode()) ^
(v==null ? 0 : v.hashCode()));
}
public String toString() {
return getKey() + "=" + getValue();
}
}
}
以上是我的分析，如有错误，请指正～