史上最詳細的HashTable源碼解析，最容易懂

HashTable源碼分析

更多資源和教程請關(guān)注公眾號：非科班的科班。
如果覺得我寫的還可以請給個贊，謝謝大家，你的鼓勵是我創(chuàng)作的動力
###1.前言
Hashtable 一個元老級的集合類，早在 JDK 1.0 就誕生了

###1.1.摘要
在集合系列的第一章，咱們了解到，Map 的實現(xiàn)類有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、HashTable、Properties 等等。

###1.2.簡介
Hashtable 一個元老級的集合類，早在 JDK 1.0 就誕生了，而 HashMap 誕生于 JDK 1.2，在實現(xiàn)上，HashMap 吸收了很多 Hashtable 的思想，雖然二者的底層數(shù)據(jù)結(jié)構(gòu)都是 數(shù)組 + 鏈表 結(jié)構(gòu)，具有查詢、插入、刪除快的特點，但是二者又有很多的不同。

?打開 Hashtable 的源碼可以看到，Hashtable 繼承自 Dictionary，而 HashMap 繼承自 AbstractMap。

public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
.....
}

?HashMap 繼承自 AbstractMap，HashMap 類的定義如下：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    .....
}

?Hashtable 和 HashMap 的底層是以數(shù)組來存儲，同時，在存儲數(shù)據(jù)通過key計算數(shù)組下標的時候，是以哈希算法為主，因此可能會產(chǎn)生哈希沖突的可能性。

?通俗的說呢，就是不同的key，在計算的時候，可能會產(chǎn)生相同的數(shù)組下標，這個時候，如何將兩個對象放入一個數(shù)組中呢？

?而解決哈希沖突的辦法，有兩種，一種開放地址方式（當發(fā)生 hash 沖突時，就繼續(xù)以此繼續(xù)尋找，直到找到?jīng)]有沖突的hash值），另一種是拉鏈方式（將沖突的元素放入鏈表）。

Java Hashtable 采用的就是第二種方式，拉鏈法！

于是，當發(fā)生不同的key通過一系列的哈希算法計算獲取到相同的數(shù)組下標的時候，會將對象放入一個數(shù)組容器中，然后將對象以單向鏈表的形式存儲在同一個數(shù)組下標容器中，就像鏈子一樣，掛在某個節(jié)點上，如下圖：

與 HashMap 類似，Hashtable 也包括五個成員變量：
/**由Entry對象組成的數(shù)組*/
private transient Entry[] table;

/**Hashtable中Entry對象的個數(shù)*/
private transient int count;

/**Hashtable進行擴容的閾值*/
private int threshold;

/**負載因子，默認0.75*/
private float loadFactor;

/**記錄修改的次數(shù)*/
private transient int modCount = 0;

具體各個變量含義如下：

?table：表示一個由 Entry 對象組成的鏈表數(shù)組，Entry 是一個單向鏈表，哈希表的key-value鍵值對都是存儲在 Entry 數(shù)組中的;
?count：表示 Hashtable 的大小，用于記錄保存的鍵值對的數(shù)量;
?threshold：表示 Hashtable 的閾值，用于判斷是否需要調(diào)整 Hashtable 的容量，threshold 等于容量 * 加載因子;
?loadFactor：表示負載因子，默認為 0.75；
?modCount：表示記錄 Hashtable 修改的次數(shù)，用來實現(xiàn)快速失敗拋異常處理；

接著來看看Entry這個內(nèi)部類，Entry用于存儲鏈表數(shù)據(jù)，實現(xiàn)了Map.Entry接口，本質(zhì)是就是一個映射（鍵值對），源碼如下：

private static class Entry<K,V> implements Map.Entry<K,V> {

/**hash值*/
final int hash;

/**key表示鍵*/
final K key;

/**value表示值*/
V value;

/**節(jié)點下一個元素*/
Entry<K,V> next;
......
}

我們再接著來看看 Hashtable 初始化過程，核心源碼如下：

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

this 調(diào)用了自己的構(gòu)造方法，核心源碼如下：

