源碼是最好的教程,它比你想象中還詳細的解讀的類的原理. 我就從源碼注解的來看一下HashMap的底層原理。你可以在任意IDE打開HashMap.java，查看這些源碼注解。此jdk版本為1.8。

翻譯

以下是類外的源碼注解:

HashMap是基于哈希表的Map接口實現(xiàn)。此實現(xiàn)提供了所有可選的map操作（譯注：實現(xiàn)了Map的所有方法）, 并允許有null值和null鍵值。（HashMap類大致相當于Hashtable，不同之處在于它是不同步的，并允許鍵和值為null。）這個類不能保證map的順序；特別是，它不能保證順序在一段時間內(nèi)保持不變。(譯注:不能保證插入的順序和輸出的順序一致, 也不能保證此輸出順序一直不變)

HashMap為基本操作（get和put）提供了恒定時間的性能，假設(shè)hash函數(shù)在桶中正確分散元素。 集合視圖的迭代需要時間與HashMap實例的“容量”（桶數(shù)）加上其大?。ㄦI值對 數(shù)）成正比。因此，如果迭代性能很重要，不要將初始容量設(shè)置得太高（或負載因子太低）是非常重要的。

分析：在我理解恒定時間的性能是指方法的運行時間是恒定的. 桶是一個比喻, 數(shù)組的每個元素空間相當于一個桶, 好像鏈表就存放于桶中，實際上是鏈表的首節(jié)點存放于數(shù)組中. 當你看見文末的示意圖就明白了. 鍵值對 數(shù)指能存放Entry的數(shù)量. 初始容量默認為16, 負載因子默認為0.75.

HashMap的一個實例有兩個參數(shù)影響它的性能：初始容量和負載因子。容量是散列表中的桶數(shù)，初始容量只是創(chuàng)建散列表時的容量。負載因子是衡量散列表完整性的度量標準，允許在容量自動增加之前獲得。當散列表中的Entry數(shù)超過了負載因子和當前容量的乘積，hash表就rehashed（即內(nèi)部數(shù)據(jù)結(jié)構(gòu)重建），使散列表大約有兩倍buckets數(shù)。

分析: 例如，當散列表的Entry數(shù)超過0.75*16時，就rehashed。因為碰撞，此時數(shù)組中可能還沒有12個桶被占用。

作為普遍規(guī)則，默認負載因子（.75）提供了時間和空間成本之間的良好折中。 更高的值會降低空間開銷，但會增加查找成本（反映在HashMap類的大部分操作中，包括get 和put）。 在設(shè)置其初始容量時，應(yīng)考慮map中預(yù)期的entries數(shù)及其負載因子，以盡量減少重復(fù)操作的次數(shù)。 如果初始容量大于最大entries數(shù)除以負載因子（譯注：相當于entries數(shù)小于初始容量乘以負載因子），則不會發(fā)生rehash操作。

如果許多映射要存儲在HashMap實例中，創(chuàng)建了一個足夠大的容量將允許存儲的映射比其按需要執(zhí)行自動rehashing以增長表更加有效率。 請注意，許多key對象有相同的hashcode是降低任何hash表的性能的一個確切原因。 為了改善影響，當鍵為可比較時，該類可以使用鍵之間的比較順序來幫助打破約束關(guān)系。（譯注：hashcode相同會發(fā)生碰撞,利用在鏈表中依次比較后插入）.

請注意，此實現(xiàn)不同步。如果多個線程并發(fā)訪問hashMap，并且至少有一個線程要在結(jié)構(gòu)上修改map，則必須在外部進行同步。（結(jié)構(gòu)修改是指添加或刪除一個或多個鍵值對的任何操作；僅改變實例已經(jīng)包含key相關(guān)聯(lián)的value不是結(jié)構(gòu)修改。）這通常通過對自然封裝過的map的一些對象進行同步來完成。（譯注：自然封裝過的是直譯）

如果沒有這樣的對象存在，應(yīng)該使用Collections.synchronizedMap方法“包裝”map。 這最好在創(chuàng)建時完成，以防止意外的不同步訪問map：Map m = Collections.synchronizedMap（new HashMap（...））;迭代器返回的所有這些類的“集合視圖方法”是fail-fast：如果map 在迭代器創(chuàng)建之后的任何時間進行結(jié)構(gòu)修改，除了通過迭代器自己的 remove 方法 ，以其他任何方式修改，迭代器將拋出一個ConcurrentModificationException異常。因此，面對并發(fā)修改，迭代器將快速而干凈(fast))失敗(fail)，而不是在未來不確定的時間里有冒著任意的、非確定性行為的風險。

請注意，迭代器的fail-fast無法保證像它所定義的那樣，因為一般來說，在不同步并發(fā)修改的情況下，無法做出任何硬性保證。 Fail-fast的迭代器在最大努力的基礎(chǔ)上拋出ConcurrentModificationException。 因此，編寫取決于此異常的正確性的程序?qū)⑹清e誤的：迭代器的fail-fast行為應(yīng)僅用于檢測錯誤。

該類是Java Collections Framework 的成員。

以下是類中的源碼:

實施說明。

這個map通常用作為一個容器（bucketed）hash表，但是當容器變得太大時，它們被轉(zhuǎn)換成TreeNodes容器，每個都與java.util.TreeMap的結(jié)構(gòu)類似。大多數(shù)方法嘗試使用正常的容器，但是在適用的情況下繼承TreeNode的方法（只需通過檢查一個節(jié)點的instanceof）。TreeNode容器可以像任何其他樹一樣遍歷和使用樹節(jié)點，但另外支持在entries過多時更快的查找。然而，由于絕大多數(shù)正常使用的容器不會entries過多，所以檢查樹類容器的存在可能會延遲table方法的運行過程。

總結(jié)

我們通過上面的源碼翻譯，可以將HashMap的底層理解為由數(shù)組加鏈表實現(xiàn)。如此圖：

image

HashMap基于hashing（散列）原理，我們通過put和get法來存儲和獲取對象。transient Node<K,V>[] table;,table存放鏈表頭結(jié)點。鏈表的每個Node(Node相當于Entry)有hash、key、value、next四個屬性。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}