通過HashMap和HashSet的源代碼分析了Hash存儲機制。
事實上，HashSet和HashMap有很多相似之處。對於HashSet，系統使用哈希算法來確定集合元素的存儲位置，這可以確保集合元素可以快速存儲和檢索。對於HashMap，系統的鍵值被視為壹個整體，鍵值的存儲位置總是根據哈希算法計算的，這可以確保映射的鍵值對可以快速存儲和檢索。
在介紹集合存儲之前，應該指出的是，盡管集合聲稱存儲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）時；，系統會調用“Chinese”的hashCode（）方法來獲取它的hashCode值——每個Java對象都有壹個hashCode（）方法，可以用來獲取它的hashCode值。得到這個對象的hashCode值後，系統會根據hashCode值確定元素的存儲位置。
我們可以看看HashMap類的put（K key，V value）方法的源代碼:
Java代碼
公共V輸入（K鍵，V值）
{
//如果鍵為null，則調用putForNullKey方法進行處理。
if（key = = null）
返回putForNullKey（值）；
//根據密鑰的keyCode計算哈希值。
int hash = hash（key . hashcode（））；
//在相應的表中搜索指定哈希值的索引。
int I = index for（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舊值= e.value
e.value =價值；
e . record access（this）；
返回舊值；
}
}
//如果I索引處的條目為空，則此處沒有條目。
modcount++；
//向I索引添加鍵和值。
add entry（hash，key，value，I）；
返回null
}
上面的程序中使用了壹個重要的內部接口:Map。條目和每個地圖。條目實際上是壹個鍵值對。從上面的程序可以看出，當系統決定將鍵值對存儲在HashMap中時，完全不考慮條目中的值，只根據鍵計算和確定每個條目的存儲位置。這也解釋了前面的結論:我們可以完全將映射集中的值視為鍵的附件，當系統確定鍵的存儲位置時，該值可以保存在那裏。
上述方法提供了壹種根據HashCode（）:hash（）的返回值計算HashCode的方法，這是壹種純數學計算，其方法如下:
Java代碼
靜態整數哈希（整數h）
{
^=（h & gt；& gt& gt^（h & gt；& gt& gt12);
返回h ^（h & gt；& gt& gt^（h & gt；& gt& gt4);
}
對於任何給定的對象，只要其HashCode（）返回值相同，則通過調用hash（int h）方法計算的哈希代碼值總是相同的。接下來，程序將調用index for（int h，int length）方法來計算對象應該存儲在表數組中的哪個索引。index for（int h，int length）方法的代碼如下:
Java代碼
靜態整數索引For（整數h，整數長度）
{
返回h & amp（長度-1）；
}
這個方法很巧妙，它總是通過H &；（table.length -1）來獲取對象的存儲位置-而HashMap的底部數組的長度始終是2的n次方，這壹點在後面HashMap構造函數的介紹中可以看到。
當長度總是2的倍數時，H &；（長度-1）將是壹個非常巧妙的設計:假設H = 5且長度= 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中時，鍵值對（即條目對象）的存儲位置由其key hashCode（）的返回值決定。當兩個條目對象的鍵的hashCode（）返回值相同時，該鍵將通過eqauls（）比較這些值，以決定是采用覆蓋行為（返回true）還是生成壹個條目鏈（返回false）。
上面的程序中還調用了add entry（hash，key，value，I）；代碼，其中addEntry是HashMap提供的包訪問方法，僅用於添加壹個鍵值對。以下是此方法的代碼:
Java代碼
void add entry（int hash，K key，V value，int bucketIndex）
{
//獲取指定bucketIndex索引處的條目。
條目& ltk，V & gte =表【bucket index】；// ①
//將新創建的條目放入bucketIndex中，並使新條目指向原始條目。
table【bucket index】=新條目& 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:該變量保存哈希表中包含的鍵值對的數量。
* threshold:該變量包含HashMap可以容納的鍵值對的限制，其值等於HashMap的容量乘以加載因子。
從上述程序中的代碼②可以看出，當size++》時；= threshold時，HashMap會自動調用resize方法來擴展HashMap的容量。每次擴展，HashMap的容量都會翻倍。
上面程序中使用的表實際上是壹個普通的數組，每個數組都有固定的長度，而這個數組的長度就是HashMap的容量。HashMap包含以下構造函數:
* HashMap（）:構建壹個HashMap，初始容量為16，加載因子為0.75。
* HashMap（int initialCapacity）:使用initial capacity和0.75的加載因子構建壹個HashMap。
* HashMap（int初始容量，float加載因子）:創建壹個具有指定初始容量和指定加載因子的HashMap。
創建散列表時，系統會自動創建壹個表數組來保存散列表中的條目。以下是HashMap中構造函數的代碼:
Java代碼
//創建壹個具有指定初始化容量和加載因子的HashMap。
公共哈希表（int initialCapacity，float loadFactor）
{
//初始容量不能為負。
if（initial capacity & lt；0)
拋出新的IllegalArgumentException（
“非法初始容量:“+
initial capacity）；
//如果初始容量大於最大容量，讓我顯示容量。
if（initial capacity & gt；最大容量）
initial CAPACITY = MAXIMUM _ CAPACITY；
//加載因子必須大於0。
if（負載系數& lt= 0 | | float . isnan（load因數））
拋出新的IllegalArgumentException（
負載系數）；
//計算大於initialCapacity的最小2次方值。
int capacity = 1；
while（容量& lt初始容量）
容量& lt& lt= 1;
this.loadFactor =負載系數；
//將容量限制設置為容量*負載系數。
threshold =（int）（容量*負載因子）；
//初始化表格數組
table =新條目【容量】；// ①
init()；
}
上述代碼中的粗體代碼包含壹個簡潔的代碼實現:找到大於initialCapacity的2的n次方中的最小值，並將其作為HashMap的實際容量（由Capacity變量保存）。例如，給定初始容量為10，哈希表的實際容量為16。
從程序①的代碼可以看出，表的本質是壹個數組，壹個長度為容量的數組。
對於HashMap及其子類，它們使用哈希算法來確定集合中元素的存儲位置。當系統開始初始化HashMap時，系統將創建壹個長度為capacity的條目數組。該數組中可以存儲元素的位置稱為“桶”，每個桶都有其指定的索引，因此系統可以根據其索引快速訪問桶中存儲的元素。
在任何時候，HashMap的每個桶都只存儲壹個元素（即壹個條目）。因為Entry對象可以包含壹個引用變量（即Entry構造函數的最後壹個參數）來指向下壹個條目，所以可能會發生這樣的情況:HashMap的bucket中只有壹個條目，但這個條目指向另壹個條目——這就形成了壹個條目鏈。如圖1所示:
圖1。散列表的存儲圖
讀取哈希表的實現
當存儲在HashMap的每個桶中的條目只有壹個條目時，HashMap具有最佳性能——也就是說，條目鏈不是通過指針生成的:當程序通過鍵獲取相應的值時，系統只需首先計算鍵的返回值。根據hashCode的返回值找出表數組中鍵的索引，然後取出索引處的條目，最後返回鍵對應的值。看看HashMap類的get（K key）方法代碼:
Java代碼
public V get（對象鍵）
{
//如果鍵為null，則調用getForNullKey獲取相應的值。
if（key = = null）
返回getForNullKey（）；
//根據關鍵字的hashcode值計算關鍵字的hashCode。
int hash = hash（key . hashcode（））；
//直接獲取表數組中指定索引處的值，
for（Entry & lt；k，V & gte = table【index for（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時，有壹個默認的load factor（默認值為0.75），這是時間和空間成本的折衷:增加load factor可以減少哈希表（即條目數組）占用的內存空間，但會增加查詢數據的時間成本，而查詢是最頻繁的操作（HashMap的get（）和put（）方法都使用查詢）；降低加載因子會提高數據查詢的性能，但會增加哈希表占用的內存空間。
掌握以上知識後，我們在創建HashMap時可以根據實際需要適當調整load factor的值；如果程序關心空間成本，內存緊張，可以適當增加加載因子；如果程序關心時間成本並且內存充足，可以適當降低加載因子。通常，程序員不需要更改加載因子的值。
如果您從壹開始就知道HashMap將保存多個鍵值對，那麽您可以在創建它時使用更大的初始化容量。如果HashMap中的條目數從未超過capacity * load factor，則HashMap不需要調用resize（）方法來重新分配表數組，從而確保更好的性能。當然，在開始時將初始容量設置得太高可能會浪費空間（系統需要創建具有容量長度的條目數組），因此在創建HashMap時也應謹慎對待初始容量設置。