如果說(shuō)Java的HashMap是數(shù)組+鏈表酒奶，那么JDK 8之后就是數(shù)組+鏈表+紅黑樹(shù)組成了HashMap。

在之前談過(guò)奶赔，如果hash算法不好讥蟆，會(huì)使得hash表蛻化為順序查找，即使負(fù)載因子和hash算法優(yōu)化再多纺阔，也無(wú)法避免出現(xiàn)鏈表過(guò)長(zhǎng)的情景（這個(gè)概論雖然很低）瘸彤，于是在JDK1.8中，對(duì)HashMap做了優(yōu)化笛钝，引入紅黑樹(shù)质况。具體原理就是當(dāng)hash表中每個(gè)桶附帶的鏈表長(zhǎng)度默認(rèn)超過(guò)8時(shí)，鏈表就轉(zhuǎn)換為紅黑樹(shù)結(jié)構(gòu)玻靡，提高HashMap的性能结榄，因?yàn)榧t黑樹(shù)的增刪改是O(logn)，而不是O(n)囤捻。

紅黑樹(shù)的具體原理和實(shí)現(xiàn)以后再總結(jié)臼朗。

主要看put方法實(shí)現(xiàn)

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

封裝了一個(gè)final方法，里面用到一個(gè)常量蝎土，具體用處看源碼：

static final int TREEIFY_THRESHOLD = 8;

下面是具體源代碼注釋：

final 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) // 首先判斷hash表是否是空的视哑，如果空，則resize擴(kuò)容
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null) // 通過(guò)key計(jì)算得到hash表下標(biāo)誊涯，如果下標(biāo)處為null挡毅，就新建鏈表頭結(jié)點(diǎn)，在方法最后插入即可
            tab[i] = newNode(hash, key, value, null);
        else { // 如果下標(biāo)處已經(jīng)存在節(jié)點(diǎn)暴构，則進(jìn)入到這里
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) // 先看hash表該處的頭結(jié)點(diǎn)是否和key一樣（hashcode和equals比較）跪呈，一樣就更新
                e = p;
            else if (p instanceof TreeNode) // hash表頭結(jié)點(diǎn)和key不一樣段磨，則判斷節(jié)點(diǎn)是不是紅黑樹(shù)，是紅黑樹(shù)就按照紅黑樹(shù)處理
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { // 如果不是紅黑樹(shù)耗绿，則按照之前的HashMap原理處理
                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 (原jdk注釋) 顯然當(dāng)鏈表長(zhǎng)度大于等于7的時(shí)候苹支，也就是說(shuō)大于8的話，就轉(zhuǎn)化為紅黑樹(shù)結(jié)構(gòu)误阻，針對(duì)紅黑樹(shù)進(jìn)行插入（logn復(fù)雜度）
                            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;
        if (++size > threshold) // 如果超過(guò)容量债蜜，即擴(kuò)容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

resize是新的擴(kuò)容方法，之前談過(guò)堕绩，擴(kuò)容原理是使用新的（2倍舊長(zhǎng)度）的數(shù)組代替策幼，把舊數(shù)組的內(nèi)容放到新數(shù)組，需要重新計(jì)算hash和hash表的位置奴紧，非常耗時(shí)特姐，但是自從 JDK 1.8 對(duì)HashMap引入了紅黑樹(shù)，它和之前的擴(kuò)容方法相比有了改進(jìn)黍氮。

擴(kuò)容方法的改進(jìn)

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 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) // 如果長(zhǎng)度沒(méi)有超過(guò)最大值唐含，則擴(kuò)容為2倍的關(guān)系
                newThr = oldThr << 1; // double threshold
        }
        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;
        if (oldTab != null) { // 進(jìn)行新舊元素的轉(zhuǎn)移過(guò)程
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode) 
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order（原注釋） 如果不是紅黑樹(shù)的情況這里改進(jìn)了，沒(méi)有rehash的過(guò)程沫浆，如下分別記錄鏈表的頭尾
                        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;
    }

因?yàn)橛羞@樣一個(gè)特點(diǎn)：比如hash表的長(zhǎng)度是16捷枯，那么15對(duì)應(yīng)二進(jìn)制是：

0000 0000， 0000 0000专执， 0000 0000淮捆， 0000 1111 = 15

擴(kuò)容之前有兩個(gè)key，分別是k1和k2：

k1的hash：

0000 0000本股， 0000 0000攀痊， 0000 0000， 0000 1111 = 15

k2的hash：

0000 0000拄显， 0000 0000苟径， 0000 0000， 0001 1111 = 15

hash值和15模得到：

k1：0000 0000躬审， 0000 0000棘街， 0000 0000， 0000 1111 = 15

k2：0000 0000承边， 0000 0000遭殉， 0000 0000， 0000 1111 = 15

擴(kuò)容之后表長(zhǎng)對(duì)應(yīng)為32炒刁，則31二進(jìn)制：

