這次主要是分析下HashMap的工作原理，為什么我會(huì)拿這個(gè)東西出來分析觅赊，原因很簡(jiǎn)單怔揩，以前我面試的時(shí)候捉邢，偶爾問起HashMap，99%的程序員都知道HashMap商膊，基本都會(huì)用Hashmap伏伐，這其中不僅僅包括剛畢業(yè)的大學(xué)生，也包括已經(jīng)工作5年晕拆，甚至是10年的程序員藐翎。HashMap涉及的知識(shí)遠(yuǎn)遠(yuǎn)不止put和get那么簡(jiǎn)單。本次的分析希望對(duì)于面試的人起碼對(duì)于面試官的問題有所應(yīng)付

** 一实幕、先來回憶下我的面試過程**

** 問：“你用過HashMap吝镣，你能跟我說說它嗎？”**

** 答：**“當(dāng)然用過昆庇，HashMap是一種<key,value>的存儲(chǔ)結(jié)構(gòu)末贾，能夠快速將key的數(shù)據(jù)put方式存儲(chǔ)起來，然后很快的通過get取出來”整吆，然后說“HashMap不是線程安全的拱撵，
HashTable是線程安全的，通過synchronized實(shí)現(xiàn)的表蝙。HashMap取值非乘┎猓快”等等。這個(gè)時(shí)候說明他已經(jīng)很熟練使用HashMap的工具了勇哗。

問：“你知道HashMap 在put和get的時(shí)候是怎么工作的嗎昼扛？”

答：“HashMap是通過key計(jì)算出Hash值，然后將這個(gè)Hash值映射到對(duì)象的引用上，get的時(shí)候先計(jì)算key的hash值抄谐，然后找到對(duì)象”渺鹦。這個(gè)時(shí)候已經(jīng)顯得不自信了。

問：“HashMap的key為什么一般用字符串比較多蛹含，能用其他對(duì)象毅厚，或者自定義的對(duì)象嗎？為什么浦箱？”

答：“這個(gè)沒研究過吸耿，一般習(xí)慣用String】峥”

問：“你剛才提到HashMap不是線程安全的咽安，你怎么理解線程安全。原理是什么蓬推？幾種方式避免線程安全的問題妆棒。”

答：“線程安全就是多個(gè)線程去訪問的時(shí)候沸伏，會(huì)對(duì)對(duì)象造成不是預(yù)期的結(jié)果糕珊，一般要加鎖才能線程安全∫阍悖”

其實(shí)红选，問了以上那些問題，我基本能判定這個(gè)程序員的基本功了姆另，一般技術(shù)中等喇肋，接下來的問題沒必要問了。

從我的個(gè)人角度來看蜕青，HashMap的面試問題能夠考察面試者的線程問題苟蹈、Java內(nèi)存模型問題、線程可見與不可變問題右核、Hash計(jì)算問題慧脱、鏈表結(jié)構(gòu)問題、二進(jìn)制的&贺喝、|菱鸥、<<、>>等問題躏鱼。所以一個(gè)HashMap就能考驗(yàn)一個(gè)人的技術(shù)功底了氮采。

二、概念分析

1染苛、HashMap的類圖結(jié)構(gòu)

　此處的類圖是根據(jù)JDK1.6版本畫出來的鹊漠。如下圖1:

202221148131465.png

　　圖(一)

2主到、HashMap存儲(chǔ)結(jié)構(gòu)

** **HashMap的使用那么簡(jiǎn)單，那么問題來了躯概，它是怎么存儲(chǔ)的登钥，他的存儲(chǔ)結(jié)構(gòu)是怎樣的，很多程序員都不知道娶靡，其實(shí)當(dāng)你put和get的時(shí)候牧牢，稍稍往前一步，你看到就是它的真面目姿锭。其實(shí)簡(jiǎn)單的說HashMap的存儲(chǔ)結(jié)構(gòu)是由數(shù)組和鏈表共同完成的塔鳍。如圖：

210003116887371.png

從上圖可以看出HashMap是Y軸方向是數(shù)組，X軸方向就是鏈表的存儲(chǔ)方式呻此。大家都知道數(shù)組的存儲(chǔ)方式在內(nèi)存的地址是連續(xù)的轮纫，大小固定，一旦分配不能被其他引用占用趾诗。它的特點(diǎn)是查詢快蜡感，時(shí)間復(fù)雜度是O(1)蹬蚁，插入和刪除的操作比較慢恃泪，時(shí)間復(fù)雜度是O(n)，鏈表的存儲(chǔ)方式是非連續(xù)的犀斋，大小不固定贝乎，特點(diǎn)與數(shù)組相反，插入和刪除快叽粹，查詢速度慢览效。HashMap可以說是一種折中的方案吧。

