還不清楚HashMap嗎？讀完這篇你就懂了！

概述

HashMap對于使用Java的小伙伴們來說最熟悉不過，每天都在使用它。這次主要是分析下HashMap的工作原理，為什么我會拿這個東西出來分析，主要是最近面試的小伙伴們，中被人問起HashMap，HashMap涉及的知識遠(yuǎn)遠(yuǎn)不止put和get那么簡單。

為什么叫做HashMap？內(nèi)部是怎樣實現(xiàn)的呢？使用的時候大多數(shù)都是用String作為它的key呢？下面就讓我們來了解HashMap，并給你詳細(xì)解釋這些問題。

HashMap名字的由來

其實HashMap的由來是基于Hasing技術(shù)(Hasing),Hasing就是將很大的字符串或者任何對象轉(zhuǎn)換成一個用來代表它們的很小的值，這些更短的值就可以很方便的用來方便索引、加快搜索。

什么是HashMap

HashMap是一個用于存儲Key-Value鍵值對的集合，你可以用一個”key”去存儲數(shù)據(jù)。當(dāng)你想獲得數(shù)據(jù)的時候，你可以通過”key”去得到數(shù)據(jù)，每一個鍵值對也叫做Entry。這些個鍵值對（Entry）分散存儲在一個數(shù)組當(dāng)中，這個數(shù)組就是HashMap的主干。

HashMap作為一種數(shù)據(jù)結(jié)構(gòu)，像數(shù)組和鏈表一樣用于常規(guī)的增刪改查，在存數(shù)據(jù)的時候(put)并不是隨便亂放，而是會先進(jìn)行一次分配索引（可以理解為“分類”）的操作再存儲，一旦分配索引存儲之后，下次取(get)的時候就可以大大縮短查找的時間。我們知道數(shù)組在執(zhí)行查、改的效率很高，而增、刪(不是尾部)的效率低，鏈表相反，HashMap則是把這兩者結(jié)合起來，看下HashMap的數(shù)據(jù)結(jié)構(gòu)

先介紹一下HashMap的變量

size,就是HashMap的存儲大小。threshold是HashMap臨界值，也叫閥值，如果HashMap到達(dá)了臨界值，需要重新分配大小。loadFactor是負(fù)載因子， 默認(rèn)為75%。閥值 = 當(dāng)前數(shù)組長度?負(fù)載因子。modCount指的是HashMap被修改或者刪除的次數(shù)總數(shù)。

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

• Entry分散存儲在一個Entry類型的數(shù)組table， table里的每一個數(shù)據(jù)都是一個Entry對象。Y軸方向代表的就是數(shù)組，X軸方向就是鏈表的存儲方式。

• table里面存儲的Entry類型，Entry類里包含了hashcode變量，key,value 和另外一個Entry對象。因為這是一個鏈表結(jié)構(gòu)。通過我找到你，你再找到他。不過這里的Entry并不是LinkedList，它是單獨(dú)為HashMap服務(wù)的一個內(nèi)部單鏈表結(jié)構(gòu)的類。

• 數(shù)組的特點(diǎn)是特點(diǎn)是查詢快，時間復(fù)雜度是O(1)，插入和刪除的操作比較慢，時間復(fù)雜度是O(n)。而鏈表的存儲方式是非連續(xù)的，大小不固定，特點(diǎn)與數(shù)組相反，插入和刪除快，查詢速度慢。HashMap引用他們，選取了他們的有段，可以說是在查詢，插入和刪除的操作，都會有些提速。

HashMap的基本原理

1、首先判斷Key是否為Null，如果為null，直接查找Enrty[0]，如果不是Null，先計算Key的HashCode，然后經(jīng)過二次Hash，得到Hash值。

2、根據(jù)Hash值，對Entry[]的長度length求余，得到的就是Entry數(shù)組的index。

3、根據(jù)對應(yīng)的索引找到對應(yīng)的數(shù)組，就是找到了其所在的鏈表，然后按照鏈表的操作對Value進(jìn)行插入、刪除和查詢操作。

Hash碰撞

hash 方法
我們都知道在Java中每個對象都有一個hashcode()方法用來返回該對象的 hash值。HashMap先對hashCode進(jìn)行hash操作，然后再通過hash值進(jìn)一步計算下標(biāo)。

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash42((String) k);
    }

    h ^= k.hashCode();

    // 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);
}
public final int hashCode() {
    return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}

HashMap是怎么通過Hash查找數(shù)組的索引的呢，調(diào)用indexFor，其中h是hash值，length是數(shù)組的長度，這個按位與的算法其實就是h%length求余。

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

其中h是hash值，length是數(shù)組的長度，這個按位與的算法其實就是h%length求余。

一般什么情況下利用該算法，典型的分組。例如怎么將100個數(shù)分組16組中，就是這個意思。應(yīng)用非常廣泛。

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

舉個例子

        int h=15,length=16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("0001111", 2) & Integer.parseInt("0001111", 2));
        h=15+16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("0011111", 2) & Integer.parseInt("0001111", 2));
        h=15+16+16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("0111111", 2) & Integer.parseInt("0001111", 2));
        h=15+16+16+16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("1111111", 2) & Integer.parseInt("0001111", 2));

在做按位與的時候，始終是低位在做計算，高位不參與計算，因為高位都是0。這樣導(dǎo)致的結(jié)果就是只要是低位是一樣的，高位無論是什么，最后結(jié)果是一樣的，如果這樣依賴，hash碰撞始終在一個數(shù)組上，導(dǎo)致這個數(shù)組開始的鏈表無限長，那么在查詢的時候就速度很慢，又怎么算得上高性能的啊。所以hashmap必須解決這樣的問題，盡量讓key盡可能均勻的分配到數(shù)組上去。避免造成Hash堆積。

