HashMap分析

這次主要是分析下HashMap的工作原理，為什麼我會拿這個東西出來分析，原因很簡單，以前我面試的時候，偶爾問起HashMap，99%的程式員都知道HashMap，基本都會用Hashmap，這其中不僅僅包括剛畢業的大學生，也包括已經工作5年，甚至是10年的程式員。HashMap涉及的知識遠遠不止put和get那麼簡單。本次的分析希望對于面試的人起碼對于面試官的問題有所應付

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

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

答：當然用過，HashMap是一種”key ,value”的存儲結構，能夠快速将key的資料put方式存儲起來，然後很快的通過get取出來”，然後說“HashMap不是線程安全的，

HashTable是線程安全的，通過synchronized實作的。HashMap取值非常快”等等。這個時候說明他已經很熟練使用HashMap的工具了。

問：“你知道HashMap 在put和get的時候是怎麼工作的嗎？”

答：“HashMap是通過key計算出Hash值，然後将這個Hash值映射到對象的引用上，get的時候先計算key的hash值，然後找到對象”。這個時候已經顯得不自信了。

問：“HashMap的key為什麼一般用字元串比較多，能用其他對象，或者自定義的對象嗎？為什麼？”

答：“這個沒研究過，一般習慣用String。”

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

答：“線程安全就是多個線程去通路的時候，會對對象造成不是預期的結果，一般要加鎖才能線程安全。”

其實，問了以上那些問題，我基本能判定這個程式員的基本功了，一般技術中等，接下來的問題沒必要問了。

從我的個人角度來看，HashMap的面試問題能夠考察面試者的線程問題、Java記憶體模型問題、線程可見與不可變問題、Hash計算問題、連結清單結構問題、二進制的&、|、<<、>>等問題。是以一個HashMap就能考驗一個人的技術功底了。

二、概念分析

1、HashMap的類圖結構

2、HashMap存儲結構

HashMap的使用那麼簡單，那麼問題來了，它是怎麼存儲的，他的存儲結構是怎樣的，很多程式員都不知道，其實當你put和get的時候，稍稍往前一步，你看到就是它的真面目。其實簡單的說HashMap的存儲結構是由數組和連結清單共同完成的。

從上圖可以看出HashMap是Y軸方向是數組，X軸方向就是連結清單的存儲方式。大家都知道數組的存儲方式在記憶體的位址是連續的，大小固定，一旦配置設定不能被其他引用占用。它的特點是查詢快，時間複雜度是O(1)，插入和删除的操作比較慢，時間複雜度是O(n)，連結清單的存儲方式是非連續的，大小不固定，特點與數組相反，插入和删除快，查詢速度慢。HashMap可以說是一種折中的方案吧。

3、HashMap基本原理

1、首先判斷Key是否為Null，如果為null，直接查找Enrty[0]，如果不是Null，先計算Key的HashCode，然後經過二次Hash。得到Hash值，這裡的Hash特征值是一個int值。

2、根據Hash值，要找到對應的數組啊，是以對Entry[]的長度length求餘，得到的就是Entry數組的index。

3、找到對應的數組，就是找到了所在的連結清單，然後按照連結清單的操作對Value進行插入、删除和查詢操作。

4、HashMap概念介紹

變量術語說明

size 大小 HashMap的存儲大小

threshold 臨界值 HashMap大小達到臨界值，需要重新配置設定大小。

loadFactor 負載因子 HashMap大小負載因子，預設為75%。

modCount 統一修改 HashMap被修改或者删除的次數總數。

Entry 實體 HashMap存儲對象的實際實體，由Key，value，hash，next組成。

5、HashMap初始化

預設情況下，大多數人都調用new HashMap()來初始化的，我在這裡分析new HashMap(int initialCapacity, float loadFactor)的構造函數，代碼如下：

複制代碼

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

　　　　 // loadFactor代表它的負載因子，預設是是DEFAULT_LOAD_FACTOR=0.75，用來計算threshold臨界值的。
        if (loadFactor <=  || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

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

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

複制代碼

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

6、HashMap中的Hash計算和碰撞問題

HashMap的hash計算時先計算hashCode(),然後進行二次hash。代碼如下：

// 計算二次Hash

int hash = hash(key.hashCode());

// 通過Hash找數組索引

int i = indexFor(hash, table.length);

先不忙着學習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[]*^(n-) + s[]*^(n-) + ... + s[n-]
     * </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 ==  && value.length > ) {
            char val[] = value;

            for (int i = ; i < value.length; i++) {
                h =  * 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為字元串的長度。這裡為什麼有一個固定常量31呢，關于這個31的讨論很多，基本就是優化的數字，主要參考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是因為它是一個奇素數，如果它做乘法溢出的時候，資訊會丢失，而且當和2做乘法的時候相當于移位，在使用它的時候優點還是不清楚，但是它已經成為了傳統的選擇，31的一個很好的特性就是做乘法的時候可以被移位和減法代替的時候有更好的性能展現。例如31*i相當于是i左移5位減去i，即31*i == (i<<5)-i。現代的虛拟記憶體系統都使用這種自動優化。

現在進入正題，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);
}

