HashMap與HashTable是兩個(gè)頗為相似的類(lèi)。抽象的說(shuō)乖阵，都是鍵值對(duì)集合宣赔，那么它們之前到達(dá)有什么區(qū)別呢？似乎面試也车山考啊儒将，我們從原理的角度來(lái)分析一下。
我們先來(lái)看看HashTable的代碼：
HashTable
首先对蒲，HashTable的核心是一個(gè)鍵值對(duì)數(shù)組钩蚊。如下：
HashtableEntry<K, V>[] table;
而鍵值對(duì)HashtableEntry的代碼我們可以看到：
private static class HashtableEntry<K, V> implements Entry<K, V> {
final K key;
V value;
final int hash;
HashtableEntry<K, V> next;
HashtableEntry(K key, V value, int hash, HashtableEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V value) {
if (value == null) {
throw new NullPointerException("value == null");
}
V oldValue = this.value;
this.value = value;
return oldValue;
}
@Override public final boolean equals(Object o) {
if (!(o instanceof Entry)) {
return false;
}
Entry<?, ?> e = (Entry<?, ?>) o;
return key.equals(e.getKey()) && value.equals(e.getValue());
}
@Override public final int hashCode() {
return key.hashCode() ^ value.hashCode();
}
@Override public final String toString() {
return key + "=" + value;
}
}
HashtablEntry是一個(gè)鏈表贡翘。它持有了一個(gè)鍵值對(duì)、一個(gè)hash值和鏈表中下一個(gè)元素两疚。那么為什么HashTable的鍵值對(duì)需要一個(gè)鏈表呢床估，鍵值對(duì)只有一個(gè)key和value不是就可以了嗎？為了回答上面的問(wèn)題诱渤，我們需要再來(lái)看看HashTable中put(K , V)方法的實(shí)現(xiàn)：
public synchronized V put(K key, V value) {
if (key == null) {
throw new NullPointerException("key == null");
} else if (value == null) {
throw new NullPointerException("value == null");
}
int hash = Collections.secondaryHash(key);
HashtableEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
HashtableEntry<K, V> first = tab[index];
for (HashtableEntry<K, V> e = first; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for key is present; create one
modCount++;
if (size++ > threshold) {
rehash(); // Does nothing!!
tab = doubleCapacity();
index = hash & (tab.length - 1);
first = tab[index];
}
tab[index] = new HashtableEntry<K, V>(key, value, hash, first);
return null;
}
上面的代碼我們首先要注意到synchronized丐巫，這個(gè)說(shuō)明HashTable很大可能是線程安全的，進(jìn)入方法后我們可以看到勺美，需要put一對(duì)鍵值對(duì)進(jìn)來(lái)時(shí)递胧，我們首先會(huì)從table中取出相應(yīng)hash位置的鍵值對(duì)，然后進(jìn)行一個(gè)循環(huán)赡茸，如果hash和key均相等缎脾，則替換掉現(xiàn)有的值，直接return了占卧。
那么這里就有一種意外的情況遗菠，是不是有可能hash相等，key不相等华蜒。即哈希沖突辙纬。
在這樣的情況下，我們發(fā)現(xiàn)HashTable選擇將所有hash相等的鍵值對(duì)叭喜，存成一個(gè)鏈表贺拣。這樣，每次我們既可以用hash值捂蕴，統(tǒng)一索引位置譬涡，又可以避免hash沖突。
剩下的代碼就是擴(kuò)容啥辨、創(chuàng)建新的鍵值對(duì)涡匀，然后將新的鍵值對(duì)存入table。這里還會(huì)將和它hash值相同的鏈表溉知，放在它的尾部渊跋。
我們?cè)倏纯磄et(Object key)方法，與我們上面描述的原理相對(duì)應(yīng)着倾。
public synchronized V get(Object key) {
int hash = Collections.secondaryHash(key);
HashtableEntry<K, V>[] tab = table;
for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
每次HashTable并不能直接在table中取得正確的值。取到的只是一個(gè)hash能夠?qū)?yīng)上的鏈表燕少。然后卡者，在這個(gè)鏈表中進(jìn)行遍歷，取到正確的值客们。這個(gè)方法叫“拉鏈法”崇决。
HashMap
HashMapEntry的代碼與HashTableEntry的代碼幾乎完全一樣材诽。因此，我們直接看put和get方法恒傻。
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}
我們發(fā)現(xiàn)put的方法也非常接近脸侥。只有一些細(xì)微的不同：
- HashMap的put方法沒(méi)有加鎖，因此HashMap并非線程安全的盈厘。
- HashMap的put方法睁枕，允許key和value為空。
- HashTable中有一個(gè)contains方法很容易引起誤解沸手，已在HashMap中取消外遇。
public boolean contains(Object value) {
return containsValue(value);
}
ConcurrentHashMap
我們直接看ConcurrentHashMap的put方法：
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
...
}
addCount(1L, binCount);
由于代碼比較長(zhǎng)，我們來(lái)逐段分析契吉。其中Node的結(jié)構(gòu)和我們前面所說(shuō)的HashMapEntry非常類(lèi)似是一個(gè)鏈表的節(jié)點(diǎn)跳仿。table也與前面一樣是個(gè)Node的數(shù)組。代碼首先就進(jìn)入了死循環(huán)捐晶，獲取了table對(duì)象菲语，如果table為空則會(huì)創(chuàng)建一個(gè)table，如果hash值所在的索引為空（即之前沒(méi)有相同的key存放在Map中）惑灵，則直接通過(guò)CAS原子操作賦值并退出循環(huán)山上。
接下來(lái)我們看看，如果ConcurrentHashMap中已經(jīng)存在了相同的key泣棋，ConcurrentHashMap是如何工作的胶哲。
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
這段代碼首先鎖定了Node<K,V> f。并重新判斷了f有沒(méi)有被改變潭辈，如果已經(jīng)發(fā)生改變程序會(huì)跑出同步鎖鸯屿，binCount為0，會(huì)繼續(xù)循環(huán)把敢。如果沒(méi)有改變寄摆，且f的hash值不小于0，則binCount = 1修赞。此時(shí)已經(jīng)決定死循環(huán)一定會(huì)退出婶恼。此時(shí)再進(jìn)入新的循環(huán)，和HashMap非常類(lèi)似柏副，通過(guò)拉鏈法防哈希沖突勾邦。
接下來(lái)我們?cè)賮?lái)看看ConcurrentHashMap的get方法：
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
由于在并發(fā)中，讀并不是很受影響割择。所以ConcurrentHashMap的get方法與HashMap的get方法比較相似眷篇。如果hash和key均相等則直接取出，只是hash相等則需要在鏈表中遍歷尋找key相等的對(duì)象荔泳。
通過(guò)分析三個(gè)類(lèi)的源碼分析蕉饼，我們嘗試總結(jié)一些結(jié)論：
共同點(diǎn)：
- 通過(guò)拉鏈法防哈希碰撞
HashTable:
通過(guò)
synchronized關(guān)鍵詞鎖定方法虐杯，保證線程安全。key和value均不能為空
有一個(gè)容易被誤解的contains昧港，其實(shí)就是containsValue
HashMap:
不保證線程安全
key和value均可以為空
不再有contains方法
ConcurrentHashMap:
通過(guò)死循環(huán)檢測(cè)值是否相等擎椰，然后CAS的方式保證線程安全。只有在確認(rèn)需要更換已有對(duì)象時(shí)才會(huì)加鎖
key和value均不能為空
以上创肥。
水平有限达舒，望斧正。
