【Java基礎】HashMap工作原理。本站提示廣大學習愛好者：（【Java基礎】HashMap工作原理）文章只能為提供參考，不一定能成為您想要的結果。以下是【Java基礎】HashMap工作原理正文
HashMap
Hash table based implementation of the Map interface. This
implementation provides all of the optional map operations, and permits
null values and the null key. (The HashMap class is roughly equivalent
to Hashtable, except that it is unsynchronized and permits nulls.)
This class makes no guarantees as to the order of the map; in particular,
it does not guarantee that the order will remain constant over time.
官方文檔描述信息：基於Map接口實現，鍵值都允許null，非線程同步的，不按插入順序排，也不保證不隨時間變化。
HashMap底層的數據結構實現是數組加鏈表，數組的每一項都是鏈。
構造函數
HashMap提供了四個構造函數：
HashMap(int initialCapacity, float loadFactor)：構造一個帶有指定容量和加載因子的空的HashMap。
HashMap(int initialCapacity)：構造一個指定容量和默認加載因子為0.75的空的HashMap
HashMap()：構造一個默認容量為16和默認加載因子為0.75的空的HashMap。
HashMap(Map<? extends K, ? extends V> m)：構造一個匹配所有map中所有的元素並且加載因子是0.75的空HashMap。
初始容量和加載因子是影響HashMap性能的重要參數。
初始容量：創建哈希表時的容量(bucket)
加載因子：哈希表在其容量自動增加之前可以達到多滿的一個尺度。
put()的實現
put()大致的思路：
public V put(K key, V value) {
// 對key的hashCode()做hash()
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table為空則創建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 計算index並做特殊處理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果hash和key都相同
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果該鏈為樹
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果該鏈為鏈表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果鏈表的長度超過了這個阈值，
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果節點存在的話，就替換新值返回舊值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果大小超過了 加載因子*當前容量，就進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get()的實現
get()的大致思路：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// table不為空才進行以下操作，table為null的話直接返回null
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 直接命中
if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 在樹中命中
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在鏈表中命中
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
static final int hash(Object key) {
int h;
// 使用key的hashCode進行hash計算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這個函數的作用是：高16bit不變，低16bit和高16bit做了一個異或。 在計算下標的時候是這樣實現的：
tab[i = (n - 1) & hash] // 使用&操作，而非%操作
resize()的實現
當put時，當超過限制的時候會resize，然而又因為我們使用的2次冪的擴展(指長度擴展為原來的2倍)，所以，元素的位置要麼是在原位置，要麼是在原位置再移動2次冪的位置。
面試題
HashMap有什麼特點？
基於Map接口實現，存儲鍵值對時，他可以接受null的鍵值，是非同步的，HashMap存儲著Entry對象
你知道HashMap的工作原理麼？
通過hash的方法，通過put和get存儲獲取對象。存儲時，我們將k/v傳給put方法時，通過獲取k的hashCode並計算hash值從而獲取到bucket的位置，進一步存儲，HashMap會根據當前bucket的占用情況自動擴容(當超出 加載因子 * 當前容量 時擴容到當前容量的兩倍)。獲取對象時，我們將k傳給get方法，通過獲取k的hashCode並計算hash值獲取到在bucket中的位置，並進一步調用獲取equals()獲取鍵值對。如果發生碰撞時，HashMap通過鏈表將產生碰撞沖突的元素組織起來，在Java8中，當一個bucket的存儲容量超過某個限制(默認是8)時就會用紅黑樹來代替鏈表，從而提高速度。
你知道get和put的原理麼？equals()和hashCode都有什麼用？
通過對key的hashCode()進行hashing，通過(n - 1 & hash)計算下標，當發生碰撞時，則利用key.equals()方法去鏈表或者樹中查找對應的鍵值對。
你知道hash的實現麼？為什麼要這樣的實現？
(h = key.hashCode()) ^ (h >>> 16)
這麼做可以在bucket的n比較小的時候，也能保證考慮到高地bit都參與到hash的計算中，同時不會有太大的開銷
如果HashMap的大小超過了負載因子(load factor)定義的容量，怎麼辦？
當超過了負載因子，會重新resize一個原來長度兩倍的HashMap，並重新調用hash方法
參考文章：
