基礎(chǔ)知識

散列表也叫哈希表，是根據(jù)鍵值對（key暮现，value）進(jìn)行訪問的一種數(shù)據(jù)結(jié)構(gòu)还绘。他是把一對（key，value）通過key的哈希值來映射到數(shù)組中的栖袋，也就是說拍顷，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度塘幅。這個映射函數(shù)叫做散列函數(shù)菇怀，存放記錄的數(shù)組叫做散列表。

1晌块，HashMap

散列表中最常見的應(yīng)該就是HashMap了爱沟，HashMap的實現(xiàn)原理非常簡單，他其實就是數(shù)組加鏈表的一種數(shù)據(jù)結(jié)構(gòu)匆背。如果映射在數(shù)組中出現(xiàn)了沖突呼伸，他會以鏈表的形式存在。我們來看一下他的數(shù)據(jù)結(jié)構(gòu)是什么樣的钝尸。

在這里插入圖片描述

上面的圖有兩處非常明顯的錯誤括享，不知道大家有沒有發(fā)現(xiàn)，如果對HashMap源碼比較熟悉的估計一眼就能看的出來珍促。首先是數(shù)組的長度必須是2的n次冪铃辖，這里長度是9，明顯有錯猪叙，然后是entry的個數(shù)不能大于數(shù)組長度的75%娇斩，如果大于就會觸發(fā)擴(kuò)容機(jī)制進(jìn)行擴(kuò)容仁卷，這里明顯是大于75%。我為什么要畫這個錯誤的圖呢犬第，因為在網(wǎng)上確實看到過不少這樣不嚴(yán)謹(jǐn)?shù)膱D锦积，希望大家能夠看清楚。那么正確的圖應(yīng)該是這樣的歉嗓。

在這里插入圖片描述

數(shù)組的長度即是2的n次冪丰介，而他的size又不大于數(shù)組長度的75%。

HashMap的實現(xiàn)原理是先要找到要存放數(shù)組的下標(biāo)鉴分，如果是空的就存進(jìn)去哮幢，如果不是空的就判斷key值是否一樣，如果一樣就替換志珍，如果不一樣就以鏈表的形式存在橙垢。

在java中1.7及以前的版本如果以鏈表的形式存在，在插入的時候采用的是頭插法碴裙。

在1.8是尾插法钢悲。并且在java1.8中如果鏈表的長度大于8的時候會轉(zhuǎn)為紅黑樹。

在HashMap中舔株，數(shù)組的大小是2^{n莺琳，無論你初始化的時候傳的值是多少，他都會初始化為2}n载慈，并且這個2^n是大于等于你初始化值的最小值惭等，比如初始化的時候傳的值是17，他會計算得到32办铡。關(guān)于怎么計算的辞做，我們有3種方式，第一種就是通過while循環(huán)寡具，我們來看下代碼

public static int tableSizeFor(int initialCapacity) {
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    return capacity;
}

這種解法是最簡單的秤茅，一眼就能看懂，還有兩種解法我們也可以看下

public static int tableSizeFor(int i) {
    i--;
    i |= i >>> 1;
    i |= i >>> 2;
    i |= i >>> 4;
    i |= i >>> 8;
    i |= i >>> 16;
    return i + 1;
}

原理比較簡單童叠，就是把最左邊的1往右全部鋪開框喳，最后在加上1就是我們要求的結(jié)果。這里第二行減1的目的是防止i等于2^n的時候結(jié)果會放大厦坛。比如當(dāng)i=32的時候如果我們在第2行不減1五垮，會導(dǎo)致結(jié)果為64。我們再來看另一種寫法

 public static int tableSizeFor(int i) {
     if ((i & (i - 1)) == 0)
         return i;
     i |= (i >> 1);
     i |= (i >> 2);
     i |= (i >> 4);
     i |= (i >> 8);
     i |= (i >> 16);
     return (i - (i >>> 1)) << 1;
}

在第2-3行實現(xiàn)判斷是不是2^n杜秸， 如果是就直接返回放仗，第4-8行也是把i最左邊的1往右全部鋪開，第9行i-(i>>>1)表示的是把i最左邊的1保留撬碟，其他的全部置為0诞挨，通俗一點也就是他返回的是小于i的最大的2^n莉撇，然后再往左移一位就是我們要求的結(jié)果。我們就以i等于17為例用最后一個方法來畫個圖分析一下亭姥。

