阿里-測試開發(fā)面經(jīng)（六）

HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn)

HashMap實(shí)際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。

首先來了解一下數(shù)據(jù)結(jié)構(gòu)中數(shù)組和鏈表來實(shí)現(xiàn)對數(shù)據(jù)的存儲，但這兩者基本上是兩個極端。

數(shù)組

數(shù)組存儲區(qū)間是連續(xù)的，占用內(nèi)存嚴(yán)重，故空間復(fù)雜的很大。但數(shù)組的二分查找時間復(fù)雜度小，為O(1)；數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難。

鏈表

鏈表存儲區(qū)間離散，占用內(nèi)存比較寬松，故空間復(fù)雜度很小，但時間復(fù)雜度很大，達(dá)O（N）。鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。

哈希表

那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的，這就是我們要提起的哈希表。哈希表（(Hash table）既滿足了數(shù)據(jù)的查找方便，同時不占用太多的內(nèi)容空間，使用也十分方便。

　　哈希表有多種不同的實(shí)現(xiàn)方法，我接下來解釋的是最常用的一種方法—— 拉鏈法，我們可以理解為“鏈表的數(shù)組” ，如圖：

　　從上圖我們可以發(fā)現(xiàn)哈希表是由數(shù)組+鏈表組成的，一個長度為16的數(shù)組中，每個元素存儲的是一個鏈表的頭結(jié)點(diǎn)。那么這些元素是按照什么樣的規(guī)則存儲到數(shù)組中呢。一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對數(shù)組長度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存儲在數(shù)組下標(biāo)為12的位置。

　首先HashMap里面實(shí)現(xiàn)一個靜態(tài)內(nèi)部類Entry，其重要的屬性有 key , value, next，從屬性key,value我們就能很明顯的看出來Entry就是HashMap鍵值對實(shí)現(xiàn)的一個基礎(chǔ)bean，我們上面說到HashMap的基礎(chǔ)就是一個線性數(shù)組，這個數(shù)組就是Entry[]，Map里面的內(nèi)容都保存在Entry[]里面。

    /**     * The table, resized as necessary. Length MUST Always be a power of two.     */    transient Entry[] table;

1. HashMap的存取實(shí)現(xiàn)

既然是線性數(shù)組，為什么能隨機(jī)存??？這里HashMap用了一個小算法，大致是這樣實(shí)現(xiàn)：

// 存儲時:int hash = key.hashCode(); // 這個hashCode方法這里不詳述,只要理解每個key的hash是一個固定的int值int index = hash % Entry[].length;Entry[index] = value;

// 取值時:int hash = key.hashCode();int index = hash % Entry[].length;return Entry[index];

put（）

疑問：如果兩個key通過hash%Entry[].length得到的index相同，會不會有覆蓋的危險(xiǎn)？

　　這里HashMap里面用到鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的一個概念。上面我們提到過Entry類里面有一個next屬性，作用是指向下一個Entry。打個比方， 第一個鍵值對A進(jìn)來，通過計(jì)算其key的hash得到的index=0，記作:Entry[0] = A。一會后又進(jìn)來一個鍵值對B，通過計(jì)算其index也等于0，現(xiàn)在怎么辦？HashMap會這樣做:B.next = A,Entry[0] = B,如果又進(jìn)來C,index也等于0,那么C.next = B,Entry[0] = C；這樣我們發(fā)現(xiàn)index=0的地方其實(shí)存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起。所以疑問不用擔(dān)心。也就是說數(shù)組中存儲的是最后插入的元素。到這里為止，HashMap的大致實(shí)現(xiàn)，我們應(yīng)該已經(jīng)清楚了。

public V put(K key, V value) {        if (key == null)            return putForNullKey(value); //null總是放在數(shù)組的第一個鏈表中        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;            //如果key在鏈表中已存在，則替換為新value            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;    }


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); //參數(shù)e, 是Entry.next    //如果size超過threshold，則擴(kuò)充table大小。再散列    if (size++ >= threshold)            resize(2 * table.length);}

　　當(dāng)然HashMap里面也包含一些優(yōu)化方面的實(shí)現(xiàn)，這里也說一下。比如：Entry[]的長度一定后，隨著map里面數(shù)據(jù)的越來越長，這樣同一個index的鏈就會很長，會不會影響性能？HashMap里面設(shè)置一個因子，隨著map的size越來越大，Entry[]會以一定的規(guī)則加長長度。

get（）

 public V get(Object key) {        if (key == null)            return getForNullKey();        int hash = hash(key.hashCode());        //先定位到數(shù)組元素，再遍歷該元素處的鏈表        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;}

null key的存取

null key總是存放在Entry[]數(shù)組的第一個元素。

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

    private V getForNullKey() {        for (Entry<K,V> e = table[0]; e != null; e = e.next) {            if (e.key == null)                return e.value;        }        return null;    }

確定數(shù)組index：hashcode % table.length取模

HashMap存取時，都需要計(jì)算當(dāng)前key應(yīng)該對應(yīng)Entry[]數(shù)組哪個元素，即計(jì)算數(shù)組下標(biāo)；算法如下：

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

按位取并，作用上相當(dāng)于取模mod或者取余%。

這意味著數(shù)組下標(biāo)相同，并不表示hashCode相同。

table初始大小

  public HashMap(int initialCapacity, float 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();    }

注意table初始大小并不是構(gòu)造函數(shù)中的initialCapacity！！

而是 >= initialCapacity的2的n次冪！?。?！

再散列rehash過程

當(dāng)哈希表的容量超過默認(rèn)容量時，必須調(diào)整table的大小。當(dāng)容量已經(jīng)達(dá)到最大可能值時，那么該方法就將容量調(diào)整到Integer.MAX_VALUE返回，這時，需要創(chuàng)建一張新表，將原表的映射到新表中。

   /**     * Rehashes the contents of this map into a new array with a     * larger capacity.  This method is called automatically when the     * number of keys in this map reaches its threshold.     *     * If current capacity is MAXIMUM_CAPACITY, this method does not     * resize the map, but sets threshold to Integer.MAX_VALUE.     * This has the effect of preventing future calls.     *     * @param newCapacity the new capacity, MUST be a power of two;     *        must be greater than current capacity unless current     *        capacity is MAXIMUM_CAPACITY (in which case value     *        is irrelevant).     */    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);    }





    /**     * Transfers all entries from current table to newTable.     */    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;                    //重新計(jì)算index                    int i = indexFor(e.hash, newCapacity);                    e.next = newTable[i];                    newTable[i] = e;                    e = next;                } while (e != null);            }        }    }

