準(zhǔn)備知識(shí)
HashMap是基于哈希表的非同步的實(shí)現(xiàn)，不保證映射的順序永久不變，可以鍵值對(duì)都為null迹缀。哈希表的核心就是根據(jù)元素求位置。而多個(gè)元素可能出現(xiàn)相同的位置蜜徽，那么就叫沖突祝懂。解決沖突的常用方式：鏈地址法：將多個(gè)值的不同的哈希結(jié)果（哈希值）用數(shù)組進(jìn)行存儲(chǔ)，然后將產(chǎn)生相同哈希值的元素拘鞋，以單向鏈表的形式進(jìn)行存儲(chǔ)砚蓬。所以拉鏈法的套路就是數(shù)組+單鏈表。第二種解決方式是線性探測(cè)法：將多個(gè)值余上表長(zhǎng)度盆色，如果多個(gè)值產(chǎn)生相同的哈希值灰蛙，那么就依次往下尋找位置祟剔，直到不沖突為止。線性探測(cè)法致命的缺點(diǎn)就是當(dāng)數(shù)據(jù)量上來(lái)時(shí)摩梧，就會(huì)頻繁的進(jìn)行碰撞沖突物延，然后找到位置比較費(fèi)勁。
HashMap中鏈地址的單鏈表結(jié)構(gòu)
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; // 鍵
V value; // 值
Entry<K,V> next;// 指向下一個(gè)相同hash值得元素
int hash;// 哈希值
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
.............
.............
}
屬性
//默認(rèn)初始化容量為16
static final int DEFAULT_INITIAL_CAPACITY = 16;
說(shuō)明：HashMap初始化容量為16障本。
//最大容量教届，必須是2的n次冪
static final int MAXIMUM_CAPACITY = 1 << 30;
說(shuō)明：HashMap的最大容量是2的30次冪。
//默認(rèn)加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
說(shuō)明：HashMap的默認(rèn)加載因子為0.75驾霜。
//存儲(chǔ)數(shù)據(jù)的Entry數(shù)組案训，是存儲(chǔ)實(shí)體的數(shù)組，長(zhǎng)度是2的冪
transient Entry<K,V>[] table;
說(shuō)明：HashMap中存儲(chǔ)單向鏈表節(jié)點(diǎn)的數(shù)組粪糙。
//映射鍵值對(duì)的個(gè)數(shù)强霎，也是數(shù)組中元素的個(gè)數(shù)
transient int size;
說(shuō)明：HashMap中存儲(chǔ)下標(biāo)和節(jié)點(diǎn)的數(shù)組中元素的個(gè)數(shù)。
//臨界值蓉冈，當(dāng)實(shí)際大小超過(guò)臨界值時(shí)城舞，會(huì)進(jìn)行擴(kuò)容threshold = 加載因子*容量
int threshold;
說(shuō)明：HashMap中的臨界值，如果實(shí)際的大小超出了臨界值會(huì)進(jìn)行擴(kuò)容寞酿。
//哈希表的加載因子
final float loadFactor;
說(shuō)明：HashMap中的加載因子家夺。
//被修改的次數(shù)
transient int modCount;
說(shuō)明：HashMap中被修改的次數(shù)。
構(gòu)造方法
構(gòu)造方法1：初始化一個(gè)Entry數(shù)組伐弹，數(shù)組大小為2的n次冪
public HashMap(int initialCapacity, float loadFactor) {
//如果初始化容量小于0拉馋，報(bào)非法參數(shù)異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果初始化容量大于最大容量，那么將最大容量作為初始化容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//如果加載因子小于0或者為非小數(shù)惨好，那么就報(bào)非法參數(shù)異常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 讓容量以2的n次冪遞增煌茴，這樣保證了容量大小為偶數(shù)
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//以定義的容量capacity初始化Entry數(shù)組
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
說(shuō)明：容量按照2的n次冪遞增，保證容量為偶數(shù)日川。
因?yàn)橹付ǖ某跏蓟萘亢拓?fù)載因子蔓腐，所以要嚴(yán)格設(shè)計(jì)。計(jì)算出的臨界值如果過(guò)小龄句，那么后面元素上來(lái)需要擴(kuò)容回论。
構(gòu)造方法2：使用默認(rèn)的加載因子和初始化容量構(gòu)造HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
構(gòu)造方法3：使用默認(rèn)的初始化容量16，和默認(rèn)的加載因子0.75構(gòu)造HashMap
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
構(gòu)造方法4：構(gòu)造一個(gè)映射關(guān)系與指定 Map 相同的 HashMap分歇；所創(chuàng)建的 HashMap 具有默認(rèn)的加載因子 (0.75) 和足以容納指定 Map中映射關(guān)系的初始容量透葛。
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
//遍歷m獲取值，放入哈希表
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
private void putForCreate(K key, V value) {
//如果鍵為空卿樱，hash值為0僚害，如果鍵不為空，那么就通過(guò)鍵來(lái)生成hash值
int hash = null == key ? 0 : hash(key);
//通過(guò)hash值來(lái)獲取索引
int i = indexFor(hash, table.length);
/**
* 通過(guò)索引查找到table中的Entry節(jié)點(diǎn)，進(jìn)行遍歷單鏈表中的Entry節(jié)點(diǎn)萨蚕。
* 如果出現(xiàn)了該索引對(duì)應(yīng)hash值和鍵都相同的靶草，那么就直接退出該方法。
*/
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
//否則就執(zhí)行createEntry方法創(chuàng)建該桶
createEntry(hash, key, value, i);
}
關(guān)鍵方法設(shè)計(jì)
1. hash方法：使用鍵key生成hash值
通過(guò)鍵來(lái)獲取對(duì)應(yīng)的hash值岳遥。使用hashCode方法先散列一次奕翔，然后進(jìn)行高位右移、異或運(yùn)算浩蓉，在進(jìn)行低位右移派继、異或運(yùn)算
// 根據(jù)鍵來(lái)獲取對(duì)應(yīng)的hash值
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
2. indexFor方法：使用hash值和鍵表的長(zhǎng)度生成鍵表的下標(biāo)（鍵表：Entry<K,V>[] table）
// 返回hash值對(duì)應(yīng)的下標(biāo)
static int indexFor(int h, int length) {
return h & (length-1);
}
說(shuō)明：
在我們自己實(shí)現(xiàn)哈希表的時(shí)候，常常會(huì)采用取%的方式來(lái)進(jìn)行散列捻艳，將余數(shù)作為散列碼驾窟。但是java采用的是二進(jìn)制與運(yùn)算來(lái)取hash值。由于length為2的n次冪认轨，所以其減一為奇數(shù)绅络，那么轉(zhuǎn)化為二進(jìn)制，末位肯定是1嘁字。如果hash值h為奇數(shù)恩急，那么h與length的與運(yùn)算，返回索引的二進(jìn)制末位為1.如果hash值h為偶數(shù)纪蜒，那么h與length的與運(yùn)算衷恭，返回索引的二進(jìn)制末位為0。這就相當(dāng)于取模運(yùn)算了纯续，但是與位運(yùn)算比取模速度快很多随珠。并且這樣也可以保證數(shù)組的下標(biāo)不會(huì)越界。是一個(gè)很棒的選擇杆烁。由于與運(yùn)算加上前面hash（key）函數(shù)的高位運(yùn)算，就減少了碰撞简卧。這樣就保證了hash值分布比較均勻并且沖突的概率很低兔魂。并且只有在值相同時(shí)，才會(huì)對(duì)應(yīng)數(shù)組中的相同位置Entry举娩，然后以next的關(guān)系構(gòu)成鏈表析校。
3. createEntry方法：初始化Entry。如果沒(méi)有相同的hash值和鍵铜涉，就會(huì)使用createEntry來(lái)創(chuàng)建單鏈表智玻。
void createEntry(int hash, K key, V value, int bucketIndex) {
//根據(jù)索引得出對(duì)應(yīng)定義的Entry類型對(duì)象e
Entry<K,V> e = table[bucketIndex];
//將e進(jìn)行初始化哈希值、鍵芙代、值吊奢，以及單鏈表指向的下一個(gè)節(jié)點(diǎn)e
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
常用方法
get方法：返回指定鍵所映射的值；如果對(duì)于該鍵來(lái)說(shuō)纹烹，此映射不包含任何映射關(guān)系页滚，則返回 null
public V get(Object key) {
// 如果鍵為null
if (key == null)
// 返回獲取null鍵對(duì)應(yīng)的值
return getForNullKey();
// 獲取鍵對(duì)應(yīng)的值
Entry<K,V> entry = getEntry(key);
// 如果獲取的節(jié)點(diǎn)為null召边，那么返回null；否則獲取節(jié)點(diǎn)對(duì)應(yīng)的值
return null == entry ? null : entry.getValue();
}
getForNullKey方法：查找null鍵對(duì)應(yīng)的值
// 獲取null鍵的值
private V getForNullKey() {
// 如果鍵表中沒(méi)有元素裹驰，返回null
if (size == 0) {
return null;
}
// 從鍵表的第一個(gè)節(jié)點(diǎn)開(kāi)始隧熙，循環(huán)遍歷存放節(jié)點(diǎn)的單鏈表
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
// 如果存在鍵值等于null的節(jié)點(diǎn)
if (e.key == null)
// 返回節(jié)點(diǎn)的值
return e.value;
}
return null;
}
getEntry方法：查找鍵對(duì)應(yīng)的Entry節(jié)點(diǎn)
final Entry<K,V> getEntry(Object key) {
// 如果鍵為null，返回hash值為0
// 如果鍵不為null幻林，返回計(jì)算的hash值
int hash = (key == null) ? 0 : hash(key);
// 使用hash值計(jì)算鍵表下標(biāo)贞盯，找到對(duì)應(yīng)的單向節(jié)點(diǎn)鏈表
// 遍歷節(jié)點(diǎn)鏈
for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {
Object k;
// 判斷遍歷節(jié)點(diǎn)的hash值和鍵是否等于查找的鍵和hash值
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
說(shuō)明：
① 當(dāng)鍵為空，就遍歷單向節(jié)點(diǎn)鏈中的節(jié)點(diǎn)沪饺，遍歷到的節(jié)點(diǎn)的鍵為null躏敢，就返回節(jié)點(diǎn)對(duì)應(yīng)的值。
② 當(dāng)鍵不為空随闽，那么就通過(guò)鍵獲取hash值父丰，再通過(guò)hash值獲取鍵表的下標(biāo)，通過(guò)下標(biāo)索引獲取對(duì)應(yīng)的Entry單向鏈表掘宪。遍歷單鏈表找到hash值和key鍵都相同的值蛾扇。
put方法：在此映射中關(guān)聯(lián)指定值與指定鍵。如果該映射以前包含了一個(gè)該鍵的映射關(guān)系魏滚，則舊值被替換镀首。
public V put(K key, V value) {
// 如果鍵為null
if (key == null)
//設(shè)置鍵key為null的值
return putForNullKey(value);
//通過(guò)鍵獲取hash值
int hash = hash(key);
//通過(guò)hash值獲取下標(biāo)索引
int i = indexFor(hash, table.length);
// 遍歷單鏈表節(jié)點(diǎn)，找到對(duì)應(yīng)的值就覆蓋
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果hash值和鍵都相同的
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 獲取舊的鍵對(duì)應(yīng)的值
V oldValue = e.value;
// 設(shè)置指定的值
e.value = value;
e.recordAccess(this);
// 返回舊值
return oldValue;
}
}
// 修改次數(shù)加1
modCount++;
//否則就添加新值并且返回為空
addEntry(hash, key, value, i);
return null;
}
putForNullKey方法：設(shè)置鍵key為null的值
private V putForNullKey(V value) {
// 鍵表0下標(biāo)開(kāi)始遍歷
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
// 如果鍵為null
if (e.key == null) {
// 獲取舊的鍵對(duì)應(yīng)的值
V oldValue = e.value;
// 設(shè)置指定的值
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 修改次數(shù)加1
modCount++;
// 添加新的值
addEntry(0, null, value, 0);
return null;
}
addEntry方法：添加新的值
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果鍵表超出了臨界值并且下標(biāo)對(duì)應(yīng)的值不為null
if ((size >= threshold) && (null != table[bucketIndex])) {
// 將HashMap擴(kuò)容
resize(2 * table.length);
// 如果鍵key不為null就獲取對(duì)應(yīng)的hash值鼠次，否則獲取hash值為0
hash = (null != key) ? hash(key) : 0;
// 通過(guò)hash值計(jì)算鍵表下標(biāo)
bucketIndex = indexFor(hash, table.length);
}
//通過(guò)新的hash值更哄、鍵、值腥寇、下標(biāo)索引來(lái)以構(gòu)造器的方式創(chuàng)建Entry單向鏈表
createEntry(hash, key, value, bucketIndex);
}
resize方法：使用新容量進(jìn)行擴(kuò)容操作
void resize(int newCapacity) {
// 獲取舊表
Entry[] oldTable = table;
// 獲取舊表的容量
int oldCapacity = oldTable.length;
//如果舊的容量值都已經(jīng)達(dá)到最大容量成翩，那么就不再進(jìn)行擴(kuò)容調(diào)整了，直接退出了
if (oldCapacity == MAXIMUM_CAPACITY) {
// 設(shè)置臨界值為Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
return;
}
//根據(jù)新容量長(zhǎng)度定義新的數(shù)組
Entry[] newTable = new Entry[newCapacity];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
//定義了新容量的數(shù)組赦役，那么這步就是將舊容量數(shù)組中的元素都放到新容量的數(shù)組中去
transfer(newTable, rehash);
//更新當(dāng)前的鍵表
table = newTable;
//臨界值由新容量進(jìn)行調(diào)整
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer方法：將舊表中的元素都轉(zhuǎn)移到新表中
void transfer(Entry[] newTable, boolean rehash) {
// 獲取新表的容量
int newCapacity = newTable.length;
// 遍歷舊鍵表中的Entry麻敌，然后通過(guò)舊鍵表中的Entry創(chuàng)建新鍵表的Entry
for (Entry<K,V> e : table) {
// 如果節(jié)點(diǎn)Entry不為null
while(null != e) {
// 獲取遍歷到節(jié)點(diǎn)的后繼節(jié)點(diǎn)
Entry<K,V> next = e.next;
// 如果需要就重新通過(guò)鍵生成hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 通過(guò)hash值獲取下標(biāo)索引
int i = indexFor(e.hash, newCapacity);
// 設(shè)置當(dāng)前Entry節(jié)點(diǎn)e指向的下一個(gè)節(jié)點(diǎn)Entry值為newTable[i]
// 將舊的鍵位置對(duì)應(yīng)的值作為當(dāng)前Entry的后繼值
e.next = newTable[i];
// 更新當(dāng)前鍵數(shù)組的值為最新值
newTable[i] = e;
// 向下個(gè)節(jié)點(diǎn)遍歷
e = next;
}
}
}
說(shuō)明：
可以看到為了轉(zhuǎn)移元素，使用舊的值生成hash值掂摔，再重新計(jì)算下標(biāo)索引的位置术羔，用了兩層循環(huán)，時(shí)間復(fù)雜度增加了數(shù)量級(jí)乙漓，非常消耗性能级历。所以如果我們已知了需要的空間，那么就會(huì)減少不必要的因?yàn)槌龅脑虍a(chǎn)生的擴(kuò)容操作叭披，減少了性能的消耗寥殖。
總結(jié)
1. HashMap的設(shè)計(jì)采用數(shù)組+單向鏈表實(shí)現(xiàn)的。
2. HashMap的默認(rèn)初始化容量為16 ，默認(rèn)加載因子為0.75扛禽。
3. HashMap指定初始容量：按照2的n次冪計(jì)算锋边。
4. HashMap中鍵和值都允許存入null值。
5. HashMap中值允許重復(fù)编曼，如果發(fā)現(xiàn)鍵相同豆巨，就更新原來(lái)的值。
6. HashMap是線程不安全的掐场。
7. HashMap是無(wú)序的往扔，不是按照插入順序遍歷出來(lái)的。
8. hash函數(shù)熊户，通過(guò)鍵獲取hash值萍膛，分別使用高位和低位的右移、異或運(yùn)算減少?zèng)_突嚷堡。
9. indexFor函數(shù)蝗罗，通過(guò)hash值獲取索引，使用與位運(yùn)算代替取模運(yùn)算蝌戒，速度就提高了串塑，而且也不用擔(dān)心下標(biāo)越界的問(wèn)題了。
10. put函數(shù)北苟，臨界值等于鍵表容量乘以負(fù)載因子桩匪，當(dāng)我們添加的時(shí)候會(huì)計(jì)算鍵表的長(zhǎng)度是否大于臨界值，如果我們初始化時(shí)臨界值過(guò)小友鼻，那么我們就需要擴(kuò)容傻昙，這樣操作會(huì)帶來(lái)性能消耗。
11. put函數(shù)彩扔，如果大于臨界值將會(huì)擴(kuò)容妆档，擴(kuò)容策略，一次擴(kuò)容為原來(lái)的2倍虫碉。
12. 為什么數(shù)組的長(zhǎng)度為2的n次冪：減小哈希沖突概率贾惦，而且還可以防止數(shù)組下標(biāo)越界。
