概念

HashMap是java中一種非常常用的基于哈希表的數據結構，允許o(1)

的時間復雜度進行元素插入，查找，和刪除。它通過”鍵-值“ 對的方式存儲數據。

總的來說：HashMap的底層原理：數組+鏈表+紅黑樹（jdk1.8之后還涉及紅黑樹）。

哈希函數與哈希值：每個鍵都會通過哈希函數計算哈希值，然后通過哈希值決定數組在那個桶（buxket)中。桶是一個數組的存儲位置。

數組：hashmap底層是一個數組，每個數組元素存放一個鏈表或者紅黑樹（1.8之后）

當新元素插入hashmap時，它首先根據哈希值找到數組中的某個位置（桶）。如果該位置為空，則

則直接插入；如果該位置已經存在了元素（發生碰撞），鏈表或紅黑樹解決沖突。

hash沖突——鏈表和紅黑樹：

如果發生哈希沖突，hashMap會將相同的哈希值的元素以鏈表的形式存儲在一個桶中（數組的某個位置）。

當鏈表長度過長時候，時間復雜度變為O(n).當鏈表長度超過一定的閾值（默認是8）時，鏈表會轉換為紅黑樹，從而將時間復雜度從O(n)降低到O（log n).

負載因子和擴容：

Hash Map有一個重要的參數叫負載因子，它決定了當數組中元素數量超過數組容量的多大比例時，會觸發擴容操作。默認負載因子是0.75，當HashMap的元素數量達到數組容量的75%時，HashMap會自動擴容，通常會將數組容量擴展為原來的2倍。擴容時，HashMap會重新分配一個更大的數組，并將原來的數組映射到新的數組中，這個過程叫做rehashing。過程比較耗時，因為要重新計算每個元素的哈希值，并將其放入桶中。

源碼分析：

HashMap 的默認初始化容量是 16，負載因子是 0.75。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap 的 put 方法是插入元素的核心邏輯。
hash() 方法計算鍵的哈希值。為了減少哈希沖突，它通過異或運算將高位信息與低位結合，混合高位與低位的位信息.

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}