通過HashMap和HashSet的源代碼分析了Hash存儲機制。
事實上，HashSet和HashMap有很多相似之處。對於HashSet，系統使用哈希算法來確定集合元素的存儲位置，可以保證集合元素能夠快速存儲和檢索。對於HashMap，將系統的鍵值作為壹個整體來對待，鍵值的存儲位置總是根據Hash算法來計算，這樣可以保證映射的鍵值對能夠被快速的存儲和檢索。
在介紹集合存儲之前，需要指出的是，雖然集合聲稱存儲Java對象，但實際上並沒有將Java對象放入集合集合中，只是在集合集合中保留對這些對象的引用。換句話說，Java集合實際上是指向實際Java對象的多個引用變量的集合。
收藏和參考
就像引用類型的數組，當我們把Java對象放入數組時，並不是真的把Java對象放入數組，只是把對對象的引用放入數組，每個數組元素都是壹個引用變量。
HashMap的存儲實現
當壹個程序試圖將多個鍵值放入壹個HashMap時，以下面的代碼片段為例:
Java代碼
HashMap & lt字符串，Double & gtmap = new HashMap & lt字符串，Double & gt();
Map.put("中文"，80.0)；
Map.put(《數學》，89.0)；
Map.put("英語"，78.2)；
HashMap使用壹種所謂的“哈希算法”來確定每個元素的存儲位置。
當程序執行map.put("中文"，80.0)；，系統會調用“中文”的hashCode()方法來獲取它的hashCode值——每個Java對象都有壹個hashCode()方法，可以用來獲取它的hashCode值。得到這個對象的hashCode值後，系統會根據hashCode值確定元素的存儲位置。
我們可以看看HashMap類的put(K key，V value)方法的源代碼:
Java代碼
公共V put(K鍵，V值)
{
//如果key為null，則調用putForNullKey方法進行處理。
if (key == null)
返回putForNullKey(值)；
//根據key的鍵碼計算哈希值。
int hash = hash(key . hashcode())；
//在相應的表中搜索指定哈希值的索引。
int i = indexFor(hash，table . length)；
//如果I索引處的條目不為空，則通過循環連續遍歷E元素的下壹個元素。
for(Entry & lt；k，V & gte =表[I]；e！= nulle = e.next)
{
對象k；
//發現指定的鍵等於要放入的鍵(哈希值相同
//通過等於比較返回true)
if(e . hash = = hash & amp；& amp((k = e.key) == key
|| key.equals(k)))
{
V oldValue = e.value
e.value =值；
e . record access(this)；
返回舊值；
}
}
//如果I索引處的條目為空，則此處沒有條目。
modcount++；
//將鍵和值添加到I索引。
addEntry(hash，key，value，I)；
返回null
}
上面的程序中使用了壹個重要的內部接口:Map。條目和每張地圖。Entry實際上是壹個鍵值對。從上面的程序可以看出，當系統決定在HashMap中存儲鍵-值對時，完全不考慮條目中的值，只根據鍵計算確定每個條目的存儲位置。這也解釋了前面的結論:我們完全可以把映射集中的值看作是鍵的附件，當系統確定了鍵的存儲位置，就可以把值保存在那裏。
上述方法提供了壹種根據hashcode (): hash()的返回值計算HashCode的方法，這是壹種純數學計算，其方法如下:
Java代碼
靜態整數哈希(整數h)
{
^=(h & gt；& gt& gt^(h & gt；& gt& gt12);
返回h ^(h & gt；& gt& gt7)^(h & gt；& gt& gt4);
}
對於任何給定的對象，只要它的HashCode()返回值相同，那麽通過調用hash(int h)方法計算出來的哈希代碼值總是相同的。接下來，程序將調用indexFor(int h，int length)方法來計算對象應該存儲在表數組中的哪個索引。indexFor(int h，int length)方法的代碼如下:
Java代碼
靜態整數索引For(整數h，整數長度)
{
返回h & amp(長度-1)；
}
這個方法很巧妙，它總是通過H &；(table.length -1)來獲取對象的存儲位置——而HashMap底部數組的長度永遠是2的n次方，這個可以在後面HashMap構造函數的介紹中看到。
當長度總是2的倍數時，H &；(length-1)會是壹個非常巧妙的設計:假設H = 5，Length = 16，那麽h & Length-1會得到5；如果h = 6，長度= 16，那麽h &；長度-1將得到6...如果H = 15，長度= 16，則H &；長度-1會得到15；但當h=16，長度=16時，則h &；長度-1會得到0；當h=17，長度=16時，則h &；長度-1將得到1...這確保了計算出的索引值總是在表數組的索引內。
根據上面put方法的源代碼可以看出，當程序試圖將壹個鍵-值對放入壹個HashMap中時，程序首先根據鍵的hashCode()返回值確定條目的存儲位置:如果兩個條目的鍵的hashCode()返回值相同，那麽它們的存儲位置相同。如果這兩個條目的鍵通過相等比較返回true，則新添加的條目的值將覆蓋集合中原始條目的值，但鍵不會覆蓋它。如果這兩個條目的鍵通過相等比較返回false，那麽新添加的條目將與集合中的原條目形成壹個條目鏈，新添加的條目位於條目鏈的頭部——詳見addEntry()方法的描述。
當壹個鍵值對被添加到HashMap中時，鍵值對(即Entry對象)的存儲位置由其key hashCode()的返回值決定。當兩個Entry對象的key的hashCode()返回值相同時，key會通過eqauls()比較值，決定是采用覆蓋行為(返回true)還是生成壹個Entry鏈(返回false)。
上面的程序中還調用了AddEntry(hash，key，value，I)；代碼，其中addEntry是HashMap提供的包訪問方法，只用於添加壹個鍵值對。下面是這個方法的代碼:
Java代碼
void addEntry(int hash，K key，V value，int bucketIndex)
{
//獲取指定bucketIndex索引處的條目。
Entry & ltk，V & gte =表[bucket index]；// ①
//將新創建的條目放入bucketIndex，並使新條目指向原始條目。
table[bucketIndex] =新條目& ltk，V & gt(hash，key，value，e)；
//如果映射中的鍵-值對的數量超過限制，
if(size++ & gt；=閾值)
//將表格對象的長度擴展到2倍。
調整大小(2 * table . length)；// ②
}
上面方法的代碼非常簡單，但是包含了壹個非常優雅的設計:系統總是將新添加的Entry對象放入表數組的bucketIndex中——如果bucketIndex處已經有壹個Entry對象，那麽新添加的Entry對象指向原來的Entry對象(生成壹個Entry鏈)。如果bucketIndex索引處沒有Entry對象，即上面程序中代碼1的e變量為null，即新添加的Entry對象指向null，即沒有生成Entry鏈。
JDK源代碼
您可以在JDK安裝目錄中找到壹個src.zip壓縮文件，其中包含Java基本類庫的所有源文件。只要讀者有興趣學習，隨時可以打開這個壓縮文件閱讀Java類庫的源代碼，對提高讀者的編程能力很有幫助。需要指出的是，src.zip中包含的源代碼並不像上面那樣包含中文註釋，這些註釋都是作者自己添加的。
哈希算法的性能選項
根據上面的代碼可以看出，在同壹個桶存儲入口鏈的情況下，新放入的入口總是位於桶中，最先放入桶中的入口位於這個入口鏈的末端。
上述程序中有兩個變量:
* size:這個變量保存這個HashMap中包含的鍵值對的數量。
* threshold:這個變量包含了HashMap所能容納的鍵值對的限制，它的值等於HashMap的容量乘以負載因子。
從上面程序中的代碼②可以看出，當size++大於；= threshold，HashMap會自動調用resize方法來擴展HashMap的容量。每次擴展，HashMap的容量都會翻倍。
上面程序中使用的表實際上是壹個普通的數組，每個數組都有固定的長度，這個數組的長度就是HashMap的容量。HashMap包含以下構造函數:
* HashMap():構建壹個HashMap，初始容量為16，加載因子為0.75。
* HashMap(int initialCapacity):用initialCapacity和load factor 0.75構建壹個HashMap。
* HashMap (int initial capacity，float load factor):用指定的初始容量和指定的加載因子創建壹個HashMap。
當創建壹個散列表時，系統會自動創建壹個表數組來保存散列表中的條目。下面是HashMap中構造函數的代碼:
Java代碼
//創建壹個具有指定初始化容量和加載因子的HashMap。
public HashMap(int initial capacity，float loadFactor)
{
//初始容量不能為負。
if(initial capacity & lt；0)
拋出新的IllegalArgumentException(
"非法初始容量:"+
初始容量)；
//如果初始容量大於最大容量，我來顯示容量。
if(initial capacity & gt；最大容量)
initial CAPACITY = max _ CAPACITY；
//加載因子必須大於0。
if(負載系數& lt= 0 || Float.isNaN(loadFactor))
拋出新的IllegalArgumentException(
負載系數)；
//計算大於initialCapacity的最小2次方值。
int容量= 1；
while(容量& lt初始容量)
容量& lt& lt= 1;
this.loadFactor =負載系數；
//將容量限制設置為容量*負載系數。
閾值= (int)(容量*負載系數)；
//初始化表格數組
table =新條目[容量]；// ①
init()；
}
上面代碼中的加粗代碼包含了壹個簡潔的代碼實現:求大於initialCapacity的2的n次方的最小值，並將其作為HashMap的實際容量(由Capacity變量保存)。例如，給定初始容量10，HashMap的實際容量是16。
從程序①的代碼中可以看出，table的本質是壹個數組，壹個長度為容量的數組。
對於HashMap及其子類，他們使用哈希算法來確定元素在集合中的存儲位置。當系統開始初始化HashMap時，系統會創建壹個長度為capacity的入口數組。這個數組中可以存放元素的位置稱為“桶”，每個桶都有其指定的索引，所以系統可以根據其索引快速訪問桶中存放的元素。
在任何時候，HashMap的每個桶只存儲壹個元素(即壹個條目)。因為Entry對象可以包含壹個引用變量(即Entry構造函數的最後壹個參數)來指向下壹個條目，所以可能會出現HashMap的桶中只有壹個條目，但是這個條目指向了另壹個條目——這就形成了壹個條目鏈。如圖1所示:
圖1。HashMap的存儲圖
讀取HashMap的實現
當HashMap的每個桶中存儲的條目只有壹個條目時——也就是說，條目鏈不是通過指針生成的——HashMap的性能最好:當程序通過鍵取相應的值時，系統只需要先計算鍵的返回值。根據hashCode的返回值找出表數組中鍵的索引，然後取出索引處的條目，最後返回鍵對應的值。看看HashMap類的get(K key)方法代碼:
Java代碼
public V get(對象鍵)
{
//如果鍵為空，則調用getForNullKey獲取相應的值。
if (key == null)
返回getForNullKey()；
//根據關鍵字的hashcode值計算關鍵字的hashCode。
int hash = hash(key . hashcode())；
//直接取表數組中指定索引處的值，
for(Entry & lt；k，V & gte = table[indexFor(hash，table . length)]；
e！= null
//搜索入口鏈的下壹個入口。
e = e.next) // ①
{
對象k；
//如果條目的關鍵字與搜索到的關鍵字相同。
if(e . hash = = hash & amp；& amp((k = e.key) == key
|| key.equals(k)))
返回e.value
}
返回null
}
從上面的代碼可以看出，如果HashMap的每個桶中只有壹個條目，HashMap可以根據索引快速檢索桶中的條目；在“哈希沖突”的情況下，單個桶存儲的不是壹個條目，而是壹個條目鏈，系統只能依次遍歷每個條目，直到找到想要搜索的條目——如果想要搜索的條目位於條目鏈的末端(最早放入桶中)，系統必須循環到末端才能找到元素。
綜上所述，HashMap在底層把key-value當做壹個整體，這個整體就是壹個Entry對象。HashMap的底層使用Entry[]數組來存儲所有的鍵值對。當壹個入口對象需要存儲時，它的存儲位置將根據哈希算法來確定。當需要取出壹個條目時，會根據哈希算法找到它的存儲位置，直接取出該條目。可以看出，HashMap之所以能夠快速存儲和檢索它所包含的條目，和我媽從小在現實生活中教給我們的完全類似:不同的東西要放在不同的位置，需要的時候可以快速找到。
創建HashMap時，有壹個默認的加載因子(默認值為0.75)，這是時間和空間開銷的折中:增加加載因子可以減少哈希表(即條目數組)占用的內存空間，但會增加查詢數據的時間開銷，而查詢是最頻繁的操作(HashMap的get()和put()方法都使用查詢)；降低加載因子會提高數據查詢的性能，但會增加哈希表占用的內存空間。
掌握以上知識後，我們可以在創建HashMap時根據實際需要適當調整load factor的值；如果程序在意空間成本，內存緊張，可以適當增加加載因子；如果程序關心時間開銷，內存充裕，可以適當降低加載因子。通常，程序員不需要改變加載因子的值。
如果壹開始就知道HashMap會保存多個鍵值對，那麽在創建它的時候可以使用更大的初始化容量。如果HashMap中的條目數從未超過capacity * load factor，HashMap就不需要調用resize()方法來重新分配表數組，從而保證更好的性能。當然，壹開始就把初始容量設置的太高可能會浪費空間(系統需要創建壹個容量長度的入口數組)，所以在創建HashMap的時候也要謹慎對待初始容量的設置。