HashMap和ConcurrentHashMap的區別，HashMap的底層源碼。

2019-11-08 02:26:31

字體：大中小

來源：轉載

供稿：網友

Hashmap本質是數組加鏈表。根據key取得hash值，然后計算出數組下標，如果多個key對應到同一個下標，就用鏈表串起來，新插入的在前面。

　　ConcurrentHashMap：在hashMap的基礎上，ConcurrentHashMap將數據分為多個segment，默認16個（concurrency level），然后每次操作對一個segment加鎖，避免多線程鎖的幾率，提高并發效率。

一、HashMap概述

　　HashMap基于哈希表的 Map 接口的實現。此實現提供所有可選的映射操作，并允許使用 null 值和 null 鍵。（除了不同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序，特別是它不保證該順序恒久不變。

　　值得注意的是HashMap不是線程安全的，如果想要線程安全的HashMap，可以通過Collections類的靜態方法synchronizedMap獲得線程安全的HashMap。

1  Map map = Collections.synchronizedMap(new HashMap()); 
二、HashMap的數據結構
　HashMap的底層主要是基于數組和鏈表來實現的，它之所以有相當快的查詢速度主要是因為它是通過計算散列碼來決定存儲的位置，能夠很快的計算出對象所存儲的位置。HashMap中主要是通過key的hashCode來計算hash值的，只要hashCode相同，計算出來的hash值就一樣。如果存儲的對象對多了，就有可能不同的對象所算出來的hash值是相同的，這就出現了所謂的hash沖突。學過數據結構的同學都知道，解決hash沖突的方法有很多，HashMap底層是通過鏈表來解決hash沖突的。
                                      