hashmap的擴(kuò)容機(jī)制

1、當(dāng)我們往hashmap中put元素的時候，先根據(jù)key的hash值得到這個元素在 數(shù)組中的位置（即下標(biāo)），然后就可以把這個元素放到對應(yīng)的位置中了。如果這個元素所在的位子上已經(jīng)存放有其他元素了，那么在同一個位子上的元素將以鏈表的 形式存放，新加入的放在鏈頭，比如a->b->c，新加入的d放到a的位置前面，最先加入的放在鏈尾，也就是c。最后變成d->a->b->c，從hashmap中g(shù)et元素時，首先計(jì)算key的hashcode，找到數(shù)組中對應(yīng)位置的某一元素， 然后通過key的equals方法在對應(yīng)位置的鏈表中找到需要的元素。

2、在hashmap中要找到某個元素，需要根據(jù)key的hash值來求得對應(yīng)數(shù)組中的位置。如何計(jì)算這個位置就是hash算法。前面說過hashmap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，所以我們當(dāng)然希望這個hashmap里面的元素位置盡量的分布均勻些，盡量使得每個位置上的元素?cái)?shù)量只有一個，那么當(dāng)我們用hash算法求得這個位置 的時候，馬上就可以知道對應(yīng)位置的元素就是我們要的，而不用再去遍歷鏈表。所以我們首先想到的就是把hashcode對數(shù)組長度取模運(yùn)算，這樣一來，元素的分布相對來說是比較均勻的。但是，“?！边\(yùn)算的消耗還是比較大的，能不能找一種更快速，消耗更小的方式那？java中是這樣做的

staticintindexFor(inth,intlength){ returnh&(length-1); }

