1. 概述

上次討論了HashMap的結(jié)構(gòu)，原理和實(shí)現(xiàn)，本文來(lái)對(duì)Map家族的另外一個(gè)常用集合HashTable進(jìn)行介紹。HashTable和HashMap兩種集合非常相似，經(jīng)常被各種面試官問(wèn)到兩者的區(qū)別。

對(duì)于兩者的區(qū)別，主要有以下幾點(diǎn)：

HashMap是非同步的，沒(méi)有對(duì)讀寫等操作進(jìn)行鎖保護(hù)，所以是線程不安全的，在多線程場(chǎng)景下會(huì)出現(xiàn)數(shù)據(jù)不一致的問(wèn)題。而HashTable是同步的，所有的讀寫等操作都進(jìn)行了鎖（synchronized）保護(hù)，在多線程環(huán)境下沒(méi)有安全問(wèn)題。但是鎖保護(hù)也是有代價(jià)的，會(huì)對(duì)讀寫的效率產(chǎn)生較大影響。

HashMap結(jié)構(gòu)中，是允許保存null的，Entry.key和Entry.value均可以為null。但是HashTable中是不允許保存null的。

HashMap的迭代器（Iterator）是fail-fast迭代器，但是Hashtable的迭代器（enumerator）不是fail-fast的。如果有其它線程對(duì)HashMap進(jìn)行的添加/刪除元素，將會(huì)拋出ConcurrentModificationException，但迭代器本身的remove方法移除元素則不會(huì)拋出異常。這條同樣也是Enumeration和Iterator的區(qū)別。

2. 原理

HashTable類中，保存實(shí)際數(shù)據(jù)的，依然是Entry對(duì)象。其數(shù)據(jù)結(jié)構(gòu)與HashMap是相同的。

HashTable類繼承自Dictionary類，實(shí)現(xiàn)了三個(gè)接口，分別是Map，Cloneable和java.io.Serializable，如下圖所示。

HashTable中的主要方法，如put，get，remove和rehash等，與HashMap中的功能相同，這里不作贅述，可以參考另外一篇文章HashMap原理和底層實(shí)現(xiàn)

3. 源碼分析

HashTable的主要方法的源碼實(shí)現(xiàn)邏輯，與HashMap中非常相似，有一點(diǎn)重大區(qū)別就是所有的操作都是通過(guò)synchronized鎖保護(hù)的。只有獲得了對(duì)應(yīng)的鎖，才能進(jìn)行后續(xù)的讀寫等操作。（鎖住整個(gè)table）

1. put方法

put方法的主要邏輯如下：

先獲取synchronized鎖。

put方法不允許null值，如果發(fā)現(xiàn)是null，則直接拋出異常。

計(jì)算key的哈希值和index

遍歷對(duì)應(yīng)位置的鏈表，如果發(fā)現(xiàn)已經(jīng)存在相同的hash和key，則更新value，并返回舊值。

如果不存在相同的key的Entry節(jié)點(diǎn)，則調(diào)用addEntry方法增加節(jié)點(diǎn)。

addEntry方法中，如果需要?jiǎng)t進(jìn)行擴(kuò)容，之后添加新節(jié)點(diǎn)到鏈表頭部。

public synchronized V put(K key, V value) {// Make sure the value is not nullif (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;@SuppressWarnings("unchecked")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;}}addEntry(hash, key, value, index);return null;} private void addEntry(int hash, K key, V value, int index) {modCount++;Entry<?,?> tab[] = table;if (count >= threshold) {// Rehash the table if the threshold is exceededrehash();tab = table;hash = key.hashCode();index = (hash & 0x7FFFFFFF) % tab.length;}// Creates the new entry.@SuppressWarnings("unchecked")Entry<K,V> e = (Entry<K,V>) tab[index];tab[index] = new Entry<>(hash, key, value, e);count++;}

2. get方法

get方法的主要邏輯如下

先獲取synchronized鎖。

計(jì)算key的哈希值和index。

在對(duì)應(yīng)位置的鏈表中尋找具有相同hash和key的節(jié)點(diǎn)，返回節(jié)點(diǎn)的value。

如果遍歷結(jié)束都沒(méi)有找到節(jié)點(diǎn)，則返回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;}

3.rehash擴(kuò)容方法

rehash擴(kuò)容方法主要邏輯如下：

數(shù)組長(zhǎng)度增加一倍（如果超過(guò)上限，則設(shè)置成上限值）。

更新哈希表的擴(kuò)容門限值。

遍歷舊表中的節(jié)點(diǎn)，計(jì)算在新表中的index，插入到對(duì)應(yīng)位置鏈表的頭部。（可以見得，Hashtable使用頭插法）

protected void rehash() {int oldCapacity = table.length;Entry<?,?>[] oldMap = table;// overflow-conscious codeint newCapacity = (oldCapacity << 1) + 1;if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;newCapacity = MAX_ARRAY_SIZE;}Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];modCount++;threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);table = newMap;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;}}}

4.remove方法

remove方法主要邏輯如下：

先獲取synchronized鎖。

計(jì)算key的哈希值和index。

遍歷對(duì)應(yīng)位置的鏈表，尋找待刪除節(jié)點(diǎn)，如果存在，用e表示待刪除節(jié)點(diǎn)，pre表示前驅(qū)節(jié)點(diǎn)。如果不存在，返回null。

更新前驅(qū)節(jié)點(diǎn)的next，指向e的next。返回待刪除節(jié)點(diǎn)的value值。

4. 總結(jié)

HashTable相對(duì)于HashMap的最大特點(diǎn)就是線程安全，所有的操作都是被synchronized鎖保護(hù)的

?

總結(jié)

以上是生活随笔為你收集整理的Java集合：Hashtable源码分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。