Java Core系列之HashMap實作

最近在看guava中的cache的源碼，它的實作基于concurrenthashmap，前段時間組裡招人，據說很多看起來很牛掰的履歷，一個hashmap就能刷掉很多，是以順便把hashmap和concurrenthashmap的源碼複習一遍。先從hashmap開始（另：hashtable是hashmap的線程安全版本，它的實作和hashmap實作基本一緻，除了它不能包含null值的key和value，并且它在計算hash值和數組索引值的方式要稍微簡單一些。對于線程安全的實作，hashtable簡單的将所有操作都标記成synchronized，即對目前執行個體的鎖，這樣容易引起一些性能問題，是以目前一般使用性能更好的concurrenthashmap）。

map是對鍵值對存儲的抽象，因而其最主要的方法有：

1. 添加新的鍵值對(key,value)；

2. 通過鍵(key)查找關聯的值(value)；

3. 通過鍵(key)移除關聯的值(value)；

4. 判斷鍵(key)或值(value)的存在性。

其他的方法有：判斷鍵值對的空屬性以及目前的鍵值對數，擷取所有鍵、所有值或者所有鍵值對的集合，批量添加，清除所有鍵值對等。在map中，一個鍵值對用entry接口來表示。因而在java中，對map接口的定義如下：

public interface map<k,v> {

    boolean isempty();

    boolean containskey(object key);

    boolean containsvalue(object value);

    v get(object key);

    v put(k key, v value);

    v remove(object key);

    void putall(map<? extends k, ? extends v> m);

    void clear();

    set<k> keyset();

    collection<v> values();

    set<map.entry<k, v>> entryset();

    interface entry<k,v> {

        k getkey();

        v getvalue();

        v setvalue(v value);

        boolean equals(object o);

        int hashcode();

    }

    boolean equals(object o);

    int hashcode();

}

hashmap是哈希表對map非線程安全版本的實作，它允許key為null，也允許value為null。所謂哈希表就是通過一個哈希函數計算出一個key的哈希值，然後使用該哈希值定位對應的value所在的位置；如果出現哈希值沖突（多個key産生相同的哈希值），則采用一定的沖突處理方法定位到正真value位置，然後傳回查找到的value值。一般哈希表内部使用一個數組實作，使用哈希函數計算出key對應數組中的位置，然後使用處理沖突法找到真正的value，并傳回。因而實作哈希表最主要的問題在于選擇哈希函數和沖突處理方法，好的哈希函數能使資料分布更加零散，進而減少沖突的可能性，而好的沖突處理方法能使沖突處理更快，盡量讓資料分布更加零散，進而不會影響将來的沖突處理方法。