0000 0000恩沽， 0000 0000， 0000 0000翔始， 0001 1111 = 31

重新hash之后得到：

k1：0000 0000罗心， 0000 0000， 0000 0000城瞎， 0000 1111 = 15

k2：0000 0000渤闷， 0000 0000， 0000 0000脖镀， 0001 1111 = 31 = 15 + 16

觀察發(fā)現(xiàn)：如果擴(kuò)容后新增的位是0飒箭，那么rehash索引不變，否則才會(huì)改變蜒灰，并且變?yōu)樵瓉?lái)的索引+舊hash表的長(zhǎng)度弦蹂，故我們只需看原h(huán)ash表長(zhǎng)新增的bit是1還是0，如果是0强窖，索引不變凸椿，如果是1，索引變成原索引+舊表長(zhǎng)翅溺，根本不用像JDK 7 那樣rehash脑漫，省去了重新計(jì)算hash值的時(shí)間，而且新增的bit是0還是1可以認(rèn)為是隨機(jī)的咙崎，因此resize的過(guò)程优幸，還能均勻的把之前的沖突節(jié)點(diǎn)分散。

故JDK 8對(duì)HashMap的優(yōu)化是非常到位的褪猛。

如下是之前整理的舊hash的實(shí)現(xiàn)機(jī)制和原理网杆，并和jdk古老的Hashtable做了比較。

整理jdk 1.8之前的HashMap實(shí)現(xiàn)：

• Java集合概述
• HashMap介紹
• HashMap源碼學(xué)習(xí)
• 關(guān)于HashMap的幾個(gè)經(jīng)典問(wèn)題
• Hashtable介紹和源碼學(xué)習(xí)
• HashMap 和 Hashtable比較

先上圖

集合

Set和List接口是Collection接口的子接口伊滋，分別代表無(wú)序集合和有序集合碳却，Queue是Java提供的隊(duì)列實(shí)現(xiàn)。

Map

Map用于保存具有key-value映射關(guān)系的數(shù)據(jù)新啼。

Java 中有四種常見(jiàn)的Map實(shí)現(xiàn)——HashMap追城，TreeMap，Hashtable和LinkedHashMap燥撞。

• HashMap就是一張hash表座柱，鍵和值都沒(méi)有排序。
• TreeMap以紅黑樹(shù)結(jié)構(gòu)為基礎(chǔ)物舒，鍵值可以設(shè)置按某種順序排列色洞。
• LinkedHashMap保存了插入時(shí)的順序。
• Hashtable是同步的(而HashMap是不同步的)冠胯。所以如果在線程安全的環(huán)境下應(yīng)該多使用HashMap火诸，而不是Hashtable，因?yàn)镠ashtable對(duì)同步有額外的開(kāi)銷荠察，不過(guò)JDK 5之后的版本可以使用conncurrentHashMap代替Hashtable置蜀。

本文重點(diǎn)總結(jié)HashMap奈搜，HashMap是基于哈希表實(shí)現(xiàn)的，每一個(gè)元素是一個(gè)key-value對(duì)盯荤，其內(nèi)部通過(guò)單鏈表解決沖突問(wèn)題馋吗，容量不足（超過(guò)了閥值）時(shí)，同樣會(huì)自動(dòng)增長(zhǎng)秋秤。

HashMap是非線程安全的宏粤，只用于單線程環(huán)境下，多線程環(huán)境下可以采用concurrent并發(fā)包下的concurrentHashMap灼卢。

HashMap 實(shí)現(xiàn)了Serializable接口绍哎，因此它支持序列化。

HashMap還實(shí)現(xiàn)了Cloneable接口鞋真，故能被克隆崇堰。

關(guān)于HashMap的用法，這里就不再贅述了灿巧，只說(shuō)原理和一些注意點(diǎn)赶袄。

HashMap的存儲(chǔ)結(jié)構(gòu)

HashMap的存儲(chǔ)結(jié)構(gòu)

紫色部分即代表哈希表本身（其實(shí)是一個(gè)數(shù)組），數(shù)組的每個(gè)元素都是一個(gè)單鏈表的頭節(jié)點(diǎn)抠藕，鏈表是用來(lái)解決hash地址沖突的饿肺，如果不同的key映射到了數(shù)組的同一位置處，就將其放入單鏈表中保存盾似。

HashMap有四個(gè)構(gòu)造方法敬辣，方法中有兩個(gè)很重要的參數(shù)：初始容量和加載因子

