HashMap 簡介
HashMap 是一個散列表经磅，它存儲的內(nèi)容是鍵值對(key-value)映射。
HashMap 實現(xiàn)了 Map 接口造烁，根據(jù)鍵的 HashCode 值存儲數(shù)據(jù)欺嗤，具有很快的訪問速度，最多允許一條記錄的鍵為 null综苔，不支持線程同步。
HashMap 是無序的位岔，即不會記錄插入的順序如筛。
HashMap 繼承于AbstractMap泄私，實現(xiàn)了 Map拉庶、Cloneable、java.io.Serializable 接口粟判。
HashMap 的繼承關(guān)系
首先看下集合框架圖擦剑，Map 和 Collection 屬于兩個不同的結(jié)構(gòu)妖胀，這里容易弄混淆。
HashMap 的繼承關(guān)系
HashMap 簡單使用
HashMap 的 key 與 value 類型可以相同也可以不同惠勒，可以是字符串（String）類型的 key 和 value赚抡，也可以是整型（Integer）的 key 和字符串（String）類型的 value。
HashMap<String, Integer> hhs = new HashMap<>();
hhs.put("aaa", 1);
hhs.put("bbb", 2);
hhs.put("aaa", 1);
hhs.get("aaa");
hhs.remove("aaa");
HashMap 的存儲結(jié)構(gòu)
在了解 HashMap 源碼之前纠屋，先來看下 HashMap 的存儲結(jié)構(gòu)圖涂臣。
可以看到左方為數(shù)組存儲方式，數(shù)組的方式特點是查詢快 [o(1)] 售担，但是增加和刪除比較慢 [o(n)] 赁遗。右方為鏈表的數(shù)據(jù)結(jié)構(gòu)署辉，鏈表數(shù)據(jù)結(jié)構(gòu)查詢慢 [o(n)] ，但是增加和刪除 [(o(1))] 比較快岩四。而 HashMap 采用兩種方式的結(jié)合哭尝。相當于折中方案，提高效率炫乓。
HashMap 的基本原理
1刚夺、首先判斷Key是否為 Null献丑，如果為 null末捣，直接查找 Enrty[0]，如果不是 Null创橄，先計算 Key 的 HashCode箩做，然后經(jīng)過二次 Hash。得到 Hash 值妥畏，這里的 Hash 特征值是一個 int 值邦邦。
2、根據(jù)Hash值醉蚁，找到對應的數(shù)組燃辖，所以對 Entry[] 的長度 length 求余，得到的就是 Entry 數(shù)組的 index网棍。
3黔龟、找到對應的數(shù)組，就是找到了所在的鏈表滥玷，然后按照鏈表的操作對 Value 進行插入氏身、刪除和查詢操作。
HashMap 的構(gòu)造方法
首先來看 HashMap 的構(gòu)造函數(shù)
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
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;
threshold = initialCapacity;
init();
}
構(gòu)造函數(shù)中初始化了一個 loadFactor 變量惑畴，默認值 DEFAULT_LOAD_FACTOR 為 0.75蛋欣。 threshold 變量默認值為 16（數(shù) 1 左移四位得到） 表示為 Entry[] 數(shù)組的臨界長度。 loadFactor 和 threshold 決定是否要對 Entry[] 的容量進行調(diào)整如贷。 threshold 由 HashMap 數(shù)組長度和 loadFactor 相乘計算得出陷虎，例如數(shù)組長度為 16 ，loadFactor 為 0.75杠袱，則 threshold 應該為 12 尚猿。即當 HashMap 中的容量數(shù)據(jù)大于等于 12 的時候，則應該對 table 數(shù)組進行擴容處理霞掺。 此時初始化 threshold 默認為數(shù)組長度 16（后續(xù)操作會對其更改）谊路。 init() 為空調(diào)用方法。
可以看到構(gòu)造函數(shù)只是初始化了一些變量菩彬。
接下來 HashMap 的 put 操作則是 HashMap 原理的主要研究點缠劝。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
// table 數(shù)組為空則根據(jù) threshold 初始化數(shù)組潮梯，即為容量為 16 的數(shù)組，初始化完成后同時 threshold 更改為 數(shù)組長度 length * loadFactor
inflateTable(threshold);
}
if (key == null) // key 為空
return putForNullKey(value);
int hash = hash(key); // 對key 進行 hash 處理
int i = indexFor(hash, table.length); // 通過 hash 值拿到 key 對應數(shù)組的位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 對應 Entry
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;
}
這里可以看到惨恭，table[] 數(shù)組中存入的為 Entry秉馏，默認初始容量為 16 。根據(jù)上述數(shù)據(jù)和 Entry 結(jié)構(gòu)圖知道 Entry 數(shù)據(jù)保存了數(shù)據(jù)的 key 脱羡、value萝究、hash 、i（數(shù)組下標）的值锉罐。
傳入 key 為 null 的時候帆竹，會將數(shù)據(jù) Entry 數(shù)據(jù)存入 table[0] 的位置；
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {// 替換 key 為 null 的value
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);// 插入數(shù)據(jù)
return null;
}
HashMap put方法的 hash 處理
如果key 不為空脓规，則對 key 進行 hash 操作栽连；
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
針對 key 獲取 hash 值，這里會再次進行一系列的邏輯操作侨舆， 這里注釋也對其進行了說明秒紧，對 hash 值進行二次操作是為了不同的 key 算出來的 hash 值盡可能不一樣，避免出現(xiàn) hash 沖突的情況
接下來挨下，拿到二次處理過的 hash 值生成對應 table 的下標 i熔恢；
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
length 為 table 數(shù)組的長度， h & (length-1) 實際為對數(shù)組長度取模運算（h % table.length()）,例如臭笆，現(xiàn)在數(shù)組長度為 16叙淌，算出來的 hash 值為 15，與運算之后即為 15耗啦。這里其實 length - 1 后對相應低位二進制全部改變凿菩，而再和 hash 值的低位進行 & 運算，對應拿到的就是 hash 對應低位的值帜讲。即為對 length 的取模衅谷。
而這里對二次處理的 hash 值進行取模運算，是為了數(shù)據(jù)能夠盡可能均勻分布在 table 數(shù)組中似将。提高 table 的使用效率获黔。
到這里，已經(jīng)找到可以找到 key 值對應在 table 數(shù)組的位置在验，前面的處理總結(jié)下有兩個目的：
- 二次 hash 處理玷氏，避免出現(xiàn) hash 碰撞的情況。
- 對數(shù)組長度取模處理腋舌，使數(shù)據(jù)均勻分布在數(shù)組中盏触。
拿到了數(shù)組 table 的對應下標 index，取出對應的 Entry 數(shù)據(jù)。針對 Entey 鏈表進行遍歷赞辩，如果查找到對應的 key 則進行替換雌芽，否則，調(diào)用 addEntry 插入數(shù)據(jù)辨嗽。
接下來再看看 addEntry 方法世落；
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) { // 當 size 達到 HashMap 臨界值了，調(diào)整 table 的長度
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
先看 createEntry 方法去創(chuàng)建數(shù)據(jù)糟需；
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++;
}
將對應數(shù)據(jù)放在 table 數(shù)組引用的節(jié)點處屉佳，假如原來 bucketIndex 處有相應的數(shù)據(jù)，存入的數(shù)據(jù)的下一個數(shù)據(jù)指向的即時 e （原存儲數(shù)據(jù)洲押，即在第一位插入數(shù)據(jù)）武花；
針對上述操作，下圖圖示展示：
現(xiàn)在 HashMap 的存儲的數(shù)據(jù)如上圖所示诅诱，假設(shè)現(xiàn)在有個（k9,v9）的值需要插入到 HashMap 中髓堪。
當對 k9 進行 hash 等一系列運算之后，發(fā)現(xiàn)此時數(shù)據(jù)的下標為 1娘荡，即和 （k3，v3）驶沼、（k8炮沐，v8）的處理下標一致，進行如下存儲回怜；
此時再次存儲 （k3大年，v10）的數(shù)據(jù)，k3 通過 hash 之后算出來的下標肯定也是在 table[1] 處玉雾，替換進行如下存儲翔试；
最后再插入一條（k10，v10）的數(shù)據(jù)复旬，算出下標為 5 垦缅，如下進行存儲；
HashMap 的擴容處理
當 HashMap 里面存儲的數(shù)據(jù)到了一定的臨界值的時候驹碍，應當對 table 進行擴容處理壁涎；
剛剛上述 addEntry 方法中提到擴容處理情況；
if ((size >= threshold) && (null != table[bucketIndex])) { // 當 size 達到 HashMap 臨界值了志秃，調(diào)整 table 的長度
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
可以看到當 size 大于等于 threshold 臨界值的時候怔球，且當前的數(shù)據(jù)不為空的情況下，我們就要進行 table 擴容了浮还。threshold 我們知道由 loadFactor（加載因子）和 table 的容量共同決定竟坛，loadFactor 為大于 0 小于 1 的值，即此時已存數(shù)據(jù) size 到達 table 容量的 loadFactor 倍數(shù)的時候，就必須進行擴容了担汤。那么如何擴容的呢?
void resize(int newCapacity) {
Entry[] oldTable = table;// 舊的table
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];// 新table 容量翻倍
transfer(newTable, initHashSeedAsNeeded(newCapacity));// 數(shù)據(jù)的轉(zhuǎn)移
table = newTable;// newtable 賦值給 table
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); // 重新計算臨界值
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
看到擴容處理不僅僅把 table 容量增長兩倍就完事了又官，原 table 中的數(shù)據(jù)該怎么存呢？
如果不進行更換的話漫试，假如對上圖所示數(shù)據(jù)進行（k9,v9）的數(shù)據(jù)查找六敬，因為 table 擴容后，二次 hash 結(jié)果和 table.length 取模后獲取的下標數(shù)據(jù)大概率是變化了驾荣，那樣就找不到數(shù)據(jù)了外构。
于是 transfer 方法拿到舊的 table 數(shù)據(jù)，然后根據(jù) newTable 的容量對原數(shù)據(jù)所有的 key 重新計算對應下標播掷，存入到新的 table 中审编，這樣保證了后續(xù)查找的正確性。
到這里歧匈，HashMap put 相關(guān)的分析已經(jīng)完成垒酬，其中涉及到對數(shù)組和對應鏈表數(shù)據(jù)的插入。以及相應的數(shù)組進行擴容方案件炉。
HashMap 的 其他方法
分析完成了 put 方法之后勘究，再看其他方法就會很容易。
get 方法：
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);// hash 處理
for (Entry<K,V> e = table[indexFor(hash, table.length)];// 找到數(shù)組對應的下標
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
get 方法需要傳入相應的 key 斟冕，如果為空 key 口糕，肯定就是去找 table 數(shù)組第 0 位的數(shù)據(jù)。否則磕蛇，key 的 hash 值獲取以及二次處理景描，找到對應的數(shù)組下標，比對對應 Entry 一致就返回秀撇，否則就返回 null超棺。
remove 方法：
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e) // 刪除的是鏈表第一個數(shù)據(jù)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
remove 方法相對 get 方法，在拿到相應數(shù)據(jù)刪除之后呵燕，同時要將鏈表對應的數(shù)據(jù)重新進行指向棠绘。即將當前要刪除數(shù)據(jù)的前一項指向后一項。
HashMap 的遍歷方法
// 方式1
for(Map.Entry<String, Integer> entry : hhs.entrySet()){
System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
}
//方式2
Iterator<Map.Entry<String, Integer>> entries = hhs.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<String, Integer> entry = entries.next();
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}
由上述 HashMap 的操作可以看到 HashMap 中存儲數(shù)據(jù)是無序的虏等，所以遍歷得到的數(shù)據(jù)也將會是無序的弄唧；通常 HashMap 使用到的兩種遍歷方式（其實兩種方法最終都會走向方式 2 ），entrySet 和 entrySet 的迭代器 iterator霍衫；
第一種遍歷方式候引；
private transient Set<Map.Entry<K,V>> entrySet = null;
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
這里 entrySet 存儲 Entry 的集合，在之前 put 方法中敦跌，并沒有發(fā)現(xiàn)往其中存入數(shù)據(jù)澄干。所以逛揩，這里去實例化 EntrySet 方法中查看是否有相關(guān)獲取數(shù)據(jù)的方法？
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}
EntrySet 的實例化又去創(chuàng)建了一個 EntryIterator麸俘；
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
EntryIterator 實則就是一個 HashIterator辩稽，到這里可以發(fā)現(xiàn)，似乎走到了第二種方式了从媚，繼續(xù)看 HashIterator逞泄；
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null) // 自增數(shù)組下標找到第一個不為null結(jié)束循環(huán) 即為HashMap要遍歷的第一個值
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {// index 處鏈表數(shù)據(jù)沒有下一位了
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
HashIterator 實現(xiàn)了 Iterator，而增強 for 循環(huán)使用的就是 Iterator 拜效，所以這里 Entry 覆蓋了 Iterator 方法進行遍歷數(shù)據(jù)喷众。
HashIterator 構(gòu)造方法回去遍歷數(shù)組找到第一個不為 null 的數(shù)據(jù)結(jié)束循環(huán)，此數(shù)據(jù)作為遍歷 HashMap 的起始數(shù)據(jù)紧憾；
這里主要看下 nextEntry 方法到千，因為 EntryIterator 的 next 方法其實調(diào)用的就是 nextEntry 方法；
可以看到 nextEntry 會將數(shù)據(jù)按照 table 的下標順序進行查找赴穗，如果某個下標對應的鏈表數(shù)據(jù)查找完畢憔四，繼續(xù)向下遍歷 table 數(shù)組。直到全部查找完畢般眉。
以上圖 HashMap 數(shù)據(jù)來看了赵，最終遍歷出數(shù)據(jù)結(jié)果應該是(null,vaule)、(k9,v9)煤篙、(k3,v8)斟览、(k8,v8)、(k10,v10),當然辑奈，存儲順序大概率不是按照這個順序來的。所以我們說 HashMap 是無序的已烤。
最后鸠窗，可以看到 HashMap 也不支持多線程的操作 ，因為對 HashMap 的操作每次都會改變 modCount 值胯究，而遍歷的過程會比對相關(guān)值稍计，所以遍歷過程也不可對 HashMap 進行增刪操作。
