JDK7與JDK8中HashMap的實現

2022-11-24 19:11:44 字數 3032 閱讀 7625

hashmap底層維護一個陣列,陣列中的每一項都是一個entry

transient entry table;

我們向 hashmap 中所放置的物件實際上是儲存在該陣列當中; 

而map中的key,value則以entry的形式存放在陣列中

static

class entryimplements map.entry

而這個entry應該放在陣列的哪一個位置上(這個位置通常稱為位桶或者hash桶,即hash值相同的entry會放在同一位置,用連結串列相連),是通過key的hashcode來計算的。

inal int

hash(object k)

通過hash計算出來的值將會使用indexfor方法找到它應該所在的table下標:

static

int indexfor(int h, int

length)

這個方法其實相當於對table.length取模。

當兩個key通過hashcode計算相同時,則發生了hash衝突(碰撞),hashmap解決hash衝突的方式是用連結串列。如圖示

當發生hash衝突時,則將存放在陣列中的entry設定為新值的next(這裡要注意的是,比如a和b都hash後都對映到下標i中,之前已經有a了,當map.put(b)時,將b放到下標i中,a則為b的next,所以新值存放在陣列中,舊值在新值的連結串列上)

所以當hash衝突很多時,hashmap退化成連結串列。

總結一下map.put後的過程:

當向 hashmap 中 put 一對鍵值時,它會根據 key的 hashcode 值計算出一個位置, 該位置就是此物件準備往陣列中存放的位置。 

如果該位置沒有物件存在,就將此物件直接放進陣列當中;如果該位置已經有物件存在了,則順著此存在的物件的鏈開始尋找(為了判斷是否是否值相同,map不允許鍵值對重複), 如果此鏈上有物件的話,再去使用 equals方法進行比較,如果對此鏈上的每個物件的 equals 方法比較都為 false,則將該物件放到陣列當中,然後將陣列中該位置以前存在的那個物件連結到此物件的後面。 

值得注意的是,當key為null時,都放到table[0]中

private

v putfornullkey(v value)

}modcount++;

addentry(0, null, value, 0);

return

null

; }

當size大於threshold時,會發生擴容。 threshold等於capacity*load factor

void addentry(int hash, k key, v value, int

bucketindex)

createentry(hash, key, value, bucketindex);

}

jdk7中resize,只有當 size>=threshold並且 table中的那個槽中已經有entry時,才會發生resize。即有可能雖然size>=threshold,但是必須等到每個槽都至少有一個entry時,才會擴容。還有注意每次resize都會擴大一倍容量

一直到jdk7為止,hashmap的結構都是這麼簡單,基於一個陣列以及多個連結串列的實現,hash值衝突的時候,就將對應節點以連結串列的形式儲存。

這樣子的hashmap效能上就抱有一定疑問,如果說成百上千個節點在hash時發生碰撞,儲存一個連結串列中,那麼如果要查詢其中一個節點,那就不可避免的花費o(n)的查詢時間,這將是多麼大的效能損失。這個問題終於在jdk8中得到了解決。再最壞的情況下,連結串列查詢的時間複雜度為o(n),而紅黑樹一直是o(logn),這樣會提高hashmap的效率。

jdk7中hashmap採用的是位桶+連結串列的方式,即我們常說的雜湊連結串列的方式,而jdk8中採用的是位桶+連結串列/紅黑樹(有關紅黑樹請檢視紅黑樹

)的方式,也是非執行緒安全的。當某個位桶的連結串列的長度達到某個閥值的時候,這個連結串列就將轉換成紅黑樹。

jdk8中,當同一個hash值的節點數不小於8時,將不再以單連結串列的形式儲存了,會被調整成一顆紅黑樹(上圖中null節點沒畫)。這就是jdk7與jdk8中hashmap實現的最大區別。

接下來,我們來看下jdk8中hashmap的原始碼實現。

jdk中entry的名字變成了node,原因是和紅黑樹的實現treenode相關聯。

transient node table;

當衝突節點數不小於8-1時,轉換成紅黑樹。

static final int treeify_threshold = 8;

以put方法在jdk8中有了很大的改變

public

v put(k key, v value)

final v putval(int hash, k key, v value, boolean

onlyifabsent,

boolean

evict)

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

break

; p =e;}}

if (e != null)

}++modcount;

//判斷閾值,決定是否擴容

if (++size >threshold)

resize();

//4.

afternodeinsertion(evict);

return

null

; }

treeifybin()就是將連結串列轉換成紅黑樹。

之前的indeffor()方法消失 了,直接用(tab.length-1)&hash,所以看到這個,代表的就是陣列的下角標。

static

final

inthash(object key)

jdk7 HashSet和HashMap原始碼分析

先來看看hashmap的一些成員變數以及他們的含義 the default initial capacity must be a power of two.static final int default initial capacity 16 預設entry陣列的長度 the load facto...

ArrayList中的一些小細節 JDK8

protected transient int modcount 0 該變數用於記錄arraylist的版本號,不可被序列化,每次對arraylist操作都會修改此版本號,為arraylist提供fastfail功能 可是,在每次操作中都操作此變數,會造成一個結果就是該變數會迅速變化,很快超過int...

HashTable的資料結構分析 jdk8

看了下hashtable的資料結構,繼承了dictionary一個比較過時的抽象類,簡單記下原理。先看下hashtable的成員變數 存放資料的陣列,entry是hashmap.node實現的介面,基本類似 private transient entry table 存放的物件數量 private ...