面試：說說你對(duì) HashMap 的認(rèn)識(shí)？

public class HashMapExam {
    public static void main(String[] args) {
        Map map = new HashMap(16);
        for (int i = 0; i < 15; i++) {
            map.put(i, new String(new char[]{(char) ('A'+ i)}));
        }
        System.out.println("======keySet=======");
        Set set = map.keySet();
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        System.out.println("======values=======");
        Collection values = map.values();
        Iterator stringIterator=values.iterator();
        while (stringIterator.hasNext()) {
            System.out.println(stringIterator.next());
        }
        System.out.println("======entrySet=======");
        for (Map.Entry entry : map.entrySet()) {
            System.out.println(entry);
        }
    }
}

//默認(rèn)的初始容量16,且實(shí)際容量是2的整數(shù)冪
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //最大容量(傳入容量過大將被這個(gè)值替換)
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默認(rèn)加載因子為0.75(當(dāng)表達(dá)到3/4滿時(shí),才會(huì)再散列),這個(gè)因子在時(shí)間和空間代價(jià)之間達(dá)到了平衡.更高的因子可以降低表所需的空間,但是會(huì)增加查找代價(jià),而查找是最頻繁操作
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //桶的樹化閾值：即 鏈表轉(zhuǎn)成紅黑樹的閾值，在存儲(chǔ)數(shù)據(jù)時(shí)，當(dāng)鏈表長(zhǎng)度 >= 8時(shí)，則將鏈表轉(zhuǎn)換成紅黑樹
    static final int TREEIFY_THRESHOLD = 8;
   // 桶的鏈表還原閾值：即 紅黑樹轉(zhuǎn)為鏈表的閾值，當(dāng)在擴(kuò)容（resize（））時(shí)（HashMap的數(shù)據(jù)存儲(chǔ)位置會(huì)重新計(jì)算），在重新計(jì)算存儲(chǔ)位置后，當(dāng)原有的紅黑樹內(nèi)數(shù)量 <= 6時(shí)，則將 紅黑樹轉(zhuǎn)換成鏈表
    static final int UNTREEIFY_THRESHOLD = 6;
   //最小樹形化容量閾值：即 當(dāng)哈希表中的容量 > 該值時(shí)，才允許樹形化鏈表 （即 將鏈表 轉(zhuǎn)換成紅黑樹）

// 為了避免擴(kuò)容/樹形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD
    // 小于該值時(shí)使用的是擴(kuò)容哦!!!
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存儲(chǔ)數(shù)據(jù)的Node數(shù)組,長(zhǎng)度是2的冪.
    // HashMap采用鏈表法解決沖突，每一個(gè)Node本質(zhì)上是一個(gè)單向鏈表
    //HashMap底層存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu),是一個(gè)Node數(shù)組.上面得知Node類為元素維護(hù)了一個(gè)單向鏈表.至此,HashMap存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)也就很清晰了:維護(hù)了一個(gè)數(shù)組,每個(gè)數(shù)組又維護(hù)了一個(gè)單向鏈表.之所以這么設(shè)計(jì),考慮到遇到哈希沖突的時(shí)候,同index的value值就用單向鏈表來維護(hù)
    //與 JDK 1.7 的對(duì)比（Entry類），僅僅只是換了名字
    transient Node[] table;
    // HashMap的底層數(shù)組中已用槽的數(shù)量
    transient int size;
    // HashMap的閾值，用于判斷是否需要調(diào)整HashMap的容量（threshold = 容量*加載因子）
    int threshold;
    // 負(fù)載因子實(shí)際大小
    final float loadFactor;
    // HashMap被改變的次數(shù)
    transient int modCount;
    // 指定“容量大小”和“加載因子”的構(gòu)造函數(shù),是最基礎(chǔ)的構(gòu)造函數(shù)
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // HashMap的最大容量只能是MAXIMUM_CAPACITY
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //負(fù)載因子須大于0
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // 設(shè)置"負(fù)載因子"
        this.loadFactor = loadFactor;
        // 設(shè)置"HashMap閾值",當(dāng)HashMap中存儲(chǔ)數(shù)據(jù)的數(shù)量達(dá)到threshold時(shí),就需將HashMap的容量加倍
        this.threshold = tableSizeFor(initialCapacity);
    }

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 = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  }

static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;
        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry e = (Map.Entry)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

