關(guān)于HashMap源碼解讀
更新時(shí)間：2024年09月20日 08:51:22 作者：億先生@
HashMap是基于哈希表的Map接口實(shí)現(xiàn),主要用于存儲(chǔ)鍵值對(duì),它通過(guò)數(shù)組、鏈表和紅黑樹來(lái)實(shí)現(xiàn),解決了哈希沖突問(wèn)題,Java?8中,HashMap對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行了優(yōu)化,引入紅黑樹來(lái)提高查找效率,此外,HashMap是非線程安全的,適用于單線程環(huán)境
一、概述
- HashMap 是基于哈希表實(shí)現(xiàn)的，每一個(gè)元素是一個(gè) key-value 對(duì)，其內(nèi)部通過(guò)單鏈表解決沖突問(wèn)題，容量不足（超過(guò)了閾值）時(shí)，同樣會(huì)自動(dòng)增長(zhǎng)。
- HashMap 是非線程安全的，只是適用于單線程環(huán)境，多線程環(huán)境可以采用并發(fā)包下的concurrentHashMap
- HashMap 實(shí)現(xiàn)了Serializable接口，支持序列化，實(shí)現(xiàn)了Cloneable接口，能被克隆。
- HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn).此實(shí)現(xiàn)提供所有可選的映射操作,并允許使用null值和null鍵。此類不保證映射的順序,特別是它不保證該順序恒久不變。
- Java8中又對(duì)此類底層實(shí)現(xiàn)進(jìn)行了優(yōu)化，比如引入了紅黑樹的結(jié)構(gòu)以解決哈希碰撞
JDK1.7和JDK1.8的區(qū)別
| 比較 | HashMap1.7 | HashMap1.8 |
|---|---|---|
| 數(shù)據(jù)結(jié)構(gòu) | 數(shù)組+鏈表 | 數(shù)組+鏈表+紅黑樹 |
| 節(jié)點(diǎn) | Entry（hash是可變的，因?yàn)橛衦ehash的操作） | Node TreeNode（為了轉(zhuǎn)換紅黑樹、hash是final修飾，也就是說(shuō)hash值一旦確定，就不會(huì)再重新計(jì)算hash值了） |
| Hash算法 | 較為復(fù)雜 | 異或Hash右移16位 |
| 對(duì)Null的處理 | 單獨(dú)寫一個(gè)putForNull()方法處理 | 作為以一個(gè)Hash值為0的普通節(jié)點(diǎn)處理 |
| 初始化 | 賦值給一個(gè)空數(shù)值，put時(shí)初始化 | 沒(méi)有賦值，懶加載，put時(shí)初始化 |
| 擴(kuò)容 | 插入前擴(kuò)容 | 插入后，初始化，樹化時(shí)擴(kuò)容 |
| 節(jié)點(diǎn)插入 | 頭插法 | 尾插法 |
什么是懶加載？
- 即延遲加載(Lazyload)。
- 簡(jiǎn)單的說(shuō)就是只有當(dāng)我們?nèi)フ{(diào)用到它時(shí)才會(huì)去做加載。
二、HashMap的數(shù)據(jù)結(jié)構(gòu)
HashMap 底層采用數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。
數(shù)組是 HashMap 的主體，用于存儲(chǔ)鍵值對(duì)；鏈表用于解決哈希沖突；紅黑樹是在鏈表長(zhǎng)度超過(guò)一定閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)換為紅黑樹，以提高查找效率。
三、迭代方式
HashMap的迭代種類
- 分別遍歷Key和Value
- 使用Iterator迭代器迭代
- 通過(guò)get的方式（不建議使用）
- Map接口中的默認(rèn)方法（映射方式）JDK1.8
public class HashMapExam {
public static void main(String[] args) {
Map<Integer, String> map = new HashMap<>();
for (int i = 0; i < 15; i++) {
map.put(i, new String(new char[]{(char) ('A'+ i)}));
}
System.out.println("======Key和Value=======");
for (Integer key:map.keySet()) {
System.out.println(key);
}
for (String value:map.values()) {
System.out.println(value);
}
System.out.println("======Iterator迭代器=======");
Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, String> mapEntry = iterator.next();
System.out.println(mapEntry.getKey()+ "====" + mapEntry.getValue());
}
System.out.println("======Get的方式=======");
Set<Integer> keySet = map.keySet();
for (Integer key : keySet) {
System.out.println(key + "====" + map.get(key));
}
System.out.println("======forEach=======");
map.forEach((key,value) -> System.out.println(key+ "----" + value));
}
}四、源碼分析
1、HashMap繼承關(guān)系
- Cloneable 空接口：表示可以克隆。創(chuàng)建并返回HashMap對(duì)象的一個(gè)副本；
- Serializable 序列化接口：屬于標(biāo)記性接口。HashMap 對(duì)象可以倍序列化和反序列化。
- AbstractMap：父類提供了Map實(shí)現(xiàn)接口。以最大限度地減少實(shí)現(xiàn)此接口所需的工作。
HashMap 繼承關(guān)系如下圖所示：
補(bǔ)充：通過(guò)上述繼承關(guān)系我們發(fā)現(xiàn)一個(gè)很奇怪的現(xiàn)象， 就是HashMap已經(jīng)繼承了AbstractMap而AbstractMap類實(shí)現(xiàn)了Map接口，那為什么HashMap還要在實(shí)現(xiàn)Map接口呢？同樣在ArrayList中LinkedList中都是這種結(jié)構(gòu)。
據(jù) java 集合框架的創(chuàng)始人Josh Bloch描述，這樣的寫法是一個(gè)失誤。在java集合框架中，類似這樣的寫法很多，最開(kāi)始寫java集合框架的時(shí)候，他認(rèn)為這樣寫，在某些地方可能是有價(jià)值的，直到他意識(shí)到錯(cuò)了。顯然的，JDK的維護(hù)者，后來(lái)不認(rèn)為這個(gè)小小的失誤值得去修改，所以就這樣存在下來(lái)了。
2、成員變量
// 序列化版本號(hào) private static final long serialVersionUID = 362498820763181265L; // 默認(rèn)的初始容量是16 --> 1<<4 相當(dāng)于 1*2的4次方也就是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量（傳入容量過(guò)大將被這個(gè)替換） static final int MAXIMUM_CAPACITY = 1 << 30; // 默認(rèn)加載因子為0.75，通過(guò)這個(gè)來(lái)算出臨界值 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 當(dāng)桶（bucket）上的結(jié)點(diǎn)數(shù)大于這個(gè)值時(shí)會(huì)轉(zhuǎn)換成紅黑樹 static final int TREEIFY_THRESHOLD = 8; // 當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)小于這個(gè)值時(shí)樹轉(zhuǎn)鏈表 static final int UNTREEIFY_THRESHOLD = 6; // 桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹對(duì)應(yīng)的數(shù)組長(zhǎng)度最小的值 static final int MIN_TREEIFY_CAPACITY = 64; //存儲(chǔ)元素的數(shù)組 transient Node<K,V>[] table; //存放具體元素的集合 transient Set<Map.Entry<K,V>> entrySet; //存放元素的個(gè)數(shù)，注意這個(gè)不等于數(shù)組的長(zhǎng)度。 transient int size; // 每次擴(kuò)容和更改map結(jié)構(gòu)的計(jì)數(shù)器 transient int modCount; // 臨界值 當(dāng)實(shí)際大小(容量*負(fù)載因子)超過(guò)臨界值時(shí)，會(huì)進(jìn)行擴(kuò)容 int threshold; // 負(fù)載因子實(shí)際大小 final float loadFactor;
3、構(gòu)造方法
①HashMap()
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 將默認(rèn)的加載因子0.75賦值給loadFactor，并沒(méi)有創(chuàng)建數(shù)組
}②HashMap(int initialCapacity)
// 指定“容量大小”的構(gòu)造函數(shù)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}③HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity, float loadFactor) {
//判斷初始化容量initialCapacity是否小于0
if (initialCapacity < 0)
//如果小于0，則拋出非法的參數(shù)異常IllegalArgumentException
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//判斷初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次冪
if (initialCapacity > MAXIMUM_CAPACITY)
//如果超過(guò)MAXIMUM_CAPACITY，會(huì)將MAXIMUM_CAPACITY賦值給initialCapacity
initialCapacity = MAXIMUM_CAPACITY;
//判斷負(fù)載因子loadFactor是否小于等于0或者是否是一個(gè)非數(shù)值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
//如果滿足上述其中之一，則拋出非法的參數(shù)異常IllegalArgumentException
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//將指定的加載因子賦值給HashMap成員變量的負(fù)載因子loadFactor
this.loadFactor = loadFactor;
/*
tableSizeFor(initialCapacity) 判斷指定的初始化容量是否是2的n次冪，如果不是那么會(huì)變?yōu)楸戎? 定初始化容量大的最小的2的n次冪。這點(diǎn)上述已經(jīng)講解過(guò)。
但是注意，在tableSizeFor方法體內(nèi)部將計(jì)算后的數(shù)據(jù)返回給調(diào)用這里了，并且直接賦值給threshold邊 界值了。有些人會(huì)覺(jué)得這里是一個(gè)bug,應(yīng)該這樣書寫：
this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
這樣才符合threshold的意思（當(dāng)HashMap的size到達(dá)threshold這個(gè)閾值時(shí)會(huì)擴(kuò)容）。
但是，請(qǐng)注意，在jdk8以后的構(gòu)造方法中，并沒(méi)有對(duì)table這個(gè)成員變量進(jìn)行初始化，table的初始化被推 遲到了put方法中，在put方法中會(huì)對(duì)threshold重新計(jì)算，put方法的具體實(shí)現(xiàn)我們下面會(huì)進(jìn)行講解
*/
this.threshold = tableSizeFor(initialCapacity);
}
最后調(diào)用了tableSizeFor，來(lái)看一下方法實(shí)現(xiàn)：
/**
* Returns a power of two size for the given target capacity.
返回比指定初始化容量大的最小的2的n次冪
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}④HashMap(Map<? extends K, ? extends V> m)
//構(gòu)造一個(gè)映射關(guān)系與指定 Map 相同的新 HashMap。
public HashMap(Map<? extends K, ? extends V> m) {
//負(fù)載因子loadFactor變?yōu)槟J(rèn)的負(fù)載因子0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
// 最后調(diào)用了putMapEntries，來(lái)看一下方法實(shí)現(xiàn)：
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//獲取參數(shù)集合的長(zhǎng)度
int s = m.size();
if (s > 0)
{
//判斷參數(shù)集合的長(zhǎng)度是否大于0，說(shuō)明大于0
if (table == null) // 判斷table是否已經(jīng)初始化
{ // pre-size
// 未初始化，s為m的實(shí)際元素個(gè)數(shù)
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 計(jì)算得到的t大于閾值，則初始化閾值
if (t > threshold)
threshold = tableSizeFor(t);
}
// 已初始化，并且m元素個(gè)數(shù)大于閾值，進(jìn)行擴(kuò)容處理
else if (s > threshold)
resize();
// 將m中的所有元素添加至HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}4、成員方法
①Node類
Node 類是 HashMap 中的靜態(tài)內(nèi)部類，實(shí)現(xiàn)Map·Entry 接口，定義了 key 鍵、value 值、next 節(jié)點(diǎn)，也就是說(shuō)元素之間構(gòu)成單向鏈表。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}②TreeNode類（Java新加的）
紅黑樹結(jié)構(gòu)包含前、后、左、右節(jié)點(diǎn)，以及標(biāo)志是否為紅黑樹的字段
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
....
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
....
}
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
static int tieBreakOrder(Object a, Object b) {
....
}
final void treeify(Node<K,V>[] tab) {
....
}
final Node<K,V> untreeify(HashMap<K,V> map) {
....
}
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
....
}
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
....
}
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
....
}
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
....
}
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
....
}
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
....
}
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
....
}
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
....
}
}③Hash方法
在JDK1.8及之后對(duì)Hash算法進(jìn)行了改良，使用較為復(fù)雜 異或Hash右移16位。
static final int hash(Object key) {
int h;
// (h = key.hashCode()) ^ (h >>> 16)：異或Hash右移16位算法
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}④Get方法
下面是JDK1.8中HashMap的Get方法的簡(jiǎn)要實(shí)現(xiàn)過(guò)程：
- 首先，需要計(jì)算鍵的哈希值，并通過(guò)哈希值計(jì)算出在數(shù)組中的索引位置。
- 如果該位置上的元素為空，說(shuō)明沒(méi)有找到對(duì)應(yīng)的鍵值對(duì)，直接返回null。
- 如果該位置上的元素不為空，遍歷該位置上的元素，如果找到了與當(dāng)前鍵相等的鍵值對(duì)，那么返回該鍵值對(duì)的值，否則返回null。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}get方法看起來(lái)很簡(jiǎn)單，就是通過(guò)同樣的 hash 得到 key 的 hash 值。重點(diǎn)看下 getNode 方法：
final Node<K,V> getNode(int hash, Object key) {
// 當(dāng)前 HashMap 的散列表的引用
Node<K,V>[] tab;
// first：桶頭元素
// e：用于存儲(chǔ)臨時(shí)元素
Node<K,V> first, e;
// n：table 數(shù)組的長(zhǎng)度
int n;
// 元素中的 k
K k;
// 將 table 賦值給 tab，不等于 null 說(shuō)明有數(shù)據(jù)，（n = table.length）> 0 同理說(shuō)明 table 中有值
if ((tab = table) != null && (n = tab.length) > 0 &&
// 同時(shí)將 該位置的元素賦值為 first
(first = tab[(n - 1) & hash]) != null) {
// 定位到了桶的到的位置就是想要獲取的 key 對(duì)應(yīng)的，直接返回該元素
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 到這一步說(shuō)明定位到的元素不是想要的，且該位置不僅僅有一個(gè)元素，想要判斷是鏈表還是樹
if ((e = first.next) != null) {
// 是否已經(jīng)樹化
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 處理鏈表的情況
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 遍歷不到返回null
return null;
}⑤Put方法
下面是 JDK 1.8 中 HashMap 的 put 方法的簡(jiǎn)要實(shí)現(xiàn)過(guò)程：
- 首先，put 方法會(huì)計(jì)算鍵的哈希值（通過(guò)調(diào)用 hash 方法），并通過(guò)哈希值計(jì)算出在數(shù)組中的索引的位置。
- 如果該位置上的元素為空，那么直接將鍵值對(duì)存儲(chǔ)在該位置上。
- 如果該位置上的元素不為空，那么遍歷該位置上的元素，如果找到了與當(dāng)前鍵相等的鍵值對(duì)，那么將該鍵值對(duì)的值更新為當(dāng)前值，并返回舊值。
- 如果該位置上的元素不為空，但沒(méi)有與當(dāng)前鍵相等的鍵值對(duì)，那么將鍵值對(duì)插入到鏈表或紅黑樹中（如果該位置上的元素?cái)?shù)量超過(guò)一個(gè)閾值，就會(huì)將鏈表轉(zhuǎn)化為紅黑樹來(lái)提高效率）。
- 如果插入成功，返回被替換的值；如果插入失敗，返回null。
- 插入成功后，如果需要擴(kuò)容，那么就進(jìn)行一次擴(kuò)容操作。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}核心其實(shí)是通過(guò)putValue方法實(shí)現(xiàn)的，在傳給putValue的參數(shù)中，先調(diào)用hash獲取了一個(gè)hashCode。
putValue 方法主要實(shí)現(xiàn)如下，給大家增加了注釋：
/**
* Implements Map.put and related methods.
*
* @param hash key 的 hash 值
* @param key key 值
* @param value value 值
* @param onlyIfAbsent true：如果某個(gè) key 已經(jīng)存在那么就不插了；false 存在則替換，沒(méi)有則新增。這里為 false
* @param evict 不用管理。我也不認(rèn)識(shí)
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab 表示當(dāng)前 hash 散列表的引用
Node<K,V>[] tab;
// 表示具體的散列表中的元素
Node<K,V> p;
// n：表示散列表數(shù)組的長(zhǎng)度
// i：表示路由尋址的結(jié)果
int n, i;
// 將 table 賦值發(fā)給 tab，如果 tab == null，說(shuō)明 table 還沒(méi)有被初始化。則此時(shí)是需要去創(chuàng)建 table 的
// 為什么這個(gè)時(shí)候才去創(chuàng)建散列表，因?yàn)榭赡軇?chuàng)建了 HashMap 時(shí)候可能并沒(méi)有存放數(shù)據(jù)，如果在初始化 HashMap 的時(shí)候創(chuàng)建散列表，勢(shì)必會(huì)造成空間的浪費(fèi)
// 這里也就是延遲初始化的邏輯
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果 p == null，說(shuō)明尋址到的桶沒(méi)有元素。那么就將 key-value 封裝到 Node 中，并放到尋址到的下標(biāo)為 i 的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 到這里說(shuō)明 該位置已經(jīng)有數(shù)據(jù)了，且此時(shí)可能是鏈表結(jié)構(gòu)，也可能是樹結(jié)構(gòu)
else {
// e 表示找到了一個(gè)與當(dāng)前要插入的 key-value 一致的元素
Node<K,V> e;
// 臨時(shí)的 key
K k;
// p 的值就是上一步 if 中的結(jié)果即：此時(shí)的（p = tab[i = (n - 1) & hash]）不等于 null
// p 是原來(lái)的已經(jīng)在 i 的位置的元素，且新插入的 key 是等于 p 中的 key
// 說(shuō)明找到了和當(dāng)前需要插入的元素相同的元素（其實(shí)就是需要替換而且）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 將 p 的值賦值給 e
e = p;
// 說(shuō)明已經(jīng)樹化，紅黑樹會(huì)有單獨(dú)的文章介紹，本文不再闡述
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 如果 p.next == null 說(shuō)明 p 是最后一個(gè)元素，說(shuō)明，該元素在鏈表中也沒(méi)有重復(fù)的
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 直接將 key-value 封裝到 Node 中并且添加到 p 的后面
p.next = newNode(hash, key, value, null);
// 當(dāng)元素已經(jīng)是 7 了，再來(lái)一個(gè)就是 8 個(gè)了，那么就需要進(jìn)行樹化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 樹化
treeifyBin(tab, hash);
break;
}
// 在鏈表中找到了某個(gè)和當(dāng)前元素一樣的元素，即需要做替換操作了
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 將e（即p.next）賦值給e，這就是為了繼續(xù)遍歷鏈表的下一個(gè)元素（沒(méi)啥好說(shuō)的）下面的有張圖幫助大家理解
p = e;
}
}
// 如果條件成立，說(shuō)明找到了需要替換的數(shù)據(jù)
if (e != null) {
// 這里不就是使用新的值賦值為舊的值嘛
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 這個(gè)方法沒(méi)用，里面啥都沒(méi)有
afterNodeAccess(e);
// HashMap put 方法的返回值是原來(lái)位置的元素值
return oldValue;
}
}
// 上面說(shuō)過(guò)，對(duì)于散列表 結(jié)構(gòu)修改次數(shù)，那么就修改 modCount 的次數(shù)
++modCount;
// size 即散列表中的元素個(gè)數(shù)，添加后需要自增，如果自增后的值大于擴(kuò)容的閾值，那么就觸發(fā)擴(kuò)容操作
if (++size > threshold)
resize();
// 啥也沒(méi)干
afterNodeInsertion(evict);
// 原來(lái)位置沒(méi)有值，那么就返回 null 唄
return null;
}⑥Resize方法
什么情況下會(huì)擴(kuò)容（擴(kuò)原來(lái)的2倍）：
- 容器初始化的時(shí)候
- 元素個(gè)數(shù)大于臨界值的時(shí)候
- 桶中的個(gè)數(shù)大于8時(shí)，并且數(shù)量小于64時(shí)
HashMap的擴(kuò)容是什么： - 首先會(huì)新建一個(gè)比原來(lái)大于2倍的哈希表
- 遍歷舊哈希表的每個(gè)桶，重新計(jì)算桶的元素的新位置（rehash方式）
- 如果高位新增1，則 原位置+舊容器
- 如果高位沒(méi)有新增1，則 原位置
- 將計(jì)算出新位置的元素放進(jìn)新哈希表中，
- 并且將舊哈希表中對(duì)應(yīng)的元素設(shè)置為null，方便后面GC回收
final Node<K,V>[] resize() {
//得到當(dāng)前數(shù)組
Node<K,V>[] oldTab = table;
//如果當(dāng)前數(shù)組等于null長(zhǎng)度返回0，否則返回當(dāng)前數(shù)組的長(zhǎng)度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//當(dāng)前閥值點(diǎn) 默認(rèn)是12(16*0.75)
int oldThr = threshold;
int newCap, newThr = 0;
//如果老的數(shù)組長(zhǎng)度大于0
//開(kāi)始計(jì)算擴(kuò)容后的大小
if (oldCap > 0) {
// 超過(guò)最大值就不再擴(kuò)充了，就只好隨你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
//修改閾值為int的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
/*
沒(méi)超過(guò)最大值，就擴(kuò)充為原來(lái)的2倍
1)(newCap = oldCap << 1) < MAXIMUM_CAPACITY 擴(kuò)大到2倍之后容量要小于最大容量
2）oldCap >= DEFAULT_INITIAL_CAPACITY 原數(shù)組長(zhǎng)度大于等于數(shù)組初始化長(zhǎng)度16
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//閾值擴(kuò)大一倍
newThr = oldThr << 1; // double threshold
}
//老閾值點(diǎn)大于0 直接賦值
else if (oldThr > 0) // 老閾值賦值給新的數(shù)組長(zhǎng)度
newCap = oldThr;
else {// 直接使用默認(rèn)值
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計(jì)算新的resize最大上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//新的閥值 默認(rèn)原來(lái)是12 乘以2之后變?yōu)?4
threshold = newThr;
//創(chuàng)建新的哈希表
@SuppressWarnings({"rawtypes","unchecked"})
//newCap是新的數(shù)組長(zhǎng)度--》32
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//判斷舊數(shù)組是否等于空
if (oldTab != null) {
// 把每個(gè)bucket都移動(dòng)到新的buckets中
//遍歷舊的哈希表的每個(gè)桶，重新計(jì)算桶里元素的新位置
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//原來(lái)的數(shù)據(jù)賦值為null 便于GC回收
oldTab[j] = null;
//判斷數(shù)組是否有下一個(gè)引用
if (e.next == null)
//沒(méi)有下一個(gè)引用，說(shuō)明不是鏈表，當(dāng)前桶上只有一個(gè)鍵值對(duì)，直接插入
newTab[e.hash & (newCap - 1)] = e;
//判斷是否是紅黑樹
else if (e instanceof TreeNode)
//說(shuō)明是紅黑樹來(lái)處理沖突的，則調(diào)用相關(guān)方法把樹分開(kāi)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 采用鏈表處理沖突
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//通過(guò)上述講解的原理來(lái)計(jì)算節(jié)點(diǎn)的新位置
do {
// 原索引
next = e.next;
//這里來(lái)判斷如果等于true e這個(gè)節(jié)點(diǎn)在resize之后不需要移動(dòng)位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} 流程圖：
⑦Remove方法
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// index 元素只有一個(gè)元素
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
// index處是一個(gè)紅黑樹
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// index處是一個(gè)鏈表，遍歷鏈表返回node
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 分不同情形刪除節(jié)點(diǎn)
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}五、擴(kuò)展
源碼符號(hào)（位運(yùn)算符）的解釋
>>> 和 >> 的區(qū)別
無(wú)符號(hào)右移運(yùn)算符。它將操作數(shù)的二進(jìn)制表示向右移動(dòng)指定的位數(shù)。
- >>>：它在右移時(shí)，無(wú)論正數(shù)還負(fù)數(shù)，高位都補(bǔ) 0。
- >>：它在右移時(shí)，正數(shù)高位補(bǔ) 0，負(fù)數(shù)高位都補(bǔ) 1。
例子如下：
n = n >>> 2; // 假設(shè)n等于-15 00000000 00000000 00000000 00001111 // 15 0000000000 00000000 00000000 00001111 //15的二進(jìn)制從高位右移2位 ------------------------------------------------- 00000000 00000000 00000000 00000011 //15右移之后3 n = n >> 2; // 假設(shè)n等于-15 00000000 00000000 00000000 00001111 // -15 11000000 00000000 00000000 0000001111 //-15的二進(jìn)制從高位右移2位 ------------------------------------------------- 11000000 00000000 00000000 00000011 //-15右移之后3
^ 和 & 的區(qū)別
- ^（按位與運(yùn)算）：運(yùn)算規(guī)則：相同的二進(jìn)制數(shù)位上，都是1的時(shí)候，結(jié)果為 1，否則為 0。
- &（按位異或運(yùn)算）：運(yùn)算規(guī)則：相同的二進(jìn)制數(shù)位上，數(shù)字相同，結(jié)果為 0，不同為 1。
例子如下：
n = i^j // 假設(shè)i等于10，j 等于15 00000000 00000000 00000000 00001000 // i=10 00000000 00000000 00000000 00001100 // j=15 ------------------------------------------------- 00000000 00000000 00000000 00001000 // n=10 n = i&j // 假設(shè)i等于10，j 等于15 00000000 00000000 00000000 00001000 // i=10 00000000 00000000 00000000 00001100 // j=15 ------------------------------------------------- 00000000 00000000 00000000 00000100 // n=5
總結(jié)
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
java使用MulticastSocket實(shí)現(xiàn)組播
這篇文章主要為大家詳細(xì)介紹了java使用MulticastSocket實(shí)現(xiàn)組播，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-01-01
下面小編就為大家?guī)?lái)一篇全面了解servlet中cookie的使用方法。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-06-06
Spring Boot 2.X整合Spring-cache(讓你的網(wǎng)站速度飛起來(lái))
這篇文章主要介紹了Spring Boot 2.X整合Spring-cache(讓你的網(wǎng)站速度飛起來(lái))，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
Java8中常見(jiàn)函數(shù)式接口的使用示例詳解
在 Java 8 中,函數(shù)式接口是一個(gè)關(guān)鍵的特性,它們?cè)试S將方法作為參數(shù)傳遞或返回類型,本文為大家整理了一些常見(jiàn)的函數(shù)式接口的使用,希望對(duì)大家有所幫助2023-12-12
這篇文章主要給大家介紹了關(guān)于java正則表達(dá)式精確查找和替換指定字符的相關(guān)資料,java正則表達(dá)式是一種用于匹配、查找和替換文本的強(qiáng)大工具,它可以用于驗(yàn)證輸入是否符合特定的格式、從文本中提取信息、以及將文本中的某些內(nèi)容替換成其他內(nèi)容,需要的朋友可以參考下2024-04-04
ObjectInputStream 和 ObjectOutputStream 介紹_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
ObjectInputStream 和 ObjectOutputStream 的作用是，對(duì)基本數(shù)據(jù)和對(duì)象進(jìn)行序列化操作支持。本文給大家詳細(xì)介紹了ObjectInputStream 和 ObjectOutputStream的相關(guān)知識(shí)，感興趣的朋友一起學(xué)習(xí)吧2017-05-05
Spring Boot實(shí)戰(zhàn)教程之自動(dòng)配置詳解
Spring Boot的自動(dòng)配置給開(kāi)發(fā)者帶來(lái)了很大的便利，當(dāng)開(kāi)發(fā)人員在pom文件中添加starter依賴后，maven或者gradle會(huì)自動(dòng)下載很多jar包到classpath中。下面這篇文章主要給大家介紹了關(guān)于Spring Boot自動(dòng)配置的相關(guān)資料，需要的朋友可以參考借鑒，下面來(lái)一起看看吧。2017-07-07
SpringBoot+Shiro+LayUI權(quán)限管理系統(tǒng)項(xiàng)目源碼
本項(xiàng)目旨在打造一個(gè)基于RBAC架構(gòu)模式的通用的、并不復(fù)雜但易用的權(quán)限管理系統(tǒng)，通過(guò)SpringBoot+Shiro+LayUI權(quán)限管理系統(tǒng)項(xiàng)目可以更好的幫助我們掌握springboot知識(shí)點(diǎn)，感興趣的朋友一起看看吧2021-04-04
本文主要帶我們了解Mapreduce序列化，序列化就是把內(nèi)存中的對(duì)象，轉(zhuǎn)換成字節(jié)序列（或其他數(shù)據(jù)傳輸協(xié)議）以便于存儲(chǔ)到磁盤（持久化）和網(wǎng)絡(luò)傳輸。想進(jìn)一步了解更多的小伙伴，可以參考閱讀本文2023-03-03
本篇文章給大家分享了關(guān)于Java中unsafe操作的相關(guān)知識(shí)點(diǎn)以及相關(guān)的實(shí)例代碼，有需要的朋友可以學(xué)習(xí)參考下。2018-03-03