HashMap使用一個(gè)的數(shù)組來(lái)保存不同散列值的key以及相應(yīng)的value。在jkd1.8中番川，對(duì)于相同hashcode形成的bucket，不再按照唯一的鏈表存儲(chǔ)，而是根據(jù)bucket的大小赊颠，超過(guò)一定限制之后將鏈表轉(zhuǎn)換為紅黑樹(shù)來(lái)存儲(chǔ)Map.Entry<k,v>。這樣劈彪，HashMap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)就是數(shù)組+鏈表+紅黑樹(shù)竣蹦。
*jkd源碼的版本為1.8.0_05
類的結(jié)構(gòu)：
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
一個(gè)不明白的地方：AbstractMap已經(jīng)實(shí)現(xiàn)了Map接口，為什么HashMap還要繼承AvstractMap之后實(shí)現(xiàn)Map沧奴。
構(gòu)造函數(shù)
HashMap的構(gòu)造函數(shù)有多種重載的方式痘括，這里只詳細(xì)說(shuō)明最重要，最復(fù)雜的一種：
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;
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
這里有一個(gè)tableSizeFor()方法滔吠，就是取大于cap的最小2的整數(shù)冪纲菌。實(shí)現(xiàn)思路是由"1....."計(jì)算得到"1111111+1"。使用將第一位不斷的向后移疮绷，然后做“或”運(yùn)算的方法翰舌。Doug Lea大神腦路之奇特，讓人佩服冬骚。
成員字段
//HashMap的默認(rèn)初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//HashMap的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)負(fù)載系數(shù)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//一個(gè)bucket的節(jié)點(diǎn)數(shù)大于這個(gè)數(shù)字的時(shí)候椅贱，使用紅黑樹(shù)來(lái)存儲(chǔ)
static final int TREEIFY_THRESHOLD = 8;
//一個(gè)bucket的節(jié)點(diǎn)數(shù)小于這個(gè)數(shù)字的時(shí)候懂算，使用鏈表來(lái)存儲(chǔ)
static final int UNTREEIFY_THRESHOLD = 6;
//紅黑樹(shù)的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
//用來(lái)散列的數(shù)組
transient Node<K,V>[] table;
//鍵值對(duì)的數(shù)量
transient int size;
//HashMap的結(jié)構(gòu)修改的次數(shù)
transient int modCount;
//閾值，下一次分配容量的閾值（capacity*loadFactor）
int threshold;
//負(fù)載系數(shù)
final float loadFactor;
關(guān)鍵方法
計(jì)算哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這里有一個(gè)無(wú)符號(hào)右移庇麦，當(dāng)h的值小于16位的時(shí)候计技，h^(h>>>16)與h是相等的。當(dāng)h高于16位的時(shí)候山橄，為了防止key的hashcode值的變化只在開(kāi)頭幾位垮媒，末尾相同，這樣導(dǎo)致在與cap-1做&運(yùn)算的時(shí)候驾胆，發(fā)生大量的哈希沖突涣澡，所以使用一些高位來(lái)spread(這里怎么翻譯？)一下低位丧诺。讓其低位變得不同入桂。為什么使用異或運(yùn)算，因?yàn)楫惢蜻\(yùn)算非常的快驳阎。
在HashMap中增加一個(gè)鍵值對(duì)
大概經(jīng)歷了下面幾個(gè)過(guò)程：
- 處理HashMap為空的情況
- 進(jìn)行Hash運(yùn)算抗愁，然后查看數(shù)組中相應(yīng)的位置
- 如果是空的，說(shuō)明沒(méi)有Hash沖突呵晚，放在這里就好
- 如果有值蜘腌，先判斷是不是和第一個(gè)值的key相同
- 然后處理是紅黑樹(shù)的情況
- 最后處理數(shù)組的情況
/**
*@param onlyIfAbsent：如果是true，在有相同key的情況下饵隙，不要改變現(xiàn)有的value
*@param evict：如果是false撮珠，是在構(gòu)造函數(shù)中調(diào)用
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果數(shù)組是空的，做一次擴(kuò)容金矛。
if ((tab = table) == null || (n = tab.length) == 0)
//n是當(dāng)前數(shù)組的容量
n = (tab = resize()).length;
//p取到當(dāng)前hash散列到的節(jié)點(diǎn)芯急。n是2的整數(shù)冪，(n-1)&hash做一次哈希值的截取
if ((p = tab[i = (n - 1) & hash]) == null)
//如果這個(gè)節(jié)點(diǎn)是空的驶俊，說(shuō)明之前沒(méi)有相同的哈希值娶耍，新建一個(gè)節(jié)點(diǎn)放在這里。
tab[i] = newNode(hash, key, value, null);
else {
//下面處理哈希沖突的情況
Node<K,V> e; K k;
//如果這個(gè)bucket里的第一個(gè)節(jié)點(diǎn)的key與我們正在添加的key相同饼酿。（使用equals做判斷榕酒，所以推薦重寫equals）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//e就是key相同的節(jié)點(diǎn)
e = p;
//如果這個(gè)bucket是一個(gè)紅黑樹(shù)
else if (p instanceof TreeNode)
//用紅黑樹(shù)的方式添加一個(gè)節(jié)點(diǎn)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//還剩下的情況就是鏈表了，遍歷這個(gè)鏈表故俐。
for (int binCount = 0; ; ++binCount) {
//到了鏈表的結(jié)尾想鹰，說(shuō)明沒(méi)有key相同的，需要在這里插入一個(gè)節(jié)點(diǎn)药版。
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果當(dāng)前bucket的數(shù)量超過(guò)的查找樹(shù)閾值辑舷，轉(zhuǎn)換為查找樹(shù)的方式，然后跳出刚陡。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果查找到了相同的key惩妇，也跳出。已經(jīng)把e的信息保存下來(lái)了筐乳。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//現(xiàn)在說(shuō)明已經(jīng)存在了相同的key歌殃，要進(jìn)行value的替換
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//這里的afterNodeAccess應(yīng)該是鉤子方法，方便LinkedHashMap繼承HashMap的時(shí)候可以調(diào)用蝙云，起到子類影響父類的效果氓皱。
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果容量超過(guò)閾值，進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
擴(kuò)容
所謂擴(kuò)容勃刨，就是當(dāng)鍵值對(duì)的數(shù)量超過(guò)閾值的時(shí)候波材，讓當(dāng)前數(shù)組的的容量擴(kuò)大為當(dāng)前的兩倍，然后進(jìn)行一次hash再散列的過(guò)程身隐。
一次hashMap重新散列的過(guò)程.png
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//因?yàn)閿?shù)組的容量總是2的整數(shù)冪廷区，所以可以使用左移一位的方式達(dá)到乘以二的效果，效率更優(yōu)贾铝。
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//這里處理的情況是舊的容量是0隙轻，但是閾值不為零。那么就擴(kuò)容到閾值垢揩。
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//容量是0玖绿，閾值也是0，全部使用默認(rèn)的值叁巨。
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//按照上面的邏輯斑匪，這里處理的是oldCap==0,oldThr>0的情況，不太理解這里锋勺。
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//新建一個(gè)新的數(shù)組蚀瘸，完成容量擴(kuò)大成為之前二倍的操作。
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//下面進(jìn)行把老的數(shù)組里面的值放到新的數(shù)組里
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果老的數(shù)組里宙刘，bucket只有一個(gè)節(jié)點(diǎn)苍姜，那么進(jìn)行重新散列，放到新的位置悬包。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是一顆紅黑樹(shù)衙猪，使用TreeNode中的slit方法，將這棵樹(shù)分成兩個(gè)小樹(shù)布近。
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//下面處理將一個(gè)鏈表分成兩個(gè)鏈表垫释。
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//oldCap應(yīng)該是二進(jìn)制“100000……”的形式，那么做&運(yùn)算之后撑瞧，剛好可以得到擴(kuò)容之后哈希值多出來(lái)的那一位棵譬。我們根據(jù)多出來(lái)的那一位是1還是0，選擇是放在原來(lái)的bucket上预伺，還是放在新的bucket上订咸。
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//把兩個(gè)鏈表頭放在數(shù)組里對(duì)應(yīng)的位置曼尊，“低位”放在原處，“高位”放在原處+老容量值
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
