HashMap實(shí)現(xiàn)原理、源碼解析（jdk1.8）

• 下面參考博文佛纫，感謝！
• Java 8系列之重新認(rèn)識HashMap
  • 全方面（主要是jdk1.8的源碼分析）
• HashMap源碼分析（jdk1.8总放，保證你能看懂）
  • 全方面（主要講解put過程呈宇、擴(kuò)容過程等）
• 用漫畫告訴你—什么是HashMap？
  • 主要講解 HashMap 的數(shù)據(jù)結(jié)構(gòu)局雄、哈希桶數(shù)組索引甥啄、hash算法以及各常量設(shè)計的巧妙之處等
• 一幅漫畫告訴你，什么是紅黑樹

• 正文

基本概念

• HashMap 是最常用的集合類框架之一炬搭，它實(shí)現(xiàn)了 Map 接口蜈漓，所以存儲的元素也是鍵值對映射的結(jié)構(gòu)，并允許使用 null值 和 null鍵尚蝌，其內(nèi)元素是無序的，如果要保證有序充尉，可以使用 LinkedHashMap（插入順序）飘言。
  • HashMap是線程不安全的，所以才有了 ConcurrentHashMap驼侠。也可以通過 Collections.synchronizedMap() 這個方法來使 HashMap 變?yōu)榫€程安全的姿鸿。
  • HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null倒源。
  • 它是根據(jù)鍵的 hashCode 值來存儲數(shù)據(jù)的苛预，大多數(shù)情況下可以直接定位到它的值，因而具有很快的訪問速度笋熬，但遍歷順序卻是不確定的热某。
  • 繼承關(guān)系如下:

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {···}

• Map集合繼承結(jié)構(gòu)圖

數(shù)據(jù)結(jié)構(gòu)

• HashMap 的數(shù)據(jù)結(jié)構(gòu)是 數(shù)組 + 鏈表 + 紅黑樹（jdk1.8增加了紅黑樹部分）
• 數(shù)組
  • 連續(xù)的內(nèi)存，通過下標(biāo)可以快速進(jìn)行尋址。
  • 插入結(jié)點(diǎn)困難
    • 當(dāng)在數(shù)組中插入一個元素時昔馋，后面的元素都得往后移動筹吐，然后才能進(jìn)行操作，比較麻煩富纸。
• 單鏈表
  • 插入萌腿、刪除數(shù)據(jù)方便（直接修改節(jié)點(diǎn)指針）
  • 查詢效率低（遍歷結(jié)點(diǎn)娱挨、時間復(fù)雜度O(n)）
• 紅黑樹
  • 一種自平衡的二叉查找樹，除了符合二叉查找樹的基本特性外洋侨，還具有以下特性：
    • 二叉查找樹，左子樹元素大于右子樹倦蚪，最大的查找次數(shù)為樹高希坚。
    • 節(jié)點(diǎn)是紅色或黑色。
    • 根節(jié)點(diǎn)是黑色审丘。
    • 每個葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）吏够。
    • 每個紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn))
    • 從任一節(jié)點(diǎn)到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)滩报。
  • 紅黑樹的這些規(guī)則锅知，保證了紅黑樹的自平衡。
  • 但是脓钾，當(dāng)插入售睹、刪除節(jié)點(diǎn)時，這些規(guī)則可能會被打破可训，導(dǎo)致紅黑樹不再是一個紅黑樹了昌妹。這時就需要做出一些調(diào)整，調(diào)整方法有：變色握截、旋轉(zhuǎn)（左旋飞崖、右旋）。
    • 變色就是將紅色變?yōu)楹谏靼谏優(yōu)榧t色固歪，為了滿足上面的條件
      • 注意：變色會發(fā)生連鎖反應(yīng)，所以要經(jīng)過多次變色胯努。
    • 左旋轉(zhuǎn)
      • 逆時針旋轉(zhuǎn)紅黑樹的兩個節(jié)點(diǎn)牢裳，使得父節(jié)點(diǎn)被自己的右孩子取代，而自己成為自己的左孩子叶沛。
    • 右旋轉(zhuǎn)
      • 順時針旋轉(zhuǎn)紅黑樹的兩個節(jié)點(diǎn)蒲讯，使得父節(jié)點(diǎn)被自己的左孩子取代，而自己成為自己的右孩子灰署。

源碼分析

