一笛求、集合框架源碼分析
- 集合框架 （第 01 篇） 源碼分析：Collection<E> 框架總覽
- 集合框架 （第 02 篇） 源碼分析：Map<K,V > 框架總覽
- 集合框架 （第 03 篇） 源碼分析：ArrayList<E>
- 集合框架 （第 04 篇） 源碼分析：LinkedList
- 集合框架 （第 05 篇） 源碼分析：Map<K, V>接口與其內(nèi)部接口Entry<K,V>
- 集合框架 （第 06 篇） 源碼分析：哈希沖突(哈希碰撞)與解決算法
- 集合框架 （第 07 篇） 源碼分析：jdk1.7版 HashMap
- 集合框架 （第 08 篇） 源碼分析：HashMap祖乳、Hashtable、ConcurrentHashMap之間的區(qū)別
- 集合框架 （第 09 篇） 源碼分析：jdk1.7版 ConcurrentHashMap
- 集合框架 （第 10 篇） 源碼分析：二叉樹周霉、平衡二叉樹、二叉查找樹樱拴、AVL樹、紅黑樹
- 集合框架 （第 11 篇） 源碼分析：jdk1.8版 HashMap
- 集合框架 （第 12 篇） 源碼分析：jdk1.8版 ConcurrentHashMap
- 集合框架 （第 13 篇） 源碼分析：LinkedHashMap
- 集合框架 （第 14 篇） 源碼分析：TreeMap
- 集合框架 （第 15 篇） 源碼分析：Set<E> 集合
- 集合框架 （第 16 篇） 源碼分析：BlockingQueue 接口
- 集合框架 （第 17 篇） 源碼分析：CopyOnWriteArrayList 與 CopyOnWriteArraySet
原文持續(xù)更新鏈接: https://github.com/about-cloud/JavaCore
正文
本文是基于
jdk1.7.0_79分析
一难述、繼承關(guān)系
HashMap1.7vExtend
二踩身、數(shù)據(jù)結(jié)構(gòu)
jdk1.7HashMap的底層數(shù)據(jù)結(jié)構(gòu)：數(shù)組 + 單向線性鏈表胀茵。HashMap的元素就是在 Map.Entry 的基礎(chǔ)上實現(xiàn)的Entry項。
上一節(jié)分析了 哈希沖突 和 解決哈希沖突的算法挟阻，HashMap 就是基于 鏈表法 來解決哈希沖突的琼娘。
jdk1.7 HashMap圖片
重要屬性（請記住這些常量和變量的含義，下面源碼分析會用到）
/** 默認初始容量 16 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 既 16
/** 最大容量 10.7億+（這里也用到效率高的位運算） */
static final int MAXIMUM_CAPACITY = 1 << 30;
/** 默認負載因子 0.75 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** 當(dāng) table 未填充的時候赁濒，共享這個空table */
static final Entry<?,?>[] EMPTY_TABLE = {};
/** （這個表又稱為基本表）該 table 根據(jù)需要而調(diào)整大小轨奄。長度必須始終是2的次冪。 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/** map 中 存儲 key-value 映射的數(shù)量 */
transient int size;
/** 下次調(diào)整大小時的閾值(容量 * 負載因子) */
int threshold;
/** 哈希表的負載因子 */
final float loadFactor;
/** 此 HashMap 修改的次數(shù) */
transient int modCount;
/** 默認容量的最大值：Integer.MAX_VALUE */
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
HashMap 重點元素 項Entry<K, V>：之前文章已講解了 Map.Entry 接口拒炎，下面就來分析一下 jdk1.7 HashMap實現(xiàn)Map.Entry 的 Entry<K, V>：
static class Entry<K,V> implements Map.Entry<K,V> {
// final 修飾的 key挪拟，防止被重復(fù)賦值
final K key;
// 可被重復(fù)設(shè)置值的value
V value;
// 此項的下一項(用于鏈表。并沒有類四的 Entry<K, V> prev击你，說名是單鏈表)
Entry<K,V> next;
int hash;
/**
* 構(gòu)造方法用于注入 entry項 的屬性值(或引用)
* 參數(shù)從左至右依次是：key的哈希碼玉组，key，value丁侄，指向的下一個entry
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
// getter & toString 方法
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final String toString() {
return getKey() + "=" + getValue();
}
// 設(shè)置節(jié)點的新值value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 比較節(jié)點的方法
public final boolean equals(Object o) {
// 檢查類型
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
// 當(dāng)前項的key
Object k1 = getKey();
// 被比較對象的key
Object k2 = e.getKey();
// 這里說明一下 Object惯雳，它的 equals方法很簡單，就是用 == 來做判斷的
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;
}
// 返回節(jié)點的哈希碼
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
/**
* 當(dāng)entry被訪問時鸿摇，都會調(diào)用此方法
* 這里只不過是一個空方法
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* 每當(dāng)entry項從表格中刪除時石景，都會調(diào)用這個空方法
*/
void recordRemoval(HashMap<K,V> m) {
}
}
三、添加元素項
public V put(K key, V value) {
// 判斷是否為空表
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
// 如果key為null的情況下拙吉，將將鍵值對放在table[0]處
// 如果table[0]已存在元素潮孽，則將替換value
return putForNullKey(value);
// key的哈希值
int hash = hash(key);
// 可以的哈希碼對表的長度模運算，計算并得到哈希槽的位置
int i = indexFor(hash, table.length);
// 對哈希桶（鏈表）進行遍歷筷黔，靠指針地址移動
// 查找是否包含key的項往史，如果包含就將value換掉
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 該元素的哈希碼與新增項的key的哈希碼項相等，并且 key 也相同
// 那么就會替換 value(因為key具有唯一性佛舱，相同的key要替換value)
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 被替換的舊值
V oldValue = e.value;
// 選用新的value
e.value = value;
// 調(diào)用上面的空方法
e.recordAccess(this);
// 返回舊值
return oldValue;
}
}
// 如果上面for循環(huán)沒有查找到key的存在（或者說沒有找到相同的key）椎例，那么就新添加一項
modCount++; // modCount加1
// 添加entry項
addEntry(hash, key, value, i);
return null;
}
/**
* 將具有指定key挨决、value、key的哈希碼订歪、桶號(也就是哈希槽的位置)的條目(元素)(項)
* 添加到指定的桶(哈希桶)脖祈。
* 此方法會在適當(dāng)?shù)那闆r下調(diào)整桶的大小
* 子類也可以重寫此方法來改變put添加的行為
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果已添加元素項的實際大小達到了HashMap所承載的閾值，并且哈希槽的位置不為空
// 那么就進行擴容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 擴容后的大小是2倍于原基本表的長度
resize(2 * table.length);
// 因為基本表已經(jīng)擴容刷晋，那么對key重新計算哈希值
// 如果 key 不為 null 那么計算key的哈希值撒犀，否則哈希值直接記為0
hash = (null != key) ? hash(key) : 0;
// 根據(jù)哈希碼和基本表(數(shù)組)長度計算桶號
// indexFor 方法并沒有使用模運行，而是使用高性能的邏輯與&運算
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
創(chuàng)建元素項的方法：
/**
* 此方法與 addEntry 不同掏秩，只有在創(chuàng)建 entry項的時候使用此方法
* 作為構(gòu)建(或偽構(gòu)建) Map 的一部分或舞。"偽構(gòu)建" 是指 克隆、反序列蒙幻。
* 使用此方法是不必擔(dān)心擴容問題映凳。
* 子類可以重新此方法改變方法的功能，比如將單向鏈表改成雙向鏈表等等邮破。
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
// 原位置的元素項要下沉诈豌，新的元素放在哈希槽(桶頂)的位置
Entry<K,V> e = table[bucketIndex];
// 構(gòu)造新的元素項放在哈西槽（桶頂），同步把原有的元素項鏈入其后
table[bucketIndex] = new Entry<>(hash, key, value, e);
// 實際大小加1
size++;
}
鏈表的時候講要添加的元素項放到桶頂抒和，那么先進的元素項位于鏈表的尾部矫渔，后進的元素項位于鏈表的頭部。（這只是本版本
HashMap的實現(xiàn)方式）
HashMap解決哈希沖突
擴容機制
/**
* 擴容方法就是給 map 換一個更大容量的新數(shù)組摧莽。
* 前提前提條件是已添加元素項的實際大小達到了HashMap所承載的閾值庙洼。
*
* 如果當(dāng)前容量達到最大容量, 此方法也能給map擴容。但是可以設(shè)置閾值為Integer類型的最大值镊辕。
*
* @param newCapacity 新的容量, 必須是2的次冪;
* 必須大于當(dāng)前容量油够，除非當(dāng)前容量達到了最大值。
* （在這種情況下值是無關(guān)緊要的）
*/
void resize(int newCapacity) {
// 當(dāng)前table數(shù)組
Entry[] oldTable = table;
// 當(dāng)前table數(shù)組長度
int oldCapacity = oldTable.length;
// 如果當(dāng)前數(shù)組達到了最大容量（1<<30）征懈，那么賦值閾值為Integer的最大值石咬，并直接返回??
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// new 新的數(shù)組
Entry[] newTable = new Entry[newCapacity];
// 將當(dāng)前的數(shù)組上索引元素項轉(zhuǎn)移到新的數(shù)組上
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 當(dāng)前數(shù)組指向新數(shù)組，完成擴容
table = newTable;
// 計算閾值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* 將當(dāng)前的數(shù)組上索引元素項轉(zhuǎn)移到新的數(shù)組上
*/
void transfer(Entry[] newTable, boolean rehash) {
// 新數(shù)組的長度(容量)
int newCapacity = newTable.length;
// 首先橫向遍歷數(shù)組
for (Entry<K,V> e : table) {
// 然后縱向遍歷鏈表
while(null != e) {
// 鏈表中提前獲取下一個元素項(節(jié)點)
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 重新計算存放元素
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
上面已經(jīng)看出每次擴容時都伴隨著所有元素項的重新 選址 存放卖哎，這不僅大大犧牲性能鬼悠，而且耗時。所以在使用 HashMap 一定要評估存放元素項的數(shù)量亏娜，指定map的大小焕窝。
四、刪除元素項
刪除元素項的的思路基本和添加操作相似照藻，只不過一個是添加袜啃，一個是刪除汗侵。先根據(jù)
key計算哈希槽(桶的位置)幸缕，然后循環(huán)鏈表比較判斷群发，這里參考:telescope:之前關(guān)于LinkedList文章的刪除節(jié)點操作吧。
其他問題
為什么 HashMap 的容量必須是2的次冪呢发乔？
key的哈希碼對 基本表 做 邏輯與 運算 h&(length-1)熟妓，來確定此元素項的數(shù)組上的位置。 原因就出在 二進制 的 與& 操作上了栏尚。與& 運算規(guī)則：
0&0=0;0&1=0;1&0=0;1&1=1;
| （指數(shù)形式）length | （十進制）length | （十進制）length - 1 | （二進制）length - 1 |
|---|---|---|---|
| 2 | 1 | 1 | |
| 4 | 3 | 11 | |
| 8 | 7 | 111 | |
| 16 | 15 | 1111 | |
| ... | ... | ... |
這種情況下起愈，
length - 1二進制的 最右位 永遠是1。這樣0 & 1 = 0译仗，1 & 1 = 1的結(jié)果既有0又有1抬虽。對于 哈希槽 的二進制最右位為1（十進制的奇數(shù)）的位置就有可能被填充，而不至于浪費存儲空間纵菌。如果
HashMap的容量不是2的次冪阐污，比如 容量length為19，length - 1的二進制為10010咱圆，任何常數(shù)與之作 與& 運算笛辟，二進制最右位都是0，那么只能存放 （十進制）尾數(shù)為偶數(shù)的數(shù)組位置序苏，這樣會大大浪費空間手幢。