這兩個(gè)參數(shù)是影響HashMap性能的重要參數(shù)，其中容量表示哈希表中槽的數(shù)量（即哈希數(shù)組的長(zhǎng)度）零院，初始容量是創(chuàng)建哈希表時(shí)的容量（默認(rèn)為16）溉跃，加載因子是哈希表當(dāng)前key的數(shù)量和容量的比值，當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時(shí)告抄，則要對(duì)該哈希表提前進(jìn)行 resize 操作（即擴(kuò)容）撰茎。如果加載因子越大，對(duì)空間的利用更充分打洼，但是查找效率會(huì)降低（鏈表長(zhǎng)度會(huì)越來(lái)越長(zhǎng)）龄糊；如果加載因子太小，那么表中的數(shù)據(jù)將過(guò)于稀疏（很多空間還沒(méi)用募疮，就開(kāi)始擴(kuò)容了）炫惩，嚴(yán)重浪費(fèi)。

JDK開(kāi)發(fā)者規(guī)定的默認(rèn)加載因子為0.75阿浓，因?yàn)檫@是一個(gè)比較理想的值他嚷。另外，無(wú)論指定初始容量為多少，構(gòu)造方法都會(huì)將實(shí)際容量設(shè)為不小于指定容量的2的冪次方筋蓖，且最大值不能超過(guò)2的30次方卸耘。

重點(diǎn)分析HashMap中用的最多的兩個(gè)方法put和get的源碼

// 獲取key對(duì)應(yīng)的value
public V get(Object key) {
    if (key == null)
        return getForNullKey();
    // 獲取key的hash值
    int hash = hash(key.hashCode());
    // 在“該hash值對(duì)應(yīng)的鏈表”上查找“鍵值等于key”的元素
    for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        // 判斷key是否相同
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    // 沒(méi)找到則返回null
    return null;
}

// 獲取“key為null”的元素的值，HashMap將“key為null”的元素存儲(chǔ)在table[0]位置扭勉，但不一定是該鏈表的第一個(gè)位置鹊奖！
private V getForNullKey() {
    for (Entry<K, V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

首先苛聘，如果key為null涂炎，則直接從哈希表的第一個(gè)位置table[0]對(duì)應(yīng)的鏈表上查找。記住设哗，key為null的鍵值對(duì)永遠(yuǎn)都放在以table[0]為頭結(jié)點(diǎn)的鏈表中唱捣，當(dāng)然不一定是存放在頭結(jié)點(diǎn)table[0]中。如果key不為null网梢，則先求的key的hash值震缭，根據(jù)hash值找到在table中的索引，在該索引對(duì)應(yīng)的單鏈表中查找是否有鍵值對(duì)的key與目標(biāo)key相等战虏，有就返回對(duì)應(yīng)的value拣宰，沒(méi)有則返回null。

// 將“key-value”添加到HashMap中
public V put(K key, V value) {
    // 若“key為null”烦感，則將該鍵值對(duì)添加到table[0]中巡社。
    if (key == null)
        return putForNullKey(value);
    // 若“key不為null”，則計(jì)算該key的哈希值手趣，然后將其添加到該哈希值對(duì)應(yīng)的鏈表中晌该。
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 若“該key”對(duì)應(yīng)的鍵值對(duì)已經(jīng)存在，則用新的value取代舊的value绿渣。然后退出朝群！
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    // 若“該key”對(duì)應(yīng)的鍵值對(duì)不存在，則將“key-value”添加到table中
    modCount++;
    // 將key-value添加到table[i]處
    addEntry(hash, key, value, i);
    return null;
}

如果key為null中符，則將其添加到table[0]對(duì)應(yīng)的鏈表中姜胖，如果key不為null，則同樣先求出key的hash值淀散，根據(jù)hash值得出在table中的索引右莱，而后遍歷對(duì)應(yīng)的單鏈表，如果單鏈表中存在與目標(biāo)key相等的鍵值對(duì)吧凉，則將新的value覆蓋舊的value隧出，且將舊的value返回，如果找不到與目標(biāo)key相等的鍵值對(duì)阀捅，或者該單鏈表為空胀瞪，則將該鍵值對(duì)插入到單鏈表的頭結(jié)點(diǎn)位置（每次新插入的節(jié)點(diǎn)都是放在頭結(jié)點(diǎn)的位置），該操作是有addEntry方法實(shí)現(xiàn)的，它的源碼如下：

// 新增Entry凄诞。將“key-value”插入指定位置圆雁，bucketIndex是位置索引。
void addEntry(int hash, K key, V value, int bucketIndex) {
    // 保存“bucketIndex”位置的值到“e”中
    Entry<K, V> e = table[bucketIndex];
    // 設(shè)置“bucketIndex”位置的元素為“新Entry”帆谍，
    // 設(shè)置“e”為“新Entry的下一個(gè)節(jié)點(diǎn)”
    table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
    // 若HashMap的實(shí)際大小 不小于 “閾值”伪朽，則調(diào)整HashMap的大小
    if (size++ >= threshold)
        resize(2 * table.length);
}

注意這里倒數(shù)第三行的構(gòu)造方法，將key-value鍵值對(duì)賦給table[bucketIndex]汛蝙，并將其next指向元素e烈涮，這便將key-value放到了頭結(jié)點(diǎn)中，并將之前的頭結(jié)點(diǎn)接在了它的后面窖剑。該方法也說(shuō)明坚洽，每次put鍵值對(duì)的時(shí)候，總是將新的該鍵值對(duì)放在table[bucketIndex]處（即頭結(jié)點(diǎn)處）西土。兩外注意最后兩行代碼讶舰，每次加入鍵值對(duì)時(shí)，都要判斷當(dāng)前已用的槽的數(shù)目是否大于等于閥值（容量*加載因子）需了，如果大于等于跳昼，則進(jìn)行擴(kuò)容，將容量擴(kuò)為原來(lái)容量的2倍肋乍。

重點(diǎn)來(lái)分析下求hash值和索引值的方法鹅颊，這兩個(gè)方法便是HashMap設(shè)計(jì)的最為核心的部分，二者結(jié)合能保證哈希表中的元素盡可能均勻地散列住拭。

由hash值找到對(duì)應(yīng)索引的方法如下

static int indexFor(int h, int length) {
    return h & (length-1);
}

因?yàn)槿萘砍跏歼€是設(shè)定都會(huì)轉(zhuǎn)化為2的冪次挪略。故可以使用高效的位與運(yùn)算替代模運(yùn)算。下面會(huì)解釋原因滔岳。

計(jì)算hash值的方法如下

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

JDK 的 HashMap 使用了一個(gè) hash 方法對(duì)hash值使用位的操作杠娱，使hash值的計(jì)算效率很高。為什么這樣做谱煤？主要是因?yàn)槿绻苯邮褂胔ashcode值摊求，那么這是一個(gè)int值（8個(gè)16進(jìn)制數(shù)，共32位）刘离，int值的范圍正負(fù)21億多室叉，但是hash表沒(méi)有那么長(zhǎng)，一般比如初始16硫惕，自然散列地址需要對(duì)hash表長(zhǎng)度取模運(yùn)算茧痕，得到的余數(shù)才是地址下標(biāo)。假設(shè)某個(gè)key的hashcode是0AAA0000恼除，hash數(shù)組長(zhǎng)默認(rèn)16踪旷，如果不經(jīng)過(guò)hash函數(shù)處理曼氛，該鍵值對(duì)會(huì)被存放在hash數(shù)組中下標(biāo)為0處，因?yàn)?AAA0000 & (16-1) = 0令野。過(guò)了一會(huì)兒又存儲(chǔ)另外一個(gè)鍵值對(duì)舀患，其key的hashcode是0BBB0000，得到數(shù)組下標(biāo)依然是0气破，這就說(shuō)明這是個(gè)實(shí)現(xiàn)得很差的hash算法聊浅，因?yàn)閔ashcode的1位全集中在前16位了，導(dǎo)致算出來(lái)的數(shù)組下標(biāo)一直是0现使。于是明明key相差很大的鍵值對(duì)低匙，卻存放在了同一個(gè)鏈表里，導(dǎo)致以后查詢起來(lái)比較慢（蛻化為了順序查找）朴下。故JDK的設(shè)計(jì)者使用hash函數(shù)的若干次的移位努咐、異或操作，把hashcode的“1位”變得“松散”殴胧，非常巧妙。

