java基礎(chǔ)類型源碼解析之多角度講HashMap

前言

成都創(chuàng)新互聯(lián)公司主營(yíng)銅陵網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,app開發(fā)定制,銅陵h5成都微信小程序搭建,銅陵網(wǎng)站營(yíng)銷推廣歡迎銅陵等地區(qū)企業(yè)咨詢

終于來(lái)到比較復(fù)雜的HashMap，由于內(nèi)部的變量，內(nèi)部類，方法都比較多，沒法像ArrayList那樣直接平鋪開來(lái)說(shuō)，因此準(zhǔn)備從幾個(gè)具體的角度來(lái)切入。

桶結(jié)構(gòu)

HashMap的每個(gè)存儲(chǔ)位置，又叫做一個(gè)桶，當(dāng)一個(gè)Key&Value進(jìn)入map的時(shí)候，依據(jù)它的hash值分配一個(gè)桶來(lái)存儲(chǔ)。

看一下桶的定義：table就是所謂的桶結(jié)構(gòu)，說(shuō)白了就是一個(gè)節(jié)點(diǎn)數(shù)組。

transient Node<K,V>[] table;
transient int size;

節(jié)點(diǎn)

HashMap是一個(gè)map結(jié)構(gòu)，它不同于Collection結(jié)構(gòu)，不是存儲(chǔ)單個(gè)對(duì)象，而是存儲(chǔ)鍵值對(duì)。

因此內(nèi)部最基本的存儲(chǔ)單元是節(jié)點(diǎn)：Node。

節(jié)點(diǎn)的定義如下：

class Node<K,V> implements Map.Entry<K,V> {
 final int hash;
 final K key;
 V value;
 Node<K,V> next;
}

可見節(jié)點(diǎn)除了存儲(chǔ)key,vaue,hash三個(gè)值之外，還有一個(gè)next指針，這樣一樣，多個(gè)Node可以形成一個(gè)單向列表。這是解決hash沖突的一種方式，如果多個(gè)節(jié)點(diǎn)被分配到同一個(gè)桶，可以組成一個(gè)鏈表。

HashMap內(nèi)部還有另一種節(jié)點(diǎn)類型，叫做TreeNode：

class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
 TreeNode<K,V> parent; // red-black tree links
 TreeNode<K,V> left;
 TreeNode<K,V> right;
 TreeNode<K,V> prev; // needed to unlink next upon deletion
 boolean red;
 }

TreeNode是從Node繼承的，它可以組成一棵紅黑樹。為什么還有這個(gè)東東呢？上面說(shuō)過，如果節(jié)點(diǎn)的被哈希到同一個(gè)桶，那么可能導(dǎo)致鏈表特別長(zhǎng)，這樣一來(lái)訪問效率就會(huì)急劇下降。此時(shí)如果key是可比較的(實(shí)現(xiàn)了Comparable接口），HashMap就將這個(gè)鏈表轉(zhuǎn)成一棵平衡二叉樹，來(lái)挽回一些效率。在實(shí)際使用中，我們期望這種現(xiàn)象永遠(yuǎn)不要發(fā)生。

有了這個(gè)知識(shí)，就可以看看HashMap幾個(gè)相關(guān)常量定義了：

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

TREEIFY_THRESHOLD，當(dāng)某個(gè)桶里面的節(jié)點(diǎn)數(shù)達(dá)到這個(gè)數(shù)量，鏈表可轉(zhuǎn)換成樹；
UNTREEIFY_THRESHOLD，當(dāng)某個(gè)桶里面數(shù)低于這數(shù)量，樹轉(zhuǎn)換回鏈表；
MIN_TREEIFY_CAPACITY，如果桶數(shù)量低于這個(gè)數(shù)，那么優(yōu)先擴(kuò)充桶的數(shù)量，而不是將鏈表轉(zhuǎn)換成樹；

put方法：Key&Value

插入接口：

public V put(K key, V value) {
 return putVal(hash(key), key, value, false, true);
}
final int hash(Object key) {
 int h;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put方法調(diào)用了私有方法putVal，不過值得注意的是，key的hash值不是直接用的hashCode，最終的hash=（hashCode右移16）^ hashCode。

在將hash值映射為桶位置的時(shí)候，取的是hash值的低位部分，這樣如果有一批key的僅高位部分不一致，就會(huì)聚集的同一個(gè)桶里面。（如果桶數(shù)量比較少，key是Float類型，且是連續(xù)的整數(shù)，就會(huì)出現(xiàn)這種case）。

執(zhí)行插入的過程：

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;

    //代碼段1
    if ((p = tab[i = (n - 1) & hash]) == null)
      tab[i] = newNode(hash, key, value, null);      
    else {
      Node<K,V> e; K k;
      //代碼段2
      if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
      //代碼段3  
      else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
      else {
        //代碼段4
        for (int binCount = 0; ; ++binCount) {
          //代碼段4.1
          if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
              treeifyBin(tab, hash);
            break;
          }
          //代碼段4.2
          if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
          p = e;
        }
      }
      //代碼段5
      if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
          e.value = value;
        afterNodeAccess(e);
        return oldValue;
      }
    }
    //代碼段6
    ++modCount;
    if (++size > threshold)
      resize();
    afterNodeInsertion(evict);
    return null;
  }

