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

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 時會将連結清單轉換為紅⿊樹。

參數	含義
capacity	table 的容量⼤⼩，預設為 16。需要注意的是 capacity 必須保證為 2 的 n 次⽅。
size	鍵值對數量。
threshold	size 的臨界值，當 size ⼤于等于 threshold 就必須進⾏擴容操作。
loadFactor	裝載因⼦，table 能夠使⽤的⽐例，threshold = (int)(capacity* loadFactor)。

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核心知識點總結！