HashTable，HashMap与ConcurrentHashMap源码分析
HashTable，HashMap与ConcurrentHashMap源码分析
HashMap与HashTable是两个颇为相似的类。抽象的说，都是键值对集合，那么它们之前到达有什么区别呢？似乎面试也常考啊，我们从原理的角度来分析一下。
我们先来看看HashTable的代码：
HashTable
首先，HashTable的核心是一个键值对数组。如下：
HashtableEntry<K, V>[] table;而键值对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是一个链表。它持有了一个键值对、一个hash值和链表中下一个元素。那么为什么HashTable的键值对需要一个链表呢，键值对只有一个key和value不是就可以了吗？为了回答上面的问题，我们需要再来看看HashTable中put(K , V)方法的实现：
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，这个说明HashTable很大可能是线程安全的，进入方法后我们可以看到，需要put一对键值对进来时，我们首先会从table中取出相应hash位置的键值对，然后进行一个循环，如果hash和key均相等，则替换掉现有的值，直接return了。
那么这里就有一种意外的情况，是不是有可能hash相等，key不相等。即哈希冲突。
在这样的情况下，我们发现HashTable选择将所有hash相等的键值对，存成一个链表。这样，每次我们既可以用hash值，统一索引位置，又可以避免hash冲突。
剩下的代码就是扩容、创建新的键值对，然后将新的键值对存入table。这里还会将和它hash值相同的链表，放在它的尾部。
我们再看看get(Object key)方法，与我们上面描述的原理相对应。
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中取得正确的值。取到的只是一个hash能够对应上的链表。然后，在这个链表中进行遍历，取到正确的值。这个方法叫“拉链法”。
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;
}我们发现put的方法也非常接近。只有一些细微的不同：
- HashMap的put方法没有加锁，因此HashMap并非线程安全的。
- HashMap的put方法，允许key和value为空。
- HashTable中有一个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);由于代码比较长，我们来逐段分析。其中Node的结构和我们前面所说的HashMapEntry非常类似是一个链表的节点。table也与前面一样是个Node的数组。代码首先就进入了死循环，获取了table对象，如果table为空则会创建一个table，如果hash值所在的索引为空（即之前没有相同的key存放在Map中），则直接通过CAS原子操作赋值并退出循环。
接下来我们看看，如果ConcurrentHashMap中已经存在了相同的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有没有被改变，如果已经发生改变程序会跑出同步锁，binCount为0，会继续循环。如果没有改变，且f的hash值不小于0，则binCount = 1。此时已经决定死循环一定会退出。此时再进入新的循环，和HashMap非常类似，通过拉链法防哈希冲突。
接下来我们再来看看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;
}由于在并发中，读并不是很受影响。所以ConcurrentHashMap的get方法与HashMap的get方法比较相似。如果hash和key均相等则直接取出，只是hash相等则需要在链表中遍历寻找key相等的对象。
通过分析三个类的源码分析，我们尝试总结一些结论：
共同点：
- 通过拉链法防哈希碰撞
HashTable:
- 通过
synchronized关键词锁定方法，保证线程安全。 - key和value均不能为空
- 有一个容易被误解的contains，其实就是containsValue
HashMap:
- 不保证线程安全
- key和value均可以为空
- 不再有contains方法
ConcurrentHashMap:
- 通过死循环检测值是否相等，然后CAS的方式保证线程安全。只有在确认需要更换已有对象时才会加锁
- key和value均不能为空
以上。 水平有限，望斧正。