最近看了遍HashMap的原始碼,打算寫一篇HashMap的原始碼決議,主要針對HashMap的增刪改查操作進行分析，接下來直接進入正題，
先看看hashMap在jdk1.8的結構，用的是陣列+鏈表+紅黑樹的結構，也叫哈希桶，在jdk1.8之前都是陣列+鏈表的結構，因為在鏈表的查詢操作是O(N)的時間復雜度，而且hashMap中查詢操作也是占了很大比例的，如果當節點數量多，轉換為紅黑樹結構，那么將會提高很大的效率，因為紅黑樹結構中，增刪改查都是O(log n)，
哈希桶就是陣列里面的一個位置中所占所有資料
HashMap的屬性
// 序列號，用于序列化時使用
private static final long serialVersionUID = 362498820763181265L;
// 默認初始化大小(1 << 4, 16) - 必須要為2的次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量(1 << 30, 1073741824)
static final int MAXIMUM_CAPACITY = 1 << 30;
// 負載因子，默認為0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 樹化閾值（與MIN_TREEIFY_CAPACITY同時作用,當HashMap大小超過64,且鏈表長度大于8時,將當前鏈表轉化成紅黑樹)
static final int TREEIFY_THRESHOLD = 8;
// 當紅黑樹內的結點數小于6時,紅黑樹將退化成為鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 樹化的最小容量，即當鏈表長度大于8，但HashMap大小小于64時，HashMap將進行擴容而不是鏈表轉化為紅黑樹
static final int MIN_TREEIFY_CAPACITY = 64;
/* ---------------- 欄位 -------------- */
// 存盤元素的Node陣列
transient Node<K,V>[] table;
// 將資料轉換成set的另一種存盤形式，這個變數主要用于迭代功能
transient Set<Map.Entry<K,V>> entrySet;
// 元素數量
transient int size;
// map被修改的次數
transient int modCount;
// 擴容閾值,當HashMap里的元素大于該數量時進行擴容
int threshold;
// 負載因子
final float loadFactor;
-
負載因子為什么要是0.75，為什么不選取其他值？
在HashMap的原始碼中有這么一段解釋:
Ideally, under random hashCodes, the frequency of * nodes in bins follows a Poisson distribution * (http://en.wikipedia.org/wiki/Poisson_distribution) with a * parameter of about 0.5 on average for the default resizing * threshold of 0.75, although with a large variance because of * resizing granularity. Ignoring variance, the expected * occurrences of list size k are (exp(-0.5) * pow(0.5, k) / * factorial(k)). The first values are: * * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * more: less than 1 in ten million *在理想情況下，使用隨機哈希嗎，節點出現的頻率在hash桶中遵循泊松分布，同時給出了桶中元素的個數和概率的對照表，從上表可以看出當桶中元素到達8個的時候，概率已經變得非常小，也就是說用0.75作為負載因子，每個碰撞位置的鏈表長度超過8個是幾乎不可能的，
- 當負載因子過小，設負載因子為0.5
負載因子是0.5的時候，這也就意味著，當陣列中的元素達到了一半就開始擴容，既然填充的元素少了，Hash沖突也會減少，那么底層的鏈表長度或者是紅黑樹的高度就會降低，查詢效率就會增加，但是與此同時的空間利用率會大幅的降低，原來存盤空間占用1M的資料，現在就意味著需要2M的空間，
- 當負載因子過大，設負載因子為1
當負載因子是1.0的時候，也就意味著，只有當陣列的8個值全部填充了，才會發生擴容，這就帶來了很大的問題，因為Hash沖突是避免不了的，當負載因子是1.0的時候，意味著會出現大量的Hash的沖突，底層的紅黑樹變得例外復雜，對于查詢效率極其不利，這種情況就是犧牲了時間來保證空間的利用率，
HashMap負載因子為0.75是空間和時間成本的一種折中，
-
**易混點：**大家都知道HashMap底層是陣列+鏈表/紅黑樹，并且當鏈表長度大于默認值為8時會將鏈表轉化成紅黑樹，但是實際上還有另外一個引數MIN_TREEIFY_CAPACITY,只有當HashMap里的元素數量大于MIN_TREEIFY_CAPACITY(默認為64)時才會將鏈表轉化成紅黑樹，這是為了避免在哈希表建立初期，多個鍵值對恰好被放入了同一個鏈表中而導致不必要的轉化，
HashMap的建構式
看完了HashMap的屬性,接下來我們來看看HashMap的建構式，HashMap共有4個建構式，首先是無參構造
/**
* 無參構造
* 將loadFactor賦值為默認的負載因子0.75, 其他的引數為默認值
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
第二個建構式，設定HashMap的初始大小和負載因子，并對默認大小和負載因子進行檢測
public HashMap(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);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
第三個，僅設定初始大小，負載因子使用默認值0.75并呼叫第二個建構式進行初始化
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
最后一個構造方法看起來有點復雜，其實并不然，就是將一個Map轉換成為HashMap，
- 首先判斷一下傳進來的Map的大小是不是大于0（等于0就沒必要初始化了），由于上圖是通過構造器新建一個HashMap，所以table是null（table是HashMap的Node陣列），然后計算閥值ft，判斷一下閥值是否超過了設定的最大容量（1<<30），如果沒超過則還是原閥值ft，這里將ft賦給t，再判斷閥值t是否大于原閥值
- 我們假設它超過閥值了，這里用到tableSizeFor()方法進行擴容，我們后面會講，引數evict可以忽略，這個引數傳遞到afterNodeInsertion(evict)，這個方法是空的，
- 最后使用了forEach回圈遍歷，將傳入HashMap構造器的形參m中的所有key-value全部放到當前HashMap物件中(this)，
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 獲取map的大小
int s = m.size();
if (s > 0) {
// 判斷當前HashMap的table是否被初始化
if (table == null) { // pre-size
/* 計算需要的容量 實際使用的長度=容量*0.75得來的，+1是因為小數相除，基本都不會是整數，容量大小不能為小數的，后面轉換為int，多余的小數就要被丟掉，所以+1，例如，map實際長度22，22/0.75=29.3,所需要的容量肯定為30*/
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
// 對HashMap進行容量設定
threshold = tableSizeFor(t);
}
// 如果table已經初始化，則進行擴容操作
else if (s > threshold)
resize();
// 遍歷Map,將值復制進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);
}
}
}
HashMap常用函式
1.put()/putVal()添加元素
HashMap的建構式我們學習完了,接下來必不可少的就是HashMap的增刪改查操作和一些重要的方法了，
首先我們來看添加元素：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 計算hash值，與自己右移16位進行異或運算（高低位異或）
* 高16bit不變，低16bit和高16bit做了一個異或，目的是減少碰撞，
* 相比在1.7中的4次位運算，5次異或運算（9次擾動），在1.8中，只進行了1次位運算和1次異或運算（2次擾動）；
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判斷HashMap中的table是否被初始化或者是否為空
if ((tab = table) == null || (n = tab.length) == 0)
// 初次擴容
n = (tab = resize()).length;
// 計算index, 并對null進行處理
// (n - 1) & hash 確定元素存放在哪個桶中，桶為空，新生成結點放入桶中(此時，這個結點是放在陣列中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 結點中的key存在，直接覆寫value
Node<K,V> e; K k;
// 判斷陣列中的結點hash相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果相等，用e來記錄當前結點
e = p;
// 判斷該鏈是否為紅黑樹
else if (p instanceof TreeNode)
// 放入樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 當前鏈為鏈表
else {
// 遍歷鏈表，同時尋找key相同的結點，若找到跳出回圈
for (int binCount = 0; ; ++binCount) {
// 到達鏈表末尾，將元素插入鏈表末尾
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 判斷當前鏈表結點數是否達到轉化成紅黑樹的臨界值
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 鏈表樹化
treeifyBin(tab, hash);
break;
}
// 判斷鏈表中結點的key值與插入的元素的key值是否相等, 相同則跳出回圈
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 遍歷下一個結點
p = e;
}
}
// 如果e不為空，即HashMap中存在相同的key
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent為false或者舊值為null
if (!onlyIfAbsent || oldValue == null)
//用新值替換舊值
e.value = value;
// 訪問后回呼
afterNodeAccess(e);
// 回傳舊值
return oldValue;
}
}
// 修改次數加一
++modCount;
// 如果添加元素后元素數量大于最大容量,則擴容
if (++size > threshold)
resize();
// 插入后回呼
afterNodeInsertion(evict);
return null;
}
上面就是HashMap的一個添加元素的程序，其中涉及到了多次的resize()擴容方法，這是HashMap中的一個重難點，
接下來用文字和流程圖來總結一下HashMap的添加元素程序
-
判斷鍵值對陣列table是否為null或者元素為空，是則將使用resize()方法對table進行初次初始化擴容
-
使用(n-1)&hash計算索引i來記錄元素應該存放在陣列的位置，判斷是否table[i]==null來判斷是否存在hash沖突，不存在則直接將元素存入陣列，轉向8
-
判斷table[i]是否與需要插入的元素hash值相等，元素相同，如果相同直接覆寫value，后者轉向4
-
判斷table[i]是否為TreeNode,即判斷table[i]是否為紅黑樹，是則使用putTreeVal()方法直接放入樹中，轉向；否則轉向5
-
如果當前table[i]不為紅黑樹,則當前結點為鏈表，遍歷當前鏈表，判斷是否有存在相同元素，如存在則記錄當前結點，并跳出回圈轉向7，否則在鏈表末端插入元素
-
判斷插入后的鏈表長度是否大于樹化閾值（默認為8），大于的話則使用treeifyBin()樹化鏈表，轉向8
-
將記錄下來的結點的值進行覆寫
-
插入成功后，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容
2.resize()擴容函式
在添加元素的程序中多次涉及到了resize()函式對HashMap的容量進行動態擴容,接下來我們就接著看原始碼來分析一下resize()函式
final Node<K,V>[] resize() {
// oldTab指向hash桶陣列
Node<K,V>[] oldTab = table;
// 判斷當前HashMap是否為空
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 原擴容閾值(即容量*負載因子)
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果原陣列空間已經大于最大容量空間無法擴容時，直接回傳原陣列
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果當前hash桶陣列的長度在擴容后仍然小于最大容量 并且oldCap大于默認值16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 兩倍化擴容閾值
}
// 舊的容量為0，但threshold大于零，代表有參構造有cap傳入，threshold已經被初始化成最小2的n次冪
// 直接將該值賦給新的容量
else if (oldThr > 0)
newCap = oldThr;
// 無參構造,將容量和擴容閾值設定成默認值
else {
newCap = DEFAULT_INITIAL_CAPACITY;
// 默認負載因子*默認初始化容量
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 計算出新的陣列長度后賦給當前成員變數table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果原陣列不為空,則需要重排邏輯
if (oldTab != null) {
// 遍歷元陣列的所有桶下標
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//當前哈希桶的位置值不為null，也就是陣列下標處有值，因為有值表示可能會發生沖突
if ((e = oldTab[j]) != null) {
// 舊陣列的桶下標賦給臨時變數e，并且解除舊陣列中的參考，否則就陣列無法被GC回收
oldTab[j] = null;
// 當前桶只有一個元素
if (e.next == null)
// 用hash演算法重排元素位置
newTab[e.hash & (newCap - 1)] = e;
// 如果當前桶不為空，且存在紅黑樹
else if (e instanceof TreeNode)
// 將當前紅黑樹中的元素分隔重排
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍歷鏈表
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
// 初始化head指向鏈表當前元素e，e不一定是鏈表的第一個元素，初始化后loHead
// 代表下標保持不變的鏈表的頭元素
loHead = e;
else
// loTail.next指向當前e
loTail.next = e;
// loTail指向當前的元素e
// 初始化后，loTail和loHead指向相同的記憶體，所以當loTail.next指向下一個元素時，
// 底層陣列中的元素的next參考也相應發生變化，造成lowHead.next.next.....
// 跟隨loTail同步，使得lowHead可以鏈接到所有屬于該鏈表的元素，
loTail = e;
}
else {
if (hiTail == null)
// 初始化head指向鏈表當前元素e, 初始化后hiHead代表下標更改的鏈表頭元素
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 遍歷結束, 將tail指向null，并把鏈表頭放入新陣列的相應下標，形成新的映射，
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
3.remove()洗掉函式
講完了增刪改查中的增，接下來我們接著看刪這個步驟，同樣的在刪的這個步驟中也沒有直接在remove函式中完成詳細的洗掉細節，而是在removeNode中具體實作
public V remove(Object key) {
Node<K,V> e;
// 判斷key是否存在，存在的話回傳value否則回傳null
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
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;
// 判斷table不為空，table的長度大于0，然后獲取洗掉key的結點所在陣列的下標的值
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))))
node = p;
else if ((e = p.next) != null) {
// 判斷當前桶是否為紅黑樹結構
if (p instanceof TreeNode)
// 獲取樹中結點
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 遍歷鏈表, 獲取結點
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//找到要洗掉的節點后，判斷!matchValue，我們正常的remove洗掉，!matchValue都為true
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 如果是紅黑樹結點,呼叫removeTreeNode洗掉樹中結點
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 如果是桶的第一個結點,直接洗掉頭結點
else if (node == p)
tab[index] = node.next;
// 不為頭結點,將next指標指向下一個元素
else
p.next = node.next;
// 修改次數加一
++modCount;
// HashMap中元素數量減一
--size;
// 回呼函式
afterNodeRemoval(node);
// 回傳結點
return node;
}
}
// 如果沒有查找到結點,回傳null
return null;
}
洗掉還有clear方法，把所有的陣列下標元素都置位null，
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
4.get()獲取元素函式
相比于增加元素和洗掉元素來講，查找元素的程序就很簡單了，通過比對hash值先判斷元素是否存在，在根據桶型別來獲取元素，
public V get(Object key) {
Node<K,V> e;
//也是呼叫getNode方法來完成的
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
//first 頭結點，e 臨時變數，n 長度,k key
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//頭結點也就是陣列下標的節點
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果是頭結點，則直接回傳頭結點
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//不是頭結點
if ((e = first.next) != null) {
//判斷是否是紅黑樹結構
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);
}
}
//找不到，表示不存在該節點
return null;
}
5.replace()/replaceAll()修改元素函式
為什么先說獲取元素而不是修改元素呢，其實通過我們分析增加元素的原始碼時我們就已經發現使用put()可以添加相同的元素，存在相同的元素就會直接覆寫value，這其實就達到了覆寫的目的，我在這稍微提一嘴，雖然可以通過put來覆寫資料，但其實HashMap的原始碼中其實是有replace()和replaceAll()替換函式的，這里給大家簡單分析一下，
/**
* 使用newValue來替換key中的oldValue
* @return 是否替換成功
*/
@Override
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
// 判斷key是否存在, 用e獲取到key所在的結點，直接替換結點
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
/**
* 使用value來替換key中的value
* @return key中原來的值
*/
@Override
public V replace(K key, V value) {
Node<K,V> e;
// 判斷key是否存在, 用e獲取到key所在的結點
if ((e = getNode(hash(key), key)) != null) {
// 保存原值
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
// 回傳原值
return oldValue;
}
return null;
}
@Override
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Node<K,V>[] tab;
if (function == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
e.value = function.apply(e.key, e.value);
}
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
HashMap的原始碼分析暫時到這里，主要的增刪改查操作都已經分析完了，因個人能力有限，如果里面內容存在錯誤，歡迎批評指正，后續會添加一些關于HashMap的面試題，歡迎大家關注，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/259772.html
標籤：其他
下一篇：Codeforces Round #701 (Div. 2) A ~ F ，6題全，超高質量良心題解【每日億題】2021/2/13