Java集合WeakHashMap源碼分析
更新時(shí)間：2023年09月07日 09:41:14 作者：lippon
這篇文章主要介紹了Java集合WeakHashMap源碼分析,和HashMap一樣,WeakHashMap 也是一個(gè)散列表,它存儲(chǔ)的內(nèi)容也是鍵值對(duì)(key-value)映射,而且鍵和值都可以是null,需要的朋友可以參考下
簡(jiǎn)介
WeakHashMap 繼承于AbstractMap，實(shí)現(xiàn)了Map接口。
和HashMap一樣，WeakHashMap 也是一個(gè)散列表，它存儲(chǔ)的內(nèi)容也是鍵值對(duì)(key-value)映射，而且鍵和值都可以是null。
不一樣的是，JDK1.8開始，HashMap中引入了紅黑樹，節(jié)點(diǎn)名從entry改成了node，而WeakHashMap還是沒有被修改，還是采用鏈表形式的拉鏈法解決哈希沖突。
所謂weak，就是WeakHashMap中存儲(chǔ)的鍵值是弱引用的，是很有可能被GC回收的，所以，WeakHashMap中需要對(duì)被GC的鍵的鍵值對(duì)進(jìn)行清除，其實(shí)現(xiàn)原理：
WeakHashMap中有一個(gè)ReferenceQueue用來存儲(chǔ)被GC回收的弱鍵；
當(dāng)每次操作WeakHashMap的時(shí)候，就會(huì)需要同步table和queue，通過同步的行為，就可以刪除table中已經(jīng)被回收了的鍵的鍵值對(duì)。
源碼分析
定義
public class WeakHashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V> {}字段
// 默認(rèn)初始容量，和hashmap一樣
private static final int DEFAULT_INITIAL_CAPACITY = 16;
// 最大容量
private static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認(rèn)負(fù)載因子
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 存儲(chǔ)鍵值對(duì)鏈表頭節(jié)點(diǎn)的數(shù)組
Entry<K,V>[] table;
// 當(dāng)前節(jié)點(diǎn)數(shù)量
private int size;
// 擴(kuò)容閾值
private int threshold;
// 加因子實(shí)際大小
private final float loadFactor;
// 被垃圾回收的弱引用鍵隊(duì)列
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
// 修改次數(shù)
int modCount;和參數(shù)和HashMap大致相同，不同的是，多了一個(gè)引用隊(duì)列，用來存儲(chǔ)被GC的引用，用于之后的同步。
構(gòu)造函數(shù)
// 初始化容量和加載因子的構(gòu)造函數(shù)
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;
// 通過比較位移的方式，得到第一個(gè)大于等于設(shè)定容量的2的冪次的合法容量
while (capacity < initialCapacity)
capacity <<= 1;
// 這個(gè)newtbale就是初始化了一個(gè)capactiy大小的空數(shù)組
table = newTable(capacity);
this.loadFactor = loadFactor;
// 計(jì)算擴(kuò)容閾值
threshold = (int)(capacity * loadFactor);
}
// 初始化容量的構(gòu)造
public WeakHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 默認(rèn)構(gòu)造
public WeakHashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 添加其他map的構(gòu)造
public WeakHashMap(Map<? extends K, ? extends V> m) {
// 設(shè)定容量和加載因子
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY),
DEFAULT_LOAD_FACTOR);
// 把節(jié)點(diǎn)都添加進(jìn)去
putAll(m);
}內(nèi)部類
1.節(jié)點(diǎn)的結(jié)構(gòu)
// 繼承了弱引用，實(shí)現(xiàn)了Map.Entry，所以它的節(jié)點(diǎn)鍵值都是弱引用，不會(huì)防止GC
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
// 節(jié)點(diǎn)存儲(chǔ)值
V value;
// 節(jié)點(diǎn)哈希值
final int hash;
// 下一個(gè)節(jié)點(diǎn)引用
Entry<K,V> next;
// 構(gòu)造，新建節(jié)點(diǎn)
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;
}
// 重寫了比較接口函數(shù)，就比較類型和鍵值
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;
}
// 重寫了hashCode函數(shù)，然會(huì)鍵值的哈希值而不是對(duì)象的哈希值
public int hashCode() {
K k = getKey();
V v = getValue();
return Objects.hashCode(k) ^ Objects.hashCode(v);
}
public String toString() {
return getKey() + "=" + getValue();
}
}2.迭代器
private abstract class HashIterator<T> implements Iterator<T> {
// 當(dāng)前索引
private int index;
// 當(dāng)前元素
private Entry<K,V> entry;
// 上一次返回的元素
private Entry<K,V> lastReturned;
// 實(shí)現(xiàn)fast-faiul機(jī)制
private int expectedModCount = modCount;
// 指向下一個(gè)鍵值（強(qiáng)引用）
private Object nextKey;
// 當(dāng)前節(jié)點(diǎn)（強(qiáng)引用）
private Object currentKey;
// 構(gòu)造
HashIterator() {
index = isEmpty() ? 0 : table.length;
}
// 判斷是否存在下一個(gè)節(jié)點(diǎn)
public boolean hasNext() {
Entry<K,V>[] t = table;
// 如果下一個(gè)而節(jié)點(diǎn)是空的，就需要遍歷table，將下一個(gè)節(jié)點(diǎn)指向table中下一個(gè)不為空的頭節(jié)點(diǎn)
while (nextKey == null) {
Entry<K,V> e = entry;
int i = index;
while (e == null && i > 0)
e = t[--i];
entry = e;
index = i;
if (e == null) {
currentKey = null;
return false;
}
nextKey = e.get(); // hold on to key in strong ref
if (nextKey == null)
entry = entry.next;
}
return true;
}
// 獲取下一個(gè)節(jié)點(diǎn)
protected Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextKey == null && !hasNext())
throw new NoSuchElementException();
lastReturned = entry;
entry = entry.next;
currentKey = nextKey;
nextKey = null;
return lastReturned;
}
// 刪除當(dāng)前節(jié)點(diǎn)
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
WeakHashMap.this.remove(currentKey);
expectedModCount = modCount;
lastReturned = null;
currentKey = null;
}
}
// 值遍歷
private class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
// 鍵的遍歷
private class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
// 鍵值對(duì)的遍歷
private class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}3.集合
// 鍵的集合
private class KeySet extends AbstractSet<K> {
// 調(diào)用迭代器的接口
public Iterator<K> iterator() {
return new KeyIterator();
}
public int size() {
return WeakHashMap.this.size();
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
if (containsKey(o)) {
WeakHashMap.this.remove(o);
return true;
}
else
return false;
}
public void clear() {
WeakHashMap.this.clear();
}
// 分割迭代器，用于并行
public Spliterator<K> spliterator() {
return new KeySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
}
}
// 鍵值對(duì)集合
private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o);
}
public int size() {
return WeakHashMap.this.size();
}
public void clear() {
WeakHashMap.this.clear();
}
// 深拷貝接口
private List<Map.Entry<K,V>> deepCopy() {
List<Map.Entry<K,V>> list = new ArrayList<>(size());
// 將鍵值對(duì)都添加到新的鏈表當(dāng)中
for (Map.Entry<K,V> e : this)
list.add(new AbstractMap.SimpleEntry<>(e));
return list;
}
// 轉(zhuǎn)化為數(shù)組
public Object[] toArray() {
return deepCopy().toArray();
}
// 模板方法的數(shù)組
public <T> T[] toArray(T[] a) {
return deepCopy().toArray(a);
}
// 分割迭代
public Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
}
}方法
1.哈希函數(shù)
// 獲取鍵的哈希值
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);
}2.元素獲取
// 獲取最新的表
private Entry<K,V>[] getTable() {
// 之所以要獲取最新的表，是因?yàn)樾枰葎h除GC的Key
expungeStaleEntries();
return table;
}
// 獲取對(duì)應(yīng)鍵的元素值
public V get(Object key) {
// 如果key是null那么就用一個(gè)final的空對(duì)象，這樣保證每次null的對(duì)象相同
Object k = maskNull(key);
// 獲取key的哈希值
int h = hash(k);
// 獲取最新的表，在這里會(huì)觸發(fā)一次表的更新，就是將GC了的key給移除
Entry<K,V>[] tab = getTable();
// 根據(jù)哈希值獲取當(dāng)前table中對(duì)應(yīng)的索引
int index = indexFor(h, tab.length);
// 拿出節(jié)點(diǎn)
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;
}3.元素添加
// 添加獲取修改鍵值
public V put(K key, V value) {
// 這些操作和上面差不多
Object k = maskNull(key);
int h = hash(k);
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
// 遍歷鏈表，如果有相同的key，那就直接修改值
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];
// 數(shù)組頭添加新的節(jié)點(diǎn)，采用了頭插法
tab[i] = new Entry<>(k, value, queue, h, e);
if (++size >= threshold)
// 如果當(dāng)數(shù)量大于等于閾值則進(jìn)行擴(kuò)容
resize(tab.length * 2);
return null;
}4.刪除被GC的節(jié)點(diǎn)
WeakHashTable就是通過這個(gè)函數(shù)實(shí)現(xiàn)弱引用被GC后的表中節(jié)點(diǎn)的回收。
private void expungeStaleEntries() {
// 遍歷引用隊(duì)列中被標(biāo)記回收得值
for (Object x; (x = queue.poll()) != null; ) {
// 獲取鎖，防止其他線程進(jìn)入
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;
// 刪除節(jié)點(diǎn)
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; // 將鍵對(duì)應(yīng)得值指向空，這樣就可以讓GC來回收原來得對(duì)象
size--;
break;
}
prev = p;
p = next;
}
}
}
}5.擴(kuò)容
擴(kuò)容的大致其實(shí)和HashMap差不多
// 擴(kuò)容到新得容量
void resize(int newCapacity) {
Entry<K,V>[] oldTable = getTable();
int oldCapacity = oldTable.length;
// 邊界判斷
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 新建一個(gè)標(biāo)準(zhǔn)大小的數(shù)組
Entry<K,V>[] newTable = newTable(newCapacity);
// 將舊數(shù)組上的數(shù)據(jù)復(fù)制過去
transfer(oldTable, newTable);
// 更新引用
table = newTable;
// 查看size是不是大于，擴(kuò)容閾值的一半，如果不是，說明size又變小了，不需要擴(kuò)容了
if (size >= threshold / 2) {
// 更新擴(kuò)容閾值
threshold = (int)(newCapacity * loadFactor);
} else {
// 更新GC后的key
expungeStaleEntries();
// 返回原有大小的表
transfer(newTable, oldTable);
table = oldTable;
}
}
// 將原表復(fù)制到目標(biāo)表
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;
// 遍歷鏈表，再將節(jié)點(diǎn)放到新表的對(duì)應(yīng)位置
while (e != null) {
Entry<K,V> next = e.next;
Object key = e.get();
if (key == null) {
// 用于GC
e.next = null;
e.value = null;
size--;
} else {
// 獲取到對(duì)應(yīng)的索引
int i = indexFor(e.hash, dest.length);
e.next = dest[i];
dest[i] = e;
}
e = next;
}
}
}6.元素刪除
public V remove(Object key) {
// 同上
Object k = maskNull(key);
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--;
// 如果是頭節(jié)點(diǎn)
if (prev == e)
tab[i] = next;
else
prev.next = next;
return e.value;
}
prev = e;
e = next;
}
return null;
}總結(jié)
- 大致的1.7的哈希表差不多，采用拉鏈法解決哈希沖突，只有鏈表，采用頭插法，包括初始容量、擴(kuò)容閾值和大小。
- 表中的節(jié)點(diǎn)繼承了弱引用，這說明它的引用的鍵是會(huì)被垃圾回收的。
- 主要的區(qū)別就是它再對(duì)表進(jìn)行修改的時(shí)候，都會(huì)調(diào)用expungeStaleEntries函數(shù)，用來刪除那些已經(jīng)被垃圾回收了的鍵，所對(duì)應(yīng)的鍵值對(duì)。需要?jiǎng)h除的鍵會(huì)存放在ReferenceQueue 中，每次去獲取需要被刪除的key。
- 和其他集合的重要區(qū)別，WeakHashMap沒有實(shí)現(xiàn)克隆和序列化的接口。
到此這篇關(guān)于Java集合WeakHashMap源碼分析的文章就介紹到這了,更多相關(guān)WeakHashMap源碼分析內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
如何利用Java輸出鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
這篇文章主要給大家介紹了關(guān)于如何利用Java輸出鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用java具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2021-12-12
java中i=i++和j=i++的區(qū)別小結(jié)
這篇文章主要給大家介紹了關(guān)于java中i=i++和j=i++區(qū)別的相關(guān)資料，文中通過圖文介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
SpringBoot導(dǎo)出PDF的四種實(shí)現(xiàn)方法詳解
在Spring?Boot應(yīng)用程序中實(shí)現(xiàn)PDF導(dǎo)出功能,可以選擇多種庫(kù)和技術(shù)棧,本文為大家整理了四種常見的方法,感興趣的小伙伴可以參考一下2025-02-02
Redis Java Lettuce驅(qū)動(dòng)框架原理解析
這篇文章主要介紹了Redis Java Lettuce驅(qū)動(dòng)框架原理解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-12-12
在RedHat系統(tǒng)上安裝JDK與Tomcat的步驟
這篇文章主要介紹了在RedHat系統(tǒng)上安裝Java與Tomcat的步驟,同樣適用于CentOS等RedHat系的Linux系統(tǒng),需要的朋友可以參考下2015-11-11
這篇文章主要介紹了Java實(shí)現(xiàn)文件讀取和寫入過程解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值。,需要的朋友可以參考下2019-10-10
SpringCloud Gateway HttpWebHandlerAdapter鏈路調(diào)用請(qǐng)求流程介
Spring Cloud Gateway旨在為微服務(wù)架構(gòu)提供一種簡(jiǎn)單有效的、統(tǒng)一的 API 路由管理方式。Spring Cloud Gateway 作為 Spring Cloud 生態(tài)系中的網(wǎng)關(guān)，它不僅提供統(tǒng)一的路由方式，并且基于 Filter 鏈的方式提供了網(wǎng)關(guān)基本的功能，例如：安全、監(jiān)控/埋點(diǎn)和限流等2022-10-10
jdk8的datetime時(shí)間函數(shù)使用示例
這篇文章主要介紹了jdk8的datetime時(shí)間函數(shù)使用示例,需要的朋友可以參考下2014-03-03
ehcache開源緩存框架_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
Ehcache是現(xiàn)在最流行的純Java開源緩存框架，這篇文章主要介紹了ehcache框架的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-07-07
這篇文章主要為大家詳細(xì)介紹了Java如何將文件壓縮成zip和下載,并處理base64和url,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以參考一下2025-04-04