下面是幾個(gè)常見(jiàn)的面試題

說(shuō)下HashMap的 擴(kuò)容機(jī)制佩迟？

前面說(shuō)了团滥，hashmap的構(gòu)造器里指明了兩個(gè)對(duì)于理解HashMap比較重要的兩個(gè)參數(shù) int initialCapacity，float loadFactor报强，這兩個(gè)參數(shù)會(huì)影響HashMap效率灸姊，HashMap底層采用的散列數(shù)組實(shí)現(xiàn)，利用initialCapacity這個(gè)參數(shù)我們可以設(shè)置這個(gè)數(shù)組的大小秉溉，也就是散列桶的數(shù)量力惯，但是如果需要Map的數(shù)據(jù)過(guò)多，在不斷的add之后召嘶，這些桶可能都會(huì)被占滿父晶，這是有兩種策略，一種是不改變Capacity弄跌，因?yàn)榧词雇罢紳M了甲喝，我們還是可以利用每個(gè)桶附帶的鏈表增加元素。但是這有個(gè)缺點(diǎn)铛只，此時(shí)HaspMap就退化成為了LinkedList埠胖，使get和put方法的時(shí)間開(kāi)銷上升，這是就要采用另一種方法：增加Hash桶的數(shù)量淳玩，這樣get和put的時(shí)間開(kāi)銷又回退到近于常數(shù)復(fù)雜度上直撤。Hashmap就是采用的該方法。

關(guān)于擴(kuò)容蜕着∧笔看HashMap的擴(kuò)容方法，resize方法，它的源碼如下：

