前面分析HashMap的put(K key,V value)源碼的時候發現，其中有兩個特殊的變量:
- size:該變量保存了該HashMap中所包含的key-value對的數量。
- threshold：該變量包含了HashMap能容納的key-value對的極限，它的值等於HashMap的容量乘以負載因子(load factor)。
在HashMap的addEntry方法中，當size++>=threshold時。HashMap會自動調用resize方法擴充HashMap的容量。但每擴充一次，HashMap的容量就增大一倍。
HashMap源碼中存在一個就table的數組。這個數組的長度其實就是HashMap的容量。HashMap包含如下幾個構造器:
- HashMap() 初始容量為16。負載因子為0.75的HashMap。
- HashMap(int initialCapacity) 構建一個初始容量為 initialCapacity，負載因子為0.75的HashMap
- HashMap(int initialCapacity,float loadFactor) 構建指定初始容量和負載因子的HashMap
當創建一個HasMap時，系統會自動創建一個table數組來保存HashMap中的Entry。
觀察構造器的源碼:
//以指定初始化容量，負載因子創建HashMap
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能為負數
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量不能太大
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//負載因子必須大於0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//計算出大於initialCapacity的最小的2的n次方值
int capacity = 1;
while(capacity<initialCapacity)
capacity<<=1;
this.loadFacotor = loadFactor;
//設置容量極限等於容量乘以負載因子
threshold = (int)(capacity * loadFactor);
//初始化table數組
table = new Entry(capacity);
init();
}
注意觀察下面這兩段代碼:
int capacity = 1;
while(capacity<initialCapacity)
capacity<<=1;找出大於initialCapacity的，最小的2的n次方值，並將其作為HashMap的實際容量。例如給定initialCapacity為10，那麼HashMap的實際容量就是16。通常來說，HaspMap最後的實際容量通常比initialCapacity大一點，除非它剛好是2的n次方，所以我們在創建HaspMap需要指定容量時指定為2的n次方可以減少不必要的開銷。
補充:
<< 把數據向左移動。移除的刪除，右邊用0補齊 相當於乘以2的移動次冪 >> 把數據向右移動。移除的刪除 ，左邊用最高位補齊 相當於除以2的移動次冪
對於HashMap及其子類而言，它們采用Hash算法來決定集合中元素的存儲位置。當系統開始初始化HashMap時，系統會創建一個長度為Capacity的Entry的數組。這個數組裡可以存儲元素的位置被稱為”桶(bucket)”，每個bucket都有其特定的索引，系統可以根據其索引快速訪問該bucket裡存儲的元素。
一般情況下，bucket裡存儲的是單個Entry，但也有會生成Entry鏈的情況(即兩個key的hash值相同但equals返回false)。當bucket裡面存儲的是單個Entry，此時HaspMap性能最好。當程序需要根據key取出value時，只需要計算出key的hash值，再根據該hash值找出key在table數組中的索引，然後取出該索引處的Entry，最後返回該Entry的value即可。下面我們來看HashMapget(K key)的源碼:
public V get(Object key) {
//如果key是null。調用getForNullKey
if (key == null)
return getForNullKey();
//計算key的hash值
int hash = hash(key.hashCode());
//直接取出table數組中的指定索引處的值
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
//搜索下一個Entry
e = e.next) {
Object k;
//如果該Entry的key與被搜索key相同
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}從上面代碼可以看出，當HashMap的每個bucket裡只有一個Entry，HaspMap可以快速從bucket裡取出Entry。在發生”Hash沖突”的情況下，單個bucket裡存儲的不是一個Entry，而是Entry鏈，此時系統只能通過遍歷每個Entry，直到找到搜索的Entry為止。
總結一下:
- HaspMap在底層把一個KEy-Value當成一個整體Entry對象來處理。
- HaspMap底層通過一個Entry[]數組來保存所有的key-value對。
- 對於每一個要存儲的key-value，系統通過Hash算法確定其存儲位置。
- 當需要取出一個Entry時，也會根據Hash值來找到其在數組中存儲位置
再談負載因子loadFactor:
HaspMap有一個默認的負載因子值0.75。這是時間和空間成本上的一種折衷:
增大負載因子可以減少Hash表(就是那個Entry[]數組)所占用內存空間，但會增大查詢數據的時間開銷，而查詢是最頻繁的操作(HashMap的get()和put()都要查詢)
減少負載因子可以會提高數據查詢的性能，但會增加Hash表所占用的內存空間。
現在我們合理的調整負載因子的值了。如果程序比較關心內存的開銷，適當增加負載因子。如果比較關心時間開銷，則適當減小負載因子，其實大部分情況下保持負載因子默認的0.75即可。
多線程環境下，使用HashMap進行put操作引起的問題分析
在多線程的環境下，多個線程對HashMap數據進行put操作時會導致死循環。而造成這個原因的罪魁禍首就是因為HashMap的自動擴容機制。
我們來觀察HashMap的put過程
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//當key為null，調用putForNullKey來處理
if (key == null)
return putForNullKey(value);
//根據key的hashCode計算hash值
int hash = hash(key);
//搜索制定hash值在對於table中的索引
int i = indexFor(hash, table.length);
//如果i處索引不為null。則通過循環不斷遍歷e元素的下一個元素
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//找到指定key與需要放入key相等(即兩者hash值相同，equals返回true)
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//如果i索引處的entry為null。表明此次沒有entry。直接插入在此次即可
modCount++;
//添加key，value到索引i處
addEntry(hash, key, value, i);
return null;
} 現在我們可以看出:當程序試圖將一個key-value對放入HashMap中時，首先根據key的hashCode()返回值決定該Entry的存儲位置，如果兩個key的hash值相同，那麼它們的存儲位置相同。如果這個兩個key的equalus比較返回true。那麼新添加的Entry的value會覆蓋原來的Entry的value，key不會覆蓋。如果這兩個equals返回false，那麼這兩個Entry會形成一個Entry鏈，並且新添加的Entry位於Entry鏈的頭部。
觀察addEntry(hash, key, value, i);源碼:
void addEntry(int hash, K key, V value, int bucketIndex) {
//獲取指定bucketIndex處的Entry
Entry<K,V> e = table[bucketIndex];
//將新創建的Entry放入bucketIndex索引處，並讓新Entry指向原來的Entry
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//如果Map中的key-value對的數量超過了極限
if(size++>=threshold){
//擴充table對象的長度到2倍
resize(2*table.length);
}
} 現在我們看罪魁禍首的resize方法的源碼:
void resize(int newCapacity)
{
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
......
//創建一個新的Hash Table
Entry[] newTable = new Entry[newCapacity];
//復制舊數據到新數組中:
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}復制舊數據到新數組中源碼:
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);
}
}
}畫了個圖做了個演示。
- 我假設了我們的hash算法就是簡單的用key mod 一下表的大小（也就是數組的長度）。
- 最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以後都沖突在table[1]這裡了。
- 接下來的三個步驟是Hash表 resize成4，然後所有的
<key,value>重新rehash的過程
多線程下的rehash:
1）假設我們有兩個線程。我用紅色和淺藍色標注了一下。
我們再回頭看一下我們的 transfer代碼中的這個細節：
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);而我們的線程二執行完成了。於是我們有下面的這個樣子。
注意，因為Thread1的 e 指向了key(3)，而next指向了key(7)，其在線程二rehash後，指向了線程二重組後的鏈表。我們可以看到鏈表的順序被反轉後。
2）線程一被調度回來執行。
先是執行 newTalbe[i] = e;
然後是e = next，導致了e指向了key(7)，
而下一次循環的next = e.next導致了next指向了key(3)
3）一切安好。
線程一接著工作。把key(7)摘下來，放到newTable[i]的第一個，然後把e和next往下移。
4）環形鏈接出現。
e.next = newTable[i] 導致 key(3).next 指向了 key(7)
注意：此時的key(7).next 已經指向了key(3)， 環形鏈表就這樣出現了。
於是，悲劇出現了。next不為null。陷入while死循環。
