一 成員變量解析
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* The next size value at which to resize (capacity * load factor).
*/
int threshold;
/**
* The load factor for the hash table.
*/
final float loadFactor;
二 方法解析
1 添加元素
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key //關鍵字的hash
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果tab為null或tab長度為0 則初始化tab長度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// HashMap用hash(key) & (length-1)的方法得到tab的索引i
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果i對應的tab值為null 則直接建立關鍵字為key，值為value的節(jié)點
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 如果tab[i].hash == hash 且 {tab[i].key == key或者key.equals(tab[i].key)}
// （java規(guī)定equals()為true的兩個對象hashcode必相等，所以在此不必比較hash值此洲，
// 這也是為何在覆蓋equals()方法的同時要覆蓋hashCode()方法的原因）
// 則找到更新節(jié)點
e = p;
else if (p instanceof TreeNode)
// 如果p是樹節(jié)點 則更新樹節(jié)點
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// binCount記錄tab[i]下的鏈表長度，如果大于TREEIFY_THRESHOLD將鏈表結(jié)構(gòu)轉(zhuǎn)化為樹結(jié)構(gòu)
for (int binCount = 0; ; ++binCount) {
// 如果tab[i]的下一個節(jié)點為null 則直接新建節(jié)點并退出循環(huán)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果e.hash == hash 且 e.key == key或者key.equals(e.key)
// 則找到更新節(jié)點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 以上不滿足 則將p設為下一個鏈表節(jié)點
p = e;
}
}
if (e != null) { // 存在key對應的映射
V oldValue = e.value;
// 如果onlyIfAbsent==false或者oldValue為null
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 修改參數(shù)加一
++modCount;
// 如果tab長度大于threshold 則擴充tab 將tab長度擴充為原來的2倍
if (++size > threshold)盼玄、
// 擴容
resize();
afterNodeInsertion(evict);
return null;
}
添加元素的過程如下：
（1）如果tab為null或tab長度為0 則初始化tab長度蚂子，默認16
（2）根據(jù)hash(key) & (length-1)的得到索引萌庆，定位tab[i]
（3）如果tab[i]等于null，則直接建立新節(jié)點
否則會先檢查tab[i]的頭結(jié)點是否和key匹配沙咏，如果匹配則找到更新的tab[i]
否則循環(huán)tab[i]中的節(jié)點鏈辨图，如果節(jié)點鏈中有節(jié)點和key匹配，則更新肢藐；如果遍歷后沒有節(jié)點匹配成功故河，則在鏈表尾部添加以key為鍵的新節(jié)點
和key匹配的原則是：
tab[i].hash == hash(key)且tab[i].key == key或者key.equals(tab[i].key)（java規(guī)定equals()為true的兩個對象hashcode必相等，所以在此不必比較hash值吆豹，這也是為何在覆蓋equals()方法的同時要覆蓋hashCode()方法的原因）
2 獲取元素
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
// hash(key) & (length-1)的方法得到tab的索引
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
// 如果first.hash==hash 且 first.key==key或者key.equals(first.key) 返回first
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 在tab[i]下的鏈表中查找對應的節(jié)點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
3 刪除元素
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) { // hash(key) & (length-1)的方法得到tab的索引
// node為待刪除節(jié)點
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果p.hash==hash 且 p.key==key或者key.equals(p.key) 則找到待刪除節(jié)點
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 從鏈表中找到待刪除節(jié)點
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 如果node是首節(jié)點鱼的，則設tab[index]為node的下一個節(jié)點
tab[index] = node.next;
else
// node和p不相等，此時p是node的前驅(qū)節(jié)點痘煤，則設node的前驅(qū)節(jié)點的后繼節(jié)點為node的后繼節(jié)點
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
4 擴容
當添加元素時凑阶，如果size > threshold，則進行擴容
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;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 擴容后元素重新計算index衷快，然后放置宙橱，詳情見下面詳述
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
在擴容后，newCap為lodCap的2倍蘸拔，而這時候就要將原tab中的元素重新放置师郑，代碼中將(e.hash & oldCap) == 0的節(jié)點放入tab[index]中，位置不變都伪；將(e.hash & oldCap) != 0的節(jié)點放入tab[index + oldCap]中呕乎，這是為何呢？
假設有兩個鍵陨晶，key1和key2，hash(key1)=0000 0101帝璧，hash(key2)=0001 0101先誉，oldCap=16(0001 0000)
則兩個鍵對應的index為：
index_1 = hash(key1) & (oldCap - 1) = 0000 0101 & 0000 1111 = 0101
index_2 = hash(key2) & (oldCap - 1) = 0001 0101 & 0000 1111 = 0101
擴容后newCap = oldCap * 2 = 32(0010 0000)，此時索引要重新計算：
index_new_1 = hash(key1) & (newCap - 1) = 0000 0101 & 0001 1111 = 00101 = index_1
index_new_2 = hash(key2) & (newCap - 1) = 0001 0101 & 0001 1111 = 10101 = 00101 + 10000 = index_2 + oldCap
因此的烁，我們在擴充HashMap的時候褐耳，不需要像JDK1.7的實現(xiàn)那樣重新計算hash，只需要判斷hash值中倒數(shù)第r位（oldCap=2^r）是否為0就可以渴庆，是0的話索引沒變铃芦，是1的話索引變成“原索引+oldCap”雅镊。
三 再談HashCode的重要性
前面講到了，HashMap中對Key的HashCode要做一次rehash刃滓，防止一些糟糕的Hash算法生成的糟糕的HashCode仁烹，那么為什么要防止糟糕的HashCode？
糟糕的HashCode意味著的是Hash沖突咧虎，即多個不同的Key可能得到的是同一個HashCode卓缰，糟糕的Hash算法意味著的就是Hash沖突的概率增大，這意味著HashMap的性能將下降砰诵，表現(xiàn)在兩方面：
- 有10個Key征唬，可能6個Key的HashCode都相同，另外四個Key所在的Entry均勻分布在table的位置上茁彭，而某一個位置上卻連接了6個Entry总寒。這就失去了HashMap的意義，HashMap這種數(shù)據(jù)結(jié)構(gòu)性高性能的前提是理肺，Entry均勻地分布在table位置上偿乖，但現(xiàn)在確是1 1 1 1 6的分布。所以哲嘲，我們要求HashCode有很強的隨機性贪薪，這樣就盡可能地可以保證了Entry分布的隨機性，提升了HashMap的效率眠副。
- HashMap在一個某個table位置上遍歷鏈表的時候的代碼：
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
看到画切，由于采用了“&&”運算符，因此先比較HashCode囱怕，HashCode都不相同就直接pass了霍弹，不會再進行equals比較了。HashCode因為是int值娃弓，比較速度非车涓瘢快，而equals方法往往會對比一系列的內(nèi)容台丛，速度會慢一些耍缴。Hash沖突的概率大，意味著equals比較的次數(shù)勢必增多挽霉，必然降低了HashMap的效率了防嗡。
四 HashMap的table為什么是transient
看到table用了transient修飾，也就是說table里面的內(nèi)容全都不會被序列化侠坎，不知道大家有沒有想過這么寫的原因蚁趁？
在我看來，這么寫是非常必要的实胸。因為HashMap是基于HashCode的他嫡，HashCode作為Object的方法番官，是native的：
public native int hashCode();
這意味著的是：HashCode和底層實現(xiàn)相關，不同的虛擬機可能有不同的HashCode算法钢属。再進一步說得明白些就是徘熔，可能同一個Key在虛擬機A上的HashCode=1，在虛擬機B上的HashCode=2署咽，在虛擬機C上的HashCode=3近顷。
這就有問題了，Java自誕生以來宁否，就以跨平臺性作為最大賣點窒升，好了，如果table不被transient修飾慕匠，在虛擬機A上可以用的程序到虛擬機B上可以用的程序就不能用了饱须，失去了跨平臺性，因為：
- Key在虛擬機A上的HashCode=100台谊，連在table[4]上
- Key在虛擬機B上的HashCode=101蓉媳，這樣，就去table[5]上找Key锅铅，明顯找不到
整個代碼就出問題了酪呻。因此，為了避免這一點盐须，Java采取了重寫自己序列化table的方法玩荠，在writeObject選擇將key和value追加到序列化的文件最后面：
private void writeObject(java.io.ObjectOutputStream s) throws IOException {
int buckets = capacity();
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
s.writeInt(buckets);
s.writeInt(size);
internalWriteEntries(s);
}
// Called only from writeObject, to ensure compatible ordering.
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
Node<K,V>[] tab;
if (size > 0 && (tab = table) != null) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
}
}
而在readObject的時候重構(gòu)HashMap數(shù)據(jù)結(jié)構(gòu)：
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException {
// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
reinitialize();
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
s.readInt(); // Read and ignore number of buckets
int mappings = s.readInt(); // Read number of mappings (size)
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
else if (mappings > 0) { // (if zero, use defaults)
// Size the table using given load factor only if within
// range of 0.25...4.0
float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
float fc = (float)mappings / lf + 1.0f;
int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
DEFAULT_INITIAL_CAPACITY :
(fc >= MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY :
tableSizeFor((int)fc));
float ft = (float)cap * lf;
threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
(int)ft : Integer.MAX_VALUE);
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
table = tab;
// 重點在這里！Ｔ舻恕阶冈！重新讀取key和value并添加
for (int i = 0; i < mappings; i++) {
@SuppressWarnings("unchecked")
K key = (K) s.readObject();
@SuppressWarnings("unchecked")
V value = (V) s.readObject();
putVal(hash(key), key, value, false, false);
}
}
}
五 HashMap和Hashtable的區(qū)別
- Hashtable是線程安全的，Hashtable所有對外提供的方法都使用了synchronized塑径，也就是同步女坑，而HashMap則是線程非安全的
- Hashtable不允許空的value，空的value將導致空指針異常统舀，而HashMap則無所謂匆骗，沒有這方面的限制
- tab的索引計算方法不一樣，Hashtable獲取索引的方式是 hash(key) mod tab.length绑咱，HashMap獲取索引的方式是 hash(key) & (tab.length-1)
Hashtable獲取索引設計原理：
因為Hashtable獲取索引的方式是 hash(key) mod tab.length绰筛，所以設置tab初始化大小為11這個素數(shù)，保證充分利用key的信息描融。注：如果length是2r次方，那么二進制數(shù)對2r取余就是該二進制數(shù)最后r位數(shù),這樣一來衡蚂，Hash函數(shù)就和鍵值（用二進制表示）的前幾位數(shù)無關了窿克，這樣我們就沒有完全用到鍵值的信息骏庸。
HashMap獲取索引設計原理：
數(shù)組初始化大小是2的冪次方時，hashmap的效率最高年叮，這是為什么呢具被？
看下圖，左邊兩組是數(shù)組長度為16（2的4次方）只损，右邊兩組是數(shù)組長度為15一姿。兩組的hashcode均為8和9，但是很明顯跃惫，當它們和1110“與”的時候叮叹，產(chǎn)生了相同的結(jié)果，也就是說它們會定位到數(shù)組中的同一個位置上去爆存，這就產(chǎn)生了碰撞蛉顽，8和9會被放到同一個鏈表上，那么查詢的時候就需要遍歷這個鏈表先较，得到8或者9携冤，這樣就降低了查詢的效率。同時闲勺，我們也可以發(fā)現(xiàn)曾棕，當數(shù)組長度為15的時候，hashcode的值會與14（1110）進行“與”菜循，那么最后一位永遠是0翘地，而0001，0011债朵，0101子眶，1001，1011序芦，0111臭杰，1101這幾個位置永遠都不能存放元素了，空間浪費相當大谚中，更糟的是這種情況中渴杆，數(shù)組可以使用的位置比數(shù)組長度小了很多，這意味著進一步增加了碰撞的幾率宪塔，減慢了查詢的效率磁奖！