首先算得key的hashcode值，然后跟數(shù)組的長度-1做一次“與”運(yùn)算（&）。看上去很簡單，其實(shí)比較有玄機(jī)。比如數(shù)組的長度是2的4次方， 那么hashcode就會和2的4次方-1做“與”運(yùn)算。很多人都有這個疑問，為什么hashmap的數(shù)組初始化大小都是2的次方大小時，hashmap 的效率最高，我以2的4次方舉例，來解釋一下為什么數(shù)組大小為2的冪時hashmap訪問的性能最高。看下圖，左邊兩組是數(shù)組長度為16（2的4次方），右邊兩組是數(shù)組長度為15。兩組的hashcode均為8和9，但是很明顯，當(dāng)它們和1110“與”的 時候，產(chǎn)生了相同的結(jié)果，也就是說它們會定位到數(shù)組中的同一個位置上去，這就產(chǎn)生了碰撞，8和9會被放到同一個鏈表上，那么查詢的時候就需要遍歷這個鏈 表，得到8或者9，這樣就降低了查詢的效率。同時，我們也可以發(fā)現(xiàn)，當(dāng)數(shù)組長度為15的時候，hashcode的值會與14（1110）進(jìn)行“與”，那么 最后一位永遠(yuǎn)是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠(yuǎn)都不能存放元素了，空間浪費(fèi)相當(dāng)大，更糟的是 這種情況中，數(shù)組可以使用的位置比數(shù)組長度小了很多，這意味著進(jìn)一步增加了碰撞的幾率，減慢了查詢的效率！所以說，當(dāng)數(shù)組長度為2的n次冪的時候，不同的key算得得index相同的幾率較小，那么數(shù)據(jù)在數(shù)組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。說到這里，我們再回頭看一下hashmap中默認(rèn)的數(shù)組大小是多少，查看源代碼可以得知是16，為什么是16，而不是15，也不是20呢，看到上面 annegu的解釋之后我們就清楚了吧，顯然是因?yàn)?6是2的整數(shù)次冪的原因，在小數(shù)據(jù)量的情況下16比15和20更能減少key之間的碰撞，而加快查詢 的效率。

3、當(dāng)hashmap中的元素越來越多的時候，碰撞的幾率也就越來越高（因?yàn)閿?shù)組的長度是固定的），所以為了提高查詢的效率，就要對hashmap的數(shù)組進(jìn)行 擴(kuò)容，數(shù)組擴(kuò)容這個操作也會出現(xiàn)在ArrayList中，所以這是一個通用的操作，很多人對它的性能表示過懷疑，不過想想我們的“均攤”原理，就釋然了， 而在hashmap數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置，并放進(jìn)去，這就是resize。

那么hashmap什么時候進(jìn)行擴(kuò)容呢？當(dāng)hashmap中的元素個數(shù)超過數(shù)組大小*loadFactor時，就會進(jìn)行數(shù)組擴(kuò)容，loadFactor的 默認(rèn)值為0.75，也就是說，默認(rèn)情況下，數(shù)組大小為16，那么當(dāng)hashmap中元素個數(shù)超過16*0.75=12的時候，就把數(shù)組的大小擴(kuò)展為 2*16=32，即擴(kuò)大一倍，然后重新計(jì)算每個元素在數(shù)組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經(jīng)預(yù)知hashmap中元素的個數(shù)，那 么預(yù)設(shè)元素的個數(shù)能夠有效的提高h(yuǎn)ashmap的性能。

比如說，我們有1000個元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合適，不過上面annegu已經(jīng)說過，即使是1000，hashmap也自動會將其設(shè)置為1024。但是new HashMap(1024)還不是更合適的，因?yàn)?.75*1000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合適，既考慮了&的問題，也避免了resize的問題。

哈希表及處理hash沖突的方法

看了ConcurrentHashMap的實(shí)現(xiàn), 使用的是拉鏈法.

雖然我們不希望發(fā)生沖突，但實(shí)際上發(fā)生沖突的可能性仍是存在的。當(dāng)關(guān)鍵字值域遠(yuǎn)大于哈希表的長度，而且事先并不知道關(guān)鍵字的具體取值時。沖突就難免會發(fā)生。

另外，當(dāng)關(guān)鍵字的實(shí)際取值大于哈希表的長度時，而且表中已裝滿了記錄，如果插入一個新記錄，不僅發(fā)生沖突，而且還會發(fā)生溢出。

因此，處理沖突和溢出是哈希技術(shù)中的兩個重要問題。

哈希法又稱散列法、雜湊法以及關(guān)鍵字地址計(jì)算法等，相應(yīng)的表稱為哈希表。這種方法的基本思想是：首先在元素的關(guān)鍵字k和元素的存儲位置p之間建立一個對應(yīng)關(guān)系f，使得p=f(k)，f稱為哈希函數(shù)。創(chuàng)建哈希表時，把關(guān)鍵字為k的元素直接存入地址為f(k)的單元；以后當(dāng)查找關(guān)鍵字為k的元素時，再利用哈希函數(shù)計(jì)算出該元素的存儲位置p=f(k)，從而達(dá)到按關(guān)鍵字直接存取元素的目的。

   當(dāng)關(guān)鍵字集合很大時，關(guān)鍵字值不同的元素可能會映象到哈希表的同一地址上，即 k1≠k2 ，但 H（k1）=H（k2），這種現(xiàn)象稱為沖突，此時稱k1和k2為同義詞。實(shí)際中，沖突是不可避免的，只能通過改進(jìn)哈希函數(shù)的性能來減少沖突。

綜上所述，哈希法主要包括以下兩方面的內(nèi)容：

 1）如何構(gòu)造哈希函數(shù)

 2）如何處理沖突。