最開始的一段處理桶數(shù)組還沒有分配的情況；
代碼段1： i = (n - 1) & hash，計(jì)算hash對(duì)應(yīng)的桶位置，因?yàn)閚是2的冥次，這是一種高效的取模操作；如果這個(gè)位置是空的，那么直接創(chuàng)建Node放進(jìn)去就OK了；否則這個(gè)沖突位置的節(jié)點(diǎn)記為P;
代碼段2：如果節(jié)點(diǎn)P的key和傳入的key相等，那么說(shuō)明新的value要放入一個(gè)現(xiàn)有節(jié)點(diǎn)里面，記為e;
代碼段3：如果節(jié)點(diǎn)P是一棵樹，那么將key&value插入到這個(gè)棵樹里面；
代碼段4：P是鏈表頭，或是單獨(dú)一個(gè)節(jié)點(diǎn)，兩種情況，都可以通過掃描鏈表的方式來(lái)做；
代碼段4.1：如果鏈表到了尾部，插入一個(gè)新節(jié)點(diǎn)，同時(shí)如果有必要，將鏈表轉(zhuǎn)成樹；
代碼段4.2：如果鏈表中找到了相等的key，和代碼段2一樣處理；
代碼段5：將value存入節(jié)點(diǎn)e
代碼段6：如果size超過某個(gè)特定值，要調(diào)整桶的數(shù)量，關(guān)于resize的策略在下文會(huì)講

remove方法

了解了put方法，remove方法就容易了，直接講解私有方法removeNode吧。

public V remove(Object key) {
  Node<K,V> e;
  return (e = removeNode(hash(key), key, null, false, true)) == null ?
    null : e.value;
}
  
Node<K,V> removeNode(int hash, Object key, Object value,
                boolean matchValue, boolean movable) {
  Node<K,V>[] tab; Node<K,V> p; int n, index;
  
  //代碼段1
  if ((tab = table) != null && (n = tab.length) > 0 &&
    (p = tab[index = (n - 1) & hash]) != null) {
    
    //代碼段2：
    Node<K,V> node = null, e; K k; V v;
    if (p.hash == hash &&
      ((k = p.key) == key || (key != null && key.equals(k))))
      node = p;
      
    //代碼段3:
    else if ((e = p.next) != null) {
      //代碼段3.1:
      if (p instanceof TreeNode)
        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
      else {
        //代碼段3.2:
        do {
          if (e.hash == hash &&
            ((k = e.key) == key ||
             (key != null && key.equals(k)))) {
            node = e;
            break;
          }
          p = e;
        } while ((e = e.next) != null);
      }
    }
    
    //代碼段4:
    if (node != null && (!matchValue || (v = node.value) == value ||
               (value != null && value.equals(v)))) {         
      //代碼段4.1:
      if (node instanceof TreeNode)
        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
      //代碼段4.2:
      else if (node == p)
        tab[index] = node.next;
      //代碼段4.3:
      else
        p.next = node.next;
      ++modCount;
      --size;
      afterNodeRemoval(node);
      return node;
    }
  }
  return null;
}

代碼段1：這個(gè)if條件在判斷hash對(duì)應(yīng)的桶是否空的，如果是話，那么map里面肯定就沒有這個(gè)key；否則第一個(gè)節(jié)點(diǎn)記為P；
代碼段2：如果P節(jié)點(diǎn)的key與參數(shù)key相等，找到了要移除的節(jié)點(diǎn)，記為node；
代碼段3：掃描桶里面的其他節(jié)點(diǎn)
代碼段3.1：如果桶里面這是一顆樹，執(zhí)行樹的查找邏輯；
代碼段3.2：執(zhí)行鏈表掃描邏輯；
代碼段4：如果找到了node，那么嘗試刪除它
代碼段4.1：如果是樹節(jié)點(diǎn)，執(zhí)行樹的節(jié)點(diǎn)刪除邏輯；
代碼段4.2：node是鏈表頭結(jié)點(diǎn)，將node.next放入桶就ok；
代碼段4.3：刪除鏈表中間節(jié)點(diǎn)

rehash

rehash就是重新分配桶，并將原有的節(jié)點(diǎn)重新hash到新的桶位置。

先看兩個(gè)和桶的數(shù)量相關(guān)的成員變量

final float loadFactor;
int threshold;

loadFactor 負(fù)載因子，是創(chuàng)建HashMap時(shí)設(shè)定的一個(gè)值，即map所包含的條目數(shù)量與桶數(shù)量的比值上限；一旦map的負(fù)載達(dá)到這個(gè)值，就需要擴(kuò)展桶的數(shù)量；
threshold map的數(shù)量達(dá)到這個(gè)值，就需要擴(kuò)展桶，它的值基本上等于桶的容量*loadFactor，我感覺就是一個(gè)緩存值，加快相關(guān)的操作，不用每次都去計(jì)算；

