JavaHashtable機(jī)制深入了解

第JavaHashtable機(jī)制深入了解目錄概述介紹和使用核心機(jī)制實(shí)現(xiàn)機(jī)制擴(kuò)容機(jī)制源碼解析成員變量構(gòu)造函數(shù)put方法get方法remove方法總結(jié)

概述

HashTable是jdk1.0中引入的產(chǎn)物，基本上現(xiàn)在很少使用了，但是會在面試中經(jīng)常被問到，你都知道嗎：

HashTable底層的實(shí)現(xiàn)機(jī)制是什么？HashTable的擴(kuò)容機(jī)制是什么？HashTable和HashMap的區(qū)別是什么？

介紹和使用

和HashMap一樣，Hashtable也是一個(gè)散列表，它存儲的內(nèi)容是鍵值對(key-value)映射,重要特點(diǎn)如下:

存儲key-value鍵值對格式是無序的底層通過數(shù)組+鏈表的方式實(shí)現(xiàn)通過synchronized關(guān)鍵字實(shí)現(xiàn)線程安全key、value都不可以為null（為null時(shí)將拋出NullPointerException）

以上是Hashtable的類結(jié)構(gòu)圖：

實(shí)現(xiàn)了Map接口，提供了鍵值對增刪改查等基礎(chǔ)操作繼承了Dictionary字典類，Dictionary是聲明了操作鍵值對函數(shù)接口的抽象類。實(shí)現(xiàn)了Cloneable接口，實(shí)現(xiàn)數(shù)據(jù)的淺拷貝實(shí)現(xiàn)了Serializable接口，標(biāo)記Hashtable支持序列化

使用案例：

@Test

publicvoidtest(){

HashtableString,Stringtable=newHashtable();

HashtableString,Stringtable1=newHashtable(16);

HashtableString,Stringtable2=newHashtable(16,0.75f);

table.put("T1","1");

table.put("T2","2");

System.out.println(table);

//報(bào)空指針異常

table.put(null,"3");

}

運(yùn)行結(jié)果：

核心機(jī)制

實(shí)現(xiàn)機(jī)制

和HashMap相似，Hashtable底層采用數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)，根據(jù)key找到數(shù)組對應(yīng)的桶，相同的key通過鏈表維護(hù)，當(dāng)數(shù)組桶的使用到達(dá)閾值后，會進(jìn)行動態(tài)擴(kuò)容。但是和HashMap不同的是，鏈表不會轉(zhuǎn)換為紅黑樹。

擴(kuò)容機(jī)制

擴(kuò)容機(jī)制依賴兩個(gè)成員變量，初始容量和加載因子。他們可以通過構(gòu)造函數(shù)設(shè)置。

容量是值哈希表中桶的數(shù)量，初始容量就是哈希表創(chuàng)建時(shí)的容量。當(dāng)容量達(dá)到閾值的時(shí)候，會進(jìn)行擴(kuò)容操作，每次擴(kuò)容是原來容量的2倍加1，然后重新為hashtable中的每個(gè)元素重新分配桶的位置。

那閾值是多少呢，Hashtable的閾值，用于判斷是否需要調(diào)整Hashtable的容量，等于Hashtable當(dāng)前的容量*加載因子。

通常，默認(rèn)加載因子是0.75,這是在時(shí)間和空間成本上尋求一種折衷。加載因子過高雖然減少了空間開銷，但同時(shí)也增加了查找某個(gè)條目的時(shí)間。

源碼解析

成員變量

//內(nèi)部采用Entry數(shù)組存儲鍵值對數(shù)據(jù)，Entry實(shí)際為單向鏈表的表頭

privatetransientEntry,[]table;

//HashTable里鍵值對個(gè)數(shù)

privatetransientintcount;

//擴(kuò)容閾值，當(dāng)超過這個(gè)值時(shí)，進(jìn)行擴(kuò)容操作，計(jì)算方式為：數(shù)組容量*加載因子

privateintthreshold;

//加載因子

privatefloatloadFactor;

//修改次數(shù)，用于快速失敗機(jī)制

privatetransientintmodCount=0;

Entry的數(shù)據(jù)結(jié)構(gòu)如下：