// 重新調(diào)整HashMap的大小圈盔，newCapacity是調(diào)整后的單位
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    // 新建一個(gè)HashMap豹芯，將“舊HashMap”的全部元素添加到“新HashMap”中，
    // 然后驱敲，將“新HashMap”賦值給“舊HashMap”铁蹈。
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int) (newCapacity * loadFactor);
}

很明顯，是從新建了一個(gè)HashMap的底層數(shù)組众眨，長(zhǎng)度為原來(lái)的兩倍握牧，而后調(diào)用transfer方法，將舊HashMap的全部元素添加到新的HashMap中（要重新計(jì)算元素在新的數(shù)組中的索引位置）娩梨。

transfer方法的源碼如下：

// 將HashMap中的全部元素都添加到newTable中
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K, V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K, V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

很明顯沿腰，擴(kuò)容是一個(gè)相當(dāng)耗時(shí)的操作，因?yàn)樗枰匦掠?jì)算這些元素在新的數(shù)組中的位置并進(jìn)行復(fù)制處理狈定。因此颂龙，我們?cè)谟肏ashMap時(shí)，最好能提前預(yù)估下HashMap中元素的個(gè)數(shù)纽什，這樣有助于提高HashMap的性能措嵌。

HashMap什么時(shí)候需要增加容量呢？

因?yàn)樾蕟?wèn)題芦缰，JDK采用預(yù)處理法企巢，這時(shí)前面說(shuō)的loadFactor就派上了用場(chǎng)，當(dāng)size > initialCapacity * loadFactor让蕾，HashMap內(nèi)部resize方法就被調(diào)用浪规，使得重新擴(kuò)充hash桶的數(shù)量，在目前的實(shí)現(xiàn)中探孝，是增加一倍笋婿，這樣就保證當(dāng)你真正想put新的元素時(shí)效率不會(huì)明顯下降。所以一般情況下HashMap并不存在鍵值放滿的情況再姑。當(dāng)然并不排除極端情況萌抵，比如設(shè)置的JVM內(nèi)存用完了，或者這個(gè)HashMap的Capacity已經(jīng)達(dá)到了MAXIMUM_CAPACITY（目前的實(shí)現(xiàn)是2^30）元镀。

initialCapacity和loadFactor參數(shù)設(shè)什么樣的值好呢绍填？

initialCapacity的默認(rèn)值是16，有些人可能會(huì)想如果內(nèi)存足夠栖疑，是不是可以將initialCapacity設(shè)大一些讨永，即使用不了這么大，就可避免擴(kuò)容導(dǎo)致的效率的下降遇革，反正無(wú)論initialCapacity大小卿闹，我們使用的get和put方法都是常數(shù)復(fù)雜度的揭糕。這么說(shuō)沒(méi)什么不對(duì)，但是可能會(huì)忽略一點(diǎn)锻霎，實(shí)際的程序可能不僅僅使用get和put方法著角，也有可能使用迭代器，如initialCapacity容量較大旋恼，那么會(huì)使迭代器效率降低吏口。所以理想的情況還是在使用HashMap前估計(jì)一下數(shù)據(jù)量。

加載因子默認(rèn)值是0.75冰更，是JDK權(quán)衡時(shí)間和空間效率之后得到的一個(gè)相對(duì)優(yōu)良的數(shù)值产徊。如果這個(gè)值過(guò)大，雖然空間利用率是高了蜀细，但是對(duì)于HashMap中的一些方法的效率就下降了舟铜，包括get和put方法，會(huì)導(dǎo)致每個(gè)hash桶所附加的鏈表增長(zhǎng)奠衔，影響存取效率谆刨。如果比較小，除了導(dǎo)致空間利用率較低外沒(méi)有什么壞處涣觉，只要有的是內(nèi)存痴荐，畢竟現(xiàn)在大多數(shù)人把時(shí)間看的比空間重要。但是實(shí)際中還是很少有人會(huì)將這個(gè)值設(shè)置的低于0.5官册。

HashMap的key和value都能為null么？如果k能為null难捌，那么它是怎么樣查找值的膝宁？

如果key為null，則直接從哈希表的第一個(gè)位置table[0]對(duì)應(yīng)的鏈表上查找根吁。記住员淫，key為null的鍵值對(duì)永遠(yuǎn)都放在以table[0]為頭結(jié)點(diǎn)的鏈表中。

HashMap中put值的時(shí)候如果發(fā)生了沖突击敌，是怎么處理的介返？

JDK使用了鏈地址法，hash表的每個(gè)元素又分別鏈接著一個(gè)單鏈表纽哥，元素為頭結(jié)點(diǎn)猖腕，如果不同的key映射到了相同的下標(biāo)腕够，那么就使用頭插法，插入到該元素對(duì)應(yīng)的鏈表徘公。