3虫几、HashMap基本原理

1锤灿、首先判斷Key是否為Null，如果為null辆脸，直接查找Enrty[0]但校，如果不是Null，先計(jì)算Key的HashCode啡氢，然后經(jīng)過二次Hash状囱。得到Hash值，這里的Hash特征值是一個(gè)int值倘是。

2亭枷、根據(jù)Hash值，要找到對(duì)應(yīng)的數(shù)組啊搀崭，所以對(duì)Entry[]的長度length求余叨粘，得到的就是Entry數(shù)組的index。

3、找到對(duì)應(yīng)的數(shù)組升敲，就是找到了所在的鏈表袍镀，然后按照鏈表的操作對(duì)Value進(jìn)行插入、刪除和查詢操作冻晤。

4苇羡、HashMap概念介紹

5笨篷、HashMap初始化

默認(rèn)情況下瞳秽，大多數(shù)人都調(diào)用new HashMap()來初始化的，我在這里分析new HashMap(int initialCapacity, float loadFactor)的構(gòu)造函數(shù)率翅，代碼如下：

public HashMap(int initialCapacity, float loadFactor) {
　　　　　// initialCapacity代表初始化HashMap的容量练俐，它的最大容量是MAXIMUM_CAPACITY = 1 << 30。
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

　　　　 // loadFactor代表它的負(fù)載因子冕臭，默認(rèn)是是DEFAULT_LOAD_FACTOR=0.75腺晾，用來計(jì)算threshold臨界值的。
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }

由上面的代碼可以看出辜贵，初始化的時(shí)候需要知道初始化的容量大小悯蝉，因?yàn)樵诤竺嬉ㄟ^按位與的Hash算法計(jì)算Entry數(shù)組的索引，那么要求Entry的數(shù)組長度是2的N次方托慨。

6鼻由、HashMap中的Hash計(jì)算和碰撞問題

HashMap的hash計(jì)算時(shí)先計(jì)算hashCode(),然后進(jìn)行二次hash。代碼如下：

// 計(jì)算二次Hash    
int hash = hash(key.hashCode());

// 通過Hash找數(shù)組索引
int i = indexFor(hash, table.length);

先不忙著學(xué)習(xí)HashMap的Hash算法榴芳，先來看看JDK的String的Hash算法嗡靡。代碼如下：

 /**
     * Returns a hash code for this string. The hash code for a
     * <code>String</code> object is computed as
     * <blockquote><pre>
     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     * </pre></blockquote>
     * using <code>int</code> arithmetic, where <code>s[i]</code> is the
     * <i>i</i>th character of the string, <code>n</code> is the length of
     * the string, and <code>^</code> indicates exponentiation.
     * (The hash value of the empty string is zero.)
     *
     * @return  a hash code value for this object.
     */
    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

從JDK的API可以看出，它的算法等式就是s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]窟感，其中s[i]就是索引為i的字符讨彼，n為字符串的長度。這里為什么有一個(gè)固定常量31呢柿祈，關(guān)于這個(gè)31的討論很多哈误，基本就是優(yōu)化的數(shù)字哩至，主要參考Joshua Bloch's Effective Java的引用如下：

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

大體意思是說選擇31是因?yàn)樗且粋€(gè)奇素?cái)?shù)，如果它做乘法溢出的時(shí)候蜜自，信息會(huì)丟失菩貌，而且當(dāng)和2做乘法的時(shí)候相當(dāng)于移位，在使用它的時(shí)候優(yōu)點(diǎn)還是不清楚重荠，但是它已經(jīng)成為了傳統(tǒng)的選擇箭阶，31的一個(gè)很好的特性就是做乘法的時(shí)候可以被移位和減法代替的時(shí)候有更好的性能體現(xiàn)。例如31i相當(dāng)于是i左移5位減去i戈鲁，即31i == (i<<5)-i〕鸩危現(xiàn)代的虛擬內(nèi)存系統(tǒng)都使用這種自動(dòng)優(yōu)化。

現(xiàn)在進(jìn)入正題婆殿，HashMap為什么還要做二次hash呢? 代碼如下：

static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

回答這個(gè)問題之前诈乒，我們先來看看HashMap是怎么通過Hash查找數(shù)組的索引的。

