當前位置:首頁 » 操作系統 » hashmap源碼分析

hashmap源碼分析

發布時間: 2022-11-30 06:37:48

⑴ HashMap是什麼東西

HashMap,中文名哈希映射,HashMap是一個用於存儲Key-Value鍵值對的集合,每一個鍵值對也叫做Entry。這些個鍵值對(Entry)分散存儲在一個數組當中,這個數組就是HashMap的主幹。HashMap數組每一個元素的初始值都是Null。

HashMap是基於哈希表的 Map 介面的實現。此實現提供所有可選的映射操作,並允許使用 null 值和 null 鍵。(除了非同步和允許使用 null 之外,HashMap 類與 Hashtable 大致相同。)此類不保證映射的順序,特別是它不保證該順序恆久不變。

(1)hashmap源碼分析擴展閱讀:

因為HashMap的長度是有限的,當插入的Entry越來越多時,再完美的Hash函數也難免會出現index沖突的情況。

HashMap數組的每一個元素不止是一個Entry對象,也是一個鏈表的頭節點。每一個Entry對象通過Next指針指向它的下一個Entry節點。當新來的Entry映射到沖突的數組位置時,只需要插入到對應的鏈表即可。

⑵ HashMap實現原理

HashMap在實際開發中用到的頻率非常高,面試中也是熱點。所以決定寫一篇文章進行分析,希望對想看源碼的人起到一些幫助,看之前需要對鏈表比較熟悉。
以下都是我自己的理解,歡迎討論,寫的不好輕噴。

HashMap中的數據結構為散列表,又名哈希表。在這里我會對散列表進行一個簡單的介紹,在此之前我們需要先回顧一下 數組 鏈表 的優缺點。

數組和鏈表的優缺點取決於他們各自在內存中存儲的模式,也就是直接使用 順序存儲 鏈式存儲 導致的。無論是數組還是鏈表,都有明顯的缺點。而在實際業務中,我們想要的往往是定址、刪除、插入性能都很好的數據結構,散列表就是這樣一種結構,它巧妙的結合了數組與鏈表的優點,並將其缺點弱化(並不是完全消除)

散列表的做法是將key映射到數組的某個下標,存取的時候通過key獲取到下標(index)然後通過下標直接存取。速度極快,而將key映射到下標需要使用 散列函數 ,又名 哈希函數 。說到哈希函數可能有人已經想到了,如何將key映射到數組的下標。

圖中計算下標使用到了以下兩個函數:

值得注意的是,下標並不是通過hash函數直接得到的,計算下標還要對hash值做index()處理。
Ps:在散列表中,數組的格子叫做 ,下標叫做 桶號 ,桶可以包含一個key-value對,為了方便理解,後文不會使用這兩個名詞。

以下是哈希碰撞相關的說明:

以下是下標沖突相關的說明:

很多人認為哈希值的碰撞和下標沖突是同一個東西,其實不是的,它們的正確關系是這樣的, hashCode發生碰撞,則下標一定沖突;而下標沖突,hashCode並不一定碰撞

上文提到,在jdk1.8以前HashMap的實現是 散列表 = 數組 + 鏈表 ,但是到目前為止我們還沒有看到鏈表起到的作用。事實上,HashMap引入鏈表的用意就是解決下標沖突。

下圖是引入鏈表後的散列表:

如上圖所示,左邊的豎條,是一個大小為16的數組,其中存儲的是鏈表的頭結點,我們知道,擁有鏈表的頭結點即可訪問整個鏈表,所以認為這個數組中的每個下標都存儲著一個鏈表。其具體做法是,如果發現下標沖突,則 後插入的節點以鏈表的形式追加到前一個節點的後面

這種使用鏈表解決沖突的方法叫做: 拉鏈法 (又叫鏈地址法)。HashMap使用的就是拉鏈法,拉鏈法是沖突發生以後的解決方案。