HashMap的key是如何散列到hash表的？相比較Hashtable有什么改進(jìn)哮针？

我們一般對(duì)哈希表的散列很自然地會(huì)想到用hash值對(duì)length取模（即除留余數(shù)法）关面，Hashtable就是這樣實(shí)現(xiàn)的坦袍，這種方法基本能保證元素在哈希表中散列的比較均勻，但取模會(huì)用到除法運(yùn)算等太，效率很低捂齐，且Hashtable直接使用了hashcode值，沒(méi)有重新計(jì)算缩抡。

HashMap中則通過(guò) h&(length-1) 的方法來(lái)代替取模奠宜，其中h是key的hash值，同樣實(shí)現(xiàn)了均勻的散列缝其，但效率要高很多挎塌，這也是HashMap對(duì)Hashtable的一個(gè)改進(jìn)。

接下來(lái)内边，我們分析下為什么哈希表的容量一定要是2的整數(shù)次冪榴都。

首先，length為2的整數(shù)次冪的話漠其，h&(length-1) 在數(shù)學(xué)上就相當(dāng)于對(duì)length取模嘴高，這樣便保證了散列的均勻，同時(shí)也提升了效率和屎；

其次拴驮，length為2的整數(shù)次冪的話，則一定為偶數(shù)柴信，那么 length-1 一定為奇數(shù)套啤，奇數(shù)的二進(jìn)制的最后一位是1，這樣便保證了 h&(length-1) 的最后一位可能為0随常，也可能為1（這取決于h的值）潜沦，即與后的結(jié)果可能為偶數(shù)，也可能為奇數(shù)绪氛，這樣便可以保證散列的均勻唆鸡，而如果length為奇數(shù)的話，很明顯 length-1 為偶數(shù)枣察，它的最后一位是0争占，這樣 h&(length-1) 的最后一位肯定為0，即只能為偶數(shù)序目，這樣導(dǎo)致了任何hash值都只會(huì)被散列到數(shù)組的偶數(shù)下標(biāo)位置上臂痕，浪費(fèi)了一半的空間，因此length取2的整數(shù)次冪宛琅，是為了使不同hash值發(fā)生碰撞的概率較小刻蟹，這樣就能使元素在哈希表中均勻地散列。

作為對(duì)比嘿辟，再討論一下Hashtable

Hashtable同樣是基于哈希表實(shí)現(xiàn)的舆瘪，其實(shí)類似HashMap片效，只不過(guò)有些區(qū)別，Hashtable同樣每個(gè)元素是一個(gè)key-value對(duì)英古，其內(nèi)部也是通過(guò)單鏈表解決沖突問(wèn)題淀衣，容量不足（超過(guò)了閥值）時(shí)，同樣會(huì)自動(dòng)增長(zhǎng)召调。

Hashtable比較古老膨桥， 是JDK1.0就引入的類，而HashMap 是 1.2 引進(jìn)的 Map 的一個(gè)實(shí)現(xiàn)唠叛。

Hashtable是線程安全的只嚣，能用于多線程環(huán)境中。Hashtable同樣也實(shí)現(xiàn)了Serializable接口艺沼，支持序列化册舞，也實(shí)現(xiàn)了Cloneable接口，能被克隆障般。

Hashtable

Hashtable繼承于Dictionary類调鲸，實(shí)現(xiàn)了Map接口。Dictionary是聲明了操作"鍵值對(duì)"函數(shù)接口的抽象類挽荡。 有一點(diǎn)注意藐石，Hashtable除了線程安全之外（其實(shí)是直接在方法上增加了synchronized關(guān)鍵字，比較古老定拟，落后于微，低效的同步方式），還有就是它的key青自、value都不為null角雷。另外Hashtable 也有 初始容量 和 加載因子。

public Hashtable() {
    this(11, 0.75f);
}

默認(rèn)加載因子也是 0.75性穿，Hashtable在不指定容量的情況下的默認(rèn)容量為11，而HashMap為16雷滚，Hashtable不要求底層數(shù)組的容量一定要為2的整數(shù)次冪需曾，而HashMap則要求一定為2的整數(shù)次冪。因?yàn)镠ashtable是直接使用除留余數(shù)法定位地址祈远。且Hashtable計(jì)算hash值呆万，直接用key的hashCode()。

還要注意：前面說(shuō)了Hashtable中key和value都不允許為null车份，而HashMap中key和value都允許為null（key只能有一個(gè)為null谋减，而value則可以有多個(gè)為null）。但如在Hashtable中有類似put(null,null)的操作扫沼，編譯同樣可以通過(guò)出爹，因?yàn)閗ey和value都是Object類型庄吼，但運(yùn)行時(shí)會(huì)拋出NullPointerException異常，這是JDK的規(guī)范規(guī)定的严就。

