hashmap是我們經常使用的一個工具類，那么知道它的一些原理和特性嗎？
特性
- HashMap是一種基于散列演算法實作的快速查找的鍵值對結構，底層實作是鏈表陣列，
- 允許空鍵和空值（但空鍵只有一個，且放在第一位）
- 元素是無序的(這里的無序是指的插入和讀取的順序不一致)
- JDK 8 后又加了底層加上了紅黑樹優化過長的鏈表以及并行遍歷，
概述
HashMap可以分析的地方很多，網上也有許多文章，本文僅從以下幾個方面進行分析：
- 基礎變數
- 插入(動態擴容，延遲插入，紅黑樹轉換，可以說的地方很多)
- 并行遍歷(jdk8的新特性，快速失敗，柵欄機制)
需要了解的基礎成員變數
| 變數名 | 中文注釋 |
|---|---|
| size | 此映射中包含的鍵-值映射的數目， |
| DEFAULT_INITIAL_CAPACITY | 默認容量 16 |
| MAXIMUM_CAPACITY | 允許的最大容量 |
| loadFactor | 負載因子 |
| threshold | 當前 HashMap 所能容納鍵值對數量的最大值，超過這個值，則需擴容 |
這些變數有什么用？ 答案是擴容
上面有提到HashMap中兩個非常關鍵的變數，容量和加載因子
如果一個map的size大于臨界值時，HashMap會自動擴容，將當前容量擴一倍出來，并重新計算每個物件的位置并存放，
加載因子，是hashmap在擴容時需要的，表示Hsah表中元素的填滿的程度，待++hashmap中存放的物件數量大于等于map容量*加載因子時++，hashmap會自動擴容，將map的容量 ++擴大一倍++ ，并將之前的物件重新進行hash尋址，并存放到新的地址中，
其中threshold就是臨界值，當實際K-V個數超過threshold時，HashMap會將容量擴容，threshold＝容量*加載因子，
這些變數如何傳入:
HashMap有四個構造方法
- public HashMap() 默認構造方法，默認初始容量為16，加載因子為0.75f
- public HashMap(int initialCapacity) 指定初始容量的構造方法，加載因子為默認的0.75f
- public HashMap(int initialCapacity, float loadFactor) 指定初始容量和默認加載因子的初始方法
- public HashMap(Map<? extends K, ? extends V> m) 以子map為入參，構造新的hashmap
擴容：threshold＝容量*加載因子，
插入
網上的講解也有許多，就簡單說一下
hashMap有兩個概念對于插入很重要，一個叫做bucket（桶），一個叫做node/entry（元素）
桶與元素他們的關系是怎樣的:
對于 HashMap 及其子類而言，它們采用 Hash 演算法來決定集合中元素的存盤位置，當系統開始初始化 HashMap 時，系統會創建一個長度為 capacity 的 Entry 陣列，這個陣列里可以存盤元素的位置被稱為“桶（bucket）”，每個 bucket 都有其指定索引，系統可以根據其索引快速訪問該 bucket 里存盤的元素，一旦插入時key的hahs相同(也叫做hash尋找沖突,或者哈希碰撞)，就會把兩個hash值相同的元素存盤在一個桶里面，
總而言之，就是一個hashMap包含許多桶，一個桶里面包含了許多元素
接下來看一下插入的api:
hashmap的插入api非常簡單，就是一個put
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}.
* (A {@code null} return can also indicate that the map
* previously associated {@code null} with {@code key}.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
從這里可以看到他是呼叫的putVal方法，在通過斷點進入
/**
* Implements Map.put and related methods.
*
* @param hash hash for key hash值
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value 如果為真，不要改變現有的值
* @param evict if false, the table is in creation mode. 如果為false，表示表處于創建模式，
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
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;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
原始碼過長，我將結合網上的博客以及自己的理解將原始碼抽取并且翻譯了成容易理解的偽代碼 https://blog.csdn.net/hsee2006/article/details/104784557/
putVal:總流程
{
//宣告了一個區域變數 tab,區域變數 Node 型別的資料 p,int 型別 n,i
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 初始化桶陣列 table，也就是說table是在有資料加載時延遲初始化的
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 找當前要插入的資料應該在哈希表中的位置,如果沒找到,代表哈希表中當前的位置是空的,否則就代表找到資料了
// 如果找到資料就賦值，就說明hash沖突了，將舊的值給臨時變數p
{
if ((p = tab[i = (n - 1) & hash]) == null)
// 說明沒有沖突,直接賦值
tab[i] = newNode(hash, key, value, null);
else {
// 處理hash尋址沖突的代碼，解決的同一個位置的新資料和舊資料的共存問題
代碼片段1(后面)
}
}
++modCount;// 增加當前的操作長度，可以用于執行緒不安全時的快速失敗機制
if (++size > threshold)// 觸發擴容
resize();
afterNodeInsertion(evict);
return null;
}
注:這里的 (n-1)&hash 是一種高效的除模取余運算
- 傳統的方式進行求余運算，需要先將10進制轉成2進制到記憶體中進行計算，然后再把結果轉換成10進制
- 而位運算是直接在記憶體中進行，不需要經過這些轉換
- 但是位運算只能用于除數是2的n次方的數的求余
代碼片段1:
{
/*
這里會經過三個判斷:
1，如果一來是key沖突，就直接替換值
2, key不一樣，且為是紅黑樹，則呼叫紅黑樹的插入方法
3, 直接對鏈表進行寫入，如果鏈表過長會轉換結構為紅黑樹,或者key沖突就直接替換
*/
// 這個e是一會將會被寫入的資料的臨時變數
Node<K,V> e; K k;
// 如果鍵的值以及節點 hash 等于鏈表中的第一個鍵值對節點時，說明key沖突，則將 e 指向該鍵值對
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)// 面對樹直接插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 對鏈表進行遍歷，并統計鏈表長度
for (int binCount = 0; ; ++binCount) {
// 鏈表中不包含要插入的鍵值對節點時，則將該節點接在鏈表的最后
if ((e = p.next) == null) {//如果當前節點的下一個是空的,就代表沒有后面的資料了,直接給賦值，這里是真正的賦值操作
p.next = newNode(hash, key, value, null);
// 如果鏈表長度大于或等于樹化閾值(8)，則進行將鏈表優化為紅黑樹或者進行擴容操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果當前遍歷到的資料和要插入的資料的 key 是一樣,和上面之前的一樣,賦值給變數 e,下面替換內容
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 開始下一次遍歷
p = e;
}
}
// 判斷要插入的鍵值對是否存在 HashMap 中
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 鉤子函式:一般不會使用
afterNodeAccess(e);
return oldValue;
}
}
代碼片段2:
并行遍歷
并行遍歷是java8給jdk多加的一個介面,用來做并行遍歷的,它的使用方式如下:
public static void main(String[] args) {
// 構造一個map
HashMap map=new HashMap(1,4);
// 插入值
for (int i = 0; i < 6; i++) {
map.put(i,"值_"+i);
}
// 得到并行遍歷器
Spliterator spliterator = map.entrySet().spliterator();
System.out.println("開始分塊元素的遍歷");
// 開始分割遍歷器
Spliterator s1 = spliterator.trySplit();
// 執行原先的遍歷器
System.out.println("執行第一塊區域的元素遍歷:");
spliterator.forEachRemaining(item-> System.out.println(item));
// 執行被分出去的遍歷器
System.out.println("執行第二塊區域的元素遍歷:");
s1.forEachRemaining(item-> System.out.println(item));
System.out.println("執行完畢");
}
結果如下:
開始分塊元素的遍歷
執行第一塊區域的元素遍歷:1=值_1
3=值_3
5=值_5
執行第二塊區域的元素遍歷:0=值_0
2=值_2
4=值_4
執行完畢
由這段代碼我們可以看出jdk8新加的這個特性的好處,相比傳統的Iterator方法，該方法可以更加高效的處理并行讀取map資料,可以將資料分割為多個迭代器，然后傳入不同的執行緒，利用多核更好的處理好海量資料，
那么map是怎么做到這一點的？原始碼如下:
hashMap的內部類:EntrySet
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
...
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
...
}
由此我們發現實質是利用了里面的一個內部類EntrySpliterator
static final class EntrySpliterator<K,V>
extends HashMapSpliterator<K,V>
implements Spliterator<Map.Entry<K,V>> {
EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
}
其中的繼承的這個Spliterator介面非常有意思，
我查了下資料,發現它是jdk官方提供的一個并行遍歷介面:
Spliterator介面是Java為了并行遍歷資料源中的元素而設計的迭代器，這個可以類比最早Java提供的順序遍歷迭代器Iterator，但一個是順序遍歷，一個是并行遍歷，
為什么有了Iterator還需要spliterator呢?
從最早Java提供順序遍歷迭代器Iterator時，那個時候還是單核時代，但現在多核時代下，順序遍歷已經不能滿足需求了，如何把多個任務分配到不同核上并行執行，才是能最大發揮多核的能力，所以Spliterator應運而生!
如果感興趣的可以讀一下這篇博客
了解Java Spliterator 這篇文章就夠了
為什么有了hahsMap還會重寫spliterator呢?
如果深入原始碼會發現，spliterator類有自己實作的默認分割遍歷，但是hashMap卻重寫了一套分割演算法，
原來Spliterator的一個特點是每次將元素拆分出去一半，對于HashMap，由于hashMap底層是鏈表，如果要完全精確到元素，勢必會造成演算法的復雜和性能的低下，
因此，Spliterator在HashMap的實作程序中，直接是按bucket進行處理，這樣會導致每次拆分的資料并不均勻，HashMap中實際上是按照bucket的數量平均拆分，只是可能每個bucket上面Node的數量可能不一致，另外有的bucket可能為空，
我們來看一下spliterator的重寫中幾個比較重要的概念以及重寫
HashMapSpliterator對于spliterator的部分實作
static class HashMapSpliterator<K,V> {
// 需要遍歷的 Map 物件
final MyHashMap<K,V> map;
// 當前正在遍歷的節點
Node<K,V> current; // current node
// 當前迭代器開始遍歷的桶索引
int index; // current index, modified on advance/split
// 當前迭代器遍歷上限的桶索引
// fence的英語代表柵欄（zha lan）的意思，這里代表邊界
int fence; // one past last index
// 需要遍歷的元素個數
int est; // size estimate
// 期望運算元，用于多執行緒情況下，如果多個執行緒同時對 HashMap 進行讀寫，
// 那么這個期望運算元 expectedModCount 和 HashMap 的 modCount 就會不一致，這時候拋個例外出來，稱為“快速失敗”
int expectedModCount; // for comodification check
MapSpliterator(MyHashMap<K,V> m, int origin,
int fence, int est,
int expectedModCount) {
this.map = m;
this.index = origin;
this.fence = fence;
this.est = est;
this.expectedModCount = expectedModCount;
}
// 獲取柵欄
final int getFence() { // initialize fence and size on first use
int hi;
// 第一個分割迭代器會執行下面 if 內的代碼,因為構造傳入的fence值為-1
if ((hi = fence) < 0) {
MyHashMap<K,V> m = map;
est = m.size;// 獲取需要遍歷的元素個數
expectedModCount = m.modCount;//獲取當前修改的數量
Node<K,V>[] tab = m.table;//得到資料
hi = fence = (tab == null) ? 0 : tab.length;// 如果為null就是0
}
return hi;
}
// 獲取當前迭代器需要遍歷的元素個數
public final long estimateSize() {
getFence(); // force init
return (long) est;
}
}
這段代碼體現了兩個概念
柵欄機制以及快速失敗(后面會講解,先把概念放在這里放在這里)
然后再看EntrySpliterator的實作
static final class EntrySpliterator<K,V>
extends HashMapSpliterator<K,V>
implements Spliterator<Map.Entry<K,V>> {
EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
// 分割遍歷器
public EntrySpliterator<K,V> trySplit() {
// hi代表上邊界
// mid代表限制值+當前索引號對折一半
// >>>用來代表一半對折(如果是奇數的話，會先減一再次對折)
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
// 構建出一個新的分割器的同時,將自己的上下邊界也進行修改
return (lo >= mid || current != null) ? null :
new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
// 遍歷剩下的元素
public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
Node<K,V>[] tab = m.table;
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = (tab == null) ? 0 : tab.length;
}
else
mc = expectedModCount;
if (tab != null && tab.length >= hi &&
(i = index) >= 0 && (i < (index = hi) || current != null)) {
// 這段代碼沒有什么好說的，就是遍歷桶，然后把桶里面的元素給讀取出來進行函式式處理
Node<K,V> p = current;
current = null;
do {
//如果p為空則移動到下一個bucket
if (p == null)
p = tab[i++];
else {
//遍歷鏈表 呼叫外部函式處理
action.accept(p);
p = p.next;
}
// 進行讀取邊界控制判斷,不會讀取到另外的分割器的邊界資料
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
}
// 對單個元素進行遍歷，前進一次，這里就不分析了
public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
...
}
public int characteristics() {
...
}
}
快速失敗
總所周知，hahsMap是執行緒不安全的，為了避免在在執行緒不安全時使用了hahsMap，java官方提供了一種檢測機制，
fail-fast 機制，即快速失敗機制，是java集合(Collection)中的一種錯誤檢測機制，當在迭代集合的程序中該集合在結構上發生改變的時候，就有可能會發生fail-fast，即拋出 ConcurrentModificationException例外，
其中，并行遍歷就利用了這個機制
在EntrySpliterator類的forEachRemaining方法的該段代碼就體現了快速失敗機制的原理:
public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
...
// 獲取預期資料量
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = (tab == null) ? 0 : tab.length;
}
else
mc = expectedModCount;
if (tab != null && tab.length >= hi &&
...
// 比較預期資料量以及實時資料量
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
}
也就是在遍歷時將期望資料量(expectedModCount)和當前實際資料量進行比較(modCount)
如果不相等，就說明在遍歷程序中，有其他執行緒在對資料進行修改，就會報錯
注意:fail-fast機制并不保證在不同步的修改下一定會拋出例外，它只是盡最大努力去拋出，所以這種機制一般僅用于檢測bug，(比如資料的卻發生了變化，但是資料量卻是相等的情況下)
以上，就是hahsMap的底層原始碼淺析，實際上hashMap所運用到的技巧遠不止如此，如果想要提升，推薦直接看jdk原始碼以及其他人的相應決議博客，
最后，希望大家一鍵三連，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/240961.html
標籤：其他