上一章我們學習了hashmap的源碼，這一節我們來讨論一下hashtable，hashtable和hashmap在某種程度上是類似的。我們依然遵循以下步驟：先對hashtable有個整體的認識，然後學習它的源碼，深入剖析hashtable。
首先看一下hashtable的繼承關系
java.lang.object
↳ java.util.dictionary<k, v>
↳ java.util.hashtable<k, v>
public class hashtable<k,v> extends dictionary<k,v>
implements map<k,v>, cloneable, java.io.serializable { }
我們可以看出，hashtable不但繼承了dictionary，而且實作了map、cloneable和serializable接口，是以hashtable也可以執行個體化。hashtable和hashmap不同，hashtable是線程安全的（等會我們在源碼中就能看出）。下面我們先總覽一下hashtable都有哪些api，然後我們詳細分析它們。
synchronized void clear()
synchronized object clone()
boolean contains(object value)
synchronized boolean containskey(object key)
synchronized boolean containsvalue(object value)
synchronized enumeration<v> elements()
synchronized set<entry<k, v>> entryset()
synchronized boolean equals(object object)
synchronized v get(object key)
synchronized int hashcode()
synchronized boolean isempty()
synchronized set<k> keyset()
synchronized enumeration<k> keys()
synchronized v put(k key, v value)
synchronized void putall(map<? extends k, ? extends v> map)
synchronized v remove(object key)
synchronized int size()
synchronized string tostring()
synchronized collection<v> values()
從hashtable的api中可以看出，hashtable之是以是線程安全的，是因為方法上都加了synchronized關鍵字。
和hashmap一樣，hashtable内部也維護了一個數組，數組中存放的是entry<k,v>實體，數組定義如下：
private transient entry<k,v>[] table;
然後我們看看entry實體的定義：
/**
* entry實體類的定義
*/
private static class entry<k,v> implements map.entry<k,v> {
int hash; //哈希值
final k key;
v value;
entry<k,v> next; //指向的下一個entry，即連結清單的下一個節點
//構造方法
protected entry(int hash, k key, v value, entry<k,v> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
//由于hashtable實作了cloneable接口，是以支援克隆操作
protected object clone() {
return new entry<>(hash, key, value, (next==null ? null : (entry<k,v>) next.clone()));
//下面對map.entry的具體操作了
public k getkey() { //拿到key
return key;
public v getvalue() { //拿到value
return value;
public v setvalue(v value) { //設定value
if (value == null) //從這裡可以看出，hashtable中的value是不允許為空的！
throw new nullpointerexception();
v oldvalue = this.value;
return oldvalue;
//判斷兩個entry是否相等
public boolean equals(object o) {
if (!(o instanceof map.entry))
return false;
map.entry<?,?> e = (map.entry)o;
//必須兩個entry的key和value均相等才行
return key.equals(e.getkey()) && value.equals(e.getvalue());
public int hashcode() { //計算hashcode
return (objects.hashcode(key) ^ objects.hashcode(value));
public string tostring() { //重寫tostring方法
return key.tostring()+"="+value.tostring();
}
從entry實體的源碼中可以看出，hashtable其實就是個存儲entry的數組，entry中包含了鍵值對以及下一個entry（用來處理沖突的），形成連結清單。而且entry中的value是不允許為nul的。好了，我們對hashtable整體上了解了後，下面開始詳細分析hashtable中的源碼。
首先我們看看hashtable都有哪些關鍵屬性：
private transient int count;//記錄hashtable中有多少entry實體
//門檻值，用于判斷是否需要調整hashtable的容量（threshold = 容量*加載因子）
private int threshold;
private float loadfactor; // 加載因子
private transient int modcount = 0; // hashtable被改變的次數，用于fail-fast
// 序列版本号
private static final long serialversionuid = 1421746759512286392l;
//最大的門限門檻值，不能超過這個
static final int alternative_hashing_threshold_default = integer.max_value;
//參數為數組容量和加載因子的構造方法
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)math.min(initialcapacity * loadfactor, max_array_size + 1);
inithashseedasneeded(initialcapacity);
//參數為初始容量的構造方法
public hashtable(int initialcapacity) {
this(initialcapacity, 0.75f); //我們可以看出，預設加載因子為0.75
}
//預設構造方法
public hashtable() { //可以看出，預設容量為11，加載因子為0.75
this(11, 0.75f);
//包含“子map”的構造函數
public hashtable(map<? extends k, ? extends v> t) {
this(math.max(2*t.size(), 11), 0.75f);//先比較容量，如果map的2倍容量大于11，則使用新的容量
putall(t);
我們可以看到，如果我們不指定數組容量和加載因子，hashtable會自動初始化容量為11，加載因子為0.75。加載因子和hashmap是相同的。
和hashmap的分析一樣，hashtable的存取部分重點分析put和get方法，其他的方法我放到代碼中分析。首先看看hashtable是如何存儲資料的：
public synchronized v put(k key, v value) {
//確定value不為空
if (value == null) {
throw new nullpointerexception();
entry tab[] = table;
int hash = hash(key); //計算哈希值
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)) { //如果對應的key已經存在
v old = e.value;
e.value = value; //替換掉原來的value
return old;
}
//否則新添加一個entry
modcount++;
if (count >= threshold) { //判斷數組中的entry數量是否已經達到門檻值
rehash(); //如果達到了，擴容
tab = table;
hash = hash(key); //重新計算哈希值
index = (hash & 0x7fffffff) % tab.length; //重新計算在新的數組中的索引
//建立一個新的entry
entry<k,v> e = tab[index];
//存到對應的位置，并将其next置為原來該位置的entry，這樣就與原來的連上了
tab[index] = new entry<>(hash, key, value, e);
count++;
return null;
然後便開始往數組中存資料了，如果目前的key已經在裡面了，那麼直接替換原來舊的value，如果不存在，先判斷數組中的entry數量有沒有達到門限值，達到了就要調用rehash方法進行擴容，然後重新計算目前key在新的數組中的索引值，然後在該位置添加進去即可。下面我們看一下rehash方法：
private static final int max_array_size = integer.max_value - 8;
protected void rehash() {
int oldcapacity = table.length;
entry<k,v>[] oldmap = table; //儲存舊數組
int newcapacity = (oldcapacity << 1) + 1; //新數組容量 = 2 * 舊容量 + 1
if (newcapacity - max_array_size > 0) {
if (oldcapacity == max_array_size)
return;
newcapacity = max_array_size; //不能超出最大值
entry<k,v>[] newmap = new entry[newcapacity];
threshold = (int)math.min(newcapacity * loadfactor, max_array_size + 1);
boolean rehash = inithashseedasneeded(newcapacity);
table = newmap;
for (int i = oldcapacity ; i-- > 0 ;) {
for (entry<k,v> old = oldmap[i] ; old != null ; ) {
entry<k,v> e = old;
old = old.next;
if (rehash) {
e.hash = hash(e.key);
}
int index = (e.hash & 0x7fffffff) % newcapacity;//重新計算在新的數組中的索引
//第一次newmap[index]為空，後面每次的nex都是目前的entry，這樣才能連上
e.next = newmap[index];
newmap[index] = e;//然後将該entry放到目前位置
到這裡put方法就分析完了，還有個putall方法，是将整個map加到目前hashtable中，内部也是周遊每個entry，然後調用上面的put方法而已，簡單看一下吧：
public synchronized void putall(map<? extends k, ? extends v> t) {
for (map.entry<? extends k, ? extends v> e : t.entryset())
put(e.getkey(), e.getvalue());
到這裡，是不是感覺hashtable其實很簡單，比hashmap簡單多了。下面來看看get方法，也很簡單，我覺得已經不用再分析了……
public synchronized v get(object key) {
int hash = hash(key); //哈希值
int index = (hash & 0x7fffffff) % tab.length; //索引值
if ((e.hash == hash) && e.key.equals(key)) {
return e.value; //拿到value
上面分析完了存取方法，剩下來的其他方法我放到代碼裡分析了，也很簡單：
//傳回數組中entry數
public synchronized int size() {
return count;
//判斷是否為空
public synchronized boolean isempty() {
return count == 0;
//傳回所有key的枚舉對象
public synchronized enumeration<k> keys() {
return this.<k>getenumeration(keys);
//傳回所有value的枚舉對象
public synchronized enumeration<v> elements() {
return this.<v>getenumeration(values);
//内部私有方法，傳回枚舉對象
private <t> enumeration<t> getenumeration(int type) {
if (count == 0) {
return collections.emptyenumeration();
} else {
return new enumerator<>(type, false); //new一個enumeration對象，見下面：
// types of enumerations/iterations
private static final int keys = 0;
private static final int values = 1;
private static final int entries = 2;
//私有内部類，實作了enumeration接口和iterator接口
private class enumerator<t> implements enumeration<t>, iterator<t> {
entry[] table = hashtable.this.table;
int index = table.length;
entry<k,v> entry = null;
entry<k,v> lastreturned = null;
int type;
//該字段用來決定是使用iterator還是enumeration
boolean iterator; //false表示使用enumeration
//fail-fast
protected int expectedmodcount = modcount;
enumerator(int type, boolean iterator) {
this.type = type;
this.iterator = iterator;
public boolean hasmoreelements() { //判斷是否含有下一個元素
entry<k,v> e = entry;
int i = index;
entry[] t = table;
/* use locals for faster loop iteration */
while (e == null && i > 0) {
e = t[--i];
entry = e;
index = i;
return e != null;
public t nextelement() { //獲得下一個元素
entry<k,v> et = entry;
while (et == null && i > 0) {
et = t[--i];
entry = et;
if (et != null) {
entry<k,v> e = lastreturned = entry;
entry = e.next;
//根據傳進來的關鍵字決定傳回什麼
return type == keys ? (t)e.key : (type == values ? (t)e.value : (t)e);
throw new nosuchelementexception("hashtable enumerator");
// iterator methods
public boolean hasnext() {
return hasmoreelements();
public t next() {
if (modcount != expectedmodcount)
throw new concurrentmodificationexception();
return nextelement();
public void remove() {
if (!iterator)
throw new unsupportedoperationexception();
if (lastreturned == null)
throw new illegalstateexception("hashtable enumerator");
synchronized(hashtable.this) { //保證了線程安全
entry[] tab = hashtable.this.table;
int index = (lastreturned.hash & 0x7fffffff) % tab.length;
for (entry<k,v> e = tab[index], prev = null; e != null;
prev = e, e = e.next) {
if (e == lastreturned) {
modcount++;
expectedmodcount++;
if (prev == null)
tab[index] = e.next;
else
prev.next = e.next;
count--;
lastreturned = null;
return;
}
//判斷hashtable中是否包含value值
public synchronized boolean contains(object value) {
if (value == null) { //value不能為空
//從後向前周遊table數組中的元素（entry）
for (int i = tab.length ; i-- > 0 ;) {
for (entry<k,v> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
return false;
public boolean containsvalue(object value) {
return contains(value);
//判斷hashtable中是否包含key
public synchronized boolean containskey(object key) {
int hash = hash(key);
int index = (hash & 0x7fffffff) % tab.length;
return true;
//删除hashtable中鍵為key的entry，并傳回value
public synchronized v remove(object key) {
//找到key對應的entry，然後在連結清單中找到要删除的節點，删除之。
for (entry<k,v> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
modcount++;
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
count--;
v oldvalue = e.value;
e.value = null;
return oldvalue;
//清空hashtable
public synchronized void clear() {
for (int index = tab.length; --index >= 0; )
tab[index] = null; //将hashtable中數組值全部設定為null
count = 0;
//克隆一個hashtable，并以object的形式傳回
public synchronized object clone() {
try {
hashtable<k,v> t = (hashtable<k,v>) super.clone();
t.table = new entry[table.length];
for (int i = table.length ; i-- > 0 ; ) {
t.table[i] = (table[i] != null)
? (entry<k,v>) table[i].clone() : null;
t.keyset = null;
t.entryset = null;
t.values = null;
t.modcount = 0;
return t;
} catch (clonenotsupportedexception e) {
// this shouldn't happen, since we are cloneable
throw new internalerror();
//重寫tostring方法：{, ,}
public synchronized string tostring() {
int max = size() - 1;
if (max == -1)
return "{}";
stringbuilder sb = new stringbuilder();
iterator<map.entry<k,v>> it = entryset().iterator();
sb.append('{');
for (int i = 0; ; i++) {
map.entry<k,v> e = it.next();
k key = e.getkey();
v value = e.getvalue();
sb.append(key == this ? "(this map)" : key.tostring());
sb.append('=');
sb.append(value == this ? "(this map)" : value.tostring());
if (i == max)
return sb.append('}').tostring();
sb.append(", ");
}
// hashtable的“key的集合”。它是一個set，意味着沒有重複元素
private transient volatile set<k> keyset = null;
// hashtable的“key-value的集合”。它是一個set，意味着沒有重複元素
private transient volatile set<map.entry<k,v>> entryset = null;
// hashtable的“value的集合”。它是一個collection，意味着可以有重複元素
private transient volatile collection<v> values = null;
//傳回一個被synchronizedset封裝後的keyset對象
//synchronizedset封裝的目的是對keyset的所有方法都添加synchronized，實作多線程同步
public set<k> keyset() {
if (keyset == null)
keyset = collections.synchronizedset(new keyset(), this);
return keyset;
private class keyset extends abstractset<k> {
public iterator<k> iterator() {
return getiterator(keys); //傳回一個疊代器，裝有hashtable的資訊
//從這裡也可以看出，擷取到了key的set集合後，要想取資料，隻能通過疊代器
public int size() {
return count;
public boolean contains(object o) {
return containskey(o);
public boolean remove(object o) {
return hashtable.this.remove(o) != null;
public void clear() {
hashtable.this.clear();
// 擷取hashtable的疊代器
// 若hashtable的實際大小為0,則傳回“空疊代器”對象；
// 否則，傳回正常的enumerator的對象。(由上面代碼可知，enumerator實作了疊代器和枚舉兩個接口)
private <t> iterator<t> getiterator(int type) {
return collections.emptyiterator();
return new enumerator<>(type, true);
//傳回一個被synchronizedset封裝後的entryset對象
public set<map.entry<k,v>> entryset() {
if (entryset==null)
entryset = collections.synchronizedset(new entryset(), this);
return entryset;
//跟keyset類似
private class entryset extends abstractset<map.entry<k,v>> {
public iterator<map.entry<k,v>> iterator() {
return getiterator(entries);
public boolean add(map.entry<k,v> o) {
return super.add(o);
// 查找entryset中是否包含object(o)
// 首先，在table中找到o對應的entry(entry是一個單向連結清單)
// 然後，查找entry連結清單中是否存在object
map.entry entry = (map.entry)o;
object key = entry.getkey();
entry[] tab = table;
int hash = hash(key);
int index = (hash & 0x7fffffff) % tab.length;
for (entry e = tab[index]; e != null; e = e.next)
if (e.hash==hash && e.equals(entry))
return false;
// 删除元素object(o)
// 然後，删除連結清單中的元素object
map.entry<k,v> entry = (map.entry<k,v>) o;
k key = entry.getkey();
for (entry<k,v> e = tab[index], prev = null; e != null;
prev = e, e = e.next) {
if (e.hash==hash && e.equals(entry)) {
modcount++;
if (prev != null)
prev.next = e.next;
else
tab[index] = e.next;
count--;
e.value = null;
// 傳回一個被synchronizedcollection封裝後的valuecollection對象
// synchronizedcollection封裝的目的是對valuecollection的所有方法都添加synchronized，實作多線程同步
public collection<v> values() {
if (values==null)
values = collections.synchronizedcollection(new valuecollection(),
this);
return values;
private class valuecollection extends abstractcollection<v> {
public iterator<v> iterator() {
return getiterator(values); //同上
return containsvalue(o);
//重寫equals()方法
// 若兩個hashtable的所有key-value鍵值對都相等，則判斷它們兩個相等
public synchronized boolean equals(object o) {
if (o == this)
return true;
if (!(o instanceof map))
map<k,v> t = (map<k,v>) o;
if (t.size() != size())
iterator<map.entry<k,v>> i = entryset().iterator();
while (i.hasnext()) {
map.entry<k,v> e = i.next();
k key = e.getkey();
v value = e.getvalue();
if (value == null) {
if (!(t.get(key)==null && t.containskey(key)))
return false;
if (!value.equals(t.get(key)))
} catch (classcastexception unused) {
} catch (nullpointerexception unused) {
return true;
//計算哈希值
//若hashtable的實際大小為0或者加載因子<0，則傳回0
//否則傳回“hashtable中的每個entry的key和value的異或值的總和”
public synchronized int hashcode() {
int h = 0;
if (count == 0 || loadfactor < 0)
return h; // returns zero
loadfactor = -loadfactor; // mark hashcode computation in progress
entry[] tab = table;
for (entry<k,v> entry : tab)
while (entry != null) {
h += entry.hashcode();
entry = entry.next;
loadfactor = -loadfactor; // mark hashcode computation complete
return h;
// java.io.serializable的寫入函數
// 将hashtable的“總的容量，實際容量，所有的entry”都寫入到輸出流中
private void writeobject(java.io.objectoutputstream s)
throws ioexception {
entry<k, v> entrystack = null;
synchronized (this) {
// write out the length, threshold, loadfactor
s.defaultwriteobject();
// write out length, count of elements
s.writeint(table.length);
s.writeint(count);
// stack copies of the entries in the table
for (int index = 0; index < table.length; index++) {
entry<k,v> entry = table[index];
while (entry != null) {
entrystack =
new entry<>(0, entry.key, entry.value, entrystack);
entry = entry.next;
// write out the key/value objects from the stacked entries
while (entrystack != null) {
s.writeobject(entrystack.key);
s.writeobject(entrystack.value);
entrystack = entrystack.next;
// java.io.serializable的讀取函數：根據寫入方式讀出
// 将hashtable的“總的容量，實際容量，所有的entry”依次讀出
private void readobject(java.io.objectinputstream s)
throws ioexception, classnotfoundexception
{
// read in the length, threshold, and loadfactor
s.defaultreadobject();
// read the original length of the array and number of elements
int origlength = s.readint();
int elements = s.readint();
// compute new size with a bit of room 5% to grow but
// no larger than the original size. make the length
// odd if it's large enough, this helps distribute the entries.
// guard against the length ending up zero, that's not valid.
int length = (int)(elements * loadfactor) + (elements / 20) + 3;
if (length > elements && (length & 1) == 0)
length--;
if (origlength > 0 && length > origlength)
length = origlength;
entry<k,v>[] newtable = new entry[length];
threshold = (int) math.min(length * loadfactor, max_array_size + 1);
inithashseedasneeded(length);
// read the number of elements and then all the key/value objects
for (; elements > 0; elements--) {
k key = (k)s.readobject();
v value = (v)s.readobject();
// synch could be eliminated for performance
reconstitutionput(newtable, key, value);
this.table = newtable;
private void reconstitutionput(entry<k,v>[] tab, k key, v value)
throws streamcorruptedexception
throw new java.io.streamcorruptedexception();
// makes sure the key is not already in the hashtable.
// this should not happen in deserialized version.
throw new java.io.streamcorruptedexception();
// creates the new entry.
hashtable的周遊方式比較簡單，一般分兩步：
1. 獲得entry或key或value的集合；
2. 通過iterator疊代器或者enumeration周遊此集合。
// 假設table是hashtable對象
// table中的key是string類型，value是integer類型
integer value = null;
iterator iter = table.entryset().iterator();
while(iter.hasnext()) {
map.entry entry = (map.entry)iter.next();
// 擷取key
key = (string)entry.getkey();
// 擷取value
value = (integer)entry.getvalue();
string key = null;
iterator iter = table.keyset().iterator();
while (iter.hasnext()) {
key = (string)iter.next();
// 根據key，擷取value
value = (integer)table.get(key);
collection c = table.values();
iterator iter= c.iterator();
value = (integer)iter.next();
enumeration enu = table.keys();
while(enu.hasmoreelements()) {
system.out.println(enu.nextelement());
enumeration enu = table.elements();
hashtable的周遊就介紹到這吧，至此，hashtable的源碼就讨論完了，如有錯誤之處，歡迎留言指正~
轉載：http://blog.csdn.net/eson_15/article/details/51208166