/**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

其中h是hash值婆芦，length是數(shù)組的長度怕磨，這個(gè)按位與的算法其實(shí)就是h%length求余，一般什么情況下利用該算法消约，典型的分組肠鲫。例如怎么將100個(gè)數(shù)分組16組中，就是這個(gè)意思荆陆。應(yīng)用非常廣泛滩届。

既然知道了分組的原理了，那我們看看幾個(gè)例子被啼，代碼如下：

        int h=15,length=16;
        System.out.println(h & (length-1));
        h=15+16;
        System.out.println(h & (length-1));
        h=15+16+16;
        System.out.println(h & (length-1));
        h=15+16+16+16;
        System.out.println(h & (length-1));

運(yùn)行結(jié)果都是15，為什么呢?我們換算成二進(jìn)制來看看棠枉。

System.out.println(Integer.parseInt("0001111", 2) & Integer.parseInt("0001111", 2));

System.out.println(Integer.parseInt("0011111", 2) & Integer.parseInt("0001111", 2));

System.out.println(Integer.parseInt("0111111", 2) & Integer.parseInt("0001111", 2));

System.out.println(Integer.parseInt("1111111", 2) & Integer.parseInt("0001111", 2));

這里你就發(fā)現(xiàn)了浓体，在做按位與操作的時(shí)候，后面的始終是低位在做計(jì)算辈讶，高位不參與計(jì)算命浴，因?yàn)楦呶欢际?。這樣導(dǎo)致的結(jié)果就是只要是低位是一樣的贱除，高位無論是什么生闲，最后結(jié)果是一樣的，如果這樣依賴月幌，hash碰撞始終在一個(gè)數(shù)組上碍讯，導(dǎo)致這個(gè)數(shù)組開始的鏈表無限長，那么在查詢的時(shí)候就速度很慢扯躺，又怎么算得上高性能的啊捉兴。所以hashmap必須解決這樣的問題蝎困，盡量讓key盡可能均勻的分配到數(shù)組上去。避免造成Hash堆積倍啥。

回到正題禾乘，HashMap怎么處理這個(gè)問題，怎么做的二次Hash虽缕。

 static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

這里就是解決Hash的的沖突的函數(shù)始藕，解決Hash的沖突有以下幾種方法：
1. 開放定址法
線性探測(cè)再散列，二次探測(cè)再散列氮趋，偽隨機(jī)探測(cè)再散列）
　2. 再哈希法
3. 鏈地址法
4. 建立一 公共溢出區(qū)

而HashMap采用的是鏈地址法鳄虱，這幾種方法在以后的博客會(huì)有單獨(dú)介紹，這里就不做介紹了凭峡。

7拙已、HashMap的put()解析

以上說了一些基本概念，下面該進(jìn)入主題了摧冀，HashMap怎么存儲(chǔ)一個(gè)對(duì)象的倍踪，代碼如下：

 /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        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;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

從代碼可以看出，步驟如下：

(1) 首先判斷key是否為null索昂，如果是null建车，就單獨(dú)調(diào)用putForNullKey(value)處理。代碼如下：

 /**
     * Offloaded version of put for null keys
     */
    private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

從代碼可以看出椒惨，如果key為null的值缤至，默認(rèn)就存儲(chǔ)到table[0]開頭的鏈表了。然后遍歷table[0]的鏈表的每個(gè)節(jié)點(diǎn)Entry康谆，如果發(fā)現(xiàn)其中存在節(jié)點(diǎn)Entry的key為null领斥，就替換新的value，然后返回舊的value沃暗，如果沒發(fā)現(xiàn)key等于null的節(jié)點(diǎn)Entry月洛，就增加新的節(jié)點(diǎn)。

(2) 計(jì)算key的hashcode孽锥，再用計(jì)算的結(jié)果二次hash嚼黔，通過indexFor(hash, table.length);找到Entry數(shù)組的索引i。

(3) 然后遍歷以table[i]為頭節(jié)點(diǎn)的鏈表惜辑，如果發(fā)現(xiàn)有節(jié)點(diǎn)的hash唬涧，key都相同的節(jié)點(diǎn)時(shí)，就替換為新的value盛撑，然后返回舊的value碎节。

(4) modCount是干嘛的啊? 讓我來為你解答。眾所周知撵彻，HashMap不是線程安全的钓株，但在某些容錯(cuò)能力較好的應(yīng)用中实牡，如果你不想僅僅因?yàn)?%的可能性而去承受hashTable的同步開銷，HashMap使用了Fail-Fast機(jī)制來處理這個(gè)問題轴合，你會(huì)發(fā)現(xiàn)modCount在源碼中是這樣聲明的创坞。