Q:有了拉鏈法,就不用擔心發生沖突嗎?
A:並不是!由於沖突的節點會不停的在鏈表上追加,大量的沖突會導致單個鏈表過長,使查詢性能降低。所以一個好的散列表的實現應該從源頭上減少沖突發生的可能性,沖突發生的概率和哈希函數返回值的均勻程度有直接關系,得到的哈希值越均勻,沖突發生的可能性越小。為了使哈希值更均勻,HashMap內部單獨實現了hash()方法。

以上是散列表的存儲結構,但是在被運用到HashMap中時還有其他需要注意的地方,這里會詳細說明。

現在我們清楚了散列表的存儲結構,細心的人應該已經發現了一個問題:java中數組的長度是固定的, 無論哈希函數是否均勻,隨著插入到散列表中數據的增多,在數組長度不變的情況下,鏈表的長度會不斷增加 。這會導致鏈表查詢性能不佳的缺點出現在散列表上,從而使散列表失去原本的意義。為了解決這個問題,HashMap引入了擴容與負載因子。

以下是和擴容相關的一些概念和解釋:

Ps: 擴容要重新計算下標 擴容要重新計算下標 擴容要重新計算下標 ,因為下標的計算和數組長度有關,長度改變,下標也應當重新計算。

在1.8及其以上的jdk版本中,HashMap又引入了紅黑樹。

紅黑樹的引入被用於替換鏈表,上文說到,如果沖突過多,會導致鏈表過長,降低查詢性能,均勻的hash函數能有效的緩解沖突過多,但是並不能完全避免。所以HashMap加入了另一種解決方案,在往鏈表後追加節點時,如果發現鏈表長度達到8,就會將鏈表轉為紅黑樹,以此提升查詢的性能。

⑶ HashMap擴容機制

之前寫過一篇專門介紹HashMap的文章,反響很不錯,不過在留言區問得最多的問題就是HashMap的負載因子初始值為什麼是0.75,私下又好好地研究了一番,總結了這篇文章。

本篇文章基於JDK1.8,特在此說明。

OK。下面我們就開始進行分析。

HashMap源碼分析(jdk1.8,保你能看懂)

一、負載因子的作用

對於HashMap的研究,我之前一直停留在考慮源碼是如何實現的,現在當我重新再來看的時候,才發現,系統默認的各種參數值,才是HashMap的精華所在。

負載因子是和擴容機制有關的,意思是如果當前容器的容量,達到了我們設定的最大值,就要開始執行擴容操作。舉個例子來解釋,避免小白聽不懂:

比如說當前的容器容量是16,負載因子是0.75,16*0.75=12,也就是說,當容量達到了12的時候就會進行擴容操作。

他的作用很簡單,相當於是一個擴容機制的閾值。當超過了這個閾值,就會觸發擴容機制。HashMap源碼已經為我們默認指定了負載因子是0.75。

我截取了部分源碼,從這里可以看出,系統默認的負載因子值就是0.75,而且我們還可以在構造方法中去指定。下面我們就正式來分析一下為什麼是默認的0.75。

二、原因解釋(重點)

我們在考慮HashMap的時候,首先要想到的是HashMap只是一個數據結構,既然是數據結構最主要的就是節省時間和空間。負載因子的作用肯定也是節省時間和空間。為什麼節省呢?我們考慮兩種極端情況。

1、負載因子是1.0

我們先看HashMap的底層數據結構

我們的數據一開始是保存在數組裡面的,當發生了Hash碰撞的時候,就是在這個數據節點上,生出一個鏈表,當鏈表長度達到一定長度的時候,就會把鏈表轉化為紅黑樹。

當負載因子是1.0的時候,也就意味著,只有當數組的8個值(這個圖表示了8個)全部填充了,才會發生擴容。這就帶來了很大的問題,因為Hash沖突時避免不了的。當負載因子是1.0的時候,意味著會出現大量的Hash的沖突,底層的紅黑樹變得異常復雜。對於查詢效率極其不利。這種情況就是犧牲了時間來保證空間的利用率。

