面試題之--HashMap原理

一,概念:

       1,HashMap是基于哈希表的Map接口的非同步實作,允許使用null值和null鍵。當即key為null的鍵值對，hash值為0，hashmap儲存的就是0。是以一個hashmap對象隻會存儲一個key為null的鍵值對，因為它們的hash值都相同。但可以存儲多條記錄的值為 Null;

      1.2,HashMap儲存的是鍵值對，是以很快。但不保證映射的順序.

     1.3HashMap的key為null時,是将元素放在table[0]這個連結清單的(在第一行就展示了) .  那麼取出也是在talbe[0]連結清單中查找key為null的元素，如果找到，則将value重新指派給這個元素的value，并傳回原來的value。 如果上面for循環沒找到則将這個元素添加到talbe[0]連結清單的表頭。

      1.4，HashMap不支援線程的同步，如果需要同步，可以用 Collections.synchronizedMap(hm)，或者使用ConcurrentHashMap。

// HashMap的put方法
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        // key為null調用putForNullKey(value)
        return putForNullKey(value);
    int hash = hash(key);
    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;
}
           

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

      2,HashMap實際上是一個“連結清單散列”的資料結構

       jdk1.8之前，它是數組和連結清單（單向連結清單）的結合體。HashMap底層就是一個數組結構(又稱為哈希桶,每個桶裡面放的是連結清單)，數組中的每一項又是一個連結清單,連結清單中的每個節點,就是哈希表中的每個元素。當建立一個HashMap的時候，就會初始化一個數組。

    .Jdk1.8之後,增加了紅黑樹,當連結清單長度大于8，并且整個table數組的長度大于64時，就會将連結清單轉為紅黑樹。當紅黑樹的節點數小于6時，就會轉為連結清單。

     2.1,數組：存儲區間連續，占用記憶體嚴重，尋址容易，插入删除困難,

     2.2 連結清單：存儲區間離散，占用記憶體比較寬松，尋址困難，插入删除容易;是以,Hashmap綜合應用了這兩種資料結構，實作了尋址容易，插入删除也容易。

    2.3,紅黑樹:在擴容的時候,即使負載因子和Hash算法設計的再合理，也免不了會出現鍊條過長的情況,這就會影響hashmap的性能.是以jdk1.8引入了紅黑樹,當連結清單長度超過8時,就轉為紅黑樹,紅黑樹的增删改查較快,就提高了hashmap的性能.

 紅黑樹是一種資料結構,它是近似平衡的二叉查找樹,，它能夠確定任何一個節點的左右子樹的高度差不會超過二者中較低那個的一倍。具體來說，紅黑樹是滿足如下條件的二叉查找樹（binary search tree）

      3,當建立一個HashMap的時候，就會初始化一個Entry數組。每個 Map.Entry 其實就是一個key-value鍵值對，它持有一個指向下一個元素的引用，就構成了連結清單。

     4,當HashMap中的元素越來越多的時候，hash沖突的幾率也就越來越高，因為數組的長度是固定的。是以為了提高查詢的效率，就要對HashMap的數組進行擴容，原數組中的資料必須重新計算其在新數組中的位置，并放進去，這就是resize(調整大小)。

    5,采用fail-fast機制

我們知道java.util.HashMap不是線程安全的，是以如果在使用疊代器的過程中有其他線程修改了map，那麼将抛出ConcurrentModificationException，這就是所謂fail-fast政策。

二,你知道HashMap的工作原理嗎？

   簡單地說，HashMap 在底層将 key-value 當成一個整體進行處理，這個整體就是 Entry數組,通過 Entry[] 數組來儲存所有的 key-value 鍵值對，通過put()和get()方法儲存和擷取對象。

      當我們将鍵值對(也就是entry對象)傳遞給put()方法時，會根據hash算法找到bucket位置來儲存值對象,當hash值相同，發生碰撞，再根據equals()方法決定其在該數組位置上的連結清單中的存儲位置；當調用get()方法時,也會根據hash算法找到其在數組中的bucket位置,再根據Key.equals()方法從改位置上的連結清單中取出這個entry對象.

三,當兩個對象的hashcode相同會發生什麼？

        1, hashcode相同，它們的bucket位置就相同，‘碰撞’就會發生。它們會儲存在同一個bucket位置的連結清單中。鍵對象的equals()方法用來找到鍵值對。

         2.equal()相等的兩個對象他們的hashCode()肯定相等，也就是用equal()對比是絕對可靠。

         3.hashCode()相等的兩個對象他們的equal()不一定相等，就是hashCode()不是絕對可靠。

hashCode是對象在記憶體位址通過hash算法得到的哈希碼,比較兩個對象是否相等：

        4.首先比較hashcode ，如果hashcode相等則進一步比較equals，不相等則兩個對象肯定不相等；

        5.hashset,hashmap,hashtable等等，比如hashset裡要求對象不能重複，則他内部必然要對添加進去的每個對象進行對比，而他的對比規則就是像上面說的那樣，先hashCode()，如果hashCode()相同，再用equal()驗證，如果hashCode()都不同，則肯定不同，這樣對比的效率就很高了。

四,如果兩個鍵的hashcode相同，你如何擷取值對象？

  當我們調用get()方法，HashMap會使用鍵對象的hashcode找到bucket位置，然後根鍵對象的equals()方法用來找到鍵值對。

五,如果HashMap的大小超過了負載因子(load factor)定義的容量，怎麼辦？

/**
       1，初始化容量16
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


    /**
        2，最大容量2的30次方
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;


    /**
        負載因子 0.75
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

           

         預設的負載因子大小為0.75(數組大小為16)，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，将會建立原來HashMap大小的兩倍的bucket數組，來重新調整map的大小，并将原來的對象放入新的bucket數組中。這個過程叫作rehashing，因為它調用hash方法找到新的bucket位置。

        HashMap的初始化容量(即初始化table時用到)，預設為16。

        loadFactor為負載因子，預設為0.75。

        threshold是HashMap進行擴容的閥值，當HashMap的存放的元素個數超過該值時，會進行擴容，它的值為HashMap的容量乘以負載因子。比如，HashMap的預設閥值為16*0.75，即12。

六,你了解重新調整HashMap大小存在什麼問題嗎？

    當多線程的情況下，可能産生條件競争(race condition).多線程并發異常

七,小結

    1,擴容是一個特别耗性能的操作，是以當程式員在使用HashMap的時候，估算map的大小，初始化的時候給一個大緻的數值，避免map進行頻繁的擴容。

    2,負載因子是可以修改的，也可以大于1，但是建議不要輕易修改，除非情況非常特殊。

    3,HashMap是線程不安全的，不要在并發的環境中同時操作HashMap，建議使用ConcurrentHashMap。或者Collections.synchronizedMap(hm)

    4,JDK1.8引入紅黑樹大程度優化了HashMap的性能。

   5,table的索引在邏輯上叫做“桶”(bucket)，它存儲了連結清單的第一個元素。

   6,key的hashcode()方法用來找到Entry對象所在的桶。

   7, 如果兩個key有相同的hash值，他們會被放在table數組的同一個桶裡面的連結清單中。

   8,key的equals()方法用來確定key的唯一性。

    9,運算大多采用位運算,效率更高

借鑒:

HashMap實作原理分析及簡單實作一個HashMap

https://blog.csdn.net/abcdad/article/details/64123291

Java8系列之重新認識HashMap

http://www.importnew.com/20386.html