privatestaticclassEntryK,VimplementsMap.EntryK,V{

finalinthash;

finalKkey;

Vvalue;

EntryK,Vnext;

protectedEntry(inthash,Kkey,Vvalue,EntryK,Vnext){

this.hash=hash;

this.key=key;

this.value=value;

this.next=next;

......

}

Entry是單向鏈表節(jié)點(diǎn)，next指向下一個(gè)entry

構(gòu)造函數(shù)

//設(shè)置指定容量和加載因子，初始化HashTable

publicHashtable(intinitialCapacity,floatloadFactor){

//非法參數(shù)校驗(yàn)

if(initialCapacity0)

thrownewIllegalArgumentException("IllegalCapacity:"+

initialCapacity);

//非法參數(shù)校驗(yàn)

if(loadFactor=0||Float.isNaN(loadFactor))

thrownewIllegalArgumentException("IllegalLoad:"+loadFactor);

if(initialCapacity==0)

//容量最小為1

initialCapacity=1;

this.loadFactor=loadFactor;

//初始化數(shù)組

table=newEntry,[initialCapacity];

//初始擴(kuò)容閾值

threshold=(int)Math.min(initialCapacity*loadFactor,MAX_ARRAY_SIZE+1);

//設(shè)置指定容量初始HashTable，加載因子為0.75

publicHashtable(intinitialCapacity){

this(initialCapacity,0.75f);

//手動指定數(shù)組初始容量為11，加載因子為0.75

publicHashtable(){

this(11,0.75f);

}

put方法

//方法synchronized修飾，線程安全

publicsynchronizedVput(Kkey,Vvalue){

//如果value為空，直接空指針

if(value==null){

thrownewNullPointerException();

//Makessurethekeyisnotalreadyinthehashtable.

Entry,tab[]=table;

//得到key的哈希值

inthash=key.hashCode();

//得到該key存在到數(shù)組中的下標(biāo)

intindex=(hash0x7FFFFFFF)%tab.length;

@SuppressWarnings("unchecked")

//得到該下標(biāo)對應(yīng)的Entry

EntryK,Ventry=(EntryK,V)tab[index];

//如果該下標(biāo)的Entry不為null，則進(jìn)行鏈表遍歷

for(;entry!=null;entry=entry.next){

//遍歷鏈表，如果存在key相等的節(jié)點(diǎn)，則替換這個(gè)節(jié)點(diǎn)的值，并返回舊值

if((entry.hash==hash)entry.key.equals(key)){

Vold=entry.value;

entry.value=value;

returnold;

//如果數(shù)組下標(biāo)對應(yīng)的節(jié)點(diǎn)為空，或者遍歷鏈表后發(fā)現(xiàn)沒有和該key相等的節(jié)點(diǎn)，則執(zhí)行插入操作

addEntry(hash,key,value,index);

returnnull;

privatevoidaddEntry(inthash,Kkey,Vvalue,intindex){

//修改次數(shù)+1

modCount++;

Entry,tab[]=table;

//判斷是否需要擴(kuò)容

if(count=threshold){

//如果count大于等于擴(kuò)容閾值，則進(jìn)行擴(kuò)容

rehash();

tab=table;

//擴(kuò)容后，重新計(jì)算該key在擴(kuò)容后table里的下標(biāo)

hash=key.hashCode();

index=(hash0x7FFFFFFF)%tab.length;

//Createsthenewentry.

@SuppressWarnings("unchecked")

//采用頭插的方式插入，index位置的節(jié)點(diǎn)為新節(jié)點(diǎn)的next節(jié)點(diǎn)

//新節(jié)點(diǎn)取代inde位置節(jié)點(diǎn)

EntryK,Ve=(EntryK,V)tab[index];

tab[index]=newEntry(hash,key,value,e);

//count+1

count++;

}

擴(kuò)容rehash源碼如下：

protectedvoidrehash(){

//暫存舊的table和容量

intoldCapacity=table.length;

Entry,[]oldMap=table;

//新容量為舊容量的2n+1倍

intnewCapacity=(oldCapacity1)+1;

//判斷新容量是否超過最大容量

if(newCapacity-MAX_ARRAY_SIZE0){

//如果舊容量已經(jīng)是最大容量大話，就不擴(kuò)容了

if(oldCapacity==MAX_ARRAY_SIZE)

//KeeprunningwithMAX_ARRAY_SIZEbuckets

return;

//新容量最大值只能是MAX_ARRAY_SIZE

newCapacity=MAX_ARRAY_SIZE;

//用新容量創(chuàng)建一個(gè)新Entry數(shù)組

Entry,[]newMap=newEntry,[newCapacity];

//模數(shù)+1

modCount++;

//重新計(jì)算下次擴(kuò)容閾值

threshold=(int)Math.min(newCapacity*loadFactor,MAX_ARRAY_SIZE+1);

//將新Entry數(shù)組賦值給table

table=newMap;

//遍歷數(shù)組和鏈表，進(jìn)行新table賦值操作

for(inti=oldCapacity;i--){

for(EntryK,Vold=(EntryK,V)oldMap[i];old!=null;){

EntryK,Ve=old;

old=old.next;

intindex=(e.hash0x7FFFFFFF)%newCapacity;

e.next=(EntryK,V)newMap[index];

newMap[index]=e;

}

rehash()方法中我們可以看到容量擴(kuò)大兩倍+1，同時(shí)需要將原來HashTable中的元素，重新計(jì)算索引位置一一復(fù)制到新的Hashtable中，這個(gè)過程是比較消耗時(shí)間的。Hashtable的索引求值公式是：hash0x7FFFFFFF%newCapacity。hash0x7FFFFFF是為了保證正數(shù)，因?yàn)閔ashCode的值有可能為負(fù)值。

get方法

publicsynchronizedVremove(Objectkey){

Entry,tab[]=table;

inthash=key.hashCode();

//獲取key對應(yīng)的index

intindex=(hash0x7FFFFFFF)%tab.length;

@SuppressWarnings("unchecked")

//遍歷鏈表，如果找到key相等的節(jié)點(diǎn)，則改變前繼和后繼節(jié)點(diǎn)的關(guān)系，并刪除相應(yīng)引用，讓GC回收

EntryK,Ve=(EntryK,V)tab[index];

for(EntryK,Vprev=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--;

VoldValue=e.value;

e.value=null;

returnoldValue;

returnnull;

}

remove方法

publicsynchronizedVremove(Objectkey){

Entry,tab[]=table;

inthash=key.hashCode();

//獲取key對應(yīng)的index

intindex=(hash0x7FFFFFFF)%tab.length;

@SuppressWarnings("unchecked")

//遍歷鏈表，如果找到key相等的節(jié)點(diǎn)，則改變前繼和后繼節(jié)點(diǎn)的關(guān)系，并刪除相應(yīng)引用，讓GC回收

EntryK,Ve=(EntryK,V)tab[index];

for(EntryK,Vprev=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