文章首發(fā)csdn博客地址：https://blog.csdn.net/u013277209?viewmode=contents
一：整體實現(xiàn)
- HashTable和HashMap實現(xiàn)大致相同，都是基于哈希表來實現(xiàn)的，數(shù)組+鏈表的形式（和HashMap有稍微的區(qū)別，HashMap加入了紅黑樹），它存儲的內(nèi)容是鍵值對(key-value)映射啦撮。
- Hashtable 繼承于Dictionary，實現(xiàn)了Map镣陕、Cloneable津坑、java.io.Serializable接口。Dictionary是一個過時的鍵值對映射的抽象類蚕冬，jdk已經(jīng)不建議使用免猾，新的實現(xiàn)應(yīng)該實現(xiàn)Map接口，而不是擴展這個類囤热。
- HashTable方法加了synchronized關(guān)鍵字猎提，所以是線程安全的。
二：重要字段
private transient Entry<?,?>[] table;
private transient int count;
private int threshold;
private float loadFactor;
private transient int modCount = 0;
table實現(xiàn)哈希表的數(shù)組結(jié)構(gòu)旁蔼，數(shù)組長度最小為1，默認為11，里面存儲著Entry
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;//哈希值容贝，用于定位數(shù)組索引位置
final K key;//鍵
V value;//值
Entry<K,V> next;//鏈表下一個元素
}
Entry是HashTable的一個內(nèi)部類淹接，實現(xiàn)了Map.Entry接口，本質(zhì)是就是一個映射(鍵值對)限佩。
count是HashTable中實際存在的鍵值對數(shù)量葵诈，而modCount字段主要用來記錄HashTable內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)，主要用于迭代的快速失敗祟同。強調(diào)一點作喘，內(nèi)部結(jié)構(gòu)發(fā)生變化指的是結(jié)構(gòu)發(fā)生變化，例如put新鍵值對晕城，但是某個key對應(yīng)的value值被覆蓋不屬于結(jié)構(gòu)變化泞坦。
loadFactor為負載因子(默認值是0.75)，threshold是HashTable所能容納的最大數(shù)據(jù)量的Entry(鍵值對)個數(shù)砖顷。threshold = length * loadFactor暇矫。也就是說，在數(shù)組定義好長度之后择吊，負載因子越大李根，所能容納的鍵值對個數(shù)越多。
threshold就是在此loadFactor和length(數(shù)組長度)對應(yīng)下允許的最大元素數(shù)目几睛，超過這個數(shù)目就重新rehash(擴容)房轿，擴容后的HashTable容量是之前容量的兩倍+1。默認的負載因子0.75是對空間和時間效率的一個平衡選擇，建議不要修改囱持，除非在時間和空間比較特殊的情況下夯接，如果內(nèi)存空間很多而又對時間效率要求很高，可以降低負載因子loadFactor的值纷妆；相反盔几，如果內(nèi)存空間緊張而對時間效率要求不高，可以增加負載因子loadFactor的值掩幢，這個值可以大于1逊拍。
三：擴容機制
當前鍵值對的數(shù)量count >= threshold時會觸發(fā)擴容。
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
//新容量=舊容量 * 2 + 1
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
//新建一個size = newCapacity的數(shù)組
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
//重新計算閥值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
//將原來的元素拷貝到新的HashTable中际邻，對數(shù)組鏈表數(shù)據(jù)進行重新 hash index 計算芯丧，
//rehash之后會使得最早插入的數(shù)據(jù)回到鏈表的第一位
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
在這個rehash()方法中我們可以看到容量擴大兩倍+1，同時需要將原來HashTable中的元素一一復(fù)制到新的HashTable中,并且對每個元素根據(jù)hash值從新計算下標世曾，這個過程是比較消耗時間的缨恒。
四：put方法
put方法的整個處理流程：計算key的hash值，根據(jù)hash值獲得key在table數(shù)組中的索引位置轮听，然后迭代該key處的Entry鏈表（我們暫且理解為鏈表）骗露，若該鏈表中存在一個這個的key對象，那么就直接替換其value值即可血巍，否則在將改key-value節(jié)點插入該index索引位置處
public synchronized V put(K key, V value) {
// 值不能為空
if (value == null) {
throw new NullPointerException();
}
//計算key的hash值椒袍，確認在table[]中的索引位置
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
//迭代index索引位置，如果該位置處的鏈表中存在一個一樣的key藻茂，則替換其value驹暑，返回舊值
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
//如果不存在，則創(chuàng)建entry加入hash表中
addEntry(hash, key, value, index);
return null;
}
//在指定索引位置加入key-value鍵值對
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
//如果當前元素的數(shù)量大于等于閾值辨赐，則觸發(fā)擴容
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// 創(chuàng)建entry并加入到鏈表的頭
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
五：get方法
get方法比較簡單优俘，處理過程就是計算key的hash值，判斷在table數(shù)組中的索引位置掀序，然后迭代鏈表帆焕，匹配直到找到相對應(yīng)key的value,若沒有找到返回null。
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
六：HashTable和HashMap區(qū)別
- HashMap線程不安全不恭，HashTable是線程安全的叶雹。HashMap內(nèi)部實現(xiàn)沒有任何線程同步相關(guān)的代碼，所以相對而言性能要好一點换吧。如果在多線程中使用HashMap需要自己管理線程同步折晦。HashTable大部分對外接口都使用synchronized包裹，所以是線程安全的沾瓦，但是性能會相對差一些满着。
- 二者的基類不一樣谦炒。HashMap派生于AbstractMap，HashTable派生于Dictionary风喇。它們都實現(xiàn)Map, Cloneable, Serializable這些接口宁改。AbstractMap中提供的基礎(chǔ)方法更多，并且實現(xiàn)了多個通用的方法魂莫，而在Dictionary中只有少量的接口还蹲，并且都是abstract類型。
- key和value的取值范圍不同耙考。HashMap的key和value都可以為null谜喊，但是HashTable key和value都不能為null。對于HashMap如果get返回null琳骡，并不能表明HashMap不存在這個key锅论，如果需要判斷HashMap中是否包含某個key讼溺，就需要使用containsKey這個方法來判斷楣号。
- 算法不一樣。HashMap的initialCapacity為16怒坯，而HashTable的initialCapacity為11炫狱。HashMap中初始容量必須是2的冪,如果初始化傳入的initialCapacity不是2的冪，將會自動調(diào)整為大于出入的initialCapacity最小的2的冪剔猿。HashMap使用自己的計算hash的方法(會依賴key的hashCode方法)视译，HashTable則使用key的hashCode方法得到。
