JavaHashtable機制深入了解

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

概述

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

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

介紹和使用

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

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

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

實現(xiàn)了Map接口，提供了鍵值對增刪改查等基礎(chǔ)操作繼承了Dictionary字典類，Dictionary是聲明了操作鍵值對函數(shù)接口的抽象類。實現(xiàn)了Cloneable接口，實現(xiàn)數(shù)據(jù)的淺拷貝實現(xiàn)了Serializable接口，標記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);

//報空指針異常

table.put(null,"3");

}

運行結(jié)果：

核心機制

實現(xiàn)機制

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

擴容機制

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

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

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

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

源碼解析

成員變量

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

privatetransientEntry,[]table;

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

privatetransientintcount;

//擴容閾值，當超過這個值時，進行擴容操作，計算方式為：數(shù)組容量*加載因子

privateintthreshold;

//加載因子

privatefloatloadFactor;

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

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é)點，next指向下一個entry

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

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

publicHashtable(intinitialCapacity,floatloadFactor){

//非法參數(shù)校驗

if(initialCapacity0)

thrownewIllegalArgumentException("IllegalCapacity:"+

initialCapacity);

//非法參數(shù)校驗

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

thrownewIllegalArgumentException("IllegalLoad:"+loadFactor);

if(initialCapacity==0)

//容量最小為1

initialCapacity=1;

this.loadFactor=loadFactor;

//初始化數(shù)組

table=newEntry,[initialCapacity];

//初始擴容閾值

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ù)組中的下標

intindex=(hash0x7FFFFFFF)%tab.length;

@SuppressWarnings("unchecked")

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

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

//如果該下標的Entry不為null，則進行鏈表遍歷

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

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

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

Vold=entry.value;

entry.value=value;

returnold;

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

addEntry(hash,key,value,index);

returnnull;

privatevoidaddEntry(inthash,Kkey,Vvalue,intindex){

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

modCount++;

Entry,tab[]=table;

//判斷是否需要擴容

if(count=threshold){

//如果count大于等于擴容閾值，則進行擴容

rehash();

tab=table;

//擴容后，重新計算該key在擴容后table里的下標

hash=key.hashCode();

index=(hash0x7FFFFFFF)%tab.length;

//Createsthenewentry.

@SuppressWarnings("unchecked")

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

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

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

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

//count+1

count++;

}

擴容rehash源碼如下：

protectedvoidrehash(){

//暫存舊的table和容量

intoldCapacity=table.length;

Entry,[]oldMap=table;

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

intnewCapacity=(oldCapacity1)+1;

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

if(newCapacity-MAX_ARRAY_SIZE0){

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

if(oldCapacity==MAX_ARRAY_SIZE)

//KeeprunningwithMAX_ARRAY_SIZEbuckets

return;

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

newCapacity=MAX_ARRAY_SIZE;

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

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

//模數(shù)+1

modCount++;

//重新計算下次擴容閾值

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

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

table=newMap;

//遍歷數(shù)組和鏈表，進行新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()方法中我們可以看到容量擴大兩倍+1，同時需要將原來HashTable中的元素，重新計算索引位置一一復(fù)制到新的Hashtable中，這個過程是比較消耗時間的。Hashtable的索引求值公式是：hash0x7FFFFFFF%newCapacity。hash0x7FFFFFF是為了保證正數(shù)，因為hashCode的值有可能為負值。

get方法

publicsynchronizedVremove(Objectkey){

Entry,tab[]=table;

inthash=key.hashCode();

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

intindex=(hash0x7FFFFFFF)%tab.length;

@SuppressWarnings("unchecked")

//遍歷鏈表，如果找到key相等的節(jié)點，則改變前繼和后繼節(jié)點的關(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é)點，則改變前繼和后繼節(jié)點的關(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