Java集合源码学习（四）HashMap
?一、數組、鏈表和哈希表結構
數據結構中有數組和鏈表來實現對數據的存儲，這兩者有不同的應用場景，
數組的特點是：尋址容易，插入和刪除困難；鏈表的特點是：尋址困難，插入和刪除容易；
哈希表的實現結合了這兩點，哈希表的實現方式有多種，在HashMap中使用的是鏈地址法，也就是拉鏈法。
拉鏈法實際上是一種鏈表數組的結構，由數組加鏈表組成，在這個長度為16的數組中（HashMap默認初始化大小就是16），每個元素存儲的是一個鏈表的頭結點。
通過元素的key的hash值對數組長度取模，將這個元素插入到數組對應位置的鏈表中。
例如在圖中，337%16=1，353%16=1，于是將其插入到數組位置1的鏈表頭結點中。
二、關于HashMap
（1）繼承和實現
繼承AbstractMap抽象類，Map的一些操作在AbstractMap里已經提供了默認實現，
實現Map接口，可以應用Map接口定義的一些操作，明確HashMap屬于Map體系，
Cloneable接口，表明HashMap對象會重寫java.lang.Object#clone()方法，HashMap實現的是淺拷貝（shallow copy），
Serializable接口，表明HashMap對象可以被序列化
（2）內部數據結構
HashMap的實際數據存儲在Entry類的數組中，
上面說到HashMap的基礎就是一個線性數組，這個數組就是Entry[]。
再來看一下Entry這個內部靜態類，
static class Entry<K,V> implements Map.Entry<K,V> {final K key;//Key-value結構的keyV value;//存儲值Entry<K,V> next;//指向下一個鏈表節點final int hash;//哈希值/*** Creates new entry.*/Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;}......}（3）線程安全
HashMap是非同步的，即線程不安全，在多線程條件下，可能出現很多問題，
1.多線程put后可能導致get死循環，具體表現為CPU使用率100%（put的時候transfer方法循環將舊數組中的鏈表移動到新數組）
2.多線程put的時候可能導致元素丟失（在addEntry方法的new Entry<K,V>(hash, key, value, e)，如果兩個線程都同時取得了e,則他們下一個元素都是e，然后賦值給table元素的時候有一個成功有一個丟失）
關于HashMap線程安全性更多的了解參考相關的網上資源，這里不多敘述。
需要線程安全的哈希表結構，可以考慮以下的方式：
使用Hashtable 類，Hashtable?是線程安全的；
使用并發包下的java.util.concurrent.ConcurrentHashMap，ConcurrentHashMap實現了更高級的線程安全；
或者使用synchronizedMap() 同步方法包裝 HashMap object，得到線程安全的Map，并在此Map上進行操作。
如：
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {return new SynchronizedMap<>(m);}
三、常用方法
（1）Map接口定義的方法
HashMap可以應用所有Map接口定義的方法：
public interface Map<K,V> {public static interface Entry<K,V> {//獲取該Entry的key public abstract Object getKey();//獲取該Entry的valuepublic abstract Object getValue();//設置Entry的value public abstract Object setValue(Object obj);public abstract boolean equals(Object obj);public abstract int hashCode();}//返回鍵值對的數目 int size();//判斷容器是否為空 boolean isEmpty();//判斷容器是否包含關鍵字key boolean containsKey(Object key);//判斷容器是否包含值value boolean containsValue(Object value);//根據key獲取value Object get(Object key);//向容器中加入新的key-value對 Object put(Object key, Object value);//根據key移除相應的鍵值對 Object remove(Object key);//將另一個Map中的所有鍵值對都添加進去 void putAll(Map<? extends K, ? extends V> m);//清除容器中的所有鍵值對 void clear();//返回容器中所有的key組成的Set集合 Set keySet();//返回所有的value組成的集合 Collection values();//返回所有的鍵值對 Set<Map.Entry<K, V>> entrySet();//繼承自Object的方法boolean equals(Object obj);int hashCode(); }（2）構造方法
HashMap使用Entry[] 數組存儲數據，
另外維護了兩個非常重要的變量：initialCapacity（初始容量）、loadFactor（加載因子）。
初始容量就是初始構造數組的大小，可以指定任何值，
但最后HashMap內部都會將其轉成一個大于指定值的最小的2的冪，比如指定初始容量12，但最后會變成16，指定16，最后就是16。
加載因子是控制數組table的飽和度的，默認的加載因子是0.75，
也就是數組達到容量的75%，就會自動的擴容。
另外，HashMap的最大容量是2^30，
static final int MAXIMUM_CAPACITY = 1 << 30;
默認的初始化大小是16，
static final int DEFAULT_INITIAL_CAPACITY = 16;
HashMap提供了四種構造方法，可以使用默認的容量等進行初始化，
也可以顯式制定大小和加載因子，還可以使用另外的map進行構造和初始化。
?
四、解決哈希沖突的辦法
（1）什么是哈希沖突
理論上哈希函數的輸入域是無限的，優秀的哈希函數可以將沖突減少到最低，但是卻不能避免，下面是一個典型的哈希沖突的例子：
用班級同學做比喻，現有如下同學數據
張三，李四，王五，趙剛，吳露.....
假如我們編址規則為取姓氏中姓的開頭字母在字母表的相對位置作為地址，則會產生如下的哈希表
| 位置 | 字母 | 姓名 | ? |
| 0 | a | ? | ? |
| 1 | b | ? | ? |
| 2 | c | ? | ? |
...
| 10??? | L???? | 李四 | ? |
...
| 22 | W | 王五，吳露 | ? |
..
| 25? | Z? | 張三，趙剛 | ? |
我們注意到，灰色背景標示的兩行里面，關鍵字王五，吳露被編到了同一個位置，關鍵字張三，趙剛也被編到了同一個位置。老師再拿號來找張三，座位上有兩個人，"你們倆誰是張三？"（這段描述很形象，引用自hash是如何處理沖突的?）
（2）解決哈希沖突的方法
常見的辦法開放定址法，再哈希法，鏈地址法以及建立一個公共溢出區等，這里只考察鏈地址法。
鏈地址法就是最開始我們提到的鏈表-數組結構，
將所有關鍵字為同義詞的記錄存儲在同一線性鏈表中。
?
五、源碼分析
（1）HashMap的存取實現
HashMap的存取主要是put和get操作的實現。
執行put方法時根據key的hash值來計算放到table數組的下標，
如果hash到相同的下標，則新put進去的元素放到Entry鏈的頭部。
get操作的實現：
public V get(Object key) {if (key == null)return getForNullKey();int hash = hash(key.hashCode());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;}
注意HashMap支持key=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;}}......}（2）哈希函數
下面看一下HashMap使用的哈希函數，源碼來自JDK1.6：
/*** 哈希函數* 看一下具體的操作，首先對h分別進行無符號右移20位和12位，* 然后對兩個值進行按位異或，最后再與h進行按位異或，* 得到新的h后再進行一次同樣的操作，分別右移7位和4位，具體的哈希函數優劣就不去研究了* 這個方法可以盡量減少碰撞*/static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}（3）再散列rehash過程
當哈希表的容量超過默認容量時，必須調整table的大小。
當容量已經達到最大可能值時，那么該方法就將容量調整到Integer.MAX_VALUE返回，這時，需要創建一個新的table數組，將table數組的元素轉移到新的table數組中。
?
/*** 再散列過程* 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.*/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);}/*** 把當前Entry[]表的全部元素轉移到新的table中*/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;int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;} while (e != null);}}}
參考?
Java HashMap的死循環?
Thinking in Java之HashMap源碼分析
hash是如何處理沖突的?
?
總結
以上是生活随笔為你收集整理的Java集合源码学习（四）HashMap的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ElasticSearch 2 (21)
- 下一篇： 解决Maven项目pom.xml文件报x