HashMap的實現原理(JDK8)

一、什麼是hash

哈希演算法

接受任意長度的二進位輸入值，對輸入值做換算（hash），最終給出固定長度的二進位輸出值；

Hash演算法不是某個固定的演算法，它代表的是一類演算法，具體換算可能各不相同

哈希表

即散列表，一種數據結構，根據關鍵碼值(Key value)而直接進行訪問

給定表M，存在函數f(key)，對任意給定的關鍵字值key，代入函數後若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數f(key)為哈希(Hash) 函數

哈希碰撞

根據上面對哈希表的定義，有一種情況是，對不同的關鍵字可能得到同一散列地址，即k1≠k2，但f(k1)=f(k2)，這種情況就是哈希碰撞。

解決哈希碰撞

拉鏈法（hashmap的解決方式）：

將鍵轉換為數組的索引(0-M-1)，但是對於兩個或者多個鍵具有相同索引值的情況，將大小為M 的數組的每一個元素指向一個條鏈表，鏈表中的每一個節點都存儲散列值為該索引的鍵值對，這就是拉鏈法

二、HashMap的實現

基於哈希表的數據結構

線程不安全

下面從代碼上來分析HashMap的實現原理

1. HashMap的結構

//實體數組

transient Node<K,V>[] table;

//實體構造函數

static class Node<K,V> implements Map.Entry<K,V> {

Node(int hash,K key,V value,Node<K,V> next){

this.hash = hash;

this.key = key;

this.value = value;

this.next = next;//鏈表中下一個元素的引用

}

}

1

2

3

4

5

6

7

8

9

10

11

12

由上面的代碼可以看出HashMap的基本結構就是:

1.儲存的結構是實體Node[]，即一個Map.Entry。內部4個值，key-value鍵值對，hash值，以及指向下一個元素的引用next，構成鏈表。

2.實體Node再構成的一個數組 Node[] table

3.而這個結構正是我們上面提到的hash表的結構，並很明顯是用拉鏈法來解決hash衝突

2. put

//使用樹而不是列表的bin計數閾值

static final int TREEIFY_THRESHOLD = 8;

public V put(K key, V value) {

// 對key的hashCode()做hash

return putVal(hash(key), key, value, false, true);

}

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

/**

* Implements Map.put and related methods

*

* @param hash hash for key

* @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.

* @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;

//數組tab為空則創建

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

//如果沒有發生hash碰撞，則直接添加到數組tab中

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

//發生了hash碰撞

else {

Node<K,V> e; K k;

//是否hash值相同，且key值也相同，即節點已存在

if (p.hash == hash &&

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

//hash值相同，且key值也相同

e = p;

//該鏈是TreeNode

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;

// 超過load factor*current capacity，resize

if (++size > threshold)

resize();

afterNodeInsertion(evict);

return null;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

由上述代碼可以看出put的邏輯

1.對key的hashCode()做hash計算得到hash值

2.根據hash值計算出對應在哈希表的數組中Node[] table中的下標：index = (size - 1) & hash

3.如果該下標上沒有存放Node，即沒有發生hash碰撞，則存放到table的該下標上

4.如果該下標上已經有存放Node，即發生了hash碰撞，則存放到table的該下標的鏈表的尾部

5.如果碰撞導致鏈表過長(大於等於TREEIFY_THRESHOLD=8)則會把鏈錶轉換成紅黑樹

6.如果節點已經存在就替換節點的值oldValue為新值

7.如果table已經滿了，則resize增加table的長度

3. get()

public V get(Object key) {

Node<K,V> e;

return (e = getNode(hash(key), key)) == null ? null : e.value;

}

final Node<K,V> getNode(int hash, Object 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) {

//直接找到了節點對應在table中的下標

if (first.hash == hash && // always check first node

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

//判斷該下標下第一個節點的key也相同，則直接返回

return first;

if ((e = first.next) != null) {

//開始遍歷鏈表

if (first instanceof TreeNode)

return

//TreeNode ((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;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

由上述代碼可以看出get的邏輯

1.對key的hashCode()做hash計算得到hash值

2.根據hash值計算出對應在哈希表的數組中Node[] table中的下標

3.該下標上的第一個元素fristNode和要查找的key值做判斷fristNode.key.equals(key),如果相同，返回

4.如果不相同，遍歷鏈表直到Node.key.equals(key)，返回

4. 擴容resize()

//臨界值（HashMap實際能存儲的大小）,公式為(threshold = capacity * loadFactor),當hashmap中存儲元素大於這個數時，就需要resize了

int threshold;

/** 負載因子,默認為0.75*/