• 下文的源碼是基于 jdk1.8 版本來進(jìn)行分析的
  • 之前 jdk1.7 的存儲結(jié)構(gòu)是數(shù)組+鏈表 ( 拉鏈?zhǔn)?)判帮，到了 jdk1.8 變成了數(shù)組+鏈表+紅黑樹局嘁。
    • 不是說變成了紅黑樹效率就一定提高了，只有在鏈表的長度不小于8脊另，而且數(shù)組的長度不小于64的時候才會將鏈表轉(zhuǎn)化為紅黑樹导狡。
    • jdk1.7 版本增刪效率高，jdk1.8 版本增刪偎痛、查找效率都高旱捧。
    • jdk1.8 版本的優(yōu)化在擴(kuò)容機(jī)制的數(shù)組元素轉(zhuǎn)移的地方有很巧妙設(shè)計的體現(xiàn)。
  • 另外踩麦，HashMap 是非線程安全的枚赡，也就是說在多個線程同時對 HashMap 中的某個元素進(jìn)行增刪改操作的時候，是不能保證數(shù)據(jù)的一致性的谓谦。

數(shù)據(jù)結(jié)構(gòu)表示

• 最終的數(shù)據(jù)結(jié)構(gòu)整體是數(shù)組贫橙，然后每個數(shù)組元素是一個鏈表的節(jié)點(diǎn)。當(dāng)發(fā)生沖突時反粥，在節(jié)點(diǎn)處使用尾插法插入節(jié)點(diǎn)卢肃。當(dāng)鏈表長度大于8之后（在數(shù)組長度大于64的前提下），鏈表就會轉(zhuǎn)換為紅黑樹了才顿。
• 鏈表節(jié)點(diǎn)的表示：
  • 存儲了 hash 碼莫湘，Key、Value郑气、鏈表的指針域（指向下一個節(jié)點(diǎn)）幅垮。

//HashMap的靜態(tài)內(nèi)部類 Node 用于表示節(jié)點(diǎn)
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

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

        public final K getKey()        {···}
        public final V getValue()      {···}
        public final String toString() {···}

        public final int hashCode() {···}

        public final V setValue(V newValue) {···}

        public final boolean equals(Object o) {···}
    }

• 紅黑樹的表示：
  • 存儲了 雙親結(jié)點(diǎn)、左子樹尾组、右子樹忙芒、前一個元素的節(jié)點(diǎn)、是否為紅色（布爾值）讳侨。
  • 另外由于它繼承自 LinkedHashMap.Entry 呵萨，而 LinkedHashMap.Entry 繼承自 HashMap.Node ，因此還有額外的 6 個屬性跨跨。

    static final 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(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
        ···
    }
    
    //繼承 LinkedHashMap.Entry 的
    Entry<K,V> before, after;
 
    //HashMap.Node 的
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

幾個常量潮峦、變量

• 其中，閾值: threshold = capacity * loadFactory歹叮。
• 注意這三個變量的區(qū)別：threshold跑杭、size铆帽、length咆耿。
• modCount 記錄的HashMap結(jié)構(gòu)的改變是指 HashMap中的 映射數(shù) 或以 其他方式修改其 內(nèi)部結(jié)構(gòu)。
  • 注意：某個key對應(yīng)的value值被覆蓋不屬于結(jié)構(gòu)變化的爹橱。

    //默認(rèn)數(shù)組容量大腥荨：16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    
    //數(shù)組最大容量大姓觥：2 的 30 次方
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    //默認(rèn)的加載因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //使用樹而不是鏈表的計數(shù)閾值，將元素添加到至少這么多的節(jié)點(diǎn)的鏈表中時慰技，鏈表將轉(zhuǎn)換為樹
    static final int TREEIFY_THRESHOLD = 8;
    
    //可以進(jìn)行樹化的最小數(shù)組容量
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    //存儲鍵值對元素的數(shù)組椭盏，分配后，長度始終是 2 的冪（哈希桶數(shù)組）
    transient Node<K,V>[] table;
    
    //此映射中包含的鍵-值映射數(shù)吻商，即當(dāng)前數(shù)組中的元素數(shù)量
    transient int size;
    
    //主要用于記錄HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)掏颊。
    transient int modCount;
    
    //哈希表所能容納的最大鍵值對個數(shù)，下次擴(kuò)容的臨界值艾帐，size>=threshold 數(shù)組就會擴(kuò)容
    int threshold;
    
    //負(fù)載因子
    final float loadFactor;