從上圖中可以看出，HashMap底層就是一個數組結構，數組中存放的是一個Entry對象，如果產生的hash沖突，也就是說要存儲的那個位置上面已經存儲了對象了，這時候該位置存儲的就是一個鏈表了。我們看看HashMap中Entry類的代碼：
 1 static class Entry<K,V> implements Map.Entry<K,V> { 2         final K key; 3         V value; 4         Entry<K,V> next; 5         final int hash; 6  7         /** 8          * Creates new entry. 9          */10         Entry(int h, K k, V v, Entry<K,V> n) {11             value = v;12             next = n; //hash值沖突后存放在鏈表的下一個13             key = k;14             hash = h;15         }16 17         .........18     }HashMap其實就是一個Entry數組，Entry對象中包含了鍵和值，其中next也是一個Entry對象，它就是用來處理hash沖突的，形成一個鏈表。
三、HashMap源碼分析
　　先看看HashMap類中的一些關鍵屬性：
1 transient Entry[] table;//存儲元素的實體數組2 3 transient int size;//存放元素的個數4 5 int threshold; //臨界值   當實際大小超過臨界值時，會進行擴容threshold = 加載因子*容量6 7 final float loadFactor; //加載因子8 9 transient int modCount;//被修改的次數　   其中加載因子是表示Hash表中元素的填滿的程度.若:加載因子越大,填滿的元素越多,好處是,空間利用率高了,但:沖突的機會加大了.反之,加載因子越小,填滿的元素越少,好處是:沖突的機會減小了,但:空間浪費多了.沖突的機會越大,則查找的成本越高.反之,查找的成本越小.因而,查找時間就越小.因此,必須在 "沖突的機會"與"空間利用率"之間尋找一種平衡與折衷. 這種平衡與折衷本質上是數據結構中有名的"時-空"矛盾的平衡與折衷.
　　如果機器內存足夠，并且想要提高查詢速度的話可以將加載因子設置小一點；相反如果機器內存緊張，并且對查詢速度沒有什么要求的話可以將加載因子設置大一點。不過一般我們都不用去設置它，讓它取默認值0.75就好了。
　　下面看看HashMap的幾個構造方法：
 1 public HashMap(int initialCapacity, float loadFactor) { 2         //確保數字合法 3         if (initialCapacity < 0) 4             throw new IllegalArgumentException("Illegal initial capacity: " + 5                                                initialCapacity); 6         if (initialCapacity > MAXIMUM_CAPACITY) 7             initialCapacity = MAXIMUM_CAPACITY; 8         if (loadFactor <= 0 || Float.isNaN(loadFactor)) 9             throw new IllegalArgumentException("Illegal load factor: " +10                                                loadFactor);11 12         // Find a power of 2 >= initialCapacity13         int capacity = 1;   //初始容量14         while (capacity < initialCapacity)   //確保容量為2的n次冪，使capacity為大于initialCapacity的最小的2的n次冪15             capacity <<= 1;16 17         this.loadFactor = loadFactor;18         threshold = (int)(capacity * loadFactor);19         table = new Entry[capacity];20         init();21     }22 23     public HashMap(int initialCapacity) {24         this(initialCapacity, DEFAULT_LOAD_FACTOR);25     }26 27     public HashMap() {28         this.loadFactor = DEFAULT_LOAD_FACTOR;29         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);30         table = new Entry[DEFAULT_INITIAL_CAPACITY];31         init();32     }　　我們可以看到在構造HashMap的時候如果我們指定了加載因子和初始容量的話就調用第一個構造方法，否則的話就是用默認的。默認初始容量為16，默認加載因子為0.75。我們可以看到上面代碼中13-15行，這段代碼的作用是確保容量為2的n次冪，使capacity為大于initialCapacity的最小的2的n次冪，至于為什么要把容量設置為2的n次冪，我們等下再看。
　　下面看看HashMap存儲數據的過程是怎樣的，首先看看HashMap的put方法：
 1 public V put(K key, V value) { 2         if (key == null) //如果鍵為null的話，調用putForNullKey(value) 3             return putForNullKey(value); 4         int hash = hash(key.hashCode());//根據鍵的hashCode計算hash碼 5         int i = indexFor(hash, table.length); 6         for (Entry<K,V> e = table[i]; e != null; e = e.next) { //處理沖突的，如果hash值相同，則在該位置用鏈表存儲 7             Object k; 8             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果key相同則覆蓋并返回舊值 9                 V oldValue = e.value;10                 e.value = value;11                 e.recordaccess(this);12                 return oldValue;13             }14         }15 16         modCount++;17         addEntry(hash, key, value, i);18         return null;19     }當我們往hashmap中put元素的時候，先根據key的hash值得到這個元素在數組中的位置（即下標），然后就可以把這個元素放到對應的位置中了。如果這個元素所在的位子上已經存放有其他元素了，那么在同一個位子上的元素將以鏈表的形式存放，新加入的放在鏈頭，最先加入的放在鏈尾。從hashmap中get元素時，首先計算key的hashcode，找到數組中對應位置的某一元素，然后通過key的equals方法在對應位置的鏈表中找到需要的元素。
具體的實現是：
當你的key為null時，會調用putForNullKey,HashMap允許key為null,這樣的對像是放在table[0]中。
如果不為空，則調用int hash = hash(key.hashCode());這是hashmap的一個自定義的hash,在key.hashCode()基礎上進行二次hash
1 static int hash(int h) {  2         h ^= (h >>> 20) ^ (h >>> 12);  3         return h ^ (h >>> 7) ^ (h >>> 4);  4   }  得到hash碼之后就會通過hash碼去計算出應該存儲在數組中的索引，計算索引的函數如下：
1 static int indexFor(int h, int length) {  2        return h & (length-1);  3    }  　這個方法非常巧妙，它通過 h & (table.length -1) 來得到該對象的保存位，而HashMap底層數組的長度總是 2 的n 次方，這是HashMap在速度上的優化。當length總是 2 的n次方時，h& (length-1)運算等價于對length取模，也就是h%length，但是&比%具有更高的效率。當數組長度為2的n次冪的時候，不同的key算得得index相同的幾率較小，那么數據在數組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。
下面我們繼續回到put方法里面，前面已經計算出索引的值了，看到第6到14行，如果數組中該索引的位置的鏈表已經存在key相同的對象，則將其覆蓋掉并返回原先的值。如果沒有與key相同的鍵，則調用addEntry方法創建一個Entry對象，addEntry方法如下：
1 void addEntry(int hash, K key, V value, int bucketIndex) {2         Entry<K,V> e = table[bucketIndex]; //如果要加入的位置有值，將該位置原先的值設置為新entry的next,也就是新entry鏈表的下一個節點3         table[bucketIndex] = new Entry<>(hash, key, value, e);4         if (size++ >= threshold) //如果大于臨界值就擴容5             resize(2 * table.length); //以2的倍數擴容6     }參數bucketIndex就是indexFor函數計算出來的索引值，第2行代碼是取得數組中索引為bucketIndex的Entry對象，第3行就是用hash、key、value構建一個新的Entry對象放到索引為bucketIndex的位置，并且將該位置原先的對象設置為新對象的next構成鏈表。
　　第4行和第5行就是判斷put后size是否達到了臨界值threshold，如果達到了臨界值就要進行擴容，HashMap擴容是擴為原來的兩倍。resize()方法如下：
 1 void resize(int newCapacity) { 2         Entry[] oldTable = table; 3         int oldCapacity = oldTable.length; 4         if (oldCapacity == MAXIMUM_CAPACITY) { 5             threshold = Integer.MAX_VALUE; 6             return; 7         } 8  9         Entry[] newTable = new Entry[newCapacity];10         transfer(newTable);//用來將原先table的元素全部移到newTable里面11         table = newTable;  //再將newTable賦值給table12         threshold = (int)(newCapacity * loadFactor);//重新計算臨界值13     }擴容是需要進行數組復制的，上面代碼中第10行為復制數組，復制數組是非常消耗性能的操作，所以如果我們已經預知HashMap中元素的個數，那么預設元素的個數能夠有效的提高HashMap的性能。