來自我的博客
正文之前
雖然平時(shí)也都有用到 HashMap（JDK 1.8），但一直都是處于只會(huì)用的狀態(tài)，一直不知道操作是如何實(shí)現(xiàn)的，以及擴(kuò)容的方式等等，剛好在周末的空閑時(shí)間，來學(xué)習(xí)一下它的源碼，一篇肯定說不完，這一篇就先做個(gè)介紹吧：
- 基本概念
- 容量
- 基本結(jié)構(gòu)
- 成員變量
- 構(gòu)造器
- 插入和查找
- 總結(jié)
正文
1. 基本概念
在 HashMap 一開始的一段注釋中，已經(jīng)對(duì)這個(gè)類解釋的很清楚了：
- 提供所有的 map 操作
- 可以有空的 key-value 對(duì)
- 與 Hashtable 大致相同（除了非線程安全和允許空值）
- 元素順序不保證
- 如果元素散列得當(dāng)，get 和 put 操作的時(shí)間是固定的
- 性能受初始容量和負(fù)載系數(shù)的影響
- 當(dāng)前容量 * 負(fù)載系數(shù) < 元素?cái)?shù)量時(shí)，就擴(kuò)容
- 負(fù)載系數(shù)默認(rèn)為 0.75，這是時(shí)間消耗和空間消耗的一個(gè)折衷點(diǎn)
- 非線程安全，如有需要，用
Collections.synchronizedMap包裝
2. 容量
關(guān)于容量，源碼中的注釋說到了一定要為 2 的冪次，這樣有利于解決哈希碰撞（實(shí)現(xiàn)均勻分布），在文末會(huì)有關(guān)于為什么的鏈接：
//默認(rèn)的初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)負(fù)載系數(shù)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
在鏈表和紅黑樹之間轉(zhuǎn)化時(shí)，有這么兩個(gè)參數(shù)：
//超過 8 時(shí)進(jìn)化為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
//小于 6 時(shí)退化為鏈表
static final int UNTREEIFY_THRESHOLD = 6;
3. 基本結(jié)構(gòu)
在普通桶中使用的單鏈表的基本結(jié)構(gòu)，存儲(chǔ)哈希值，鍵值對(duì)以及下一個(gè)節(jié)點(diǎn)的引用：
static class Node<K,V> implements Map.Entry<K,V> {
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//節(jié)點(diǎn)的哈希值為 key 的哈希值異或 value 的哈希值
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
4. 成員變量
HashMap 中有幾個(gè)成員變量，在下文中會(huì)用到，這里就不解釋，下面的方法中會(huì)有說明：
//table 的大小是要為 2 的冪次，在初次使用時(shí)才初始化（延遲加載）
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
5. 構(gòu)造器
//自定義容量以及負(fù)載系數(shù)的初始化
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);
}
//自定義容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//默認(rèn)容量 16 以及負(fù)載系數(shù) 0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//復(fù)制一個(gè) Map
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
tableSizeFor() 這個(gè)方法單獨(dú)拎出來說一下：
前面說到 table 的值要是 2 的冪次，如果輸入的數(shù)字不符合要求呢？那就找到比這個(gè)數(shù)大的最小的2次冪，接下來給出源碼，并用數(shù)字 9 舉個(gè)例子：
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
6. 插入和查找
插入操作，代碼中有分為單鏈表和紅黑樹兩種情況：
public V put(K key, V value) {
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;
//將節(jié)點(diǎn)散列至相應(yīng)位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
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);
//轉(zhuǎn)化為紅黑樹
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;
}
}
//已經(jīng)存在對(duì)應(yīng)的值，就更新
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
查找操作：
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//總是先檢查根節(jié)點(diǎn)
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;
}
7. 總結(jié)
其實(shí)這一篇只能算是科普文，因?yàn)樽钪攸c(diǎn)的擴(kuò)容、紅黑樹的轉(zhuǎn)化等操作都還沒說，接下來的文章將會(huì)全面說明這些重點(diǎn)內(nèi)容
參考資料：
容量為什么是 2 的冪次：https://blog.csdn.net/qq_36523667/article/details/79657400
關(guān)于負(fù)載系數(shù)：http://www.itdecent.cn/p/64f6de3ffcc1