調(diào)用put方法時，盡管我們設(shè)法避免碰撞以提高HashMap的性能，還是可能發(fā)生碰撞。據(jù)說碰撞率還挺高，平均加載率到10%時就會開始碰撞。

源碼分析

HashMap初始化
默認(rèn)情況下，大多數(shù)人都調(diào)用 HashMap hashMap = new HashMap();來初始化的，我們在這分析newHashMap（int initialCapacity, float loadFactor）的構(gòu)造函數(shù)。

我們都知道在Java中每個對象都有一個hashcode()方法用來返回該對象的 hash值。HashMap先對hashCode進(jìn)行hash操作，然后再通過hash值進(jìn)一步計算下標(biāo)。

代碼如下：

public HashMap(int initialCapacity, float loadFactor) {
　// initialCapacity代表初始化HashMap的容量，它的最大容量是MAXIMUM_CAPACITY = 1 << 30。
　// loadFactor代表它的負(fù)載因子，默認(rèn)是是DEFAULT_LOAD_FACTOR=0.75，用來計算threshold臨界值的。    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);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

由上面的代碼可以看出，初始化的時候需要知道初始化的容量大小，因為在后面要通過按位與的Hash算法計算Entry數(shù)組的索引，那么要求Entry的數(shù)組長度是2的N次方。

put操作
HashMap怎么存儲一個對象呢，代碼如下：

public V put(K key, V value) {
        //數(shù)組為空時創(chuàng)建數(shù)組
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        //①key為空單獨(dú)對待
        if (key == null)
            return putForNullKey(value);
        //②根據(jù)key計算hash值
        int hash = hash(key);
        //②根據(jù)hash值和當(dāng)前數(shù)組的長度計算在數(shù)組中的索引
        int i = indexFor(hash, table.length);
        //遍歷整條鏈表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //③hash值和key值都相同的情況，替換之前的值
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                //返回被替換的值
                return oldValue;
            }
        }

        modCount++;
        //③如果沒有找到key的hash相同的節(jié)點(diǎn),直接存值或發(fā)生hash碰撞都走這
        addEntry(hash, key, value, i);
        return null;
    }

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

1.首先會判斷可以是否為null，如果是null，就調(diào)用pullForNullKey（value）處理。代碼如下：

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)就存儲到table[0]開頭的鏈表了。然后遍歷table[0]的鏈表的每個節(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. 計算key的hashcode，再用計算的結(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)時，就替換為新的value，然后返回舊的value。

如果沒有找到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)
        //判斷數(shù)組容量是否足夠，不足夠擴(kuò)容
            resize(2 * table.length);
    }

（4）如果HashMap大小超過臨界值，就要重新設(shè)置大小，擴(kuò)容，稍后講解。

附上一張流程圖，這個圖是從別的博主哪里copy的，感覺畫的不錯。

get操作

我們通過hashMap.get(K key) 來獲取存入的值，key的取值很簡單了。我們通過數(shù)組的index直接找到Entry，然后再遍歷Entry，當(dāng)hashcode和key都一樣就是我們當(dāng)初存入的值啦。

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

調(diào)用getEntry(key)拿到entry ,然后返回entry的value,來看getEntry(key)方法

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        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 != null && key.equals(k))))
                return e;
        }
        return null;
    }

相比put，get操作就沒這么多套路，只需要根據(jù)key值計算hash值，和數(shù)組長度取模，然后就可以找到在數(shù)組中的位置(key為空同樣單獨(dú)操作)，接著就是Entry遍歷，hash相等的情況下，如果key相等就知道了我們想要的值。

再get方法中有null的判斷，null取hash值總是0,再getNullKey(K key)方法中，也是按照遍歷方法來查找的。

modCount的作用

眾所周知，HashMap不是線程安全的，但在某些容錯能力較好的應(yīng)用中，如果你不想僅僅因為1%的可能性而去承受hashTable的同步開銷，HashMap使用了Fail-Fast機(jī)制來處理這個問題，你會發(fā)現(xiàn)modCount在源碼中是這樣聲明的。

reSize

調(diào)用put方法時，當(dāng)HashMap的大小超過臨界值的時候，就需要擴(kuò)充HashMap的容量了。代碼如下：

void resize(int newCapacity) { //傳入新的容量
    //獲取舊數(shù)組的引用
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    //極端情況，當(dāng)前鍵值對數(shù)量已經(jīng)達(dá)到最大
    if (oldCapacity == MAXIMUM_CAPACITY) {
        //修改閥值為最大直接返回
        threshold = Integer.MAX_VALUE;
        return;
    }
    //步驟①根據(jù)容量創(chuàng)建新的數(shù)組
    Entry[] newTable = new Entry[newCapacity];
    //步驟②將鍵值對轉(zhuǎn)移到新的數(shù)組中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    //步驟③將新數(shù)組的引用賦給table
    table = newTable;
    //步驟④修改閥值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

如果大小超過最大容量就返回。否則就new 一個新的Entry數(shù)組，長度為舊的Entry數(shù)組長度的兩倍。然后將舊的Entry[]復(fù)制到新的Entry[].代碼如下：

    void transfer(Entry[] newTable, boolean rehash) {
        //獲取新數(shù)組的長度
        int newCapacity = newTable.length;
        //遍歷舊數(shù)組中的鍵值對
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //計算在新表中的索引，并到新數(shù)組中
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

到這里相信你對HashMap內(nèi)部已經(jīng)非常清楚了，如果本篇文章對你有幫助記得關(guān)注我，我會繼續(xù)更新文章，感謝支持！