在這里插入圖片描述

2稼钩，ArrayMap

除了使用數(shù)組和鏈表以外顾稀，我們能不能只使用一種數(shù)據(jù)結(jié)構(gòu)呢达罗，比如數(shù)組，當(dāng)然也是可以的静秆。大家可能會懷疑粮揉，如果只使用一種數(shù)據(jù)結(jié)構(gòu)的話，映射出現(xiàn)了沖突怎么辦抚笔，其實也很好解決扶认。ArrayMap的實現(xiàn)原理是使用兩個數(shù)組，一個存放hash值殊橙，一個存放key和value辐宾，其中存放key和value的數(shù)組長度是存放hash值數(shù)組長度的二倍，其中存放hash值的數(shù)組必須是排序的膨蛮。如果hash值出現(xiàn)了沖突叠纹，說明hash值最終的計算是一樣的，那么在hash數(shù)組中肯定是挨著的敞葛，所以查找的時候如果hash值有重復(fù)的就會把重復(fù)的也查找一遍誉察。我們來看ArrayMap中的一段代碼

 int indexOf(Object key, int hash) {
     final int N = mSize;

     // Important fast case: if nothing is in here, nothing to look for.
     if (N == 0) {
         return ~0;
     }

     int index = binarySearchHashes(mHashes, N, hash);

    // If the hash code wasn't found, then we have no entry for this key.
    if (index < 0) {
        return index;
    }

    // If the key at the returned index matches, that's what we want.
    if (key.equals(mArray[index<<1])) {
        return index;
    }

    // Search for a matching key after the index.
    int end;
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        if (key.equals(mArray[end << 1])) return end;
    }

    // Search for a matching key before the index.
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
        if (key.equals(mArray[i << 1])) return i;
    }

    // Key not found -- return negative value indicating where a
    // new entry for this key should go.  We use the end of the
    // hash chain to reduce the number of array entries that will
    // need to be copied when inserting.
    return ~end;
}

我們看到第23-30行，如果hash值一樣惹谐，在查找的時候不光往前查找而且還會往后查找持偏。他的數(shù)據(jù)結(jié)構(gòu)是這樣的。

在這里插入圖片描述

3氨肌，SparseArray

在散列表中如果可以確定key值都是int類型鸿秆，那么又可以簡化，直接用key值當(dāng)hash值存儲即可怎囚，和ArrayMap一樣只需要兩個數(shù)組即可卿叽，一個是存放key的，一個是存放value的桩了，不同的是這兩個數(shù)組的長度都是一樣的附帽。這種情況下就不會出現(xiàn)hash值一樣的問題了，因為這個時候如果hash值一樣的話井誉，那么他們的key肯定是一樣的蕉扮，而在散列表中是不可能存在了，假如在插入數(shù)據(jù)的時候有一樣的key颗圣，那么他的value是要被替換掉的喳钟，所以不會出現(xiàn)兩個完全一樣的key屁使。他的數(shù)據(jù)結(jié)構(gòu)圖是這樣的

在這里插入圖片描述

4，ThreadLocalMap

在java語言中還有一個關(guān)于散列表的奔则，那就是ThreadLocalMap蛮寂，這個類是ThreadLocal的一個靜態(tài)內(nèi)部類，一般我們用不到易茬。如果出現(xiàn)hash沖突的時候他的實現(xiàn)原理和上面的幾種也都不太一樣酬蹋。存儲的時候他首先會根據(jù)hash值映射到指定的數(shù)組，如果當(dāng)前位置為空就直接存進(jìn)去抽莱，如果不為空就往后找范抓，找他的下一個，我們來看其中的一段代碼

    /**
     * Increment i modulo len.
     */
    private static int nextIndex(int i, int len) {
        return ((i + 1 < len) ? i + 1 : 0);
    }

總結(jié)：
散列表大家第一個想到的就是HashMap食铐，需要數(shù)組加鏈表的方式才能實現(xiàn)匕垫，通過我們上面的分析，其實我們不需要鏈表也能實現(xiàn)虐呻。散列表的實現(xiàn)原理其實很簡單象泵。他的核心是當(dāng)我們的hash值出現(xiàn)沖突的時候該怎么解決。