volatile關(guān)鍵字聲明了modCount，代表了多線程環(huán)境下訪問modCount受葛，根據(jù)JVM規(guī)范题涨，只要modCount改變了，其他線程將讀到最新的值总滩。其實(shí)在Hashmap中modCount只是在迭代的時(shí)候起到關(guān)鍵作用纲堵。

private abstract class HashIterator<E> implements Iterator<E> {
        Entry<K,V> next;    // next entry to return
        int expectedModCount;    // For fast-fail
        int index;        // current slot
        Entry<K,V> current;    // current entry

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

        public final boolean hasNext() {
            return next != null;
        }

        final Entry<K,V> nextEntry() {
　　　　　　　　// 這里就是關(guān)鍵
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();

            if ((next = e.next) == null) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        current = e;
            return e;
        }

        public void remove() {
            if (current == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Object k = current.key;
            current = null;
            HashMap.this.removeEntryForKey(k);
            expectedModCount = modCount;
        }

    }

使用Iterator開始迭代時(shí)，會(huì)將modCount的賦值給expectedModCount闰渔，在迭代過程中席函，通過每次比較兩者是否相等來判斷HashMap是否在內(nèi)部或被其它線程修改，如果modCount和expectedModCount值不一樣冈涧，證明有其他線程在修改HashMap的結(jié)構(gòu)茂附，會(huì)拋出異常。

所以HashMap的put督弓、remove等操作都有modCount++的計(jì)算营曼。

(5) 如果沒有找到key的hash相同的節(jié)點(diǎn)，就增加新的節(jié)點(diǎn)addEntry(),代碼如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

這里增加節(jié)點(diǎn)的時(shí)候取巧了愚隧，每個(gè)新添加的節(jié)點(diǎn)都增加到頭節(jié)點(diǎn)蒂阱，然后新的頭節(jié)點(diǎn)的next指向舊的老節(jié)點(diǎn)。

(6) 如果HashMap大小超過臨界值狂塘，就要重新設(shè)置大小录煤，擴(kuò)容，見第9節(jié)內(nèi)容睹耐。

8辐赞、HashMap的get()解析

理解上面的put，get就很好理解了硝训。代碼如下：

 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

別看這段代碼，它帶來的問題是巨大的新思，千萬記住,HashMap是非線程安全的窖梁，所以這里的循環(huán)會(huì)導(dǎo)致死循環(huán)的。為什么呢?當(dāng)你查找一個(gè)key的hash存在的時(shí)候夹囚，進(jìn)入了循環(huán)纵刘，恰恰這個(gè)時(shí)候，另外一個(gè)線程將這個(gè)Entry刪除了荸哟，那么你就一直因?yàn)檎也坏紼ntry而出現(xiàn)死循環(huán)假哎，最后導(dǎo)致的結(jié)果就是代碼效率很低瞬捕，CPU特別高。一定記住舵抹。

9肪虎、HashMap的size()解析

HashMap的大小很簡(jiǎn)單，不是實(shí)時(shí)計(jì)算的惧蛹，而是每次新增加Entry的時(shí)候扇救，size就遞增。刪除的時(shí)候就遞減香嗓⊙盖唬空間換時(shí)間的做法。因?yàn)樗皇蔷€程安全的靠娱。完全可以這么做沧烈。效力高。

9像云、HashMap的reSize()解析

當(dāng)HashMap的大小超過臨界值的時(shí)候锌雀，就需要擴(kuò)充HashMap的容量了。代碼如下：

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

從代碼可以看出苫费，如果大小超過最大容量就返回汤锨。否則就new 一個(gè)新的Entry數(shù)組，長度為舊的Entry數(shù)組長度的兩倍百框。然后將舊的Entry[]復(fù)制到新的Entry[].代碼如下：

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);
            }
        }
    }

在復(fù)制的時(shí)候數(shù)組的索引int i = indexFor(e.hash, newCapacity);重新參與計(jì)算闲礼。

至此，HashMap還有一些迭代器的代碼铐维，這里不一一做介紹了柬泽，在JDK1.7版本中HashMap也做了一些升級(jí)，具體有Hash因子的參與嫁蛇。

今天差不多完成了HashMap的源碼解析锨并，下一步將會(huì)分析ConcurrencyHashMap的源碼。ConcurrencyHashMap彌補(bǔ)了HashMap線程不安全睬棚、HashTable性能低的缺失第煮。是目前高性能的線程安全的HashMap類。

很晚了抑党，希望對(duì)大家有所幫助包警，晚安。