在嚴蔚敏、吳偉明版本的《資料結構（c語言版）》中提供的哈希函數有：1. 直接定址法（線性函數法）；2. 數字分析法；3. 平方取中法；4. 折疊法；5. 除留餘數法；6. 随機數法。在jdk的hashmap中采用了移位異或法後除留餘數（和2的n次方'&'操作）。hashmap内部的資料結構是一個entry<k, v>的數組，在使用key查找value時，先使用key執行個體計算hash值，然後對計算出的hash值做各種移位和異或操作，然後取其數組的最大索引值的餘數（'&'操作，一般其容量值都是2的倍數，因而可以認為是除留餘數）。在jdk 1.7中對string類型采用了内部hash算法（當數組容量超過一定的閥值，使用“jdk.map.althashing.threshold”設定該閥值，預設為integer.max_value，即關閉該功能），并且使用了一個hashseed作為初始值，不了解這些算法的具體緣由，就這樣淺嘗辄止了。

    final int hash(object k) {

        int h = 0;

        if (usealthashing) {

            if (k instanceof string) {

                return sun.misc.hashing.stringhash32((string) k);

            }

            h = hashseed;

        }

        h ^= k.hashcode();

        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

    static int indexfor(int h, int length) {

        return h & (length-1);

同樣在上述的資料結構書中關于沖突處理提供了幾個方法：1. 開放定址法；2. 再哈希法；3.鍊位址法；4. 建立一個公共溢出區法。在jdk的hashmap中采用了鍊位址法，即每個數組bucket中存放的是一個entry鍊，每次新添加一個鍵值對，就是向鍊頭添加一個entry執行個體，新添加的entry的下一個元素是原有的鍊頭（如果該數組bucket不存在entry鍊，則原有鍊頭值為null，不影響邏輯）。每個entry包含key、value、hash值和指向下一個entry的next指針。

    static class entry<k,v> implements map.entry<k,v> {

        final k key;

        v value;

        entry<k,v> next;

        int hash;

添加

從以上描述中，我們可以知道添加新的鍵值對可以分成兩部分：

1. 使用key計算出内部數組的索引值（index）。

2. 如果該索引的數組bucket中已經存在entry鍊，并且該鍊中已經存在新添加的key的值，則将原有的值設定成新添加的值，并傳回舊值。

3. 否則，建立新的entry執行個體，将該執行個體插入到原有鍊的頭部。

4. 在新添加entry執行個體時，如果目前size超過閥值（capacity * loadfactor），數組容量将會自動擴大兩倍，在數組擴容時，所有原存在的entry會重新計算索引值，并且entry鍊的順序也會發生颠倒（如果還在同一個鍊中的話）；而該新添加的entry的索引值也會重新計算。

5. 對key為null時，預設數組的索引值為0，其他邏輯不變。

    void addentry(int hash, k key, v value, int bucketindex) {

        if ((size >= threshold) && (null != table[bucketindex])) {

            resize(2 * table.length);

            hash = (null != key) ? hash(key) : 0;

            bucketindex = indexfor(hash, table.length);

        createentry(hash, key, value, bucketindex);

    void createentry(int hash, k key, v value, int bucketindex) {

        entry<k,v> e = table[bucketindex];

        table[bucketindex] = new entry<>(hash, key, value, e);

        size++;

插入原理圖：

查找 

查找和添加類似，首先根據key計算出數組的索引值（如果key為null，則索引值為0），然後順序查找該索引值對應的entry鍊，如果在entry鍊中找到相等的key，則表示找到相應的entry記錄，否則，表示沒找到，傳回null。對get()操作傳回entry中的value值，對于containskey()操作，則判斷是否存在記錄，兩個方法都調用getentry()方法：

    final entry<k,v> getentry(object key) {

        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;

而對于value查找（如containsvalue()操作）則需要整個表周遊（數組周遊和數組中的entry鍊周遊），因而這種查找的效率比較低，代碼實作也比較簡單。

移除

移除操作（remove()）也是先通過key值計算數組中的索引号（當key為null時索引号為0），進而找到entry鍊，查找entry鍊中的entry，并将該entry删除。

周遊

hashmap中實作了一個hashiterator，它首先周遊數組，查找到一個非null的entry執行個體，記錄該entry所在數組索引，然後在下一個next()操作中，繼續查找下一個非null的entry，并将之前查找到的非null entry傳回。為實作周遊時不能修改hashmap的内容（可以更新已存在的記錄的值，但是不可以添加、删除原有記錄），hashmap記錄一個modcount字段，在每次添加或删除操作起效時，将modcount自增，而在建立hashiterator時記錄目前的modcount值（expectedmodcount），如果在周遊過程中（next()、remove()）操作時，hashmap中的modcount和已存儲的expectedmodcount不一樣，表示hashmap已經被修改，抛出concurrentmodificationexception。即所謂的fail fast原則。

在hashmap中傳回的key、value、entry集合都是基于該iterator實作，實作比較簡單，不細講。

注：clear()操作引起的記憶體問題-由于clear()操作隻是将數組中的所有項置為null，數組本身大小并不改變，因而當某個hashmap已存儲過較大的資料時，調用clear()有些時候不是一個好的做法。

最後吐槽一下，即使jdk内部的hashmap也有很多的代碼重複。。。。。