public Hashtable(int initialCapacity, float loadFactor) {
.....
//默認的初始大小為 11
//并且計算擴容的閾值
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

可以看到 HashTable 默認的初始大小為 11，如果在初始化給定容量大小，那么 HashTable 會直接使用你給定的大??；

擴容的閾值threshold等于initialCapacity * loadFactor，我們在來看看 HashTable 擴容，方法如下：

protected void rehash() {
int oldCapacity = table.length;
//將舊數(shù)組長度進行位運算，然后 +1
//等同于每次擴容為原來的 2n+1
int newCapacity = (oldCapacity << 1) + 1;

//省略部分代碼......
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
}

可以看到，HashTable 每次擴充為原來的 2n+1。

我們再來看看 HashMap，如果是執(zhí)行默認構(gòu)造方法，會在擴容那一步，進行初始化大小，核心源碼如下：

final Node<K,V>[] resize() {
int newCap = 0;

//部分代碼省略......
newCap = DEFAULT_INITIAL_CAPACITY;//默認容量為 16
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
}

可以看出 HashMap 的默認初始化大小為 16，我們再來看看，HashMap 擴容方法，核心源碼如下：

final Node<K,V>[] resize() {
//獲取舊數(shù)組的長度
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int newCap = 0;

//部分代碼省略......
//當進行擴容的時候，容量為 2 的倍數(shù)
newCap = oldCap << 1;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
}

可以看出 HashMap 的擴容后的數(shù)組數(shù)量為原來的 2 倍；

也就是說 HashTable 會盡量使用素數(shù)、奇數(shù)來做數(shù)組的容量，而 HashMap 則總是使用 2 的冪作為數(shù)組的容量。

我們知道當哈希表的大小為素數(shù)時，簡單的取模哈希的結(jié)果會更加均勻，所以單從這一點上看，HashTable 的哈希表大小選擇，似乎更高明些。

Hashtable 的 hash 算法，核心代碼如下：

//直接計算key.hashCode()
int hash = key.hashCode();

//通過除法取余計算數(shù)組存放下標
// 0x7FFFFFFF 是最大的 int 型數(shù)的二進制表示
int index = (hash & 0x7FFFFFFF) % tab.length;

從源碼部分可以看出，HashTable 的 key 不能為空，否則報空指針錯誤！

但另一方面我們又知道，在取模計算時，如果模數(shù)是 2 的冪，那么我們可以直接使用位運算來得到結(jié)果，效率要大大高于做除法。所以在 hash 計算數(shù)組下標的效率上，HashMap 卻更勝一籌，但是這也會引入了哈希分布不均勻的問題， HashMap 為解決這問題，又對 hash 算法做了一些改動，具體我們來看看。

HashMap 的 hash 算法，核心代碼如下：

/**獲取hash值方法*/
static final int hash(Object key) {
    int h;
    // h = key.hashCode() 為第一步 取hashCode值（jdk1.7）
    // h ^ (h >>> 16)  為第二步 高位參與運算（jdk1.7）
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//jdk1.8
}

/**獲取數(shù)組下標方法*/
static int indexFor(int h, int length) {
    //jdk1.7的源碼，jdk1.8沒有這個方法，但是實現(xiàn)原理一樣的
    return h & (length-1);  //第三步 取模運算
}

HashMap 由于使用了2的冪次方，所以在取模運算時不需要做除法，只需要位的與運算就可以了。但是由于引入的 hash 沖突加劇問題，HashMap 在調(diào)用了對象的 hashCode 方法之后，又做了一些高位運算，也就是第二步方法，來打散數(shù)據(jù)，讓哈希的結(jié)果更加均勻。

###1.3.常用方法介紹
####1.3.1.put方法
put 方法是將指定的 key, value 對添加到 map 里。

put 流程圖如下：

打開 HashTable 的 put 方法，源碼如下：

public synchronized V put(K key, V value) {
//當 value 值為空的時候，拋異常！
if (value == null) {
throw new NullPointerException();
}

Entry<?,?> tab[] = table;

//通過key 計算存儲下標
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

//循環(huán)遍歷數(shù)組鏈表
//如果有相同的key并且hash相同，進行覆蓋處理
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}

//加入數(shù)組鏈表中
addEntry(hash, key, value, index);
return null;
}