因此一句話總結就是負載因子過大,雖然空間利用率上去了,但是時間效率降低了。

2、負載因子是0.5

負載因子是0.5的時候,這也就意味著,當數組中的元素達到了一半就開始擴容,既然填充的元素少了,Hash沖突也會減少,那麼底層的鏈表長度或者是紅黑樹的高度就會降低。查詢效率就會增加。

但是,兄弟們,這時候空間利用率就會大大的降低,原本存儲1M的數據,現在就意味著需要2M的空間。

一句話總結就是負載因子太小,雖然時間效率提升了,但是空間利用率降低了。

3、負載因子0.75

經過前面的分析,基本上為什麼是0.75的答案也就出來了,這是時間和空間的權衡。當然這個答案不是我自己想出來的。答案就在源碼上,我們可以看看:

大致意思就是說負載因子是0.75的時候,空間利用率比較高,而且避免了相當多的Hash沖突,使得底層的鏈表或者是紅黑樹的高度比較低,提升了空間效率。

OK,寫到這答案基本上就出來了,一句話能總結的寫成了一篇文章。如有問題,還請批評指正。

⑷ golang map源碼淺析

golang 中 map的實現結構為: 哈希表 + 鏈表。 其中鏈表,作用是當發生hash沖突時,拉鏈法生成的結點。

可以看到, []bmap 是一個hash table, 每一個 bmap是我們常說的「桶」。 經過hash 函數計算出來相同的hash值, 放到相同的桶中。 一個 bmap中可以存放 8個 元素, 如果多出8個,則生成新的結點,尾接到隊尾。

以上是只是靜態文件 src/runtime/map.go 中的定義。 實際上編譯期間會給它加料 ,動態地創建一個新的結構:

上圖就是 bmap的內存模型, HOB Hash 指的就是 top hash。 注意到 key 和 value 是各自放在一起的,並不是 key/value/key/value/... 這樣的形式。源碼里說明這樣的好處是在某些情況下可以省略掉 padding 欄位,節省內存空間。

每個 bmap設計成 最多隻能放 8 個 key-value 對 ,如果有第 9 個 key-value 落入當前的 bmap,那就需要再構建一個 bmap,通過 overflow 指針連接起來。

map創建方法:

我們實際上是通過調用的 makemap ,來創建map的。實際工作只是初始化了hmap中的各種欄位,如:設置B的大小, 設置hash 種子 hash 0.

注意 :

makemap 返回是*hmap 指針, 即 map 是引用對象, 對map的操作會影響到結構體內部

使用方式

對應的是下面兩種方法

map的key的類型,實現了自己的hash 方式。每種類型實現hash函數方式不一樣。

key 經過哈希計算後得到hash值,共 64 個 bit 位。 其中後B 個bit位置, 用來定位當前元素落在哪一個桶里, 高8個bit 為當前 hash 值的top hash。 實際上定位key的過程是一個雙重循環的過程, 外層循環遍歷 所有的overflow, 內層循環遍歷 當前bmap 中的 8個元素

舉例說明: 如果當前 B 的值為 5, 那麼buckets 的長度 為 2^5 = 32。假設有個key 經過hash函數計算後,得到的hash結果為:

外層遍歷bucket 中的鏈表

內層循環遍歷 bmap中的8個 cell

建議先不看此部分內容,看完後續 修改 map中元素 -> 擴容 操作後 再回頭看此部分內容。

擴容前的數據:

等量擴容後的數據:

等量擴容後,查找方式和原本相同, 不多做贅述。

兩倍擴容後的數據

兩倍擴容後,oldbuckets 的元素,可能被分配成了兩部分。查找順序如下:

此處只分析 mapaccess1 ,。 mapaccess2 相比 mapaccess1 多添加了是否找到的bool值, 有興趣可自行看一下。

使用方式:

步驟如下:

擴容條件 :

擴容的標識 : h.oldbuckets != nil