最后針對(duì)擴(kuò)容：Hashtable擴(kuò)容時(shí)总寻，將容量變?yōu)樵瓉?lái)的2倍加1，而HashMap擴(kuò)容時(shí)梢为，將容量變?yōu)樵瓉?lái)的2倍渐行。

下面是幾個(gè)常見(jiàn)的筆試，面試題

Hashtable和HashMap的區(qū)別有哪些铸董？

HashMap和Hashtable都實(shí)現(xiàn)了Map接口祟印，但決定用哪一個(gè)之前先要弄清楚它們之間的分別。主要的區(qū)別有：線程安全性粟害，同步(synchronization)蕴忆，以及速度。

理解HashMap是Hashtable的輕量級(jí)實(shí)現(xiàn)（非線程安全的實(shí)現(xiàn)我磁，Hashtable是非輕量級(jí)孽文，線程安全的），都實(shí)現(xiàn)Map接口夺艰，主要區(qū)別在于：

1. 由于HashMap非線程安全芋哭，在只有一個(gè)線程訪問(wèn)的情況下，效率要高于Hashtable郁副。
2. HashMap允許將null作為一個(gè)entry的key或者value减牺，而Hashtable不允許。
3. HashMap把Hashtable的contains方法去掉了存谎，改成containsValue和containsKey拔疚。因?yàn)閏ontains方法容易讓人引起誤解。
4. Hashtable繼承自陳舊的Dictionary類既荚，而HashMap是Java1.2引進(jìn)的Map 的一個(gè)實(shí)現(xiàn)稚失。
5. Hashtable和HashMap擴(kuò)容的方法不一樣，Hashtable中hash數(shù)組默認(rèn)大小11恰聘，擴(kuò)容方式是 old*2+1句各。HashMap中hash數(shù)組的默認(rèn)大小是16，而且一定是2的指數(shù)晴叨，增加為原來(lái)的2倍凿宾，沒(méi)有加1。
6. 兩者通過(guò)hash值散列到hash表的算法不一樣兼蕊，HashTbale是古老的除留余數(shù)法初厚，直接使用hashcode，而后者是強(qiáng)制容量為2的冪孙技，重新根據(jù)hashcode計(jì)算hash值产禾，在使用hash 位與 （hash表長(zhǎng)度 – 1）排作，也等價(jià)取模，但更加高效下愈，取得的位置更加分散纽绍，偶數(shù)，奇數(shù)保證了都會(huì)分散到势似。前者就不能保證拌夏。
7. 另一個(gè)區(qū)別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的履因。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素）障簿，將會(huì)拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會(huì)拋出ConcurrentModificationException異常栅迄。但這并不是一個(gè)一定發(fā)生的行為站故，要看JVM。這條同樣也是Enumeration和Iterator的區(qū)別毅舆。

• fail-fast和iterator迭代器相關(guān)西篓。如果某個(gè)集合對(duì)象創(chuàng)建了Iterator或者ListIterator，然后其它的線程試圖“結(jié)構(gòu)上”更改集合對(duì)象憋活，將會(huì)拋出ConcurrentModificationException異常岂津。但其它線程可以通過(guò)set()方法更改集合對(duì)象是允許的，因?yàn)檫@并沒(méi)有從“結(jié)構(gòu)上”更改集合悦即。但是假如已經(jīng)從結(jié)構(gòu)上進(jìn)行了更改吮成，再調(diào)用set()方法，將會(huì)拋出IllegalArgumentException異常辜梳。
• 結(jié)構(gòu)上的更改指的是刪除或者插入一個(gè)元素粱甫，這樣會(huì)影響到map的結(jié)構(gòu)。
• 該條說(shuō)白了就是在使用迭代器的過(guò)程中有其他線程在結(jié)構(gòu)上修改了map作瞄，那么將拋出ConcurrentModificationException茶宵，這就是所謂fail-fast策略。

為什么HashMap是線程不安全的宗挥，實(shí)際會(huì)如何體現(xiàn)节预？

第一，如果多個(gè)線程同時(shí)使用put方法添加元素

假設(shè)正好存在兩個(gè)put的key發(fā)生了碰撞(hash值一樣)属韧，那么根據(jù)HashMap的實(shí)現(xiàn)，這兩個(gè)key會(huì)添加到數(shù)組的同一個(gè)位置蛤吓，這樣最終就會(huì)發(fā)生其中一個(gè)線程的put的數(shù)據(jù)被覆蓋宵喂。

第二，如果多個(gè)線程同時(shí)檢測(cè)到元素個(gè)數(shù)超過(guò)數(shù)組大小*loadFactor

這樣會(huì)發(fā)生多個(gè)線程同時(shí)對(duì)hash數(shù)組進(jìn)行擴(kuò)容会傲，都在重新計(jì)算元素位置以及復(fù)制數(shù)據(jù)锅棕，但是最終只有一個(gè)線程擴(kuò)容后的數(shù)組會(huì)賦給table拙泽，也就是說(shuō)其他線程的都會(huì)丟失，并且各自線程put的數(shù)據(jù)也丟失裸燎。且會(huì)引起死循環(huán)的錯(cuò)誤顾瞻。