final float loadFactor;

//默認負載因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//數組默認的大小，16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//數組最大的容量，2^30

static final int MAXIMUM_CAPACITY = 1 << 30;

final Node<K,V>[] resize() {

Node<K,V>[] oldTab = table;

int oldCap = (oldTab == null) ? 0 : oldTab.length;

int oldThr = threshold;

int newCap, newThr = 0;

//舊錶大小不為0

if (oldCap > 0) {

if (oldCap >= MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return oldTab;

}

//把新表的長度設置為舊錶長度的兩倍

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

//把新表的閥值設為舊錶2倍

newThr = oldThr << 1; // double threshold

}

//如果舊錶的長度的是0，則初始化表

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];

table = newTab;//新表賦值給table

//如果舊錶不為空，要把舊錶的值轉移到新表

if (oldTab != null) {

//遍歷舊錶

for (int j = 0; j < oldCap; ++j) {

Node<K,V> e;

if ((e = oldTab[j]) != null) {

oldTab[j] = null;

//node沒有鏈表則直接放在新表的e.hash & (newCap - 1)位置

if (e.next == null)

newTab[e.hash & (newCap - 1)] = e;

//e是treeNode，則拆樹

else if (e instanceof TreeNode)

((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

//e有鏈表，拆鏈表

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)

loHead = e;

else

loTail.next = e;

loTail = e;

}

else {

if (hiTail == null)

hiHead = e;

else

hiTail.next = e;

hiTail = e;

}

} while ((e = next) != null);

if (loTail != null) {

loTail.next = null;

newTab[j] = loHead;

}

if (hiTail != null) {

hiTail.next = null;

newTab[j + oldCap] = hiHead;

}

}

}

}

}

return newTab;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

由上述代碼可以看出reSize的邏輯

1.先判斷舊錶，如果沒有舊錶，則初始化一個默認大小的新表或者構造函數中傳入過的initialCapacity大小的新表（默認大小16；閥值為12；16*0.75），

2.如果有舊錶，則初始化一個新表，大小為舊錶的兩倍，閥值也是舊錶的兩倍

3.把舊錶的值轉移到新表

5. loadFactor和initialCapacity：

loadFactor負載因子，代表的是map的裝填程度，構造函數中有

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal load factor: " +loadFactor);

1

2

表示loadFactor必須是大於0的數字。

由前面的知識我們知道HashMap是有數組table和鏈表的來實現的

initialCapacity表示HashMap的初始化數組table的大小

而HashMap的實際容量 = initailCapacity*loadFactor

當HashMap的實際容量滿的時候，才會進行resize擴充容量

由此可知loadFactor越大，則HashMap中table會填的越滿，鏈表會越長，越容易發生hash碰撞，造成索引效率低下；反之則會越稀疏，但會造成空間浪費。

loadFactor根據情況進行設置（時間空間選擇）

注意：initailCapacity的值系統會根據傳入的值換算成比傳入值大的最接近的2的n次方這是因為

table下標計算：index = (size - 1) & hash

如當數組長度為15的時候，hashcode的值會與size - 1=14（1110）進行「與」，那麼最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大

6. 使用注意：

1.reSize()比較耗性能的（主要是舊錶的值轉移到新表）,所以初始化的時候最好能初始化合適的大小

2.HashMap hashMap = new HashMap(1000); 初始化後的表的大小為1024,即總是比傳入值大的最小的2的n次方。這是因為數組長度為2的n次方的時候，不同的key算得得index相同的幾率較小，可以減少hash碰撞，從而提高效率

3.jdk8中，HashMap處理碰撞才增加了紅黑樹這種數據結構，當碰撞結點較少時，採用鏈表存儲，當較大時（>TREEIFY_THRESHOLD=8個），採用紅黑樹存儲這樣碰撞後的查詢由鏈表變為了紅黑樹，即時間複雜度有O(n)變為了O(logn)

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！