假設當前定位到了新的buckets的3號桶中,首先會判斷oldbuckets中的對應的桶有沒有被搬遷過。 如果搬遷過了,不需要看原來的桶了,直接遍歷新的buckets的3號桶。

擴容前:

等量擴容結果

雙倍擴容會將old buckets上的元素分配到x, y兩個部key & 1 << B == 0 分配到x部分,key & 1 << B == 1 分配到y部分

注意: 當前只對雙倍擴容描述, 等量擴容只是重新填充了一下元素, 相對位置沒有改變。

假設當前map 的B == 5,原本元素經過hash函數計算的 hash 值為:

因為雙倍擴容之後 B = B + 1,此時B == 6。key & 1 << B == 1, 即 當前元素rehash到高位,新buckets中 y 部分. 否則 key & 1 << B == 0 則rehash到低位,即x 部分。

使用方式:

可以看到,每一遍歷生成迭代器的時候,會隨機選取一個bucket 以及 一個cell開始。 從前往後遍歷,再次遍歷到起始位置時,遍歷完成。

https://www.qcrao.com/2019/05/22/dive-into-go-map/

https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/

https://www.bilibili.com/video/BV1Q4411W7MR?spm_id_from=333.337.search-card.all.click

⑸ LinkedHashMap實現LRU - 附重點源碼解析

最近接觸 LRU(Least Recently Used) ,即最近最少使用,也稱 淘汰演算法 ,在JDK中LinkedHashMap有相關實現,下面針對 LRU及LinkedHashMap的LRU實現 進行詳細講解

有些數據需要緩存在內存中,以便高效查詢。但是當緩存的數據量很大,並且某一時間段只有某小部分緩存數據被頻繁使用(稱之為熱點數據),而其他緩存數據暫時沒有訪問,這時就需要LRU策略對熱點數據進行保留,對非熱點數據進行及時下線,保證緩存空間健康。
應用場景 : 商城分時段商品秒殺

創建LRULinkedHashMap繼承LinkedHashMap並重寫removeEldestEntry方法,該方法返回的boolean代表是否刪除最早使用/存放的Entry。

LinkedHashMap 繼承自 HashMap ,HashMap採用數組加鏈表的結構存儲數據,存儲節點為HashMap.Node,分別存放hash值,key,value,以及指向下一個Node節點的next指針,鏈表結構是單項鏈表,HashMap並沒有維護有序性。

LinkedHashMap 繼承了HashMap,也是採用了數據加鏈表的結構,不同的是LinkedHashMap的存儲節點(Entry)繼承自HashMap.Node, 多維護了before和after指針,用來指向上一個和下一個節點,實現雙向鏈表 。這個雙向鏈表就可以實現Map有序性(access-order:訪問順序/insertion-order插入順序, 默認是insertion-order )。

下面是設置 LinkedHashMap 訪問順序 時的示意圖。

⑹ hashmap底層實現原理

hashmap底層實現原理是SortedMap介面能夠把它保存的記錄根據鍵排序,默認是按鍵值的升序排序,也可以指定排序的比較器,當用Iterator遍歷TreeMap時,得到的記錄是排過序的。

如果使用排序的映射,建議使用TreeMap。在使用TreeMap時,key必須實現Comparable介面或者在構造TreeMap傳入自定義的Comparator,否則會在運行時拋出java.lang.ClassCastException類型的異常。

Hashtable是遺留類,很多映射的常用功能與HashMap類似,不同的是它承自Dictionary類,並且是線程安全的,任一時間只有一個線程能寫Hashtable

從結構實現來講,HashMap是:數組+鏈表+紅黑樹(JDK1.8增加了紅黑樹部分)實現的。

(6)hashmap源碼分析擴展閱讀

從源碼可知,HashMap類中有一個非常重要的欄位,就是 Node[] table,即哈希桶數組。Node是HashMap的一個內部類,實現了Map.Entry介面,本質是就是一個映射(鍵值對),除了K,V,還包含hash和next。

