HashMap 是用于映射(鍵值對)處理的資料類型，基于哈希表的 Map 接口的非同步實作，允許插入最多一條
key
為
null
的記錄，允許插入多條
value
為
null
的記錄。此外，HashMap 不保證元素順序，根據需要該容器可能會對元素重新哈希，元素的順序也會被重新打散，是以在不同時間段疊代同一個 HashMap 的順序可能會不同。HashMap 非線程安全，即任一時刻有多個線程同時寫 HashMap 的話可能會導緻資料的不一緻
HashMap 實際上是數組+連結清單+紅黑樹的結合體，其底層包含一個數組，數組中的每一項元素的可能值有四種：null、單獨一個結點、連結清單、紅黑樹（JDK1.8 開始 HashMap 通過使用紅黑樹來提高元素查找效率）。當往 HashMap 中 put 元素的時候，需要先根據 key 的哈希值得到該元素在數組中的位置（即下标），如果該位置上已經存放有其他元素了，那麼在這個位置上的元素将以連結清單或者紅黑樹的形式來存放，如果該位置上沒有元素，就直接向該位置存放元素
HashMap 要求映射中的 key 是不可變對象，即要求該對象在建立後它的哈希值不會被改變，否則 Map 對象很可能就定位不到映射的位置了
類聲明
public class HashMap<K, V> extends AbstractMap<K, V>
implements Map<K, V>, Cloneable, Serializable
常量
HashMap 中聲明的常量有以下幾個，其中需要特别關注的是裝載因子 DEFAULT_LOAD_FACTOR 和 TREEIFY_THRESHOLD
裝載因子用于規定數組在自動擴容之前可以資料占有其容量的最高比例，即當資料量占有數組的容量達到這個比例後，數組将自動擴容。裝載因子衡量的是一個散清單的空間的使用程度，裝載因子越大表示散清單的裝填程度越高，反之愈小。是以如果裝載因子越大，則對空間的利用程度更高，相對應的是查找效率的降低。如果裝載因子太小，那麼數組的資料将過于稀疏，對空間的使用率低，官方預設的裝載因子為0.75，是平衡空間使用率和運作效率兩者之後的結果。如果在實際情況中，記憶體空間較多而對時間效率要求很高，可以選擇降低裝載因子的值；如果記憶體空間緊張而對時間效率要求不高，則可以選擇提高裝載因子的值
此外，即使裝載因子和雜湊演算法設計得再合理，也不免會出現由于哈希沖突導緻連結清單長度過長的情況，這将嚴重影響 HashMap 的性能。為了優化性能，從 JDK1.8 開始引入了紅黑樹，當連結清單長度超出 TREEIFY_THRESHOLD 規定的值時，連結清單就會被轉換為紅黑樹，利用紅黑樹快速增删改查的特點以提高 HashMap 的性能
//序列化ID
private static final long serialVersionUID = 362498820763181265L;
//哈希桶數組的預設容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//網上很多文章都說這個值是哈希桶數組能夠達到的最大容量，其實這樣說并不準确
//從 resize() 方法的擴容機制可以看出來，HashMap 每次擴容都是将數組的現有容量增大一倍
//如果現有容量已大于或等于 MAXIMUM_CAPACITY ，則不允許再次擴容
//否則即使此次擴容會導緻容量超出 MAXIMUM_CAPACITY ，那也是允許的
static final int MAXIMUM_CAPACITY = 1 << 30;
//裝載因子的預設值
//裝載因子用于規定數組在自動擴容之前可以資料占有其容量的最高比例，即當資料量占有數組的容量達到這個比例後，數組将自動擴容
//裝載因子衡量的是一個散清單的空間的使用程度，負載因子越大表示散清單的裝填程度越高，反之愈小
//對于使用連結清單的散清單來說，查找一個元素的平均時間是O(1+a)，是以如果負載因子越大，則對空間的利用程度更高，相對應的是查找效率的降低
//如果負載因子太小，那麼數組的資料将過于稀疏，對空間的使用率低
//官方預設的負載因子為0.75，是平衡空間使用率和運作效率兩者之後的結果
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//為了提高效率，當連結清單的長度超出這個值時，就将連結清單轉換為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
成員變量
//哈希桶數組，在第一次使用時才初始化
//容量值應是2的整數倍
transient Node<K, V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K, V>> entrySet;
//Map的大小
transient int size;
//每當Map的結構發生變化時，此參數就會遞增
//當在對Map進行疊代操作時，疊代器會檢查此參數值
//如果檢查到此參數的值發生變化，就說明在疊代的過程中Map的結構發生了變化，是以會直接抛出異常
transient int modCount;
//數組的擴容臨界點，當數組的資料量達到這個值時就會進行擴容操作
//計算方法：目前容量 x 裝載因子
int threshold;
//使用的裝載因子值
final float loadFactor;
構造函數
//設定Map的初始化大小和裝載因子
public HashMap(int initialCapacity, float loadFactor) {
//檢查參數合法性
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//設定Map的初始化大小
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//都使用預設值
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//傳入初始資料
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
結點類
//結點
static class Node<K, V> implements Map.Entry<K, V> {
//目前結點的 key 的哈希值
final int hash;
//鍵
final K key;
//值
V value;
//下一個結點
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
···
}
雜湊演算法
在查詢、添加和移除鍵值對時，定位到哈希桶數組的指定位置都是很關鍵的第一步，隻有 HashMap 中的元素盡量分布均勻，才能在定位鍵值對時快速地查找到相應位置，避免頻繁地去周遊連結清單或者紅黑樹，這就需要依靠于一個比較好的雜湊演算法了
以下是 HashMap 中計算 key 值的哈希值以及根據哈希值擷取其在哈希桶數組中位置的算法
//計算哈希值
static final int hash(Object key) {
int h;
//高位參與運算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//根據 key 值擷取 Value
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) {
···
//隻有當 table 不為空且 hash 對應的位置不為 null 才有可擷取的元素值
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
···
}
return null;
}
确定鍵值對在哈希桶數組的位置的步驟分為三步：計算 key 的 hashCode（h = key.hashCode()）、高位運算（h >>> 16）、取模運算（(n - 1) & hash）
我也不懂這麼取值的優點在于哪裡，就不多說了
插入資料
在上邊說過，HashMap 是數組+連結清單+紅黑樹的結合，數組包含的元素的可能值分為四種類型：null、單個結點、連結清單、紅黑樹。在插入結點時（每一個待存資料都會被包裝為結點對象），會根據待插入 Key 的哈希值來決定結點在數組中的位置，如果計算得出的位置此時包含的元素為 null ，則直接将結點存入該位置，如果不為 null ，則說明發生了哈希碰撞，此時就需要将結點插入到連結清單或者是紅黑樹中。當雜湊演算法的計算結果越分散均勻，哈希碰撞的機率就越小，map 的存取效率就會越高
如果待插入結點的 key 與連結清單或紅黑樹中某個已有結點的 key 相等（hash 值相等且兩者 equals 成立），則新添加的結點将覆寫原有資料
插入資料對應的是
put(K key, V value)
方法
//插入資料
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);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent 為 true 表示不會覆寫有相同 key 的非 null value，否則會覆寫原有值
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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 還未初始化，則調用 resize 方法進行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//判斷要存入的 key 是否存在哈希沖突，等于 null 說明不存在沖突
if ((p = tab[i = (n - 1) & hash]) == null)
//直接在索引 i 處建構包含待存入元素的結點
tab[i] = newNode(hash, key, value, null);
else { //走入本分支，說明待存入的 key 存在哈希沖突
Node<K, V> e;
K k;
//p 值已在上一個 if 語句中指派了，此處就直接來判斷 key 值之間的相等性
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
//指向沖突的頭結點
e = p;
//如果頭結點的 key 與待插入的 key 不相等，且頭結點是 TreeNode 類型，說明該 hash 值是采用紅黑樹來處理沖突
else if (p instanceof TreeNode)
//如果紅黑數中包含有相同 key 的結點，則傳回該結點，否則傳回 null
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else { //采用連結清單來處理 hash 值沖突
for (int binCount = 0; ; ++binCount) {
//當周遊到連結清單尾部時
if ((e = p.next) == null) {
//建構一個新的結點添加到連結清單尾部
p.next = newNode(hash, key, value, null);
//如果連結清單的長度已達到允許的最大長度 TREEIFY_THRESHOLD - 1 時，就将連結清單轉換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//當 e 指向的結點的 key 值與待插入的 key 相等時則跳出循環
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果 e != null，說明原先已存在相同 key 的鍵
if (e != null) {
V oldValue = e.value;
//隻有當 onlyIfAbsent 為 true 且 oldValue 不為 null 時才不會覆寫原有值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//用于 LinkedHashMap ，在 HashMap 中是空實作
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//當元素數量達到擴容臨界點時，需要進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
讀取資料
讀取資料對應的是
get(Object key)
方法
//根據 key 值擷取 Value
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 不為空且 hash 對應的位置不為 null 才有可擷取的元素值
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//如果頭結點的 hash 值與 Key 與待插入資料相等的話，則說明找到了對應值
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
// != null 說明存在哈希沖突
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;
}
移除結點
從 Map 中移除鍵值對的操作，在底層資料結構的展現就是移除對某個結點對象的引用，可能是從數組中、也可能是連結清單或者紅黑樹
public V remove(Object key) {
Node<K, V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods
*
* @param hash key 的哈希值
* @param key the key
* @param value key對應的值，隻有當 matchValue 為 true 時才需要使用到，否則忽略該值
* @param matchValue 如果為 true ，則隻有當 Map 中存在某個鍵 equals key 且 value 相等時才會移除該元素，否則隻要 key 的 hash 值相等就直接移除該元素
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K, V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K, V>[] tab;
Node<K, V> p;
int n, index;
//隻有當 table 不為空且 hash 對應的索引位置存在值時才有可移除的對象
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node<K, V> node = null, e;
K k;
V v;
//如果與頭結點的 key 相等
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) { //存在哈希沖突
//用紅黑樹來處理哈希沖突
if (p instanceof TreeNode)
//查找對應結點
node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
else { //用連結清單來處理哈希沖突
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//node != null 說明存在相應結點
//如果 matchValue 為 false ，則通過之前的判斷可知查找到的結點的 key 與 參數 key 的哈希值一定相等，此處就可以直接移除結點 node
//如果 matchValue 為 true ，則當 value 相等時才需要移除該結點
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
if (node instanceof TreeNode) //對應紅黑樹
((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
else if (node == p) //對應 key 與頭結點相等的情況，此時直接将指針移向下一位即可
tab[index] = node.next;
else //對應的是連結清單的情況
p.next = node.next;
++modCount;
--size;
//用于 LinkedHashMap ，在 HashMap 中是空實作
afterNodeRemoval(node);
return node;
}
}
return null;
}
擴容
如果哈希桶數組很大，即使用的是較差的雜湊演算法元素也會比較分散，如果哈希桶數組很小，即使用的是好的雜湊演算法也會出現較多哈希碰撞的情況，是以就需要在空間成本和時間成本之間權衡，除了設計較好的雜湊演算法以減少哈希沖突外，也需要在合适的的時機對哈希桶數組進行必要的擴容
當 HashMap 中的元素越來越多時，因為數組的長度是固定的，是以哈希沖突的幾率也就越來越高，為了提高效率，此時就需要對 HashMap 中的數組進行擴容，而擴容操作最消耗性能的地方就在于：原數組中的資料必須重新計算其在新數組中的位置并存放到新數組中
那麼 HashMap 擴容操作的觸發時機是什麼時候呢？當 HashMap 中的元素個數超出 threshold 時（數組容量 與 loadFactor 的乘積），就會進行數組擴容。預設情況下，數組的預設值為 16，loadFactor 的預設值為 0.75，這是平衡空間使用率和運作效率兩者之後的結果。也就是說，假設數組目前大小為16，loadFactor 值為0.75，那麼當 HashMap 中的元素個數達到12個時，就會自動觸發擴容操作，把數組的大小擴充到 2 * 16 = 32，即擴大一倍，然後重新計算每個元素在新數組中的位置，而這是一個非常消耗性能的操作，是以如果已經預知到待存入 HashMap 的資料量，那麼在初始化 HashMap 時直接指定初始化大小會是一種更為高效的做法
擴容操作對應的是
resize()
方法
//用于初始化 table 或者對之進行擴容
//并傳回新的數組
final Node<K, V>[] resize() {
//擴容前的數組
Node<K, V>[] oldTab = table;
//擴容前數組的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//擴容前Map的擴容臨界值
int oldThr = threshold;
//擴容後數組的容量和擴容臨界值
int newCap, newThr = 0;
if (oldCap > 0) {
//oldCap > 0 對應的是 table 已被初始化的情況，此時是來判斷是否需要進行擴容
//如果數組已達到最大容量，則不再進行擴容，并将擴容臨界點 threshold 提升到 Integer.MAX_VALUE，結束
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
//如果将數組的現有容量提升到現在的兩倍依然小于允許的最大容量，而且現有容量大于或等于預設容量
//則将數組的容量和擴容臨界值均提升為原先的兩倍
newThr = oldThr << 1;
}
//此處應該還有一種情況
//即将數組的現有容量提升到現在的兩倍後大于 MAXIMUM_CAPACITY 的情況
//此時 newThr 等于 0，newCap 等于 oldCap 的兩倍值
//此處并沒有對 newCap 的數值進行還原，說明 HashMap 是允許擴容後容量超出 MAXIMUM_CAPACITY 的
//隻是在現有容量超出 MAXIMUM_CAPACITY 後，不允許再次進行擴容
} else if (oldThr > 0) {
//oldCap <= 0 && oldThr > 0 對應的是 table 還未被初始化，且在調用構造函數時有傳入初始化大小 initialCapacity 或者包含原始資料的 Map 的情況
//這導緻了 threshold 被指派 (tableSizeFor 方法)
//此時就直接将Map的容量提升為 threshold，在後邊重新計算新的擴容臨界值
newCap = oldThr;
} else {
//oldCap <= 0 && oldThr <= 0 對應的是 table 還未被初始化，且調用的是無參數的構造函數
//此時就将 table 的容量擴充到預設值大小，并使用預設的裝載因子值來計算擴容臨界值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
//計算擴容後新的擴容臨界值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
table = newTab;
//如果舊數組中存在值，則需要将其中的資料複制到新數組中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {
//将舊數組中的引用切換，幫助GC回收
oldTab[j] = null;
//e.next == null 說明元素 e 沒有産生 hash 沖突，是以可以直接轉移該元素
if (e.next == null)
//計算元素 e 在新數組中的位置
newTab[e.hash & (newCap - 1)] = e;
//e instanceof TreeNode 說明元素 e 有産生 hash 沖突，且使用紅黑樹管理沖突的元素
else if (e instanceof TreeNode)
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
//走入如下分支，說明元素 e 有産生 hash 沖突，且使用連結清單結構來管理沖突的元素
else {
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
效率測試
這裡來測試下不同的初始化大小以及 key 值的 HashCode 值的分布情況的不同對 HashMap 效率的影響
首先來定義作為 Key 的類，
hashCode()
方法直接傳回其包含的屬性 value
public class Key {
private int value;
public Key(int value) {
this.value = value;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Key key = (Key) o;
return value == key.value;
}
@Override
public int hashCode() {
return value;
}
}
初始化大小從 100 到 100000 之間以 10 倍的倍數遞增，向 HashMap 存入同等資料量的資料，觀察不同 HashMap 存入資料消耗的總時間
public class KeyMain {
private static final int MAX_KEY = 20000;
private static final Key[] KEYS = new Key[MAX_KEY];
static {
for (int i = 0; i < MAX_KEY; i++) {
KEYS[i] = new Key(i);
}
}
private static void test(int size) {
long startTime = System.currentTimeMillis();
Map<Key, Integer> map = new HashMap<>(size);
for (int i = 0; i < MAX_KEY; i++) {
map.put(KEYS[i], i);
}
long endTime = System.currentTimeMillis();
System.out.println("初始化大小是：" + size + " , 所用時間：" + (endTime - startTime) + "毫秒");
}
public static void main(String[] args) {
for (int i = 20; i <= MAX_KEY; i *= 10) {
test(i);
}
}
}
在上述使用的例子中，各個 Key 對象之間的哈希碼值各不相同，是以鍵值對在哈希桶數組中的分布可以說是很均勻的了，此時主要影響性能的就是擴容機制了，由上圖可以看出各個初始化大小對 HashMap 的性能影響還是很大的
接下來再看看各個 Key 對象之間頻繁發生哈希沖突時 HashMap 的性能
令 Key 類的
hashCode()
方法固定傳回 100，則每個鍵值對在存入 HashMap 時，一定會發生哈希沖突
@Override
public int hashCode() {
return 100;
}
可以看到此時存入同等資料量的資料所用時間呈幾何數增長了，此時主要影響性能的點就在于對哈希沖突的處理了