複制代碼

回答這個問題之前，我們先來看看HashMap是怎麼通過Hash查找數組的索引的。

複制代碼

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

複制代碼

其中h是hash值，length是數組的長度，這個按位與的算法其實就是h%length求餘，一般什麼情況下利用該算法，典型的分組。例如怎麼将100個數分組16組中，就是這個意思。應用非常廣泛。

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

複制代碼

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

複制代碼

運作結果都是15，為什麼呢?我們換算成二進制來看看。

複制代碼

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

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

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

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

複制代碼

這裡你就發現了，在做按位與操作的時候，後面的始終是低位在做計算，高位不參與計算，因為高位都是0。這樣導緻的結果就是隻要是低位是一樣的，高位無論是什麼，最後結果是一樣的，如果這樣依賴，hash碰撞始終在一個數組上，導緻這個數組開始的連結清單無限長，那麼在查詢的時候就速度很慢，又怎麼算得上高性能的啊。是以hashmap必須解決這樣的問題，盡量讓key盡可能均勻的配置設定到數組上去。避免造成Hash堆積。

回到正題，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 >>> ) ^ (h >>> );
        return h ^ (h >>> ) ^ (h >>> );
    }

複制代碼

這裡就是解決Hash的的沖突的函數，解決Hash的沖突有以下幾種方法：

(1)、開放定址法（線性探測再散列，二次探測再散列，僞随機探測再散列）

　(2)、再哈希法

(3)、鍊位址法

(4)、建立一公共溢出區

而HashMap采用的是鍊位址法，這幾種方法在以後的部落格會有單獨介紹，這裡就不做介紹了。

7、HashMap的put()解析

以上說了一些基本概念，下面該進入主題了，HashMap怎麼存儲一個對象的，代碼如下：

複制代碼

/**
     * 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，就單獨調用putForNullKey(value)處理。代碼如下：

複制代碼

private V putForNullKey(V value) {

for (Entry

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( * table.length);
    }

這裡增加節點的時候取巧了，每個新添加的節點都增加到頭節點，然後新的頭節點的next指向舊的老節點。

(6) 如果HashMap大小超過臨界值，就要重新設定大小，擴容，見第9節内容。

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是非線程安全的，是以這裡的循環會導緻死循環的。為什麼呢?當你查找一個key的hash存在的時候，進入了循環，恰恰這個時候，另外一個線程将這個Entry删除了，那麼你就一直因為找不到Entry而出現死循環，最後導緻的結果就是代碼效率很低，CPU特别高。一定記住。

9、HashMap的size()解析

HashMap的大小很簡單，不是實時計算的，而是每次新增加Entry的時候，size就遞增。删除的時候就遞減。空間換時間的做法。因為它不是線程安全的。完全可以這麼做。效力高。

9、HashMap的reSize()解析

當HashMap的大小超過臨界值的時候，就需要擴充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 一個新的Entry數組，長度為舊的Entry數組長度的兩倍。然後将舊的Entry[]複制到新的Entry[].代碼如下：

void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = ; 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);
            }
        }
    }

複制代碼

在複制的時候數組的索引int i = indexFor(e.hash, newCapacity);重新參與計算。

至此，HashMap還有一些疊代器的代碼，這裡不一一做介紹了，在JDK1.7版本中HashMap也做了一些更新，具體有Hash因子的參與。

今天差不多完成了HashMap的源碼解析，下一步将會分析ConcurrencyHashMap的源碼。ConcurrencyHashMap彌補了HashMap線程不安全、HashTable性能低的缺失。是目前高性能的線程安全的HashMap類。

很晚了，希望對大家有所幫助，晚安。

HashMap分析

繼續閱讀

子類能不能繼承父類的構造函數

HashMap多個構造方法的了解

有參構造方法

Java的成員變量與構造方法## Java的成員變量與構造方法

黑馬程式員_Java基礎_面向對象,封裝,繼承,單例設計模式,構造函數,構造代碼塊

File類删除有内容的檔案夾

java讀取檔案夾檔案及操作

javamail實作簡單郵件發送

javaweb基礎之servlet

java學習筆記（11）——集合詳解java學習筆記（11）——集合

java學習筆記（8）——String類詳解java學習筆記（8）——String類詳解5.常用方法：

java UDP傳輸詳解

Java Stream API的介紹和使用（Stream對象執行個體的初始化）

有關servlet的描述

JMX詳解詳細介紹及使用

java io性能分析(轉載)