HashMap繼承于AbstractMap，實現了Map接口，同時標記了Cloneable和Serializable接口。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, SerializableHashMap提供了四個構造函數： (1) HashMap()：構造一個初始容量為16和加載因子為0.75的空HashMap。 (2) HashMap(int initialCapacity)：構造一個帶指定初始容量和默認加載因子0.75的空HashMap。 (3) HashMap(int initialCapacity, float loadFactor)：構造一個帶指定初始容量和指定加載因子的空HashMap。 (4) HashMap(Map
public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); inflateTable(threshold); putAllForCreate(m); } PRivate void inflateTable(int toSize) { // Find a power of 2 >= toSize，計算出大于toSize的最小的2的n次方值。 int capacity = roundUpToPowerOf2(toSize); // 設置HashMap的容量極限，當HashMap的容量達到該極限時就會進行擴容操作 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 初始化table數組 table = new Entry[capacity]; // Initialize the hashing mask value. We defer initialization until we really need it. initHashSeedAsNeeded(capacity); }初始容量是創建哈希表時的桶的數量， 加載因子是哈希表容量擴展前可以達到多滿的一種尺度，它衡量的是一個散列表的空間的使用程度。負載因子越大，表示散列表的裝填程度越高、對空間的利用更充分，后果卻是查找效率的降低；而負載因子太小，那么散列表的數據將過于稀疏，對空間的利用存在著浪費。
從構造函數中可以看出，HashMap本質是一個table數組，table數組里的元素是Entry鏈表。Entry為HashMap的內部類，它包含了鍵key、值value、下一個節點next以及hash值，正是由于Entry才構成了table數組的項為鏈表。
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } // 部分源碼略去put(K key, V value)方法的源碼如下。基本過程是： 1. 判斷key是否為null，若為null，則直接調用putForNullKey方法。 2. key不為空則計算key的hash值，再根據hash值搜索key落在哪個桶上。 3. 對該桶上的Entry鏈表進行遍歷，如果該鏈表上存在相同的key，則覆蓋原來key的value，否則將該元素保存在鏈頭（最先保存的元素放在鏈尾）。
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } // 當key為null，調用putForNullKey方法，保存null到table的第一個位置，這就是HashMap允許為null的原因 if (key == null) return putForNullKey(value); // 計算key的hash值 int hash = hash(key); // 計算key的hash值在table數組中的位置，即落在哪一個桶上 int i = indexFor(hash, table.length); // 迭代該桶上的Entry鏈表,找到key保存的位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 判斷該鏈表上是否有相同的hash值和相同的key（僅僅判斷hash值是否相同是不夠的） if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // 若存在相同，則直接覆蓋value，返回舊value V oldValue = e.value; e.value = value; e.recordaccess(this); return oldValue; } } //修改次數增加1 modCount++; // 該鏈表上不存在相同的hash值和key，則將key、value添加至i位置處 addEntry(hash, key, value, i); return null; }以上的存儲機制也解釋了HashSet是如何保證元素唯一性的。
這里需要強調下indexFor方法。HashMap就是通過該方法實現均勻分布table數據和充分利用空間的。初始化時，我們保證了capacity是大于初始容量的最小的2的n次方值。當length = 2^n時，不同的hash值發生碰撞的概率比較小，從而數據在table數組中分布較均勻，查詢速度也較快。
/** * Returns index for hash code h. */ static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }最后看一下鏈的產生和擴容問題。 1. 鏈的產生：系統總是將新創建的Entry放入bucketIndex索引處。如果bucketIndex處已經有了對象，那么新添加的Entry對象將指向原有的Entry對象，形成一條Entry鏈；如果bucketIndex處還沒有Entry對象，那么新添加的Entry對象將指向null。在table數組未擴容的情況下，兩個元素的hash值相同，就意味著它們會在同一個桶上。 2. 擴容問題：當HashMap中元素的數量等于table數組長度*加載因子，就會觸發擴容操作。擴容操作需盡量避免，因為它需要重新計算這些元素在新table數組中的位置并進行復制處理。
void addEntry(int hash, K key, V value, int bucketIndex) { // 若HashMap中元素的個數超過極限了，則容量擴大兩倍 if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { // 獲取bucketIndex處的Entry Entry<K,V> e = table[bucketIndex]; // 將新創建的Entry放入bucketIndex索引處，并讓新的Entry指向原來的Entry e table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }新聞熱點
疑難解答
