終于有人把HashTable這種數(shù)據(jù)結(jié)構(gòu)講清楚了！
概論
HashTable是遺留類，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類，并且是線程安全的，并發(fā)性不如ConcurrentHashMap，因?yàn)镃oncurrentHashMap引入了分段鎖。
Hashtable不建議在新代碼中使用，不需要線程安全的場(chǎng)合可以用HashMap替換，需要線程安全的場(chǎng)合可以用ConcurrentHashMap替換。
對(duì)比HashMap 的初始容量
默認(rèn)11 的初始容量
需要注意的是Hashtable的默認(rèn)初始容量大小是11，而HashMap 是16,但是他們的加載因子都是0.75f
????/**
?????*?Constructs?a?new,?empty?hashtable?with?a?default?initial?capacity?(11)
?????*?and?load?factor?(0.75).
?????*/
????public?Hashtable()?{
????????this(11,?0.75f);
????}
/**
?*?Constructs?an?empty?HashMap?with?the?default?initial?capacity
?*?(16)?and?the?default?load?factor?(0.75).
?*/
public?HashMap()?{
????this.loadFactor?=?DEFAULT_LOAD_FACTOR;?//?all?other?fields?defaulted
}
任意指定非負(fù)的容量
還有一點(diǎn)就是Hashtable的initialCapacity 也就是初始容量是是可以是你指定的任何非負(fù)整數(shù)，也就是你給它設(shè)置個(gè)0 也可以的
public?Hashtable(int?initialCapacity)?{
????this(initialCapacity,?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)Math.min(initialCapacity?*?loadFactor,?MAX_ARRAY_SIZE?+?1);
}
但是你看一下HashMap 的初始容量就不那么聽(tīng)話了，默認(rèn)情況下，當(dāng)我們?cè)O(shè)置HashMap的初始化容量時(shí)，實(shí)際上HashMap會(huì)采用第一個(gè)大于該數(shù)值的2的冪作為初始化容量(0 1 除外)
public?HashMap(int?initialCapacity,?float?loadFactor)?{
????if?(initialCapacity?0)
????????throw?new?IllegalArgumentException("Illegal?initial?capacity:?"?+?initialCapacity);
????if?(initialCapacity?>?MAXIMUM_CAPACITY)
????????initialCapacity?=?MAXIMUM_CAPACITY;
????if?(loadFactor?<=?0?||?Float.isNaN(loadFactor))
????????throw?new?IllegalArgumentException("Illegal?load?factor:?"?+?loadFactor);
????this.loadFactor?=?loadFactor;
????this.threshold?=?tableSizeFor(initialCapacity);
}
對(duì)比HashMap 的 對(duì)null 值的支持
HashTable key value 都不支持null
首先HashMap 是支持null 值做key和value 的，但是HashTable 是不支持的，key 也不支持 value 也不支持
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;
????@SuppressWarnings("unchecked")
????Entry?entry?=?(Entry)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;
}
聰明的你們發(fā)現(xiàn)了嗎，上面值檢測(cè)了value ==null 則拋出NPE 但是沒(méi)有說(shuō)key 啊，因?yàn)槿绻鹝ey 是null 的話，key.hashCode()則會(huì)拋出異常，根本不需要判斷，但是value 就不會(huì)拋出來(lái)
但是需要注意的實(shí)HashMap 對(duì)null 值雖然支持，但是可以從hash值的計(jì)算方法中看出，
static?final?int?hash(Object?key)?{
????int?h;
????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);
}
升級(jí)HashTable 使其支持null 做value
大部分代碼都是直接copy 的HashTable，只去掉了value 的空值檢測(cè)
public?class?BuerHashTable<K,?V>?extends?Hashtable<K,?V>?{
????????//?.....?省略了部分代碼，直接copy?HashTable?的即可，主要是BuerHashTable.Entry?的定義和構(gòu)造方法
????public?synchronized?V?put(K?key,?V?value)?{
????????//?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?entry?=?(Entry)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++;
????????BuerHashTable.Entry?tab[]?=?table;
????????if?(count?>=?threshold)?{
????????????//?Rehash?the?table?if?the?threshold?is?exceeded
????????????rehash();
????????????tab?=?table;
????????????hash?=?key.hashCode();
????????????index?=?(hash?&?0x7FFFFFFF)?%?tab.length;
????????}
????????//?Creates?the?new?entry.
????????@SuppressWarnings("unchecked")
????????BuerHashTable.Entry?e?=?(BuerHashTable.Entry)?tab[index];
????????tab[index]?=?new?BuerHashTable.Entry<>(hash,?key,?value,?e);
????????count++;
????}
}
接下來(lái)，就可以將null 值作為value 存入BuerHashTable 了
BuerHashTable?buerHashTable?=?new?BuerHashTable<>();
buerHashTable.put("a",?null);
對(duì)比 HashTable 的繼承關(guān)系
Dictionary
這個(gè)類是HashTable特有繼承的，HashMap 是沒(méi)有繼承的，但是這個(gè)抽象類其實(shí)是沒(méi)有多大意義的,因?yàn)樗姆椒ǘ荚贛ap接口中有，其實(shí)這個(gè)就是個(gè)歷史問(wèn)題了，因?yàn)镸ap接口是在Java1.2 中才加進(jìn)去的，而Dictionary抽象類在Java1.0中就存在了
public?abstract
class?Dictionary<K,V>?{
????public?Dictionary()?{
????}
????abstract?public?int?size();
????abstract?public?boolean?isEmpty();
????abstract?public?Enumeration?keys() ;
????abstract?public?Enumeration?elements() ;
????abstract?public?V?get(Object?key);
????/**
?????*?@exception??NullPointerException??if?the?key?or
?????*/
????abstract?public?V?put(K?key,?V?value);
????abstract?public?V?remove(Object?key);
}
這個(gè)地方的NullPointerException 對(duì)應(yīng)的就是HashTable 中put 方法中的null 值檢測(cè)
最后一點(diǎn)就是Dictionary 抽象類上的注釋，新的實(shí)現(xiàn)應(yīng)該實(shí)現(xiàn)Map 接口而不是該抽象類
NOTE:?This?class?is?obsolete.??New?implementations?should?implement?the?Map?interface,?rather?than?extending?this?class
其實(shí)HashMap更準(zhǔn)確地說(shuō)是繼承自AbstractMap類，而不是直接實(shí)現(xiàn)了Map 接口，所以要是Dictionary這個(gè)抽象類要是實(shí)現(xiàn)的實(shí)Map 接口，那HashMap和Hashtable 就在繼承關(guān)系上保持一致了
Hashtable
線程安全
其實(shí)HashTable 沒(méi)有那么多要說(shuō)的，比較重要的一點(diǎn)就是線程安全，但是這個(gè)線程安全的實(shí)現(xiàn)方式就是所有的操作都加了synchronized關(guān)鍵字，哈哈！關(guān)于synchronized 我們后面會(huì)說(shuō)
public?synchronized?int?size()?{}
public?synchronized?boolean?isEmpty()?{}
public?synchronized?boolean?contains(Object?value)?{}
public?synchronized?boolean?containsKey(Object?key)?{}
public?synchronized?V?get(Object?key)?{}
public?synchronized?V?put(K?key,?V?value)?{}
public?synchronized?V?remove(Object?key)?{}
而HashMap 是線程不安全的
contains方法
HashMap中沒(méi)有Hashtable中的contains方法，只有containsValue和containsKey，因?yàn)閏ontains方法容易讓人引起誤解。
Hashtable則保留了contains，containsValue和containsKey三個(gè)方法，其中contains和containsValue功能相同。
debug 源碼 put 方法
public?synchronized?V?put(K?key,?V?value)?{
????//?Make?sure?the?value?is?not?null?確保value?不是null
????if?(value?==?null)?{
????????throw?new?NullPointerException();
????}
????//?Makes?sure?the?key?is?not?already?in?the?hashtable.
????//?這里的英文注釋很有意思啊，就是告訴你確保key?不存在，存在咋地，覆蓋又咋地
????Entry?tab[]?=?table;
????//?哈希值的計(jì)算不同，HashTable直接使用對(duì)象的hashCode。而HashMap重新計(jì)算hash值(高16位異或低16位)
????int?hash?=?key.hashCode();
????//?計(jì)算下標(biāo) HashMap 是計(jì)算key的hash再與tab.length-1進(jìn)行與運(yùn)算；
????//?HashTable則是key的hash值與0x7FFFFFFF進(jìn)行與運(yùn)算，然后再對(duì)tab.length取模
????//?先hash&0x7FFFFFFF后，再對(duì)length取模，與0x7FFFFFFF的目的是為了將負(fù)的hash值轉(zhuǎn)化為正值，因?yàn)閔ash值有可能為負(fù)數(shù)，而&0x7FFFFFFF后，只有符號(hào)外改變，而后面的位都不變
????int?index?=?(hash?&?0x7FFFFFFF)?%?tab.length;
????@SuppressWarnings("unchecked")
????//?確定?index?位置上的鏈表頭，這里主要是遍歷鏈表找到key?值相等的節(jié)點(diǎn)，然后返回old?value，這樣的話就不用添加新值
????//?也就是不用調(diào)用addEntry?方法
????Entry?entry?=?(Entry)tab[index];
????//?存在key?
????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);
????//?返回null?
????return?null;
}
private?void?addEntry(int?hash,?K?key,?V?value,?int?index)?{
????modCount++;
????Entry?tab[]?=?table;
????//?判斷是否要擴(kuò)容
????if?(count?>=?threshold)?{
????????//?Rehash?the?table?if?the?threshold?is?exceeded
????????rehash();
????????tab?=?table;
????????hash?=?key.hashCode();
????????index?=?(hash?&?0x7FFFFFFF)?%?tab.length;
????}
????//?Creates?the?new?entry.
????@SuppressWarnings("unchecked")
????Entry?e?=?(Entry)?tab[index];
????//?e?也就是??tab[index]?是這個(gè)鏈表的頭結(jié)點(diǎn)，?tab[index]?=?new?Entry<>(hash,?key,?value,?e);?也就是將元素添加到鏈表的頭部，e?做為new?Entry<>(hash,?key,?value,?e)的next?節(jié)點(diǎn)
????tab[index]?=?new?Entry<>(hash,?key,?value,?e);
????count++;
}
這里我們對(duì)比一下HashMap 的添加方法,很明顯別人都是添加的鏈表尾部的，因?yàn)镠ashTable 是線程安全的，在這個(gè)前提下，使用頭查法性能更好，否則還有遍歷到鏈表的尾部插入
for?(int?binCount?=?0;?;?++binCount)?{
????if?((e?=?p.next)?==?null)?{
????????p.next?=?newNode(hash,?key,?value,?null);
????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st
????????????treeifyBin(tab,?hash);
????????break;
????}
????if?(e.hash?==?hash?&&
????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????break;
????p?=?e;
}
最后我們?cè)倏匆幌聰U(kuò)容的方法
@SuppressWarnings("unchecked")
protected?void?rehash()?{
????int?oldCapacity?=?table.length;
????Entry[]?oldMap?=?table;
????//?overflow-conscious?code?
????//?擴(kuò)容成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;
????????//?最大容量?MAX_ARRAY_SIZE????
????????newCapacity?=?MAX_ARRAY_SIZE;
????}
????//?創(chuàng)建新的數(shù)組
????Entry[]?newMap?=?new?Entry[newCapacity];
????modCount++;
????//?更新?threshold
????threshold?=?(int)Math.min(newCapacity?*?loadFactor,?MAX_ARRAY_SIZE?+?1);
????table?=?newMap;
????//?數(shù)據(jù)遷移，遍歷數(shù)組
????for?(int?i?=?oldCapacity?;?i--?>?0?;)?{
????????????//?for?循環(huán)的方式遍歷鏈表
????????for?(Entry?old?=?(Entry)oldMap[i]?;?old?!=?null?;?)?{
????????????Entry?e?=?old;
????????????old?=?old.next;
????????????int?index?=?(e.hash?&?0x7FFFFFFF)?%?newCapacity;
????????????e.next?=?(Entry)newMap[index];
????????????newMap[index]?=?e;
????????}
????}
}
總結(jié)
需要注意的是Hashtable的默認(rèn)初始容量大小是11，而HashMap 是16,但是他們的加載因子都是0.75f
HashTable的初始容量可以使任何非負(fù)整數(shù)，但是HashMap會(huì)采用第一個(gè)大于該數(shù)值的2的冪作為初始化容量(0 1 除外，都是 1)
HashTable的線程安全是完全借助synchronized 的加持
HashTable 的元素是頭插法，也就是插入到鏈表的頭部，因?yàn)镠ashTable 是線程安全的，在這個(gè)前提下，使用頭查法性能更好，否則還有遍歷到鏈表的尾部插入
HashTable 是沒(méi)有紅黑樹(shù)支持的，就是不論鏈表的長(zhǎng)度有多長(zhǎng)，都不會(huì)轉(zhuǎn)化成紅黑樹(shù)
哈希值的計(jì)算不同，HashTable直接使用對(duì)象的hashCode。而HashMap重新計(jì)算hash值(高16位異或低16位)，并且HashMap 支持key 為null 就是在這里的
Hashtable擴(kuò)容時(shí)，將容量變?yōu)樵瓉?lái)的2倍加1，而HashMap擴(kuò)容時(shí)，將容量變?yōu)樵瓉?lái)的2倍。
你覺(jué)得HashTable 還有什么可以改進(jìn)的地方嗎，歡迎討論
和上一節(jié)一樣這里我依然給出這個(gè)思考題，雖然我們的說(shuō)法可能不對(duì)，可能我們永遠(yuǎn)也站不到源代碼作者當(dāng)年的高度，但是我們依然積極思考，大膽討論
雖然java 源代碼的山很高，如果你想跨越，至少你得有登山的勇氣，這里我給出自己的一點(diǎn)點(diǎn)愚見(jiàn)，希望各位不吝指教
int?hash?=?key.hashCode();
addEntry(hash,?key,?value,?index);
private?void?addEntry(int?hash,?K?key,?V?value,?int?index)?{
????????//?記錄修改，快速失敗
????modCount++;
????Entry?tab[]?=?table;
????//?count?實(shí)際存儲(chǔ)的key-value?數(shù)目，在HashMap?中用size?表示
????if?(count?>=?threshold)?{
????????//?Rehash?the?table?if?the?threshold?is?exceeded
????????rehash();
????????tab?=?table;
????????//?咋地，數(shù)組擴(kuò)容之后key?的hash值會(huì)變嗎，你還有重新計(jì)算一下
????????hash?=?key.hashCode();
????????index?=?(hash?&?0x7FFFFFFF)?%?tab.length;
????}
????//?Creates?the?new?entry.
????@SuppressWarnings("unchecked")
????Entry?e?=?(Entry)?tab[index];
????tab[index]?=?new?Entry<>(hash,?key,?value,?e);
????count++;
}
當(dāng)然這只是小問(wèn)題，但是也有很多其他小問(wèn)題，例如求index 時(shí)候的計(jì)算方式是直接取模，而不是用與運(yùn)算，它最大的問(wèn)題在設(shè)計(jì)上，例如hash值的計(jì)算方式就沒(méi)有HashMap 設(shè)計(jì)的好，還有就是沒(méi)有紅黑樹(shù)的支持，還有就是線程安全的實(shí)現(xiàn)方式也不高效，所以我們說(shuō)它好像是遺留類,HashTable 在Java1.0 時(shí)代就存在了，而HashMap才是Java1.2才有的