Hashtable從JDK1.0就已經有了, 所以讓我們先來看看它是怎么工作, 然后有淺入深, 來研究HashMap的原理, 以及兩者的不同點.

Hashtable有幾個主要的字段, 如下,

/**
* The hash table data.
*/
private transient Entry[] table;

/**
* The total number of entries in the hash table.
*/
private transient int count;

/**
* The table is rehashed when its size exceeds this threshold. (The
* value of this field is (int)(capacity * loadFactor).)
*
* @serial
*/
private int threshold;



其中最重要的就是那個table數組了. 它就是整個hashtable的基本數據結構! 在來看一下這個字段
private transient Entry[] table;

可以看到, hashtable的基本數據結構就是, 一個包涵Entry類的二維數組. 而這個Entry類是hashtable的內在類, 它其實是一個單向鏈, 讓我們詳細分析一下.


private static class Entry<K,V> implements Map.Entry<K,V> {
int hash;
K key;
V value;
Entry<K,V> next;
...
...

看到這里有沒有想到學校里教的數據結構原理這門課呢? Entry類就是定義了一個很簡單的單向鏈結構, 它里面包括key, value和下個Entry類的對象next.
在這里我在強調一下, hashtable的數據結構就是一個包涵單向鏈的二維數組.


接下來讓我們來看看hashtable的構造器是長的什么樣的.

最長用的

public Hashtable() {
this(11, 0.75f);
}

這個構造器調用了另外一個構造器

public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);

if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)(initialCapacity * loadFactor);
}

細讀代碼后, 我們發現這個構造器構造了table字段和threshold. Table前面已經詳細講了, 那么這個threshold又是什么東東呢?
其 實這個threshold對hashtalbe的性能影響是很大的! 因為table是個數組, 如果在hashtable中保存的實體大于一定的數量后, 對數據的讀寫就會有很慢, 那是因為, 很多數據都保存在entry類的單向鏈中, 每次讀寫都要比對鏈中所有的數據, 鏈越長讀寫就越慢.
所以當數據容量大于threshold的時候, hashtable就會做rehash(), rehash把table的容量擴大一倍, 再把從前在table里的數據統統搬回新的table. 這樣的一個過程, 開銷是多么的大呀.
threshold = (int)(initialCapacity * loadFactor);
Hashtable類提供了構造涵數, 用戶可以自定, intitialCapacity和loadFactor. 對于那些大概知道容量的hashtable, 用戶應該自定intitialCapacity. 這樣的話, 就可以省去一大筆rehash的開銷.

現在讓我們來看hashtable的put和get操作


public synchronized V get(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}

先來看get方法, get可謂是hashtable中的最基本方法了, 它是通過key來拿到hashtable中的value.
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
從key拿到hashCode, 從hashCode再計算出在table中的index, 也就是在數組中的第幾個列.
至于為什么要與 0x7FFFFFFF, 那是hashtable 提供的hash算法, hashMap提供了不同的算法, 用戶如果要定義自己的算法也是可以的. 如果要知道不同的具體算法, 就google or 百度一下吧.

好了, 現在我們有了index, 就可以到table數組里的entry單向鏈去找value啦.

for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}

for語句就是簡單的檢索entry的單鏈, if語句檢查key是否相同. 這里就遇到了java學習中的一個重大知識點. hasCode()和equal()的關系.
大家都學過如果hasCode()的值相同的話, equal不一定相同, 而如果equal相同的話, hasCode一定要相同. 但那是為什么呢? 其實答案就在上面的代碼中!
Hashtable 的數據結構是一個包涵單向鏈的二維數組. 從hasCode我們得到hash和index, 并得以確定這個key在table數組中的第幾個列, 然而這顯然是不夠的, 因為, entry類是一個單向列, 它可以是一個, 也可能是很多個key組成, 那么要從一系列有著相同hasCode的entry中找到, 我們所要的key的話, 就要用equals了. 只有兩個key是相等的, 那才是我們要找的. 找到key之后, 只要簡單的把value返回就好了. 如果對entry類還有疑問的話, 請參考前面的解釋.



public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}

// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}

modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();

tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}

// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<K,V>(hash, key, value, e);
count++;
return null;
}

接下來再來看看put方法, 理解了get, put就很容易弄明白了.
首先, 要放入hashtable的value不能是null, 否則就報錯.
其次, 然后要確保key不能已經在hashtable里面, 有的話, 就返回value.
再次, 檢查是否容量已經太大, 如果太大話就rehash, 這會是一個很浪費資源的方法, 請參考前文.

最后, 也是最重要的, 我們要把key-value保存到hashtable中去.

Entry<K,V> e = tab[index];
tab[index] = new Entry<K,V>(hash, key, value, e);

1.拿到當前在table數組中的entry對象.
2.根據傳入的key和value建一個新的entry并賦予給當前的table的index中
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
這是entry類的構造函數. 簡單的說, 就是在單鏈的最前端加了個新的entry對象. 從這里也可以看出, 對于那些后寫入的object, 反而可以以比較快的速度讀出, 那是因為后寫入的object, 總是在鏈的前端.

看完了hashtable, 我們在來看看hashMap
hashMap可以算作是hashtable的升級版本, 最早從1.2開始有的.
整體上hashMap對hashtable類優化了代碼. 比如說, 消除了hardcoding, 增加了code reuse等等.
但是, 兩者之間最主要的不同有兩點.
1.hashMap的讀寫是unsynchronized, 在多線程的環境中要注意使用
而hashtable是synchronized
這兩者的不同是通過在讀寫方法上加synchronized關鍵字來實現的.

hashMap
public V put(K key, V value)
public V get(Object key)

hashtable
public synchronized V get(Object key)
public synchronized V put(K key, V value)

可能有人問, 能synchronized, 能線程安全好啊. 為什么不要呢?
這里其實還是一個效率的問題. 對于線程安全的方法, 系統要進行加鎖, 減鎖操作. 性能會有很大的影響. 由于很多程序是在單線程或者說是線程安全的情況下工作的, 所以用synchronized就顯得多余了.

3.第二個不同是hashMap可以放空值, 而hashtable就會報錯.
hashMap
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);

hashtable
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}