構(gòu)造方法

• HashMap 有四個構(gòu)造方法乌叶，如下：

    /**
     * 使用默認(rèn)的初始容量（16）和默認(rèn)的加載因子（0.75）構(gòu)造一個空的 HashMap
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    
    public HashMap(int initialCapacity) {
         this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
       
    /**
     * 構(gòu)造一個新的 HashMap ，其映射與指定的 Map 相同柒爸。
     * HashMap 是使用默認(rèn)負(fù)載因子（0.75）和足以將映射保存在指定的 Map 中的初始容量創(chuàng)建的
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
    
    /**
     * 構(gòu)造一個帶指定初始容量和加載因子的空 HashMap准浴。
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

• 這里簡單的說一下構(gòu)造方法中的兩個東西

• initialCapacity 初始容量

  • 官方要求我們要輸入一個2的N次冪的值，比如說2捎稚、4乐横、8、16等等這些今野，但是我們忽然一個不小心葡公，輸入了一個20怎么辦？沒關(guān)系腥泥，虛擬機(jī)會根據(jù)你輸入的值匾南，找一個離20最近的2的N次冪的值，比如說16離他最近蛔外，就取16為初始容量蛆楞。

• loadFactor 負(fù)載因子

  • 默認(rèn)值是0.75。負(fù)載因子表示一個散列表的空間的使用程度夹厌，有這樣一個公式：initailCapacity*loadFactor = HashMap 的容量豹爹。
  • 所以負(fù)載因子越大則散列表的裝填程度越高，也就是能容納更多的元素矛纹，元素多了臂聋，鏈表大了，所以此時索引效率就會降低或南。反之孩等，負(fù)載因子越小則鏈表中的數(shù)據(jù)量就越稀疏，此時會對空間造成爛費(fèi)采够，但是此時索引效率高肄方。

確定哈希桶數(shù)組索引位置

• 主要是hash算法（均勻的）。
• jdk1.8 版本將這個過程的一部分融入到了 put() 過程中蹬癌。
• 首先我們知道 HashMap 是根據(jù) Key 的 hashCode來確定鍵值對在哈希桶數(shù)組的位置的权她。得到了hash值之后又該怎么做呢虹茶？首先想到的是取模，當(dāng)然隅要，肯定不是這樣的蝴罪，不然人人都能當(dāng)大牛了_{_}。其實(shí)是通過巧妙的位運(yùn)算來操作的（更高效）步清。
  • 下面就是 HashMap 中的 hash() 方法的實(shí)現(xiàn)要门。

//經(jīng)過兩步操作最后得到的才是我們用來確定位置的hash值
    static final int hash(Object key) {
        int h;
        // h = key.hashCode() 為第一步 取hashCode值
        // h ^ (h >>> 16)  為第二步 高位參與運(yùn)算
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
//確定hash值之后的操作就是確定在哈希桶中的位置了
//下面是 put() 方法中的一行代碼，n為哈希桶數(shù)組長度廓啊，hash為前一步確定的hash值
    p = tab[i = (n - 1) & hash]

• 可以看到暂衡，哈希桶數(shù)組索引位置是由位運(yùn)算來操作。下面是一個例子
  • 圖片來自美團(tuán)技術(shù)團(tuán)隊在知乎上的文章：Java 8系列之重新認(rèn)識HashMap

HashMap確定哈希桶數(shù)組索引位置的位移運(yùn)算舉例

• 仔細(xì)想一下崖瞭，數(shù)組長度減一得到的值的二進(jìn)制數(shù)狂巢，前面大部分都是0，所以书聚，可以說唧领，Hash算法最終得到的index結(jié)果，完全取決于Key的Hashcode值的最后幾位雌续。
• 那么這樣的過程是不是會出現(xiàn)不同的key得到同一個索引位置的情況呢斩个？
  • 當(dāng)計算的hash值出現(xiàn)了重復(fù)，就出現(xiàn)了地址沖突了（嚴(yán)格來收叫做碰撞）
  • 這時候就需要解決沖突了驯杜。詳情請見后面小標(biāo)題——解決沖突受啥。

put 插入過程

• 具體的流程就如下圖所示（在put過程中是解決了地址沖突的），get操作自己下去看鸽心，也是類似的滚局。
  • 下面的圖片來自美團(tuán)技術(shù)團(tuán)隊在知乎上的文章：Java 8系列之重新認(rèn)識HashMap

HashMap的put過程圖解

    public V put(K key, V value) {
        //這里調(diào)用了hash()方法，拿到了Key的hash值
        return putVal(hash(key), key, value, false, true);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //第一部分：哈希桶數(shù)組是否為空顽频，為空則使用默認(rèn)值創(chuàng)建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //第二部分：拿到index對應(yīng)的數(shù)組元素（節(jié)點(diǎn)）藤肢，判斷是否為空，為空則直接插入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //第三部分：節(jié)點(diǎn)存在糯景，發(fā)生哈希碰撞嘁圈，解決哈希碰撞
        else {
            Node<K,V> e; K k;
            //第三部分第一小節(jié)：Key存在，則直接覆蓋Value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //第三部分第二小節(jié)：節(jié)點(diǎn)所處的數(shù)據(jù)結(jié)構(gòu)是否為紅黑樹
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //第三部分第三小節(jié)：節(jié)點(diǎn)所處的數(shù)據(jù)結(jié)構(gòu)為鏈表蟀淮，遍歷鏈表節(jié)點(diǎn)
            else {
                for (int binCount = 0; ; ++binCount) {
                    //第三小節(jié)第一段：是否存在節(jié)點(diǎn)最住，不存在則創(chuàng)建
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //這個時候計數(shù)閾值大于了8則轉(zhuǎn)換為紅黑樹進(jìn)行操作
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //第三小節(jié)第二段：Key存在則直接覆蓋
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //第三小節(jié)第三段：
                    p = e;
                }
            }
            //第三部分第四小節(jié)：
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //第四部分：鏈表中的元素數(shù)量大于閾值，則擴(kuò)容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

resize 擴(kuò)容機(jī)制

• 不斷的向 HashMap 中添加元素怠惶，當(dāng)哈希桶數(shù)組的元素數(shù)目超過閾值涨缚，就要擴(kuò)容了。
  • 擴(kuò)容后的 HashMap 容量是之前容量的兩倍甚疟。
  • 擴(kuò)容操作十分耗時仗岖，所以在使用的時候要適當(dāng)?shù)慕o定容量值。
• 對數(shù)組進(jìn)行擴(kuò)容览妖，數(shù)組大小是不能改變的轧拄，所以這里使用了構(gòu)建新數(shù)組，然后轉(zhuǎn)移舊數(shù)組元素的方式來實(shí)現(xiàn)的讽膏。
  • 這一點(diǎn)在 ArrayList 中也有體現(xiàn)檩电。
• 所以，具體的流程如下：
  • 排除異常情況
  • 擴(kuò)容2倍新建數(shù)組
  • 轉(zhuǎn)移數(shù)據(jù)
  • 新數(shù)組引用到table上
  • 重新設(shè)置閾值

 final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        //第一部分：排除異常情況府树，擴(kuò)容
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        //第二部分：設(shè)置閾值
        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;
        //第三部分：舊數(shù)據(jù)保存在新數(shù)組里面
        if (oldTab != null) {
            //遍歷舊數(shù)組
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                     //只有一個節(jié)點(diǎn)俐末，通過索引位置直接映射
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果是紅黑樹，需要進(jìn)行樹拆分然后映射
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //如果是多個節(jié)點(diǎn)的鏈表奄侠，將原鏈表拆分為兩個鏈表
                    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;
                            }
                            //原索引 + oldCap
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                         //鏈表1存于原索引
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //鏈表2存于原索引加上原h(huán)ash桶長度的偏移量
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

• 經(jīng)上分析之后卓箫，可以得出：在擴(kuò)容后，原數(shù)組元素被分為了兩部分：
  • 索引位置要么不變
  • 要么動舊容量個位置
• 鏈表轉(zhuǎn)移數(shù)據(jù)的部分垄潮，分為了兩個鏈表烹卒，通過下面的語句來判斷

if ((e.hash & oldCap) == 0) {···}

• 擴(kuò)容后，若hash值新增參與運(yùn)算的位=0弯洗，那么元素在擴(kuò)容后的位置=原始位置
• 擴(kuò)容后旅急，若hash值新增參與運(yùn)算的位=1，那么元素在擴(kuò)容后的位置=原始位置+擴(kuò)容后的舊位置牡整。
• hash值新增參與運(yùn)算的位是什么呢藐吮？我們把hash值轉(zhuǎn)變成二進(jìn)制數(shù)字，新增參與運(yùn)算的位就是倒數(shù)第五位逃贝。
• 這里面有一個非常好的設(shè)計理念谣辞，擴(kuò)容后長度為原h(huán)ash表的2倍，于是把hash表分為兩半沐扳，分為低位和高位潦闲，如果能把原鏈表的鍵值對， 一半放在低位迫皱，一半放在高位歉闰，而且是通過e.hash & oldCap == 0來判斷，這個判斷有什么優(yōu)點(diǎn)呢卓起？

舉個例子：n = 16和敬，二進(jìn)制為10000，第5位為1戏阅，e.hash & oldCap 是否等于0就取決于e.hash第5 位是0還是1昼弟，這就相當(dāng)于有50%的概率放在新hash表低位，50%的概率放在新hash表高位奕筐。

線程安全性

• 不安全舱痘！
• 所以才會有了 ConcurrentHashMap变骡，它的功能和 HashMap 是一樣的，但它支持并發(fā)訪問芭逝。

解決沖突

• java 中 HashMap 采用的是 鏈地址法 來解決沖突的塌碌。
• 哈希碰撞： 在插入數(shù)據(jù)時，通過hash算法計算出來的index這個位置旬盯，在哈希桶數(shù)組上已經(jīng)存在元素台妆，則會出現(xiàn)哈希沖突（哈希碰撞更官方）。
• 發(fā)生沖突之后會解決沖突：將數(shù)據(jù)掛在初始化位置（有點(diǎn)問題）的鏈表后（尾插法）胖翰，然后當(dāng)某個結(jié)點(diǎn)出現(xiàn)過多的鏈表結(jié)點(diǎn)之后接剩，就會轉(zhuǎn)換為紅黑樹以提高效率

學(xué)完 HashMap 原理之后，我們應(yīng)該解決的問題

HashMap的底層數(shù)據(jù)結(jié)構(gòu)是什么萨咳？

jdk1.7 及之前的版本是：數(shù)組 + 鏈表
jdk1.8 版本是：數(shù)組 + 鏈表 + 紅黑樹

為什么是紅黑樹呢懊缺？

紅黑樹是一個自平衡的二叉查找樹，也就是說紅黑樹的查找效率是非常的高培他，查找效率會從鏈表的o(n)降低為o(logn)桐汤。

為什么不一下子把整個鏈表變?yōu)榧t黑樹呢？

1. 構(gòu)造紅黑樹要比構(gòu)造鏈表復(fù)雜靶壮，在鏈表的節(jié)點(diǎn)不多的時候怔毛，從整體的性能看來， 數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)可能不一定比數(shù)組+鏈表的結(jié)構(gòu)性能高腾降。

2. HashMap 頻繁的擴(kuò)容拣度，會造成底部紅黑樹不斷的進(jìn)行拆分和重組，這是非常耗時的螃壤。因此抗果，也就是鏈表長度比較長的時候轉(zhuǎn)變成紅黑樹才會顯著提高效率。

HashMap中增刪改查操作的底部實(shí)現(xiàn)原理是什么奸晴？

太多了冤馏，自己想想put過程、數(shù)據(jù)結(jié)構(gòu)等

為什么HashMap容量一定要為16或者2的冪呢寄啼？

HashMap 采用這種非常規(guī)設(shè)計逮光，主要是為了在取模和擴(kuò)容時做優(yōu)化，同時為了減少hash碰撞墩划，HashMap 定位哈希桶索引位置時涕刚，也加入了高位參與運(yùn)算的過程。

長度16或者其他2的冪乙帮，Length-1的值是所有二進(jìn)制位全為1杜漠，這種情況下，index的結(jié)果等同于HashCode后幾位的值。只要輸入的HashCode本身分布均勻驾茴，Hash算法的結(jié)果就是均勻的盼樟。

如果不為16或者2的冪，那么锈至，經(jīng)過hash算法之后晨缴，有些index結(jié)果出現(xiàn)的概率會更大，而有些index則永遠(yuǎn)步會出現(xiàn)裹赴。即不符合hash算法的j均勻分布的原則。

為什么負(fù)載因子默認(rèn)值會是0.75呢诀浪？

在HashMap的源碼中有這樣一段注解：
     * Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million
     *
大概意思就是：在理想情況下棋返，使用隨機(jī)哈希嗎，節(jié)點(diǎn)出現(xiàn)的頻率在hash桶中遵循泊松分布雷猪，同時給出了桶中元素的個數(shù)和概率的對照表睛竣。

從上表可以看出當(dāng)桶中元素到達(dá)8個的時候，概率已經(jīng)變得非常小求摇，也就是說用0.75作為負(fù)載因子射沟，每個碰撞位置的鏈表長度超過8個是幾乎不可能的。
hash容器指定初始容量盡量為2的冪次方与境。
HashMap負(fù)載因子為0.75是空間和時間成本的一種折中验夯。

HashMap是如何實(shí)現(xiàn)擴(kuò)容的？

結(jié)合resize擴(kuò)容過程思考摔刁，注意轉(zhuǎn)移數(shù)據(jù)的時候是兩個鏈表（hash表高低位）挥转。

HashMap是如何解決hash沖突的？

鏈地址法９睬０笠ァ！
哈希桶數(shù)組元素發(fā)生哈希碰撞拗引，產(chǎn)生鏈表借宵，鏈表長度不小于8（數(shù)組大小不小于64），轉(zhuǎn)換為鏈表矾削。

HashMap為什么是非線程安全的壤玫？

• HashMap不是線程安全的，在多線程并發(fā)的環(huán)境下哼凯，可能會產(chǎn)生死鎖等問題垦细。
• 補(bǔ)充一點(diǎn) Hashtable 是線程安全的。還有并發(fā)的 HashMap ：ConcurrentHashMap（java5引入的）挡逼。

因?yàn)樵创a里面方法全部都是非線程安全的呀括改。
可以將 HashMap 轉(zhuǎn)變?yōu)榫€程安全的：

HashMap<Integer, String> hashMap1 = (HashMap<Integer, String>) Collections.synchronizedMap(hashMap);

HashMap 與 Hashtable 的區(qū)別？

• Hashtable 是java的遺留類，java4的時候被重寫了嘱能，加入了集合類吝梅。

1. HashMap線程不安全，是非synchronized的惹骂，Hashtable是線程安全的苏携。

2. HashMap可以接受null(HashMap可以接受為null的鍵值(key)和值(value))，而Hashtable則不行对粪。

3. 是HashMap的迭代器(Iterator)是fail-fast迭代器右冻，而Hashtable的enumerator迭代器不是fail-fast的。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素）著拭，將會拋出ConcurrentModificationException纱扭，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常。但這并不是一個一定發(fā)生的行為儡遮，要看JVM乳蛾。這條同樣也是Enumeration和Iterator的區(qū)別。

4. 由于Hashtable是線程安全的也是synchronized鄙币，所以在單線程環(huán)境下它比HashMap要慢肃叶。如果你不需要同步，只需要單一線程十嘿，那么使用HashMap性能要好過Hashtable因惭。

5. HashMap不能保證隨著時間的推移Map中的元素次序是不變的。

6. 繼承的父類不同绩衷、作者不同筛欢，產(chǎn)生時間不同。HashMap是繼承自AbstractMap類唇聘，而HashTable是繼承自Dictionary類版姑。不過它們都實(shí)現(xiàn)了同時實(shí)現(xiàn)了Map、Cloneable（可復(fù)制）迟郎、Serializable（可序列化）這三個接口

7. 初始容量大小和每次擴(kuò)充容量大小的不同剥险。Hashtable默認(rèn)的初始大小為11，之后每次擴(kuò)充宪肖，容量變?yōu)樵瓉淼?n+1表制。HashMap默認(rèn)的初始化大小為16。之后每次擴(kuò)充控乾，容量變?yōu)樵瓉淼?倍么介。

8. 計算hash值的方法不同。為了得到元素的位置蜕衡，首先需要根據(jù)元素的Key計算出一個hash值壤短，然后再用這個hash值來計算得到最終的位置。Hashtable直接使用對象的hashCode。然后再使用取余來獲得最終的位置久脯，比較耗時纳胧。HashMap是通過位運(yùn)算來進(jìn)行操作的，效率高帘撰。
    下面是 Hashtable 的確定索引方法：
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;

該怎么設(shè)置HashMap的閾值和負(fù)載因子呢跑慕？

個人認(rèn)為，不需要設(shè)置摧找。只需要設(shè)置好數(shù)組容量大小就好了核行。