java中HashMap詳解
HashMap和HashSet是JavaCollectionFramework的兩個(gè)重要成員，其中HashMap是Map接口的常用實(shí)現(xiàn)類，HashSet是Set接口的常用實(shí)現(xiàn)類。雖然HashMap和HashSet實(shí)現(xiàn)的接口規(guī)范不同，但它們底層的Hash存儲機(jī)制完全一樣，甚至HashSet本身就采用HashMap來實(shí)現(xiàn)的。
通過HashMap、HashSet的源代碼分析其Hash存儲機(jī)制
實(shí)際上，HashSet和HashMap之間有很多相似之處，對于HashSet而言，系統(tǒng)采用Hash算法決定集合元素的存儲位置，這樣可以保證能快速存、取集合元素；對于HashMap而言，系統(tǒng)key-value當(dāng)成一個(gè)整體進(jìn)行處理，系統(tǒng)總是根據(jù)Hash算法來計(jì)算key-value的存儲位置，這樣可以保證能快速存、取Map的key-value對。
在介紹集合存儲之前需要指出一點(diǎn)：雖然集合號稱存儲的是Java對象，但實(shí)際上并不會真正將Java對象放入Set集合中，只是在Set集合中保留這些對象的引用而言。也就是說：Java集合實(shí)際上是多個(gè)引用變量所組成的集合，這些引用變量指向?qū)嶋H的Java對象。
集合和引用
就像引用類型的數(shù)組一樣，當(dāng)我們把Java對象放入數(shù)組之時(shí)，并不是真正的把Java對象放入數(shù)組中，只是把對象的引用放入數(shù)組中，每個(gè)數(shù)組元素都是一個(gè)引用變量。
HashMap的存儲實(shí)現(xiàn)
當(dāng)程序試圖將多個(gè)key-value放入HashMap中時(shí)，以如下代碼片段為例：
Java代碼
HashMapmap=newHashMap（）；
map.put（"語文",80.0）；
map.put（"數(shù)學(xué)",89.0）；
map.put（"英語",78.2）；
HashMap采用一種所謂的“Hash算法”來決定每個(gè)元素的存儲位置。
當(dāng)程序執(zhí)行map.put（"語文",80.0）；時(shí)，系統(tǒng)將調(diào)用"語文"的hashCode（）方法得到其hashCode值——每個(gè)Java對象都有hashCode（）方法，都可通過該方法獲得它的hashCode值。得到這個(gè)對象的hashCode值之后，系統(tǒng)會根據(jù)該hashCode值來決定該元素的存儲位置。
我們可以看HashMap類的put（Kkey,Vvalue）方法的源代碼：
Java代碼
publicVput（Kkey,Vvalue）
{
//如果key為null，調(diào)用putForNullKey方法進(jìn)行處理
if（key==null）
returnputForNullKey（value）；
//根據(jù)key的keyCode計(jì)算Hash值
inthash=hash（key.hashCode（））；
//搜索指定hash值在對應(yīng)table中的索引
inti=indexFor（hash,table.length）；
//如果i索引處的Entry不為null，通過循環(huán)不斷遍歷e元素的下一個(gè)元素
for（Entrye=table[i];e!=null;e=e.next）
{
Objectk;
//找到指定key與需要放入的key相等（hash值相同
//通過equals比較放回true）
if（e.hash==hash&&（（k=e.key）==key
||key.equals（k）））
{
VoldValue=e.value;
e.value=value;
e.recordAccess（this）；
returnoldValue;
}
}
//如果i索引處的Entry為null，表明此處還沒有Entry
modCount++;
//將key、value添加到i索引處
addEntry（hash,key,value,i）；
returnnull;
}
上面程序中用到了一個(gè)重要的內(nèi)部接口：Map.Entry，每個(gè)Map.Entry其實(shí)就是一個(gè)key-value對。從上面程序中可以看出：當(dāng)系統(tǒng)決定存儲HashMap中的key-value對時(shí)，完全沒有考慮Entry中的value，僅僅只是根據(jù)key來計(jì)算并決定每個(gè)Entry的存儲位置。這也說明了前面的結(jié)論：我們完全可以把Map集合中的value當(dāng)成key的附屬，當(dāng)系統(tǒng)決定了key的存儲位置之后，value隨之保存在那里即可。
上面方法提供了一個(gè)根據(jù)hashCode（）返回值來計(jì)算Hash碼的方法：hash（），這個(gè)方法是一個(gè)純粹的數(shù)學(xué)計(jì)算，其方法如下：
Java代碼
staticinthash（inth）
{
h^=（h>>>20）^（h>>>12）；
returnh^（h>>>7）^（h>>>4）；
}
對于任意給定的對象，只要它的hashCode（）返回值相同，那么程序調(diào)用hash（inth）方法所計(jì)算得到的Hash碼值總是相同的。接下來程序會調(diào)用indexFor（inth,intlength）方法來計(jì)算該對象應(yīng)該保存在table數(shù)組的哪個(gè)索引處。indexFor（inth,intlength）方法的代碼如下：
Java代碼
staticintindexFor（inth,intlength）
{
returnh&（length-1）；
}
這個(gè)方法非常巧妙，它總是通過h&（table.length-1）來得到該對象的保存位置——而HashMap底層數(shù)組的長度總是2的n次方，這一點(diǎn)可參看后面關(guān)于HashMap構(gòu)造器的介紹。
當(dāng)length總是2的倍數(shù)時(shí)，h&（length-1）將是一個(gè)非常巧妙的設(shè)計(jì)：假設(shè)h=5,length=16,那么h&length-1將得到5；如果h=6,length=16,那么h&length-1將得到6……如果h=15,length=16,那么h&length-1將得到15；但是當(dāng)h=16時(shí),length=16時(shí)，那么h&length-1將得到0了；當(dāng)h=17時(shí),length=16時(shí)，那么h&length-1將得到1了……這樣保證計(jì)算得到的索引值總是位于table數(shù)組的索引之內(nèi)。
根據(jù)上面put方法的源代碼可以看出，當(dāng)程序試圖將一個(gè)key-value對放入HashMap中時(shí)，程序首先根據(jù)該key的hashCode（）返回值決定該Entry的存儲位置：如果兩個(gè)Entry的key的hashCode（）返回值相同，那它們的存儲位置相同。如果這兩個(gè)Entry的key通過equals比較返回true，新添加Entry的value將覆蓋集合中原有Entry的value，但key不會覆蓋。如果這兩個(gè)Entry的key通過equals比較返回false，新添加的Entry將與集合中原有Entry形成Entry鏈，而且新添加的Entry位于Entry鏈的頭部——具體說明繼續(xù)看addEntry（）方法的說明。
當(dāng)向HashMap中添加key-value對，由其key的hashCode（）返回值決定該key-value對（就是Entry對象）的存儲位置。當(dāng)兩個(gè)Entry對象的key的hashCode（）返回值相同時(shí)，將由key通過eqauls（）比較值決定是采用覆蓋行為（返回true），還是產(chǎn)生Entry鏈（返回false）。
上面程序中還調(diào)用了addEntry（hash,key,value,i）；代碼，其中addEntry是HashMap提供的一個(gè)包訪問權(quán)限的方法，該方法僅用于添加一個(gè)key-value對。下面是該方法的代碼：
Java代碼
voidaddEntry（inthash,Kkey,Vvalue,intbucketIndex）
{
//獲取指定bucketIndex索引處的Entry
Entrye=table[bucketIndex];//①
//將新創(chuàng)建的Entry放入bucketIndex索引處，并讓新的Entry指向原來的Entry
table[bucketIndex]=newEntry（hash,key,value,e）；
//如果Map中的key-value對的數(shù)量超過了極限
if（size++>=threshold）
//把table對象的長度擴(kuò)充到2倍。
resize（2*table.length）；//②
}
上面方法的代碼很簡單，但其中包含了一個(gè)非常優(yōu)雅的設(shè)計(jì)：系統(tǒng)總是將新添加的Entry對象放入table數(shù)組的bucketIndex索引處——如果bucketIndex索引處已經(jīng)有了一個(gè)Entry對象，那新添加的Entry對象指向原有的Entry對象（產(chǎn)生一個(gè)Entry鏈），如果bucketIndex索引處沒有Entry對象，也就是上面程序①號代碼的e變量是null，也就是新放入的Entry對象指向null，也就是沒有產(chǎn)生Entry鏈。
JDK源碼
在JDK安裝目錄下可以找到一個(gè)src.zip壓縮文件，該文件里包含了Java基礎(chǔ)類庫的所有源文件。只要讀者有學(xué)習(xí)興趣，隨時(shí)可以打開這份壓縮文件來閱讀Java類庫的源代碼，這對提高讀者的編程能力是非常有幫助的。需要指出的是：src.zip中包含的源代碼并沒有包含像上文中的中文注釋，這些注釋是筆者自己添加進(jìn)去的。
Hash算法的性能選項(xiàng)
根據(jù)上面代碼可以看出，在同一個(gè)bucket存儲Entry鏈的情況下，新放入的Entry總是位于bucket中，而最早放入該bucket中的Entry則位于這個(gè)Entry鏈的最末端。
上面程序中還有這樣兩個(gè)變量：
*size：該變量保存了該HashMap中所包含的key-value對的數(shù)量。
*threshold：該變量包含了HashMap能容納的key-value對的極限，它的值等于HashMap的容量乘以負(fù)載因子（loadfactor）。
從上面程序中②號代碼可以看出，當(dāng)size++>=threshold時(shí)，HashMap會自動調(diào)用resize方法擴(kuò)充HashMap的容量。每擴(kuò)充一次，HashMap的容量就增大一倍?！∩厦娉绦蛑惺褂玫膖able其實(shí)就是一個(gè)普通數(shù)組，每個(gè)數(shù)組都有一個(gè)固定的長度，這個(gè)數(shù)組的長度就是HashMap的容量。HashMap包含如下幾個(gè)構(gòu)造器：
*HashMap（）：構(gòu)建一個(gè)初始容量為16，負(fù)載因子為0.75的HashMap。
*HashMap（intinitialCapacity）：構(gòu)建一個(gè)初始容量為initialCapacity，負(fù)載因子為0.75的HashMap。
*HashMap（intinitialCapacity,floatloadFactor）：以指定初始容量、指定的負(fù)載因子創(chuàng)建一個(gè)HashMap。
當(dāng)創(chuàng)建一個(gè)HashMap時(shí)，系統(tǒng)會自動創(chuàng)建一個(gè)table數(shù)組來保存HashMap中的Entry，下面是HashMap中一個(gè)構(gòu)造器的代碼：
Java代碼
//以指定初始化容量、負(fù)載因子創(chuàng)建HashMap
publicHashMap（intinitialCapacity,floatloadFactor）
{
//初始容量不能為負(fù)數(shù)
if（initialCapacity<0）
thrownewIllegalArgumentException（
"Illegalinitialcapacity:"+
initialCapacity）；
//如果初始容量大于容量，讓出示容量
if（initialCapacity>MAXIMUM_CAPACITY）
initialCapacity=MAXIMUM_CAPACITY;
//負(fù)載因子必須大于0的數(shù)值
if（loadFactor<=0||Float.isNaN（loadFactor））
thrownewIllegalArgumentException（
loadFactor）；
//計(jì)算出大于initialCapacity的最小的2的n次方值。
intcapacity=1;
while（capacity capacity《=1;
this.loadFactor=loadFactor;
//設(shè)置容量極限等于容量*負(fù)載因子
threshold=（int）（capacity*loadFactor）；
//初始化table數(shù)組
table=newEntry[capacity];//①
init（）；
}
上面代碼中粗體字代碼包含了一個(gè)簡潔的代碼實(shí)現(xiàn)：找出大于initialCapacity的、最小的2的n次方值，并將其作為HashMap的實(shí)際容量（由capacity變量保存）。例如給定initialCapacity為10，那么該HashMap的實(shí)際容量就是16。
程序①號代碼處可以看到：table的實(shí)質(zhì)就是一個(gè)數(shù)組，一個(gè)長度為capacity的數(shù)組。
對于HashMap及其子類而言，它們采用Hash算法來決定集合中元素的存儲位置。當(dāng)系統(tǒng)開始初始化HashMap時(shí)，系統(tǒng)會創(chuàng)建一個(gè)長度為capacity的Entry數(shù)組，這個(gè)數(shù)組里可以存儲元素的位置被稱為“桶（bucket）”，每個(gè)bucket都有其指定索引，系統(tǒng)可以根據(jù)其索引快速訪問該bucket里存儲的元素。
無論何時(shí)，HashMap的每個(gè)“桶”只存儲一個(gè)元素（也就是一個(gè)Entry），由于Entry對象可以包含一個(gè)引用變量（就是Entry構(gòu)造器的的最后一個(gè)參數(shù)）用于指向下一個(gè)Entry，因此可能出現(xiàn)的情況是：HashMap的bucket中只有一個(gè)Entry，但這個(gè)Entry指向另一個(gè)Entry——這就形成了一個(gè)Entry鏈。
HashMap的讀取實(shí)現(xiàn)
當(dāng)HashMap的每個(gè)bucket里存儲的Entry只是單個(gè)Entry——也就是沒有通過指針產(chǎn)生Entry鏈時(shí)，此時(shí)的HashMap具有的性能：當(dāng)程序通過key取出對應(yīng)value時(shí)，系統(tǒng)只要先計(jì)算出該key的hashCode（）返回值，在根據(jù)該hashCode返回值找出該key在table數(shù)組中的索引，然后取出該索引處的Entry，最后返回該key對應(yīng)的value即可。看HashMap類的get（Kkey）方法代碼：
Java代碼
publicVget（Objectkey）
{
//如果key是null，調(diào)用getForNullKey取出對應(yīng)的value
if（key==null）
returngetForNullKey（）；
//根據(jù)該key的hashCode值計(jì)算它的hash碼
inthash=hash（key.hashCode（））；
//直接取出table數(shù)組中指定索引處的值，
for（Entrye=table[indexFor（hash,table.length）];
e!=null;
//搜索該Entry鏈的下一個(gè)Entr
e=e.next）//①
{
Objectk;
//如果該Entry的key與被搜索key相同
if（e.hash==hash&&（（k=e.key）==key
||key.equals（k）））
returne.value;
}
returnnull;
}
從上面代碼中可以看出，如果HashMap的每個(gè)bucket里只有一個(gè)Entry時(shí)，HashMap可以根據(jù)索引、快速地取出該bucket里的Entry；在發(fā)生“Hash沖突”的情況下，單個(gè)bucket里存儲的不是一個(gè)Entry，而是一個(gè)Entry鏈，系統(tǒng)只能必須按順序遍歷每個(gè)Entry，直到找到想搜索的Entry為止——如果恰好要搜索的Entry位于該Entry鏈的最末端（該Entry是最早放入該bucket中），那系統(tǒng)必須循環(huán)到最后才能找到該元素。
歸納起來簡單地說，HashMap在底層將key-value當(dāng)成一個(gè)整體進(jìn)行處理，這個(gè)整體就是一個(gè)Entry對象。HashMap底層采用一個(gè)Entry[]數(shù)組來保存所有的key-value對，當(dāng)需要存儲一個(gè)Entry對象時(shí)，會根據(jù)Hash算法來決定其存儲位置；當(dāng)需要取出一個(gè)Entry時(shí)，也會根據(jù)Hash算法找到其存儲位置，直接取出該Entry。由此可見：HashMap之所以能快速存、取它所包含的Entry，完全類似于現(xiàn)實(shí)生活中母親從小教我們的：不同的東西要放在不同的位置，需要時(shí)才能快速找到它。
當(dāng)創(chuàng)建HashMap時(shí)，有一個(gè)默認(rèn)的負(fù)載因子（loadfactor），其默認(rèn)值為0.75，這是時(shí)間和空間成本上一種折衷：增大負(fù)載因子可以減少Hash表（就是那個(gè)Entry數(shù)組）所占用的內(nèi)存空間，但會增加查詢數(shù)據(jù)的時(shí)間開銷，而查詢是最頻繁的的操作（HashMap的get（）與put（）方法都要用到查詢）；減小負(fù)載因子會提高數(shù)據(jù)查詢的性能，但會增加Hash表所占用的內(nèi)存空間。
掌握了上面知識之后，我們可以在創(chuàng)建HashMap時(shí)根據(jù)實(shí)際需要適當(dāng)?shù)卣{(diào)整loadfactor的值；如果程序比較關(guān)心空間開銷、內(nèi)存比較緊張，可以適當(dāng)?shù)卦黾迂?fù)載因子；如果程序比較關(guān)心時(shí)間開銷，內(nèi)存比較寬裕則可以適當(dāng)?shù)臏p少負(fù)載因子。通常情況下，程序員無需改變負(fù)載因子的值。
如果開始就知道HashMap會保存多個(gè)key-value對，可以在創(chuàng)建時(shí)就使用較大的初始化容量，如果HashMap中Entry的數(shù)量一直不會超過極限容量（capacity*loadfactor），HashMap就無需調(diào)用resize（）方法重新分配table數(shù)組，從而保證較好的性能。當(dāng)然，開始就將初始容量設(shè)置太高可能會浪費(fèi)空間（系統(tǒng)需要創(chuàng)建一個(gè)長度為capacity的Entry數(shù)組），因此創(chuàng)建HashMap時(shí)初始化容量設(shè)置也需要小心對待。
通過HashMap、HashSet的源代碼分析其Hash存儲機(jī)制
實(shí)際上，HashSet和HashMap之間有很多相似之處，對于HashSet而言，系統(tǒng)采用Hash算法決定集合元素的存儲位置，這樣可以保證能快速存、取集合元素；對于HashMap而言，系統(tǒng)key-value當(dāng)成一個(gè)整體進(jìn)行處理，系統(tǒng)總是根據(jù)Hash算法來計(jì)算key-value的存儲位置，這樣可以保證能快速存、取Map的key-value對。
在介紹集合存儲之前需要指出一點(diǎn)：雖然集合號稱存儲的是Java對象，但實(shí)際上并不會真正將Java對象放入Set集合中，只是在Set集合中保留這些對象的引用而言。也就是說：Java集合實(shí)際上是多個(gè)引用變量所組成的集合，這些引用變量指向?qū)嶋H的Java對象。
集合和引用
就像引用類型的數(shù)組一樣，當(dāng)我們把Java對象放入數(shù)組之時(shí)，并不是真正的把Java對象放入數(shù)組中，只是把對象的引用放入數(shù)組中，每個(gè)數(shù)組元素都是一個(gè)引用變量。
HashMap的存儲實(shí)現(xiàn)
當(dāng)程序試圖將多個(gè)key-value放入HashMap中時(shí)，以如下代碼片段為例：
Java代碼
HashMapmap=newHashMap（）；
map.put（"語文",80.0）；
map.put（"數(shù)學(xué)",89.0）；
map.put（"英語",78.2）；
HashMap采用一種所謂的“Hash算法”來決定每個(gè)元素的存儲位置。
當(dāng)程序執(zhí)行map.put（"語文",80.0）；時(shí)，系統(tǒng)將調(diào)用"語文"的hashCode（）方法得到其hashCode值——每個(gè)Java對象都有hashCode（）方法，都可通過該方法獲得它的hashCode值。得到這個(gè)對象的hashCode值之后，系統(tǒng)會根據(jù)該hashCode值來決定該元素的存儲位置。
我們可以看HashMap類的put（Kkey,Vvalue）方法的源代碼：
Java代碼
publicVput（Kkey,Vvalue）
{
//如果key為null，調(diào)用putForNullKey方法進(jìn)行處理
if（key==null）
returnputForNullKey（value）；
//根據(jù)key的keyCode計(jì)算Hash值
inthash=hash（key.hashCode（））；
//搜索指定hash值在對應(yīng)table中的索引
inti=indexFor（hash,table.length）；
//如果i索引處的Entry不為null，通過循環(huán)不斷遍歷e元素的下一個(gè)元素
for（Entrye=table[i];e!=null;e=e.next）
{
Objectk;
//找到指定key與需要放入的key相等（hash值相同
//通過equals比較放回true）
if（e.hash==hash&&（（k=e.key）==key
||key.equals（k）））
{
VoldValue=e.value;
e.value=value;
e.recordAccess（this）；
returnoldValue;
}
}
//如果i索引處的Entry為null，表明此處還沒有Entry
modCount++;
//將key、value添加到i索引處
addEntry（hash,key,value,i）；
returnnull;
}
上面程序中用到了一個(gè)重要的內(nèi)部接口：Map.Entry，每個(gè)Map.Entry其實(shí)就是一個(gè)key-value對。從上面程序中可以看出：當(dāng)系統(tǒng)決定存儲HashMap中的key-value對時(shí)，完全沒有考慮Entry中的value，僅僅只是根據(jù)key來計(jì)算并決定每個(gè)Entry的存儲位置。這也說明了前面的結(jié)論：我們完全可以把Map集合中的value當(dāng)成key的附屬，當(dāng)系統(tǒng)決定了key的存儲位置之后，value隨之保存在那里即可。
上面方法提供了一個(gè)根據(jù)hashCode（）返回值來計(jì)算Hash碼的方法：hash（），這個(gè)方法是一個(gè)純粹的數(shù)學(xué)計(jì)算，其方法如下：
Java代碼
staticinthash（inth）
{
h^=（h>>>20）^（h>>>12）；
returnh^（h>>>7）^（h>>>4）；
}
對于任意給定的對象，只要它的hashCode（）返回值相同，那么程序調(diào)用hash（inth）方法所計(jì)算得到的Hash碼值總是相同的。接下來程序會調(diào)用indexFor（inth,intlength）方法來計(jì)算該對象應(yīng)該保存在table數(shù)組的哪個(gè)索引處。indexFor（inth,intlength）方法的代碼如下：
Java代碼
staticintindexFor（inth,intlength）
{
returnh&（length-1）；
}
這個(gè)方法非常巧妙，它總是通過h&（table.length-1）來得到該對象的保存位置——而HashMap底層數(shù)組的長度總是2的n次方，這一點(diǎn)可參看后面關(guān)于HashMap構(gòu)造器的介紹。
當(dāng)length總是2的倍數(shù)時(shí)，h&（length-1）將是一個(gè)非常巧妙的設(shè)計(jì)：假設(shè)h=5,length=16,那么h&length-1將得到5；如果h=6,length=16,那么h&length-1將得到6……如果h=15,length=16,那么h&length-1將得到15；但是當(dāng)h=16時(shí),length=16時(shí)，那么h&length-1將得到0了；當(dāng)h=17時(shí),length=16時(shí)，那么h&length-1將得到1了……這樣保證計(jì)算得到的索引值總是位于table數(shù)組的索引之內(nèi)。
根據(jù)上面put方法的源代碼可以看出，當(dāng)程序試圖將一個(gè)key-value對放入HashMap中時(shí)，程序首先根據(jù)該key的hashCode（）返回值決定該Entry的存儲位置：如果兩個(gè)Entry的key的hashCode（）返回值相同，那它們的存儲位置相同。如果這兩個(gè)Entry的key通過equals比較返回true，新添加Entry的value將覆蓋集合中原有Entry的value，但key不會覆蓋。如果這兩個(gè)Entry的key通過equals比較返回false，新添加的Entry將與集合中原有Entry形成Entry鏈，而且新添加的Entry位于Entry鏈的頭部——具體說明繼續(xù)看addEntry（）方法的說明。
當(dāng)向HashMap中添加key-value對，由其key的hashCode（）返回值決定該key-value對（就是Entry對象）的存儲位置。當(dāng)兩個(gè)Entry對象的key的hashCode（）返回值相同時(shí)，將由key通過eqauls（）比較值決定是采用覆蓋行為（返回true），還是產(chǎn)生Entry鏈（返回false）。
上面程序中還調(diào)用了addEntry（hash,key,value,i）；代碼，其中addEntry是HashMap提供的一個(gè)包訪問權(quán)限的方法，該方法僅用于添加一個(gè)key-value對。下面是該方法的代碼：
Java代碼
voidaddEntry（inthash,Kkey,Vvalue,intbucketIndex）
{
//獲取指定bucketIndex索引處的Entry
Entrye=table[bucketIndex];//①
//將新創(chuàng)建的Entry放入bucketIndex索引處，并讓新的Entry指向原來的Entry
table[bucketIndex]=newEntry（hash,key,value,e）；
//如果Map中的key-value對的數(shù)量超過了極限
if（size++>=threshold）
//把table對象的長度擴(kuò)充到2倍。
resize（2*table.length）；//②
}
上面方法的代碼很簡單，但其中包含了一個(gè)非常優(yōu)雅的設(shè)計(jì)：系統(tǒng)總是將新添加的Entry對象放入table數(shù)組的bucketIndex索引處——如果bucketIndex索引處已經(jīng)有了一個(gè)Entry對象，那新添加的Entry對象指向原有的Entry對象（產(chǎn)生一個(gè)Entry鏈），如果bucketIndex索引處沒有Entry對象，也就是上面程序①號代碼的e變量是null，也就是新放入的Entry對象指向null，也就是沒有產(chǎn)生Entry鏈。
JDK源碼
在JDK安裝目錄下可以找到一個(gè)src.zip壓縮文件，該文件里包含了Java基礎(chǔ)類庫的所有源文件。只要讀者有學(xué)習(xí)興趣，隨時(shí)可以打開這份壓縮文件來閱讀Java類庫的源代碼，這對提高讀者的編程能力是非常有幫助的。需要指出的是：src.zip中包含的源代碼并沒有包含像上文中的中文注釋，這些注釋是筆者自己添加進(jìn)去的。
Hash算法的性能選項(xiàng)
根據(jù)上面代碼可以看出，在同一個(gè)bucket存儲Entry鏈的情況下，新放入的Entry總是位于bucket中，而最早放入該bucket中的Entry則位于這個(gè)Entry鏈的最末端。
上面程序中還有這樣兩個(gè)變量：
*size：該變量保存了該HashMap中所包含的key-value對的數(shù)量。
*threshold：該變量包含了HashMap能容納的key-value對的極限，它的值等于HashMap的容量乘以負(fù)載因子（loadfactor）。
從上面程序中②號代碼可以看出，當(dāng)size++>=threshold時(shí)，HashMap會自動調(diào)用resize方法擴(kuò)充HashMap的容量。每擴(kuò)充一次，HashMap的容量就增大一倍?！∩厦娉绦蛑惺褂玫膖able其實(shí)就是一個(gè)普通數(shù)組，每個(gè)數(shù)組都有一個(gè)固定的長度，這個(gè)數(shù)組的長度就是HashMap的容量。HashMap包含如下幾個(gè)構(gòu)造器：
*HashMap（）：構(gòu)建一個(gè)初始容量為16，負(fù)載因子為0.75的HashMap。
*HashMap（intinitialCapacity）：構(gòu)建一個(gè)初始容量為initialCapacity，負(fù)載因子為0.75的HashMap。
*HashMap（intinitialCapacity,floatloadFactor）：以指定初始容量、指定的負(fù)載因子創(chuàng)建一個(gè)HashMap。
當(dāng)創(chuàng)建一個(gè)HashMap時(shí)，系統(tǒng)會自動創(chuàng)建一個(gè)table數(shù)組來保存HashMap中的Entry，下面是HashMap中一個(gè)構(gòu)造器的代碼：
Java代碼
//以指定初始化容量、負(fù)載因子創(chuàng)建HashMap
publicHashMap（intinitialCapacity,floatloadFactor）
{
//初始容量不能為負(fù)數(shù)
if（initialCapacity<0）
thrownewIllegalArgumentException（
"Illegalinitialcapacity:"+
initialCapacity）；
//如果初始容量大于容量，讓出示容量
if（initialCapacity>MAXIMUM_CAPACITY）
initialCapacity=MAXIMUM_CAPACITY;
//負(fù)載因子必須大于0的數(shù)值
if（loadFactor<=0||Float.isNaN（loadFactor））
thrownewIllegalArgumentException（
loadFactor）；
//計(jì)算出大于initialCapacity的最小的2的n次方值。
intcapacity=1;
while（capacity capacity《=1;
this.loadFactor=loadFactor;
//設(shè)置容量極限等于容量*負(fù)載因子
threshold=（int）（capacity*loadFactor）；
//初始化table數(shù)組
table=newEntry[capacity];//①
init（）；
}
上面代碼中粗體字代碼包含了一個(gè)簡潔的代碼實(shí)現(xiàn)：找出大于initialCapacity的、最小的2的n次方值，并將其作為HashMap的實(shí)際容量（由capacity變量保存）。例如給定initialCapacity為10，那么該HashMap的實(shí)際容量就是16。
程序①號代碼處可以看到：table的實(shí)質(zhì)就是一個(gè)數(shù)組，一個(gè)長度為capacity的數(shù)組。
對于HashMap及其子類而言，它們采用Hash算法來決定集合中元素的存儲位置。當(dāng)系統(tǒng)開始初始化HashMap時(shí)，系統(tǒng)會創(chuàng)建一個(gè)長度為capacity的Entry數(shù)組，這個(gè)數(shù)組里可以存儲元素的位置被稱為“桶（bucket）”，每個(gè)bucket都有其指定索引，系統(tǒng)可以根據(jù)其索引快速訪問該bucket里存儲的元素。
無論何時(shí)，HashMap的每個(gè)“桶”只存儲一個(gè)元素（也就是一個(gè)Entry），由于Entry對象可以包含一個(gè)引用變量（就是Entry構(gòu)造器的的最后一個(gè)參數(shù)）用于指向下一個(gè)Entry，因此可能出現(xiàn)的情況是：HashMap的bucket中只有一個(gè)Entry，但這個(gè)Entry指向另一個(gè)Entry——這就形成了一個(gè)Entry鏈。
HashMap的讀取實(shí)現(xiàn)
當(dāng)HashMap的每個(gè)bucket里存儲的Entry只是單個(gè)Entry——也就是沒有通過指針產(chǎn)生Entry鏈時(shí)，此時(shí)的HashMap具有的性能：當(dāng)程序通過key取出對應(yīng)value時(shí)，系統(tǒng)只要先計(jì)算出該key的hashCode（）返回值，在根據(jù)該hashCode返回值找出該key在table數(shù)組中的索引，然后取出該索引處的Entry，最后返回該key對應(yīng)的value即可。看HashMap類的get（Kkey）方法代碼：
Java代碼
publicVget（Objectkey）
{
//如果key是null，調(diào)用getForNullKey取出對應(yīng)的value
if（key==null）
returngetForNullKey（）；
//根據(jù)該key的hashCode值計(jì)算它的hash碼
inthash=hash（key.hashCode（））；
//直接取出table數(shù)組中指定索引處的值，
for（Entrye=table[indexFor（hash,table.length）];
e!=null;
//搜索該Entry鏈的下一個(gè)Entr
e=e.next）//①
{
Objectk;
//如果該Entry的key與被搜索key相同
if（e.hash==hash&&（（k=e.key）==key
||key.equals（k）））
returne.value;
}
returnnull;
}
從上面代碼中可以看出，如果HashMap的每個(gè)bucket里只有一個(gè)Entry時(shí)，HashMap可以根據(jù)索引、快速地取出該bucket里的Entry；在發(fā)生“Hash沖突”的情況下，單個(gè)bucket里存儲的不是一個(gè)Entry，而是一個(gè)Entry鏈，系統(tǒng)只能必須按順序遍歷每個(gè)Entry，直到找到想搜索的Entry為止——如果恰好要搜索的Entry位于該Entry鏈的最末端（該Entry是最早放入該bucket中），那系統(tǒng)必須循環(huán)到最后才能找到該元素。
歸納起來簡單地說，HashMap在底層將key-value當(dāng)成一個(gè)整體進(jìn)行處理，這個(gè)整體就是一個(gè)Entry對象。HashMap底層采用一個(gè)Entry[]數(shù)組來保存所有的key-value對，當(dāng)需要存儲一個(gè)Entry對象時(shí)，會根據(jù)Hash算法來決定其存儲位置；當(dāng)需要取出一個(gè)Entry時(shí)，也會根據(jù)Hash算法找到其存儲位置，直接取出該Entry。由此可見：HashMap之所以能快速存、取它所包含的Entry，完全類似于現(xiàn)實(shí)生活中母親從小教我們的：不同的東西要放在不同的位置，需要時(shí)才能快速找到它。
當(dāng)創(chuàng)建HashMap時(shí)，有一個(gè)默認(rèn)的負(fù)載因子（loadfactor），其默認(rèn)值為0.75，這是時(shí)間和空間成本上一種折衷：增大負(fù)載因子可以減少Hash表（就是那個(gè)Entry數(shù)組）所占用的內(nèi)存空間，但會增加查詢數(shù)據(jù)的時(shí)間開銷，而查詢是最頻繁的的操作（HashMap的get（）與put（）方法都要用到查詢）；減小負(fù)載因子會提高數(shù)據(jù)查詢的性能，但會增加Hash表所占用的內(nèi)存空間。
掌握了上面知識之后，我們可以在創(chuàng)建HashMap時(shí)根據(jù)實(shí)際需要適當(dāng)?shù)卣{(diào)整loadfactor的值；如果程序比較關(guān)心空間開銷、內(nèi)存比較緊張，可以適當(dāng)?shù)卦黾迂?fù)載因子；如果程序比較關(guān)心時(shí)間開銷，內(nèi)存比較寬裕則可以適當(dāng)?shù)臏p少負(fù)載因子。通常情況下，程序員無需改變負(fù)載因子的值。
如果開始就知道HashMap會保存多個(gè)key-value對，可以在創(chuàng)建時(shí)就使用較大的初始化容量，如果HashMap中Entry的數(shù)量一直不會超過極限容量（capacity*loadfactor），HashMap就無需調(diào)用resize（）方法重新分配table數(shù)組，從而保證較好的性能。當(dāng)然，開始就將初始容量設(shè)置太高可能會浪費(fèi)空間（系統(tǒng)需要創(chuàng)建一個(gè)長度為capacity的Entry數(shù)組），因此創(chuàng)建HashMap時(shí)初始化容量設(shè)置也需要小心對待。