具體細(xì)節(jié)上的原因，可以參考：不正當(dāng)使用HashMap導(dǎo)致cpu 100%的問(wèn)題追究

能否讓HashMap實(shí)現(xiàn)線程安全德绿，如何做荷荤？

1. 直接使用Hashtable，但是當(dāng)一個(gè)線程訪問(wèn)Hashtable的同步方法時(shí)移稳，其他線程如果也要訪問(wèn)同步方法蕴纳，會(huì)被阻塞住。舉個(gè)例子个粱，當(dāng)一個(gè)線程使用put方法時(shí)古毛，另一個(gè)線程不但不可以使用put方法，連get方法都不可以都许，效率很低稻薇，現(xiàn)在基本不會(huì)選擇它了。
2. HashMap可以通過(guò)下面的語(yǔ)句進(jìn)行同步：

Collections.synchronizeMap(hashMap);

3. 直接使用JDK 5 之后的 ConcurrentHashMap胶征，如果使用Java 5或以上的話塞椎，請(qǐng)使用ConcurrentHashMap。

Collections.synchronizeMap(hashMap);又是如何保證了HashMap線程安全弧烤？

直接分析源碼吧忱屑。

// synchronizedMap方法
public static <K, V> Map<K, V> synchronizedMap(Map<K, V> m) {
    return new SynchronizedMap<>(m);
}

// SynchronizedMap類
private static class SynchronizedMap<K, V>
        implements Map<K, V>, Serializable {
    private static final long serialVersionUID = 1978198479659022715L;

    private final Map<K, V> m;     // Backing Map
    final Object mutex;        // Object on which to synchronize

    SynchronizedMap(Map<K, V> m) {
        this.m = Objects.requireNonNull(m);
        mutex = this;
    }

    SynchronizedMap(Map<K, V> m, Object mutex) {
        this.m = m;
        this.mutex = mutex;
    }

    public int size() {
        synchronized (mutex) {
            return m.size();
        }
    }

    public boolean isEmpty() {
        synchronized (mutex) {
            return m.isEmpty();
        }
    }

    public boolean containsKey(Object key) {
        synchronized (mutex) {
            return m.containsKey(key);
        }
    }

    public boolean containsValue(Object value) {
        synchronized (mutex) {
            return m.containsValue(value);
        }
    }

    public V get(Object key) {
        synchronized (mutex) {
            return m.get(key);
        }
    }

    public V put(K key, V value) {
        synchronized (mutex) {
            return m.put(key, value);
        }
    }

    public V remove(Object key) {
        synchronized (mutex) {
            return m.remove(key);
        }
    }
    // 省略其他方法
}

從源碼中看出 synchronizedMap()方法返回一個(gè)SynchronizedMap類的對(duì)象，而在SynchronizedMap類中使用了synchronized來(lái)保證對(duì)Map的操作是線程安全的暇昂，故效率其實(shí)也不高莺戒。

為什么Hashtable的默認(rèn)大小和HashMap不一樣？

前面分析了急波，Hashtable 的擴(kuò)容方法是乘2再+1从铲，不是簡(jiǎn)單的乘2，故Hashtable保證了容量永遠(yuǎn)是奇數(shù)澄暮，結(jié)合之前分析HashMap的重算hash值的邏輯名段，就明白了，因?yàn)樵跀?shù)據(jù)分布在等差數(shù)據(jù)集合(如偶數(shù))上時(shí)泣懊，如果公差與桶容量有公約數(shù) n伸辟，則至少有(n-1)/n 數(shù)量的桶是利用不到的，故之前的HashMap會(huì)在取模（使用位與運(yùn)算代替）哈希前先做一次哈希運(yùn)算馍刮，調(diào)整hash值信夫。這里Hashtable比較古老，直接使用了除留余數(shù)法，那么就需要設(shè)置容量起碼不是偶數(shù)（除（近似）質(zhì)數(shù)求余的分散效果好）静稻。而JDK開(kāi)發(fā)者選了11警没。

JDK 8對(duì)HashMap有了什么改進(jìn)？說(shuō)說(shuō)你對(duì)紅黑樹(shù)的理解振湾？

參考更新的jdk 8對(duì)HashMap的的改進(jìn)部分整理杀迹，并且還能引申出高級(jí)數(shù)據(jù)結(jié)構(gòu)——紅黑樹(shù)，這又能引出很多問(wèn)題……學(xué)無(wú)止境把禾隆树酪！

臨時(shí)小結(jié)：感覺(jué)針對(duì)Java的HashMap和Hashtable面試，或者理解嵌言，到這里就可以了嗅回，具體就是多寫(xiě)代碼實(shí)踐。