HashMap詳解-有解無憂

HashMap詳解

HashMap相關介紹

HashMap是Java中的比較常見的集合，主要存放的是鍵值對，以key-value的形式存盤，不是執行緒安全的，它里面的存盤的key和value可以為null值，但是key只允許有一個null值，HashMap是無序的，無法保證里面存盤的鍵值對的有序性，jdk1.8之前的版本底層采用的是陣列+鏈表的方式組成，jdk1.8之后采用的是陣列+鏈表+紅黑樹的方式，陣列具有查詢效率高、插入、洗掉效率低，鏈表具有查詢效率低，但是插入、洗掉效率高，HashMap采用這兩種方式的結構，可以保證查詢、插入、洗掉效率都得到保證，

HashMap資料結構

jdk1.8之后的版本使用資料+鏈表+紅黑樹的方式作為底層的資料結構，在鏈表長度大于閾值8之后，如果陣列長度大于64時，才會轉換成紅黑樹進行存盤，閾值默認是8，下面我們介紹一下HashMap的設值程序：

我們在呼叫HashMap的put設值時，首先會對值進行hash操作，

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

判斷索引的陣列位置是否為空，如果為空，則進行初始化，分配空間，進行擴容，
```
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);

如果這個位置有值，則需要解決沖突
- 首先判斷鏈表的頭，代碼中的p，先判斷hash值是否和我們的相同，如果hash值相同的話，在判斷具體數值，如果相同，則先記錄該位置，也就是代碼中的e，
```
Node<K,V> e; K k;
if (p.hash == hash &&
  ((k = p.key) == key || (key != null && key.equals(k))))
  e = p;
```
- 如果不同，那就需要遍歷鏈表，jdk1.8之后的做了優化，鏈表太長時，會轉換成紅黑樹，如果是TreeNode,則呼叫TreeNode的方法進行插入，此時就是采用的紅黑樹作為資料結構，
```
else if (p instanceof TreeNode)
  e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
```
- 如果不是TreeNode,則是用回圈的方式遍歷鏈表，如果有相同的鏈表節點，則記錄該節點,代碼中的e，如果沒有相同的鏈表節點，則e為null,此時會創建一個新的Node，插入在鏈表最后，
```
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;
}
```
- 最后判斷e是不是null,e代表的是是否存在相同的值，存在，則記錄的位置，不存在，則為null,如果存在，則會直接更新e記錄的位置的值，
```
if (e != null) { // existing mapping for key
    V oldValue = https://www.cnblogs.com/aibianchengya/archive/2022/10/31/e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}
```
- 在回圈遍歷鏈表時，如果該節點是個新的節點，插入在鏈表最后，此時會判斷鏈表的長度是否大于TREEIFY_THRESHOLD - 1,默認是8，如果大于8,則會呼叫轉換成紅黑樹的方法，但是，方法里面還會判斷陣列長度是否大于MIN_TREEIFY_CAPACITY,默認是64,如果大于，則轉換成紅黑樹，
```
if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
    break;
}
```
```
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
```

關注微信公眾號「平哥技術站」, 每日更新，在手機上閱讀所有教程，隨時隨地都能學習，

原文鏈接:https://monkey.blog.xpyvip.top/archives/hashmap-xiang-jie

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/523899.html

標籤：其他

上一篇：設計模式

下一篇：python基礎-函式