摘要：前言本文的目的是閱讀理解的源碼，作為集合中重要的一個(gè)角色，平時(shí)用到十分多的一個(gè)類(lèi)，深入理解它，知其所以然很重要。
前言
本文的目的是閱讀理解HashMap的源碼，作為集合中重要的一個(gè)角色，平時(shí)用到十分多的一個(gè)類(lèi)，深入理解它，知其所以然很重要。本文基于Jdk1.7，因?yàn)镴dk1.8改變了HashMap的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行了優(yōu)化，我們先從基礎(chǔ)閱讀，之后再閱讀理解Jdk1.8的內(nèi)容
HashMap的特性
1.通過(guò)key-value的形式快速的存取元素
2.允許鍵為Null，但只允許有一個(gè)鍵的值為Null
3.線(xiàn)程不安全
4.底層結(jié)構(gòu)是Hash表，元素是無(wú)序的
5.再不考慮Hash沖突的時(shí)候，插入和查詢(xún)的復(fù)雜度是可以達(dá)到O（1）的
HashMap的數(shù)據(jù)結(jié)構(gòu)
底層數(shù)據(jù)結(jié)構(gòu)是一個(gè)Hash表，基于數(shù)組和鏈表，數(shù)組里面保存著一個(gè)單向鏈表的頭節(jié)點(diǎn)，單項(xiàng)鏈表保存著具有相同Hash值的不同元素，再不發(fā)生Hash沖突的情況下，鏈表應(yīng)該只有一個(gè)元素，這是最理想的狀態(tài)。
鏈表的數(shù)據(jù)結(jié)構(gòu)代碼
`
static class Entry implements Map.Entry {
final K key;
V value;
Entry next; // 下一個(gè)Entry對(duì)象的引用
int hash; // 其實(shí)就是key的hash值
}
HashMap的常量結(jié)構(gòu)
// 默認(rèn)初始化容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// HashMap允許的最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認(rèn)的負(fù)載率 75%
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 空的哈希表
static final Entry[] EMPTY_TABLE = {};
// 實(shí)際使用的哈希表
transient Entry[] table = (Entry[]) EMPTY_TABLE;
// HashMap的大小,即存儲(chǔ)的key-value的數(shù)量
transient int size;
// 擴(kuò)容的閥值，當(dāng)HashMap的size達(dá)到閥值時(shí)，就開(kāi)始擴(kuò)容 threshold=length*threshold
int threshold;
// 負(fù)載率
final float loadFactor;
// 修改次數(shù), 用于fail-fast機(jī)制
transient int modCount;
// 替代哈希使用的默認(rèn)擴(kuò)容閥值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
// 隨機(jī)的哈希種子, 有助于減少發(fā)生哈希碰撞的幾率
transient int hashSeed = 0;
HashMap的初始化
HashMap的初始化涉及到上面的多個(gè)常量，在了解完常量的作用之后，我們就可以理解HashMap的初始化思想，首先，HashMap并不是通過(guò)構(gòu)造函數(shù)來(lái)初始化的，構(gòu)造函數(shù)只是初始化HashMap的初始化參數(shù)，包括DEFAULT_INITIAL_CAPACITY ，loadFactor等，再初始化參數(shù)之后，真正的調(diào)用Put方法時(shí)，會(huì)判斷table 是否已經(jīng)初始化，沒(méi)有的話(huà)再根據(jù)參數(shù)進(jìn)行初始化。
put方法的流程我們這邊也要先理解：
（1）檢查哈希表是否是個(gè)空表，如果是空表就調(diào)用inflateTable方法進(jìn)行初始化
（2）判斷key是否為null，如果為null，就調(diào)用putForNullKey方法, 將key為null的key-value存儲(chǔ)在哈希表的第一個(gè)位置中
如果key不為null，則調(diào)用hash方法計(jì)算key的hash值
（3）根據(jù)hash值和Entry數(shù)組的長(zhǎng)度定位到Entry數(shù)組的指定槽位
（4）判斷Entry數(shù)組指定槽位的值e是否為null, 如果e不為null, 則遍歷e指向的單鏈表, 如果傳入的key在單鏈表中已經(jīng)存在了, 就進(jìn)行替換操作, 否則就新建一個(gè)Entry并添加到單鏈表的表頭位置
（5）如果e為null,?就新建一個(gè)Entry并添加到指定槽位
下面是代碼：
構(gòu)造方法
public HashMap(int initialCapacity, float loadFactor) {
// 如果初始容量小于0，則拋出異常
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
}
// 如果初始容量大于容量最大值，則使用最大值作為初始容量
if (initialCapacity > MAXIMUM_CAPACITY) { initialCapacity = MAXIMUM_CAPACITY; }
// 如果負(fù)載率小于等于0或負(fù)載率不是浮點(diǎn)數(shù)，則拋出異常
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
}
// 設(shè)置負(fù)載率
this.loadFactor = loadFactor;
// 設(shè)置閥值為初始容量
threshold = initialCapacity;
// 空實(shí)現(xiàn), 交由子類(lèi)實(shí)現(xiàn)
init();
}
//
初始化數(shù)組方法
private void inflateTable(int toSize) {
// 尋找大于toSize的,最小的,2的n次方作為新的容量
int capacity = roundUpToPowerOf2(toSize);
// 閥值=容量*負(fù)載因子, 如果容量*負(fù)載因子>最大容量時(shí), 閥值=最大容量
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 按新的容量創(chuàng)建一個(gè)新的數(shù)組
table = new Entry[capacity];
// 重新初始化hashSeed
initHashSeedAsNeeded(capacity);
}
put方法
public V put(K key, V value) {
// 如果哈希表沒(méi)有初始化就進(jìn)行初始化
if (table == EMPTY_TABLE) {
// 初始化哈希表
inflateTable(threshold);
}
// 當(dāng)key為null時(shí)，調(diào)用putForNullKey方法，保存null于table的第一個(gè)位置中，這是HashMap允許為null的原因
if (key == null) {
return putForNullKey(value);
}
// 計(jì)算key的hash值
int hash = hash(key);
// 根據(jù)key的hash值和數(shù)組的長(zhǎng)度定位到entry數(shù)組的指定槽位
int i = indexFor(hash, table.length);
// 獲取存放位置上的entry，如果該entry不為空，則遍歷該entry所在的鏈表
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
// 通過(guò)key的hashCode和equals方法判斷，key是否存在， 如果存在則用新的value取代舊的value，并返回舊的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 修改次數(shù)增加1
modCount++;
// 如果找不到鏈表 或者 遍歷完鏈表后，發(fā)現(xiàn)key不存在，則創(chuàng)建一個(gè)新的Entry，并添加到HashMap中
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//添加key到table[bucketIndex]位置，新的元素總是在table[bucketIndex]的第一個(gè)元素，原來(lái)的元素后移
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
//判斷元素個(gè)數(shù)是否達(dá)到了臨界值，若已達(dá)到臨界值則擴(kuò)容，table長(zhǎng)度翻倍
if (size++ >= threshold)
resize(2 * table.length);
}
HashMap的查
當(dāng)key值為Null的時(shí)候會(huì)進(jìn)行特殊處理，在table[0]的鏈表上查找Key為null的元素，get的過(guò)程是：
（1）計(jì)算hash與table.length取模計(jì)算index值
（2）遍歷table[index]上的鏈表，直到找到key
void addEntry(int hash, K key, V value, int bucketIndex) {
//添加key到table[bucketIndex]位置，新的元素總是在table[bucketIndex]的第一個(gè)元素，原來(lái)的元素后移
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
//判斷元素個(gè)數(shù)是否達(dá)到了臨界值，若已達(dá)到臨界值則擴(kuò)容，table長(zhǎng)度翻倍
if (size++ >= threshold)
resize(2 * table.length);
}
#HashMap的刪
remove方法同樣也是，先計(jì)算hash,在計(jì)算index，遍歷查找，找到之后刪除節(jié)點(diǎn)
/**
* 根據(jù)key刪除元素
*/
public V remove(Object key) {
Entry e = removeEntryForKey(key);
return (e == null ? null : e. value);
}
/**
* 根據(jù)key刪除鏈表節(jié)點(diǎn)
*/
final Entry removeEntryForKey(Object key) {
// 計(jì)算key的hash值
int hash = (key == null) ? 0 : hash(key.hashCode());
// 根據(jù)hash值計(jì)算key在數(shù)組的索引位置
int i = indexFor(hash, table.length );
// 找到該索引出的第一個(gè)節(jié)點(diǎn)
Entry prev = table[i];
Entry e = prev;
// 遍歷鏈表（從鏈表第一個(gè)節(jié)點(diǎn)開(kāi)始next），找出相同的key，
while (e != null) {
Entry next = e. next;
Object k;
// 如果hash值和key都相等，則認(rèn)為相等
if (e.hash == hash &&
((k = e. key) == key || (key != null && key.equals(k)))) {
// 修改版本+1
modCount++;
// 計(jì)數(shù)器減1
size--;
// 如果第一個(gè)就是要?jiǎng)h除的節(jié)點(diǎn)（第一個(gè)節(jié)點(diǎn)沒(méi)有上一個(gè)節(jié)點(diǎn)，所以要分開(kāi)判斷）
if (prev == e)
// 則將下一個(gè)節(jié)點(diǎn)放到table[i]位置（要?jiǎng)h除的節(jié)點(diǎn)被覆蓋）
table[i] = next;
else
// 否則將上一個(gè)節(jié)點(diǎn)的next指向當(dāng)要?jiǎng)h除節(jié)點(diǎn)下一個(gè)（要?jiǎng)h除節(jié)點(diǎn)被忽略，沒(méi)有指向了）
prev. next = next;
e.recordRemoval( this);
// 返回刪除的節(jié)點(diǎn)內(nèi)容
return e;
}
// 保存當(dāng)前節(jié)點(diǎn)為下次循環(huán)的上一個(gè)節(jié)點(diǎn)
prev = e;
// 下次循環(huán)
e = next;
}
return e;
}
HashMap的擴(kuò)容
resize擴(kuò)容是HashMap中非常重要的一個(gè)操作，在容器里的元素達(dá)到一個(gè)臨界值時(shí)，HashMap會(huì)自動(dòng)進(jìn)行擴(kuò)容，擴(kuò)容的具體流程是；
1.在put的時(shí)候檢查是否需要擴(kuò)容，根據(jù)兩個(gè)參數(shù)：初始容量和裝載因子
2.創(chuàng)建一個(gè)容量為table.length*2的table，修改臨界值
3.重新計(jì)算所有元素的hash值，并放入新的table，使用的是頭插法
4.用新的table替換舊的table
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {//最大容量為 1 << 30
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];//新建一個(gè)新表
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;//是否再hash
transfer(newTable, rehash);//完成舊表到新表的轉(zhuǎn)移
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
---------------------
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry e : table) {//遍歷同桶數(shù)組中的每一個(gè)桶
while(null != e) {//順序遍歷某個(gè)桶的外掛鏈表
Entry next = e.next;//引用next
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//找到新表的桶位置;原桶數(shù)組中的某個(gè)桶上的同一鏈表中的Entry此刻可能被分散到不同的桶中去了，有效的緩解了哈希沖突。
e.next = newTable[i];//頭插法插入新表中
newTable[i] = e;
e = next;
}
}
}
擴(kuò)容的整體操作如上，但是有一些十分精妙的細(xì)節(jié)十分厲害
為什么擴(kuò)容的容量一定是2的冪？
這么設(shè)計(jì)當(dāng)然是為了性能，而且是十分顯著的性能提升，涉及到了位操作，我覺(jué)得非常有意思，會(huì)在下一篇專(zhuān)門(mén)講這樣計(jì)算進(jìn)行提升性能的例子。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77765.html
