java集合框架08——HashMap和源碼分析
1.HashMap簡介
首先看一下HashMap的繼承關系
java.lang.Object
? java.util.AbstractMap
? java.util.HashMap
public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable { }
我們可以看出，HashMap不僅繼承了AbstractMap，而且實現了Map、Cloneable和Serializable接口，所以HashMap也可以序列化。另外，HashMap是非同步的，但是我們可以通過Collections類的靜態方法synchronizedMap獲得線程安全的HashMap。即：
Map map = Collections.synchronizedMap(new HashMap());
下面先總覽一下HashMap都有哪些API，然後我們詳細分析它們。
void clear()
Object clone()
boolean containsKey(Object key)
boolean containsValue(Object value)
Set> entrySet()
V get(Object key)
boolean isEmpty()
Set keySet()
V put(K key, V value)
void putAll(Map map)
V remove(Object key)
int size()
Collection values()
2.HashMap的數據結構
2.1存儲結構
HashMap存儲數據的數組定義如下，裡面存放的是Entry實體：
transient Entry[] table
HashMap的底層主要是基於數組合練不來實現的，它之所以有相當快的查詢速度主要是因為它是通過計算散列碼來決定存儲位置的。HashMap中主要是通過key的hashCode來計算hash值，然後通過hash值選擇不同的數組來存儲。只要hashCode相同，計算出來的hash值就一樣，如果存儲對象多了，就有可能不同的對象計算出來的hash值是相同的，這就出現了所謂的hash沖突，解決hash沖突的方法很多。HashMap的底層是通過鏈表來解決hash沖突的。下面看一下它的存儲結構圖：
圖中紫色部分代表哈希表，其實就是哈希數組，數組的每個元素都是一個單鏈表的頭結點，鏈表是用來解決hash沖突的，如果不同的key映射到了數組的同一位置，那麼就將其放入單鏈表中。下面的圖可能在代碼的角度更能說明問題：
下面我們閱讀一下數組中存儲的Entry實體類源碼。
2.2Entry實體
/**
* Entry其實是個單向鏈表：它是“HashMap鏈式存儲法”對應的鏈表。
* 它實現了Map.Entry接口，也就是實現了getKey()、getValue()、setValue(V value)
* equals(Object o)和hashCode()這些方法。
**/
static class Entry implements Map.Entry {
final K key;
V value;
Entry next; //指向下一個節點
int hash;
/**
* 構造方法，創建一個Entry
* 參數：哈希值h，鍵值k，值v和下一個節點n
*/
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//判斷兩個Entry是否相等，必須key和value都相等，才返回true
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() { //實現hashCode
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* 當向HashMap中添加元素時，即調用put(k,v)時，
* 對已經在HashMap中k位置進行v的覆蓋時，會調用此方法
* 這裡沒做任何處理
*/
void recordAccess(HashMap m) {
}
/**
* 當從HashMap中刪除了一個Entry時，會調用該函數
* 這裡沒做任何處理
*/
void recordRemoval(HashMap m) {
}
}
從Entry實體源碼中可以看出，HashMap其實就是一個存儲Entry的數組，Entry對象包含了鍵和值，其中next也是一個Entry對象，用來處理hash沖突的，形成一個鏈表。這樣一來，我們對HashMap就有很好的理解了。下面我們詳細分析HashMap中的源碼。
3. HashMap源碼分析
之前分析源碼都是將所有源碼全部貼上來，然後分析部分放到源碼內部，這樣看起來有點太多，一下子好幾百行源碼看的有點懵。這章開始采用分段式分析，將源碼分分類，然後各部分突破，這樣看起來更加清晰明朗。
3.1成員屬性
先看看HashMap的幾個關鍵屬性：
//默認初始容量是16，必須是2的冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量（必須是2的冪且小於2的30次方，傳入容量過大會被這個值替換）
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認加載因子，所謂加載因子是指哈希表在其容量自動增加之前可以達到多滿的一種尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//存儲Entry的默認空數組
static final Entry[] EMPTY_TABLE = {};
//存儲Entry的數組，長度為2的冪。HashMap采用拉鏈法實現的，每個Entry的本質是個單向鏈表
transient Entry[] table = (Entry[]) EMPTY_TABLE;
//HashMap的大小，即HashMap存儲的鍵值對數量
transient int size;
//HashMap的阈值，用於判斷是否需要調整HashMap的容量
int threshold;
//加載因子實際大小
final float loadFactor;
//HashMap被修改的次數，用於fail-fast機制
transient int modCount;
我們主要來看看loadFactor屬性，loadFactor表示Hash表中元素的填滿程度。
若加載因子設置過大，則填滿的元素越多，無疑空間利用率變高了，但是沖突的機會增加了，沖突的越多，鏈表就會變得越長，那麼查找效率就會變得更低；
若加載因子設置過小，則填滿的元素越少，那麼空間利用率變低了，表中數據將變得更加稀疏，但是沖突的機會減小了，這樣鏈表就不會太長，查找效率變得更高。
這看起來有點繞口，我舉個簡單的例子，如果數組容量為100，加載因子設置為80，即裝滿了80個才開始擴容，但是在裝的過程中，可能有很多key對應相同的hash值，這樣就會放到同一個鏈表中（因為沒到80個不能擴容），這樣就會導致很多鏈表都變得很長，也就是說，不同的key對應相同的hash值比數組填滿到80個更加容易出現。
但是如果設置加載因子為10，那麼數組填滿10個就開始擴容了，10個相對來說是很容易填滿的，而且在10個內出現相同的hash值概率比上面的情況要小的多，一旦擴容之後，那麼計算hash值又會跟原來不一樣，就不會再沖突了，這樣保證了鏈表不會很長，甚至就一個表頭都有可能，但是空間利用率很低，因為始終有很多空間沒利用就開始擴容。
因此，就需要在“減小沖突”和“空間利用率”之間尋找一種平衡，這種平衡就是數據結構中有名的“時-空”矛盾的平衡。如果機器內存足夠，並且想要提高查詢速度的話可以將加載因子設置小一點；相反如果機器內存緊張，並且對查詢速度沒什麼要求的話可以將加載因子設置大一點。一般我們都使用它的默認值，即0.75。
3.2構造方法
下面看看HashMap的幾個構造方法：
/************************** 構造函數 *******************************/
public HashMap(int initialCapacity, float loadFactor) {//帶有初始容量和加載因子
//確保容量數字合法
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//將阈值設置為初始容量，這裡不是真正的阈值，是為了擴展table的，後面這個阈值會重新計算
threshold = initialCapacity;
init();//一個空方法用於未來的子對象擴展
}
public HashMap(int initialCapacity) { //帶有初始容量，加載因子設為默認值
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() { //初始容量和加載因子均為默認值
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//構造一個映射關系與指定 Map 相同的新 HashMap
public HashMap(Map m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
我們可以看到，在構造HashMap的時候，如果我們指定了加載因子和初始容量的話就調用第一個構造方法，否則就用默認的。默認的初始容量為16加載因子為0.75。
3.3存取方法
存取部分重點分析一下put和get方法，因為這兩個方法也是最常用的。其他的存取方法，我放到代碼中分析。首先看看HashMap中是如何存儲數據的，看put方法：
public V put(K key, V value) {
if (table == EMPTY_TABLE) { //如果哈希表沒有初始化(table為空)
inflateTable(threshold); //用構造時的阈值(其實就是初始容量)擴展table
}
//如果key==null，就將value加到table[0]的位置
//該位置永遠只有一個value，新傳進來的value會覆蓋舊的value
if (key == null)
return putForNullKey(value);
int hash = hash(key); //根據鍵值計算hash值
int i = indexFor(hash, table.length); //搜索指定hash在table中的索引
//循環遍歷Entry數組，若該key對應的鍵值對已經存在，則用新的value取代舊的value
for (Entry 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; //並返回舊的value
}
}
modCount++;
//如果在table[i]中沒找到對應的key，那麼就直接在該位置的鏈表中添加此Entry
addEntry(hash, key, value, i);
return null;
}
我們下面一步步分析put方法內部都干了些啥：
首先檢測table是不是為空table，如果是空table，說明並沒有給table初始化，所以調用inflateTable(threadshold)方法給table初始化。該方法如下：
//擴展table
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize); //獲取和toSize最接近的2的冪作為容量
//重新計算阈值 threshold = 容量 * 加載因子
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity]; //用該容量初始化table
initHashSeedAsNeeded(capacity);
}
//將初始容量轉變成2的冪
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY //如果容量超過了最大值，設置為最大值
//否則設置為最接近給定值的2的次冪數
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
在inflateTable方法內，首先初始化數組容量大小，數組容量永遠是2的冪（下面會分析為什麼要這樣）。所以調用roundUpToPowerOf2方法將傳進來的容量轉換成最接近2的次冪的值，然後重新計算阈值threadshold =容量 x加載因子，最後初始化table。所以剛開始初始化table不是在HashMap的構造函數裡，因為構造函數中僅僅簡單的將傳進去的容量作為阈值。真正初始化table是在第一次往HashMap中put數據的時候。
初始化好了table後，就開始往table中存入數據了，table中存的是Entry實體，而put方法傳進來的是key和value，所以接下來要做兩件事：
1.找到table數組中要存入的位置；
2.將key和value封裝到Entry中存入。
我們再回到put方法中，先來分析第一步，找存儲的位置就要依靠key的值了，因為需要用key的值來計算hash值，根據hash值來決定在table中的位置。首先當key為null時，調用putForNullKey方法，該方法內部實現如下：
//傳進key==null的Entry
private V putForNullKey(V value) {
for (Entry 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++;
//如果table[0]處沒有key為null
addEntry(0, null, value, 0);//如果鍵為null的話，則hash值為0
return null;
}
從方法中可以看出，null的hash值為0，所以首先會定位到table[0]處，然後依次查詢是否有key==null的鍵，如果有，將對應的value用新的value值取代，同時返回舊的value值。如果沒有key==null的鍵，那麼調用addEntry方法，將空鍵和值封裝到Entry中放到table[0]的位置，addEntry方法如下：
//向HashMap中添加Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //擴容2倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
//創建一個Entry
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];//先把table中該位置原來的Entry保存
//在table中該位置新建一個Entry，將原來的Entry掛到該Entry的next
table[bucketIndex] = new Entry<>(hash, key, value, e);
//所以table中的每個位置永遠只保存一個最新加進來的Entry，其他Entry是一個掛一個，這樣掛上去的
size++;
}
從該方法中可以看出，第一個參數是hash值，中間兩個是key和value，最後一個是插入table的索引位置。插入之前先判斷容量是否足夠，若不夠，HashMap中是2倍擴容。若夠了，addEntry中先計算hash值，然後通過調用indexFor方法返回在索引的位置，這兩個方法如下：
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// 預處理hash值，避免較差的離散hash序列，導致table沒有充分利用
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//這個方法有點意思，也是為什麼容量要設置為2的冪的原因
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
indexFor方法返回索引的位置，裡面只做了一件事：h & (length-1)。這究竟做了什麼？為什麼這句能解釋容量必須為2的冪呢？我們詳細分析下：
首先，h & (length-1)相當於h & length，但是h % length效率比較低（HashTable中是這兒干的）。為啥h & (length-1)相當於h % length呢？現在假設length為2的冪，那麼length就可以表示成100......00的形式（表示至少1個0），那麼length-1就是01111....11。對於任意小於length的數h來說，與01111...11做&後都是h本身，對於h=length來說，&後結果為0，對於大於length的數h，&過後相當於h-j*length，也就是h % length。這也就是為啥容量必須為2的冪了，為了優化，好做&運算，效率高。
其次，length為2的次冪的話，是偶數，這樣length-1為奇數，奇數的最後一位是1，這樣便保證了h & (length-1)的最後一位可能為0也可能為1（取決於h的值），即結果可能為奇數，也可能為偶數，這樣便可以保證散列的均勻性，即均勻分布在數組table中；而如果length為奇數的話，很明顯length-1為偶數，它的最後一位是0，這樣h & (length-1)的最後一位肯定為0，級只能為偶數，這樣任何hash值都會被映射到數組的偶數下標位置上，這便浪費了近一半的空間！因此，length去2的整數次冪，也是為了使不同hash值發生碰撞的概率較小，這樣就能使元素在哈希表中均勻的散列。
再回到addEntry方法中，接下來就調用createEntry方法在table數組適當的位置開創一個Entry了，new Entry的時候，將next置為原本在該位置的Entry即可，這樣，原來的Entry就掛到現在的Entry上了，以後只要在該位置新new一個Entry，就將原來的掛上去，這樣一個掛一個，形成了一個鏈表。但是table中永遠存儲的是最新的Entry，並非一個真正的鏈表數據結構，只是這麼多Entry是一個個連在一起的，跟鏈表很像而已。
現在往上回到put方法，我們剛剛分析完了key==null的情況，接著往下走，下面其實跟剛剛分析的一樣了，先計算hash值，然後找到在table中的位置，然後開始判斷是否已經有相同的key的Entry放在那了，如果有，用新的value取代舊的value，如果沒有，用傳進來的key和value新new一個Entry放到table中，並與原來的Entry掛上。過程跟上面分析的一模一樣，唯一不同的就是key!=null。這裡就不再贅述了。
分析了put方法，看get方法應該很容易理解了。下面再看看HashMap中讀取數據的get方法：
public V get(Object key) {
if (key == null)
return getForNullKey(); //hey==null時，從table[0]中取
Entry entry = getEntry(key);//key!=null->getEntry
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;//從table[0]中取key==null的value值
}
return null;
}
final Entry getEntry(Object key) {
if (size == 0) {
return null;
}
//取值與上面put中傳值相反
int hash = (key == null) ? 0 : hash(key);
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 如果hash值相等，並且key相等則證明這個桶裡的東西是我們想要的
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