桶的擴(kuò)展策略，見下面的函數(shù)，如果需要的容量是cap，真實(shí)擴(kuò)展的容量是大于cap的一個(gè)2的冥次。
這樣依賴，每次擴(kuò)展，增加的容量都是2的倍數(shù)。

static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

這是具體的擴(kuò)展邏輯

Node<K,V>[] resize() {
  
   //此處省略了計(jì)算newCap的邏輯

  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        
        //分支1
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        //分支2
        else if (e instanceof TreeNode)
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        //分支3
        else { // preserve order
          //此處省略了鏈表拆分邏輯  
        }
    }
  }
  return newTab;
}

首先分配新的桶數(shù)組；
掃描舊的桶，將元素遷移過來(lái)；
分支1：桶里面只有一個(gè)新的節(jié)點(diǎn)，那么放入到新桶對(duì)應(yīng)的位置即可；
分支2：桶里面是一棵樹，執(zhí)行樹的拆分邏輯
分支3：桶里面是一個(gè)鏈表，執(zhí)行鏈表的拆分邏輯；

由于新桶的數(shù)量是舊桶的2的倍數(shù)，所以每個(gè)舊桶都能對(duì)應(yīng)2個(gè)或更多的新桶，互不干擾。所以上面的遷移邏輯，并不需要檢查新桶里面是否有節(jié)點(diǎn)。

可見，rehash的代價(jià)是很大的，最好在初始化的時(shí)候，能夠設(shè)定一個(gè)合適的容量，避免rehash。

最后，雖然上面的代碼沒有體現(xiàn)，在HashMap的生命周期內(nèi)，桶的數(shù)量只會(huì)增加，不會(huì)減少。

迭代器

所有迭代器的核心就是這個(gè)HashIterator

abstract class HashIterator {
  Node<K,V> next;    // next entry to return
  Node<K,V> current;   // current entry
  int expectedModCount; // for fast-fail
  int index;       // current slot

  final Node<K,V> nextNode() {
    Node<K,V>[] t;
    Node<K,V> e = next;
    if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
    if (e == null)
      throw new NoSuchElementException();
    if ((next = (current = e).next) == null && (t = table) != null) {
      do {} while (index < t.length && (next = t[index++]) == null);
    }
    return e;
  }
}

簡(jiǎn)單起見，只保留了next部分的代碼。原理很簡(jiǎn)單，next指向下一個(gè)節(jié)點(diǎn)，肯定處在某個(gè)桶當(dāng)中(桶的位置是index)。那么如果同一個(gè)桶還有其他節(jié)點(diǎn)，那么一定可以順著next.next來(lái)找到，無(wú)論這是一個(gè)鏈表還是一棵樹。否則掃描下一個(gè)桶。

有了上面的節(jié)點(diǎn)迭代器，其他用戶可見的迭代器都是通過它來(lái)實(shí)現(xiàn)的。

final class KeyIterator extends HashIterator
  implements Iterator<K> {
  public final K next() { return nextNode().key; }
}

final class ValueIterator extends HashIterator
  implements Iterator<V> {
  public final V next() { return nextNode().value; }
}

final class EntryIterator extends HashIterator
  implements Iterator<Map.Entry<K,V>> {
  public final Map.Entry<K,V> next() { return nextNode(); }
}

視圖

KeySet的部分代碼：這并不是一個(gè)獨(dú)立的Set，而是一個(gè)視圖，它的接口內(nèi)部訪問的都是HashMap的數(shù)據(jù)。

final class KeySet extends AbstractSet<K> {
  public final int size()         { return size; }
  public final void clear()        { HashMap.this.clear(); }
  public final Iterator<K> iterator()   { return new KeyIterator(); }
  public final boolean contains(Object o) { return containsKey(o); }
  public final boolean remove(Object key) {
    return removeNode(hash(key), key, null, false, true) != null;
  }
}

EntrySet、Values和KeySet也是類似的，不再贅述。

要點(diǎn)總結(jié)

1、key&value存儲(chǔ)在節(jié)點(diǎn)中；

2、節(jié)點(diǎn)有可能是鏈表節(jié)點(diǎn)，也有可能是樹節(jié)點(diǎn)；

3、依據(jù)key哈希值給節(jié)點(diǎn)分配桶；

4、如果桶里面有多個(gè)節(jié)點(diǎn)，那么要么形成一個(gè)鏈表，要么形成一顆樹；

5、裝載因子限制的了節(jié)點(diǎn)和桶的數(shù)量比例，必要時(shí)會(huì)擴(kuò)展桶的數(shù)量；

6、桶數(shù)量必然是2的冥次，重新分配桶的過程叫做rehash，這是很昂貴的操作；

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)創(chuàng)新互聯(lián)的支持。

分享名稱：java基礎(chǔ)類型源碼解析之多角度講HashMap
標(biāo)題鏈接：http://chinadenli.net/article26/jsijcg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、微信公眾號(hào)、網(wǎng)站設(shè)計(jì)、企業(yè)建站、網(wǎng)站排名、網(wǎng)站內(nèi)鏈

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

java基礎(chǔ)類型源碼解析之多角度講HashMap