static final class TreeNode extends LinkedHashMap.Entry {
        TreeNode parent; // red-black tree links
        TreeNode left;
        TreeNode right;
        TreeNode prev; // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node next) {}
        // 返回當(dāng)前節(jié)點(diǎn)的根節(jié)點(diǎn)
        final TreeNode root() {
          for (TreeNode r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
 }

public V put(K key, V value) {
        // 對(duì)key的hashCode()做hash
        return putVal(hash(key), key, value, false, true);
    }
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node[] tab; Node p; int n, i;
        // 步驟① tab為空則調(diào)用resize()初始化創(chuàng)建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 步驟② 計(jì)算index,并對(duì)null做處理
        //tab[i = (n - 1) & hash對(duì)應(yīng)下標(biāo)的第一個(gè)節(jié)點(diǎn)
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 無哈希沖突的情況下,將value直接封裝為Node并賦值
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            // 步驟③ 節(jié)點(diǎn)的key相同,直接覆蓋節(jié)點(diǎn)
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 步驟④ 判斷該鏈為紅黑樹
            else if (p instanceof TreeNode)
                 // p是紅黑樹類型，則調(diào)用putTreeVal方式賦值
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            // 步驟⑤ p非紅黑樹類型,該鏈為鏈表
            else {
                // index 相同的情況下
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        // 如果p的next為空,將新的value值添加至鏈表后面
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            // 如果鏈表長(zhǎng)度大于8,鏈表轉(zhuǎn)化為紅黑樹,執(zhí)行插入
                            treeifyBin(tab, hash);
                        break;
                    }
                    // key相同則跳出循環(huán)
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //就是移動(dòng)指針方便繼續(xù)取 p.next
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //根據(jù)規(guī)則選擇是否覆蓋value
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 步驟⑥:超過最大容量,就擴(kuò)容
        if (++size > threshold)
            // size大于加載因子,擴(kuò)容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

/**
     * 該函數(shù)有2種使用情況：1.初始化哈希表 2.當(dāng)前數(shù)組容量過小，需擴(kuò)容
     */
final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 針對(duì)情況2：若擴(kuò)容前的數(shù)組容量超過最大值，則不再擴(kuò)充
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 針對(duì)情況2：若無超過最大值，就擴(kuò)充為原來的2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //newCap設(shè)置為oldCap的2倍并小于MAXIMUM_CAPACITY，且大于默認(rèn)值, 新的threshold增加為原來的2倍
                newThr = oldThr << 1; // double threshold
        }
        // 針對(duì)情況1：初始化哈希表（采用指定 or 默認(rèn)值）
        else if (oldThr > 0) // initial capacity was placed in threshold
            // threshold>0, 將threshold設(shè)置為newCap,所以要用tableSizeFor方法保證threshold是2的冪次方
            newCap = oldThr;
        else { // zero initial threshold signifies using defaults
            // 默認(rèn)初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 計(jì)算新的resize上限
        if (newThr == 0) {
            // newThr為0，newThr = newCap * 0.75
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            // 新生成一個(gè)table數(shù)組
            Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            // oldTab 復(fù)制到 newTab
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                       // 鏈表只有一個(gè)節(jié)點(diǎn)，直接賦值
                       //為什么要重新Hash呢？因?yàn)殚L(zhǎng)度擴(kuò)大以后，Hash的規(guī)則也隨之改變。
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // e為紅黑樹的情況
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order鏈表優(yōu)化重hash的代碼塊
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        do {
                            next = e.next;
                            // 原索引
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 原索引 + oldCap
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 原索引放到bucket里
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 原索引+oldCap放到bucket里
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

final Node removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node[] tab; Node p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // index 元素只有一個(gè)元素
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    // index處是一個(gè)紅黑樹
                    node = ((TreeNode)p).getTreeNode(hash, key);
                else {
                    // index處是一個(gè)鏈表，遍歷鏈表返回node
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            // 分不同情形刪除節(jié)點(diǎn)
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

/**
   * 函數(shù)原型
   * 作用：根據(jù)鍵key，向HashMap獲取對(duì)應(yīng)的值
   */ 
   map.get(key)；
 /**
   * 源碼分析
   */ 
   public V get(Object key) {
    Node e;
    // 1\. 計(jì)算需獲取數(shù)據(jù)的hash值
    // 2\. 通過getNode（）獲取所查詢的數(shù)據(jù) ->>分析1
    // 3\. 獲取后，判斷數(shù)據(jù)是否為空
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
   * 分析1：getNode(hash(key), key))
   */ 
final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    // 1\. 計(jì)算存放在數(shù)組table中的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 4\. 通過該函數(shù)，依次在數(shù)組、紅黑樹、鏈表中查找（通過equals（）判斷）
        // a. 先在數(shù)組中找，若存在，則直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // b. 若數(shù)組中沒有，則到紅黑樹中尋找
        if ((e = first.next) != null) {
            // 在樹中g(shù)et
            if (first instanceof TreeNode)
                return ((TreeNode)first).getTreeNode(hash, key);
            // c. 若紅黑樹中也沒有，則通過遍歷，到鏈表中尋找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

/**
   * 源碼分析：resize(2 * table.length)
   * 作用：當(dāng)容量不足時(shí)（容量 > 閾值），則擴(kuò)容（擴(kuò)到2倍）
   */ 
   void resize(int newCapacity) {
    // 1\. 保存舊數(shù)組（old table）
    Entry[] oldTable = table;
    // 2\. 保存舊容量（old capacity ），即數(shù)組長(zhǎng)度
    int oldCapacity = oldTable.length;
    // 3\. 若舊容量已經(jīng)是系統(tǒng)默認(rèn)最大容量了，那么將閾值設(shè)置成整型的最大值，退出
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 4\. 根據(jù)新容量（2倍容量）新建1個(gè)數(shù)組，即新table
    Entry[] newTable = new Entry[newCapacity];
    // 5\. （重點(diǎn)分析）將舊數(shù)組上的數(shù)據(jù)（鍵值對(duì)）轉(zhuǎn)移到新table中，從而完成擴(kuò)容 ->>分析1.1
    transfer(newTable);
    // 6\. 新數(shù)組table引用到HashMap的table屬性上
    table = newTable;
    // 7\. 重新設(shè)置閾值
    threshold = (int)(newCapacity * loadFactor);
}
 /**
   * 分析1.1：transfer(newTable);
   * 作用：將舊數(shù)組上的數(shù)據(jù)（鍵值對(duì)）轉(zhuǎn)移到新table中，從而完成擴(kuò)容
   * 過程：按舊鏈表的正序遍歷鏈表、在新鏈表的頭部依次插入
   */ 
void transfer(Entry[] newTable) {
      // 1\. src引用了舊數(shù)組
      Entry[] src = table;
      // 2\. 獲取新數(shù)組的大小 = 獲取新容量大小
      int newCapacity = newTable.length;
      // 3\. 通過遍歷 舊數(shù)組，將舊數(shù)組上的數(shù)據(jù)（鍵值對(duì)）轉(zhuǎn)移到新數(shù)組中
      for (int j = 0; j < src.length; j++) {
          // 3.1 取得舊數(shù)組的每個(gè)元素
          Entry e = src[j];
          if (e != null) {
              // 3.2 釋放舊數(shù)組的對(duì)象引用（for循環(huán)后，舊數(shù)組不再引用任何對(duì)象）
              src[j] = null;
              do {
                  // 3.3 遍歷 以該數(shù)組元素為首 的鏈表
                  // 注：轉(zhuǎn)移鏈表時(shí)，因是單鏈表，故要保存下1個(gè)結(jié)點(diǎn)，否則轉(zhuǎn)移后鏈表會(huì)斷開
                  Entry next = e.next;
                 // 3.3 重新計(jì)算每個(gè)元素的存儲(chǔ)位置
                 int i = indexFor(e.hash, newCapacity);
                 // 3.4 將元素放在數(shù)組上：采用單鏈表的頭插入方式 = 在鏈表頭上存放數(shù)據(jù) = 將數(shù)組位置的原有數(shù)據(jù)放在后1個(gè)指針、將需放入的數(shù)據(jù)放到數(shù)組位置中
                 // 即 擴(kuò)容后，可能出現(xiàn)逆序：按舊鏈表的正序遍歷鏈表、在新鏈表的頭部依次插入
                 e.next = newTable[i];
                 newTable[i] = e;
                 // 訪問下1個(gè)Entry鏈上的元素，如此不斷循環(huán)，直到遍歷完該鏈表上的所有節(jié)點(diǎn)
                 e = next;
             } while (e != null);
             // 如此不斷循環(huán)，直到遍歷完數(shù)組上的所有數(shù)據(jù)元素
         }
     }
 }

e.next = newTable[1] = null
newTable[1] = e = key(5)
e = next = key(9)

HashIterator() {
  expectedModCount = modCount;
  if (size > 0) { // advance to first entry
  Entry[] t = table;
  while (index < t.length && (next = t[index++]) == null)
    ;
  }
}