put 方法中的 addEntry 方法，源碼如下：

private void addEntry(int hash, K key, V value, int index) {
    //新增修改次數(shù)
    modCount++;

    Entry<?,?> tab[] = table;
    if (count >= threshold) {
       //數(shù)組容量大于擴容閥值，進行擴容
        rehash();

        tab = table;
        //重新計算對象存儲下標
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    //將對象存儲在數(shù)組中
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

addEntry 方法中的 rehash 方法，源碼如下：

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    //每次擴容為原來的 2n+1
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            //大于最大閥值，不再擴容
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    //重新計算擴容閥值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
    //將舊數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組中
    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;
        }
    }
}

總結(jié)流程如下：
?1、通過 key 計算對象存儲在數(shù)組中的下標；
?2、如果鏈表中有 key，直接進行新舊值覆蓋處理；
?3、如果鏈表中沒有 key，判斷是否需要擴容，如果需要擴容，先擴容，再插入數(shù)據(jù)；

有一個值得注意的地方是 put 方法加了synchronized關(guān)鍵字，所以，在同步操作的時候，是線程安全的。

####1.3.2.get方法
get 方法根據(jù)指定的 key 值返回對應(yīng)的 value。

get 流程圖如下：

打開 HashTable 的 get 方法，源碼如下：

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    //通過key計算節(jié)點存儲下標
    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;
}

同樣，有一個值得注意的地方是 get 方法加了synchronized關(guān)鍵字，所以，在同步操作的時候，是線程安全的。

####1.3.3.remove方法
remove 的作用是通過 key 刪除對應(yīng)的元素。

remove 流程圖如下：

打開 HashTable 的 remove 方法，源碼如下：

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    //通過key計算節(jié)點存儲下標
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    Entry<K,V> e = (Entry<K,V>)tab[index];
    //循環(huán)遍歷鏈表，通過hash和key判斷鍵是否存在
    //如果存在，直接將改節(jié)點設(shè)置為空，并從鏈表上移除
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}

同樣，有一個值得注意的地方是 remove 方法加了synchronized關(guān)鍵字，所以，在同步操作的時候，是線程安全的。

####1..3.4.總結(jié)
總結(jié)一下 Hashtable 與 HashMap 的聯(lián)系與區(qū)別，內(nèi)容如下：

?1、雖然 HashMap 和 Hashtable 都實現(xiàn)了 Map 接口，但 Hashtable 繼承于 Dictionary 類，而 HashMap 是繼承于 AbstractMap；
?2、HashMap 可以允許存在一個為 null 的 key 和任意個為 null 的 value，但是 HashTable 中的 key 和 value 都不允許為 null；
?3、Hashtable 的方法是同步的，因為在方法上加了 synchronized 同步鎖，而 HashMap 是非線程安全的；

盡管，Hashtable 雖然是線程安全的，但是我們一般不推薦使用它，因為有比它更高效、更好的選擇 ConcurrentHashMap，在后面我們也會講到它。
最后，引入來自 HashTable 的注釋描述：

If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.

簡單來說就是，如果你不需要線程安全，那么使用 HashMap，如果需要線程安全，那么使用 ConcurrentHashMap。

更多資源和教程請關(guān)注公眾號：非科班的科班。
努力不一定成功，但是放棄一定失敗，把過程留給自己，把結(jié)果留給他人，當你的才華撐不起你的雄心的時候，你就應(yīng)該好好努力了

最后分享一波java的資源，資源包括java從入門到開發(fā)的全套視頻，以及java的26個項目，資源比較大，大小大概是290g左右，鏈接容易失效，獲取的方式是關(guān)注公眾號：非科班的科班，讓后回復(fù)：java項目即可獲得，祝大家學(xué)習(xí)愉快