HashMap知識點總結，這一篇算是總結的不錯的了，建議看看！

• 2020 年 12 月 28 日
• 筆記
• JAVA, 互聯網, 後端, 程序員, 面試

HashMap存儲結構

內部包含了⼀個 Entry 類型的數組 Entry[] table。transient Entry[] table;(transient:表示不能被序列化)Entry類型存儲着鍵值對。它包含了四個字段， Entry 是⼀個鏈表。即數組中的每個位置被當成⼀個桶，⼀個桶存放⼀個Entry鏈表。HashMap 使⽤拉鏈法來解決衝突，同⼀個鏈表中存放哈希值和散列桶取模運算結果相同的 Entry。

常規操作

• final K getKey();
• final V getValue()；
• final V setValue(V newValue);
• final boolean equals(Object o);
• final int hashCode();
• final String toString();

static class Entry<K,V> implements Map.Entry<K,V> {
 final K key;
 V value;
 Entry<K,V> next;
 int hash;
 Entry(int h, K k, V v, Entry<K,V> n) {
 value = v;
 next = n;
 key = k;
 hash = h;
2. 拉鏈法的⼯作原理
 }
 public final K getKey() {
 return key;
 }
 public final V getValue() {
 return value;
 }
 public final V setValue(V newValue) {
 V oldValue = value;
 value = newValue;
 return oldValue;
 }
 public final boolean equals(Object o) {
 if (!(o instanceof Map.Entry))
 return false;
 Map.Entry e = (Map.Entry)o;
 Object k1 = getKey();
 Object k2 = e.getKey();
 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
 Object v1 = getValue();
 Object v2 = e.getValue();
 if (v1 == v2 || (v1 != null && v1.equals(v2)))
 return true;
 }
 return false;
 }
 public final int hashCode() {
 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
 }
 public final String toString() {
 return getKey() + "=" + getValue();
 }
}

插入put操作

• 插入數組是對hash值與散列表使用除留餘數的方法計算得到對應桶序號；

• 插入時採用鏈表的頭插法進行插入;

• HashMap 允許插⼊鍵為 null 的鍵值對。但是因為 null 的 hashCode() ⽅法，也就⽆法確定該鍵值對應桶下標，只能通過強制指定第 0 個桶存放鍵為 null 的鍵值對；

public V put(K key, V value) {
 if (table == EMPTY_TABLE) {
 inflateTable(threshold);
 }
 // 鍵為 null 單獨處理
 if (key == null)
 return putForNullKey(value);
 int hash = hash(key);
 // 確定桶下標
 int i = indexFor(hash, table.length);
 // 先找出是否已經存在鍵為 key 的鍵值對，如果存在的話就更新這個鍵值對的值為 value
 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
 Object k;
 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
 V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
 }
 modCount++;
 // 插⼊新鍵值對
 addEntry(hash, key, value, i);
 return null; }

private V putForNullKey(V value) {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
 if (e.key == null) {
 V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
 }
 modCount++;
 addEntry(0, null, value, 0);
 return null; }

void addEntry(int hash, K key, V value, int bucketIndex) {
 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) {
 Entry<K,V> e = table[bucketIndex];
 // 頭插法，鏈表頭部指向新的鍵值對
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 size++; }

擴容

設 HashMap 的 table ⻓度為 M，需要存儲的鍵值對數量為 N，如果哈希函數滿⾜均勻性的要求，那麼每條鏈表的⻓度⼤約為 N/M，因此查找的複雜度為 O(N/M)。為了讓查找的成本降低，應該使 N/M 儘可能⼩，因此需要保證 M 儘可能⼤，也就是說 table 要儘可能⼤。

• HashMap 采⽤動態擴容來根據當前的鍵值對數量來調整數組長度，使得空間效率和時間效率都能得到保證。(HashMap擴容並不是等到數組滿了才擴容，因為元素是插入到鏈表中，永遠也不會滿，所以有一個閾值–threshold，當等於它時就進行擴容操作)

• capacity一般為2的n次方，即使用戶傳入的不是2的n次方，它也可以⾃動地將傳⼊的容量轉換為 2 的n 次⽅。原因是除留餘數取模時採用的是位運算來代替取模運算，能夠極⼤降低重新計算桶下標操作的複雜度。(位運算只用於2進制，所以需要2的n次方)；

• 當需要擴容時，使⽤ resize() 實現，令 capacity 為原來的兩倍，擴容操作需要把oldTable 的所有鍵值對重新插入newTable 中，因此這⼀步是很費時的。

• 當⼀個桶存儲的鏈表⻓度⼤於等於 8 時會將鏈錶轉換為紅⿊樹。

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry[] table;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;

void addEntry(int hash, K key, V value, int bucketIndex) {
 Entry<K,V> e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 if (size++ >= threshold)
 resize(2 * table.length);
}

void resize(int newCapacity) {
 Entry[] oldTable = table;
 int oldCapacity = oldTable.length;
 if (oldCapacity == MAXIMUM_CAPACITY) {
 threshold = Integer.MAX_VALUE;
 return;
 }
 Entry[] newTable = new Entry[newCapacity];
 transfer(newTable);
 table = newTable;
 threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
 Entry[] src = table;
 int newCapacity = newTable.length;
 for (int j = 0; j < src.length; j++) {
 Entry<K,V> e = src[j];
 if (e != null) {
 src[j] = null;
 do {
 Entry<K,V> next = e.next;
 int i = indexFor(e.hash, newCapacity);
 e.next = newTable[i];
 newTable[i] = e;
 e = next;
 } while (e != null);
 }
 }
}

與 Hashtable 的⽐較**

Hashtable 使⽤ synchronized 來進⾏同步。
HashMap 可以插⼊鍵為 null 的 Entry。
HashMap 的迭代器是 fail-fast 迭代器。
HashMap 不能保證隨着時間的推移 Map 中的元素次序是不變的。

總結

歡迎關注公眾號：前程有光，領取一線大廠Java面試題總結+各知識點學習思維導+一份300頁pdf文檔的Java核心知識點總結！