HashMap就是使用哈希表來存儲的。哈希表為解決沖突,採用鏈地址法來解決問題,鏈地址法,簡單來說,就是數組加鏈表的結合。在每個數組元素上都一個鏈表結構,當數據被Hash後,得到數組下標,把數據放在對應下標元素的鏈表上。

如果哈希桶數組很大,即使較差的Hash演算法也會比較分散,如果哈希桶數組數組很小,即使好的Hash演算法也會出現較多碰撞,所以就需要在空間成本和時間成本之間權衡,其實就是在根據實際情況確定哈希桶數組的大小,並在此基礎上設計好的hash演算法減少Hash碰撞。

⑺ java7和java8對hashmap做了哪些優化

HashMap的原理介紹

此乃老生常談,不作仔細解說。
一句話概括之:HashMap是一個散列表,它存儲的內容是鍵值對(key-value)映射。

Java 7 中HashMap的源碼分析

首先是HashMap的構造函數代碼塊1中,根據初始化的Capacity與loadFactor(載入因子)初始化HashMap.
//代碼塊1
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;
threshold = initialCapacity;
init();
}

Java7中對於<key1,value1>的put方法實現相對比較簡單,首先根據 key1 的key值計算hash值,再根據該hash值與table的length確定該key所在的index,如果當前位置的Entry不為null,則在該Entry鏈中遍歷,如果找到hash值和key值都相同,則將值value覆蓋,返回oldValue;如果當前位置的Entry為null,則直接addEntry。
代碼塊2
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

//addEntry方法中會檢查當前table是否需要resize
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //當前map中的size 如果大於threshole的閾值,則將resize將table的length擴大2倍。
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}

createEntry(hash, key, value, bucketIndex);
}

Java7 中resize()方法的實現比較簡單,將OldTable的長度擴展,並且將oldTable中的Entry根據rehash的標記重新計算hash值和index移動到newTable中去。代碼如代碼塊3中所示,
//代碼塊3 --JDK7中HashMap.resize()方法
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}

Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

/**
* 將當前table的Entry轉移到新的table中
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

HashMap性能的有兩個參數:初始容量(initialCapacity) 和載入因子(loadFactor)。容量 是哈希表中桶的數量,初始容量只是哈希表在創建時的容量。載入因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了載入因子與當前容量的乘積時,則要對該哈希表進行 rehash 操作(即重建內部數據結構),從而哈希表將具有大約兩倍的桶數。
根據源碼分析可以看出:在Java7 中 HashMap的entry是按照index索引存儲的,遇到hash沖突的時候採用拉鏈法解決沖突,將沖突的key和value插入到鏈表list中。
然而這種解決方法會有一個缺點,假如key值都沖突,HashMap會退化成一個鏈表,get的復雜度會變成O(n)。
在Java8中為了優化該最壞情況下的性能,採用了平衡樹來存放這些hash沖突的鍵值對,性能由此可以提升至O(logn)。
代碼塊4 -- JDK8中HashMap中常量定義
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int TREEIFY_THRESHOLD = 8; // 是否將list轉換成tree的閾值
static final int UNTREEIFY_THRESHOLD = 6; // 在resize操作中,決定是否untreeify的閾值
static final int MIN_TREEIFY_CAPACITY = 64; // 決定是否轉換成tree的最小容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; // default的載入因子

在Java 8 HashMap的put方法實現如代碼塊5所示,
代碼塊5 --JDK8 HashMap.put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

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; //table為空的時候,n為table的長度
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // (n - 1) & hash 與Java7中indexFor方法的實現相同,若i位置上的值為空,則新建一個Node,table[i]指向該Node。
else {
// 若i位置上的值不為空,判斷當前位置上的Node p 是否與要插入的key的hash和key相同
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)
// 不同,且當前位置上的的node p已經是TreeNode的實例,則再該樹上插入新的node。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 在i位置上的鏈表中找到p.next為null的位置,binCount計算出當前鏈表的長度,如果繼續將沖突的節點插入到該鏈表中,會使鏈表的長度大於tree化的閾值,則將鏈表轉換成tree。
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;
}

再看下resize方法,由於需要考慮hash沖突解決時採用的可能是list 也可能是balance tree的方式,因此resize方法相比JDK7中復雜了一些,
代碼塊6 -- JDK8的resize方法
inal Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
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;//如果超過最大容量,無法再擴充table
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // threshold門檻擴大至2倍
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// 創建容量為newCap的newTab,並將oldTab中的Node遷移過來,這里需要考慮鏈表和tree兩種情況。

⑻ HashMap底層實現原理剖析

Hashmap是一種非常常用的、應用廣泛的數據類型,最近研究到相關的內容,就正好復習一下。網上關於hashmap的文章很多,但到底是自己學習的總結,就發出來跟大家一起分享,一起討論。

1.HashMap的數據結構:在java 中 數據結構,最基本 也就兩種 一種數組 一種模擬指針。所有的數據結構都可以用這兩個基本結構來構造的,hashmap也不例外。Hashmap實際上是一個數組和鏈表的結合體。數組的默認長度為16,

2.hashMap源碼解析

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化容量大小 

static final int MAXIMUM_CAPACITY = 1 << 30; ///容器最大值

static final float DEFAULT_LOAD_FACTOR = 0.75f; //載入影子

static final Entry[] EMPTY_TABLE = {}; //null 的hashMap

transient Entry[] table = (Entry[]) EMPTY_TABLE;///動態擴大容器時使用的一個hashMap

transient int size;//當前數據量

int threshold;//擴大容器時的大小 為 capacity * load factor

final float loadFactor;//使用率閥值,默認為:DEFAULT_LOAD_FACTOR

存取元素 :調用put方法

public V put(K key, V value) { 

//判斷當前table 為Null 第一次Put 

 if (table == EMPTY_TABLE) {

     inflateTable(threshold);  //初始化容器的大小

 }

 if (key == null) 

 return putForNullKey(value); //判斷當前key 為null 將Null key添加到數組的第一個位置

 int hash = hash(key); //將當前key進行hash 詳情見下方

 int i = indexFor(hash, table.length); //調用完hash演算法後,詳情見下方

 for (Entry e = table[i]; e != null; e = e.next) { //循環判斷當前數組下標為Entry的實體 將當前key相同的替換為最新的值

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(hash, key, value, i); //如果key都不同 則添加Entry.詳情見下方

        return null;

    }

hashMap的hash演算法剖析

final int hash(Object k) {

        int h = hashSeed;

        if (0 != h && k instanceof String) {  //判斷當前k是否為string 和

            return sun.misc.Hashing.stringHash32((String) k); //使用stringHash32演算法得出key   的hash值

        }

        h ^= k.hashCode(); //調用key的hashCode 得出值 後使用"或"運算符 

        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

前面說過HashMap的數據結構是數組和鏈表的結合,所以我們當然希望這個HashMap裡面的 元素位置盡量的分布均勻些,盡量使得每個位置上的元素數量只有一個,那麼當我們用hash演算法求得這個位置的時候,馬上就可以知道對應位置的元素就是我們要的,而不用再去遍歷鏈表,這樣就大大優化了查詢的效率。

一個十進制數32768(二進制1000 0000 0000 0000),經過上述公式運算之後的結果是35080(二進制1000 1001 0000 1000)。看出來了嗎?或許這樣還看不出什麼,再舉個數字61440(二進制1111 0000 0000 0000),運算結果是65263(二進制1111 1110 1110 1111),現在應該很明顯了,它的目的是讓「1」變的均勻一點,散列的本意就是要盡量均勻分布。使用上述演算法後 "1"就變得很均勻了。

我們用table[index]表示已經找到的元素需要存儲的位置。先判斷該位置上有沒有元素(這個元素是HashMap內部定義的一個類Entity, 基本結構它包含三個類,key,value和指向下一個Entity的next),沒有的話就創建一個Entity對象,在 table[index]位置上插入,這樣插入結束;如果有的話,通過鏈表的遍歷方式去逐個遍歷,看看有沒有已經存在的key,有的話用新的value替 換老的value;如果沒有,則在table[index]插入該Entity,把原來在table[index]位置上的Entity賦值給新的 Entity的next,這樣插入結束

    }

indexFor 返回當前數組下標 ,

static int indexFor(int h, int length) {

        return h & (length-1);

    }

那麼得到key 之後的hash如何得到數組下標呢 ?把h與HashMap的承載量(HashMap的默認承載量length是16,可以自動變長。在構造HashMap的時候也可以指定一個長 度。這個承載量就是上圖所描述的數組的長度。)進行邏輯與運算,即 h & (length-1),這樣得到的結果就是一個比length小的正數,我們把這個值叫做index。其實這個index就是索引將要插入的值在數組中的 位置。第2步那個演算法的意義就是希望能夠得出均勻的index,這是HashTable的改進,HashTable中的演算法只是把key的 hashcode與length相除取余,即hash % length,這樣有可能會造成index分布不均勻。

首先來解釋一下為什麼數組大小為2的冪時hashmap訪問的性能最高?

看下圖,左邊兩組是數組長度為16(2的4次方),右邊兩組是數組長度為15。兩組的hashcode均為8和9,但是很明顯,當它們和1110「與」的時候,產生了相同的結果,也就是說它們會定位到數組中的同一個位置上去,這就產生了碰撞,8和9會被放到同一個鏈表上,那麼查詢的時候就需要遍歷這個鏈表,得到8或者9,這樣就降低了查詢的效率。同時,我們也可以發現,當數組長度為15的時候,hashcode的值會與14(1110)進行「與」,那麼最後一位永遠是0,而0001,0011,0101,1001,1011,0111,1101這幾個位置永遠都不能存放元素了,空間浪費相當大,更糟的是這種情況中,數組可以使用的位置比數組長度小了很多,這意味著進一步增加了碰撞的幾率,減慢了查詢的效率! 

void addEntry(int hash, K key, V value, int bucketIndex) {

  //// 若HashMap的實際大小 不小於 「閾值」,則調整HashMap的大小

        if ((size >= threshold) && (null != table[bucketIndex])) {

            resize(2 * table.length);

            hash = (null != key) ? hash(key) : 0;

          //// 設置「bucketIndex」位置的元素為「新Entry」,// 設置「e」為「新Entry的下一個節點」

            bucketIndex = indexFor(hash, table.length);

        }

        createEntry(hash, key, value, bucketIndex);

    }

//將當前key 和value添加到Entry[]中

void createEntry(int hash, K key, V value, int bucketIndex) { 

        Entry e = table[bucketIndex];  //將第一個就得table 復制個新的entry 

        table[bucketIndex] = new Entry<>(hash, key, value, e); //將當前新的Entry 復制個table[bucketIndex]  舊的table[bucketIndex] 和新的table[buckIndex]之間用next關聯。第一個鍵值對A進來,通過計算其key的hash得到的index=0,記做:table[0] = A。一會後又進來一個鍵值對B,通過計算其index也等於0,現在怎麼辦?HashMap會這樣做: B.next = A ,table[0] = B,如果又進來C,index也等於0,那麼 C.next = B ,table[0] = C;這樣我們發現index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起

        size++; //容量加1

    }

以上就是HashMap添加元素時的過程解析

那麼如何get元素呢?

public V get(Object key) {

 if (key == null) return getForNullKey(); //當前key是否為null 如果為null值返回table[0]這個value

    Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();

    }

final EntrygetEntry(Object key) {

 if (size == 0) { return null; }  //判斷容量是否大於0 

 int hash = (key == null) ? 0 : hash(key); //對當前key 進行hash hash後得到一個值

 for (Entry e = table[indexFor(hash, table.length)]; //獲取當前Entry 循環遍歷

            e != null;

            e = e.next) {

            Object k;

            if (e.hash == hash &&

                ((k = e.key) == key || (key != null && key.equals(k))))

                return e;

        }

        return null;

    }

擴展問題:

1.當前我們的hashMap中越來越大的之後,"碰撞"就越來越明顯,那麼如何解決碰撞呢?擴容!

當hashmap中的元素個數超過數組大小capti*loadFactor時,就會進行數組擴容,loadFactor的默認值為0.75,也就是說,默認情況下,數組大小為16,那麼當hashmap中元素個數超過16*0.75=12的時候,就把數組的大小擴展為2*16=32,即擴大一倍,然後重新計算每個元素在數組中的位置,而這是一個非常消耗性能的操作,所以如果我們已經預知hashmap中元素的個數,那麼預設元素的個數能夠有效的提高hashmap的性能。比如說,我們有1000個元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合適,不過上面annegu已經說過,即使是1000,hashmap也自動會將其設置為1024。 但是new HashMap(1024)還不是更合適的,因為0.75*1000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合適,既考慮了&的問題,也避免了resize的問題

HashMap的兩種遍歷方式

第一種

Map map = newHashMap();

Iterator iter = map.entrySet().iterator();

while(iter.hasNext()) {

Map.Entry entry = (Map.Entry) iter.next();

Object key = entry.getKey();

Object val = entry.getValue();

}

效率高,以後一定要使用此種方式!

第二種

Map map = newHashMap();

Iterator iter = map.keySet().iterator();

while(iter.hasNext()) {

Object key = iter.next();

Object val = map.get(key);

}

效率低,以後盡量少使用!

歸納

簡單地說,HashMap 在底層將 key-value 當成一個整體進行處理,這個整體就是一個 Entry 對象。HashMap 底層採用一個 Entry[] 數組來保存所有的 key-value 對,當需要存儲一個 Entry 對象時,會根據hash演算法來決定其在數組中的存儲位置,在根據equals方法決定其在該數組位置上的鏈表中的存儲位置;當需要取出一個Entry時,

也會根據hash演算法找到其在數組中的存儲位置,再根據equals方法從該位置上的鏈表中取出該Entry。

⑼ 同步的數據結構,例如concurrenthashmap的源碼理解以及內部實現原理,為什麼他是同

nized是針對整張Hash表的,即每次鎖住整張表讓線程獨占,ConcurrentHashMap允許多個修改操作並發進行,其關鍵在於使用了鎖分離技術。它使用了多個鎖來控制對hash表的不同部分進行的修改。ConcurrentHashMap內部使用段(Segment)來表示這些不同的部分,每個段其實就是一個小的hash table,它們有自己的鎖。只要多個修改操作發生在不同的段上,它們就可以並發進行。
有些方法需要跨段,比如size()和containsValue(),它們可能需要鎖定整個表而而不僅僅是某個段,這需要按順序鎖定所有段,操作完畢後,又按順序釋放所有段的鎖。這里「按順序」是很重要的,否則極有可能出現死鎖,在ConcurrentHashMap內部,段數組

熱點內容
安卓外部資源怎麼下載 發布:2024-03-29 04:01:17 瀏覽:244
華為被加密碼的相冊在哪裡查看 發布:2024-03-29 04:00:27 瀏覽:747
自動欣悅版有哪些配置 發布:2024-03-29 03:48:26 瀏覽:287
如何用腳本搶 發布:2024-03-29 03:01:59 瀏覽:120
火影忍者手游配置怎麼調 發布:2024-03-29 02:53:53 瀏覽:103
編程畫櫻花 發布:2024-03-29 02:11:24 瀏覽:473
騰訊雲伺服器1mb老掉線 發布:2024-03-29 01:56:11 瀏覽:215
執行sql語句的存儲過程 發布:2024-03-29 01:52:37 瀏覽:697
婚紗攝影腳本 發布:2024-03-29 01:47:40 瀏覽:901
我的世界伺服器咋開外掛 發布:2024-03-29 01:07:45 瀏覽:456