HashMap是最常用的數(shù)據(jù)結(jié)構(gòu)之一杜跷，是JDK中util包下的一個(gè)集合類氏仗，基于Map接口實(shí)現(xiàn)、允許null鍵/值我碟、非同步放案、不保證有序(比如插入的順序)、也不保證順序不隨時(shí)間變化矫俺。
這是HashMap的數(shù)據(jù)結(jié)構(gòu)吱殉，基于JDK8的，JDK8之前是沒(méi)有紅黑樹的厘托。在早期的HashMap中友雳，最常用的兩種數(shù)據(jù)結(jié)構(gòu)一種是數(shù)組，一種是鏈表結(jié)構(gòu)铅匹。HashMap為了解決hash算法帶來(lái)的hash沖突押赊，所以采用了數(shù)組和鏈表的結(jié)合模式，它的底層是一個(gè)數(shù)組包斑，然后根據(jù)求得的hash值在數(shù)組相應(yīng)位置將相應(yīng)的值插入鏈表中流礁。但是這樣的問(wèn)題就是，數(shù)組的某一個(gè)桶的元素很多罗丰，那么鏈表就會(huì)很長(zhǎng)神帅，從而使得訪問(wèn)效率比較低。因此后來(lái)HashMap引入了紅黑樹的概念萌抵。就是當(dāng)一個(gè)桶的鏈表上的元素個(gè)數(shù)達(dá)到一定數(shù)目之后枕稀，便會(huì)將鏈表結(jié)構(gòu)轉(zhuǎn)化為紅黑樹結(jié)構(gòu)。這樣使得訪問(wèn)效率得到了提高，尤其是數(shù)量很大的時(shí)候萎坷。以下便來(lái)介紹一下引進(jìn)紅黑樹結(jié)構(gòu)的HashMap凹联。
接下來(lái)我們從源碼一步步看看HashMap的實(shí)現(xiàn)過(guò)程和對(duì)外提供的方法
首先來(lái)看看它的繼承和實(shí)現(xiàn)
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
繼承于抽象的AbstractMap，實(shí)現(xiàn)了Map哆档，Cloneable蔽挠，Serializable這三個(gè)接口。
在結(jié)尾或者下一篇在聊Map瓜浸，Cloneable澳淑，Serializable這三個(gè)接口。
跟著源碼一步一步往下走：
/**
* 默認(rèn)初始容量為16 必須是2的冪次方也就是2的倍數(shù)
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量
* 必須是2的倍數(shù)
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 在構(gòu)造函數(shù)中未指定時(shí)使用的 負(fù)載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 鏈表結(jié)構(gòu)轉(zhuǎn)化為紅黑樹的閾值插佛，大于8時(shí)鏈表結(jié)構(gòu)轉(zhuǎn)化為紅黑樹
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 紅黑樹轉(zhuǎn)化為鏈表結(jié)構(gòu)的閾值杠巡，桶(bucket)內(nèi)元素個(gè)數(shù)小于6時(shí)轉(zhuǎn)化為鏈表結(jié)構(gòu)
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 樹形化最小hash表 元素個(gè)數(shù)，如果桶內(nèi)元素已經(jīng)達(dá)到轉(zhuǎn)化紅黑樹閾值雇寇，但是表元素總數(shù)未達(dá)到閾值氢拥，則值進(jìn)行擴(kuò)容resize()，不進(jìn)行樹形化
*/
static final int MIN_TREEIFY_CAPACITY = 64;
ps: 當(dāng)hash表元素小于MIN_TREEIFY_CAPACITY時(shí)锨侯，但是桶內(nèi)元素個(gè)數(shù)大于TREEIFY_THRESHOLD閾值時(shí)嫩海，進(jìn)行擴(kuò)容resize()。而當(dāng)hash中元素個(gè)數(shù)大于MIN_TREEIFY_CAPACITY時(shí)囚痴，則進(jìn)行樹形化叁怪。
接下來(lái)是一個(gè)節(jié)點(diǎn)的源碼，并沒(méi)有開始構(gòu)造函數(shù)的介紹深滚，我們就跟著源碼來(lái)吧奕谭，一步一步往下看
/**
* 該類只實(shí)現(xiàn)了 Map.Entry 接口，
* 所以該類只需要實(shí)現(xiàn)getKey痴荐、getValue血柳、setValue三個(gè)方法即可
* 除此之外以什么樣的方式來(lái)組織數(shù)據(jù)，就和接口無(wú)關(guān)了
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // hash值蹬昌，不可變
final K key; // 鍵混驰，不可變
V value; // 值
Node<K,V> next; // 下一個(gè)節(jié)點(diǎn)，表明鍵值映射記錄的存儲(chǔ)方式是鏈表
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// 實(shí)現(xiàn)接口定義的方法皂贩，且該方法不可被重寫
public final K getKey() { return key; }
//實(shí)現(xiàn)接口定義的方法栖榨，且該方法不能被重寫
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
// 重寫父類Object的hashCode方法，且該方法不可被自己的子類再重寫
// 返回：key的hashCode值和value的hashCode值進(jìn)行異或運(yùn)算結(jié)果
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//實(shí)現(xiàn)接口定義的方法明刷，且該方法不可被重寫
// 設(shè)值婴栽，返回舊值
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 重寫父類Object的equals方法，且該方法不可被自己的子類再重寫
// 判斷相等的依據(jù)是辈末，只要是Map.Entry的一個(gè)實(shí)例愚争，并且鍵鍵映皆、值值都相等就返回True
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;
}
}
下面是hash的實(shí)現(xiàn)
// hash實(shí)現(xiàn)，沒(méi)有直接使用key的hashcode()轰枝，而是使key的hashcode()高16位不變捅彻，低16位與高16位異或作為最終hash值。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Java8中hash計(jì)算是通過(guò)key的hashCode()的高16位異或低16位實(shí)現(xiàn)的鞍陨，既保證高低bit都能參與到hash的計(jì)算中步淹，又不會(huì)有太大的開銷。
這是源碼中的注釋：
Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.
大概的意思是：
如果直接使用key的hashcode()作為hash很容易發(fā)生碰撞诚撵。比如缭裆，在n - 1為15(0x1111)時(shí)，散列值真正生效的只是低4位寿烟。當(dāng)新增的鍵的hashcode()是2澈驼，18，34這樣恰好以16的倍數(shù)為差的等差數(shù)列筛武，就產(chǎn)生了大量碰撞缝其。
因此，設(shè)計(jì)者綜合考慮了速度畅铭、作用氏淑、質(zhì)量勃蜘，把高16bit和低16bit進(jìn)行了異或硕噩。因?yàn)楝F(xiàn)在大多數(shù)的hashCode的分布已經(jīng)很不錯(cuò)了，就算是發(fā)生了較多碰撞也用O(logn)的紅黑樹去優(yōu)化了缭贡。僅僅異或一下炉擅，既減少了系統(tǒng)的開銷，也不會(huì)造成因?yàn)楦呶粵](méi)有參與下標(biāo)的計(jì)算(table長(zhǎng)度比較小時(shí))阳惹，從而引起的碰撞谍失。
再來(lái)介紹hashMap中一個(gè)精巧的算法：
/**
* Returns a power of two size for the given target capacity.
* 精巧算法 返回最近的不小于輸入?yún)?shù)的2的整數(shù)次冪。比如10莹汤，則返回16快鱼。
*/
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;
}
**原理如下： **
先說(shuō)5個(gè)移位操作，會(huì)使cap的二進(jìn)制從最高位的1到末尾全部置為1纲岭。
假設(shè)cap的二進(jìn)制為01xx…xx抹竹。
對(duì)cap右移1位：01xx…xx，位或：011xx…xx止潮，使得與最高位的1緊鄰的右邊一位為1窃判，
對(duì)cap右移2位：00011x..xx，位或：01111x..xx喇闸，使得從最高位的1開始的四位也為1袄琳，
以此類推询件，int為32位，所以在右移16位后異或最多得到32個(gè)連續(xù)的1唆樊，保證從最高位的1到末尾全部為1宛琅。
最后讓結(jié)果+1，就得到了最近的大于cap的2的整數(shù)次冪逗旁。
再看第一條語(yǔ)句：
int n = cap - 1;
讓cap-1再賦值給n的目的是令找到的目標(biāo)值大于或等于原值夯秃。如果cap本身是2的冪，如8（1000(2)）痢艺，不對(duì)它減1而直接操作仓洼，將得到16。
通過(guò)tableSizeFor()堤舒，保證了HashMap容量始終是2的次方色建，在通過(guò)hash尋找index時(shí)就可以用邏輯運(yùn)算來(lái)替代取余，即hash％n用hash&(n -1)替代
一些變量的介紹
// 存儲(chǔ)元素的數(shù)組舌缤，總是2的冪箕戳，可以為0
transient Node<K,V>[] table;
// 存放具體元素的集合
transient Set<Map.Entry<K,V>> entrySet;
// 存放元素的個(gè)數(shù)，注意這個(gè)不等于數(shù)組的長(zhǎng)度国撵。
transient int size;
// 每次擴(kuò)容和更改map結(jié)構(gòu)的計(jì)數(shù)器
transient int modCount;
// 臨界值 當(dāng)實(shí)際節(jié)點(diǎn)個(gè)數(shù)超過(guò)臨界值(容量*填充因子)時(shí)陵吸，會(huì)進(jìn)行擴(kuò)容
int threshold;
// 哈希表的負(fù)載因子
final float loadFactor
接下來(lái)是4個(gè)構(gòu)造函數(shù)
//制定初始容量和填充因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) // 初始容量不能小于0，否則報(bào)錯(cuò)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) // 初始容量不能大于最大值介牙，否則為最大值
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 填充因子不能小于或等于0壮虫，不能為非數(shù)字
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor; // 初始化填充因子
this.threshold = tableSizeFor(initialCapacity); // 通過(guò)tableSizeFor(cap)計(jì)算出不小于initialCapacity的最近的2的冪作為初始容量，將其先保存在threshold里环础，當(dāng)put時(shí)判斷數(shù)組為空會(huì)調(diào)用resize分配內(nèi)存囚似，并重新計(jì)算正確的threshold
}
//指定初始容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//默認(rèn)構(gòu)造函數(shù)
public HashMap() {
// 初始化填充因子
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// HashMap(Map<? extends K>)型構(gòu)造函數(shù)
public HashMap(Map<? extends K, ? extends V> m) {
// 初始化填充因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 將m中的所有元素添加至HashMap中
putMapEntries(m, false);
}
這里介紹一下構(gòu)造函數(shù)中的putMapEntries這個(gè)方法：
// 將m中的所有元素添加至本HashMap中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // 判斷table是否已經(jīng)初始化
float ft = ((float)s / loadFactor) + 1.0F; // 未初始化，s為m的實(shí)際元素個(gè)數(shù)
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 計(jì)算得到的t大于閾值线得，則初始化閾值
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold) // 已初始化饶唤，并且m元素個(gè)數(shù)大于閾值，進(jìn)行擴(kuò)容處理
resize();
// 將m中的所有元素添加至HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
// 集合大小
public int size() {
return size;
}
// 本HashMap大小 是否 為0 true表示本HashMap沒(méi)有存儲(chǔ)任何鍵值對(duì)
public boolean isEmpty() {
return size == 0;
}
接下來(lái)就是HashMap的儲(chǔ)存詳解了贯钩，由于儲(chǔ)存涉及到HashMap的擴(kuò)容處理募狂，所以這里先把擴(kuò)容聊一下，這個(gè)也是hashMap中比較重要的一個(gè)知識(shí)點(diǎn)角雷。
擴(kuò)容
resize用來(lái)重新分配內(nèi)存
- 當(dāng)數(shù)組未初始化祸穷，按照之前在threashold中保存的初始容量分配內(nèi)存，沒(méi)有就使用缺省值
- 當(dāng)超過(guò)限制時(shí)谓罗，就擴(kuò)充兩倍粱哼，因?yàn)槲覀兪褂玫氖?次冪的擴(kuò)展，所以檩咱，元素的位置要么是在原位置揭措，要么是在原位置再移動(dòng)2次冪的位置
如oldCap為16時(shí)胯舷，如圖
因此，我們?cè)跀U(kuò)充HashMap的時(shí)候绊含，不需要重新計(jì)算hash桑嘶，只需要看看原來(lái)的hash值高位新增的那個(gè)bit是1還是0，是0的話索引不變躬充，是1的話索引變成“原索引+oldCap”, 直接拆分原鏈表為高低鏈表相比先保存數(shù)據(jù)再尋址追加效率更好逃顶。
源碼如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 當(dāng)前table保存
int oldCap = (oldTab == null) ? 0 : oldTab.length; / /保存table大小
int oldThr = threshold; // 保存當(dāng)前閾值
int newCap, newThr = 0;
if (oldCap > 0) { // 之前table大小大于0，即已初始化
if (oldCap >= MAXIMUM_CAPACITY) { // 超過(guò)最大值就不再擴(kuò)充了充甚，只設(shè)置閾值
threshold = Integer.MAX_VALUE; // 閾值為最大整形
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 容量翻倍
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 閾值翻倍
}
else if (oldThr > 0) // 初始容量已存在threshold中
newCap = oldThr;
else { // 使用缺省值（使用默認(rèn)構(gòu)造函數(shù)初始化）
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { // 計(jì)算新閾值
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
table = newTab;
if (oldTab != null) { // 之前的table已經(jīng)初始化過(guò)
for (int j = 0; j < oldCap; ++j) { // 復(fù)制元素以政，重新進(jìn)行hash
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 將原數(shù)組位置置為空，應(yīng)該是便于垃圾回收吧
if (e.next == null) // 桶中只有一個(gè)結(jié)點(diǎn)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //紅黑樹
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //根據(jù)(e.hash & oldCap)分為兩個(gè)伴找，如果哪個(gè)數(shù)目不大于UNTREEIFY_THRESHOLD盈蛮，就轉(zhuǎn)為鏈表
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do { // 將同一桶中的元素根據(jù)(e.hash & oldCap)是否為0進(jìn)行分割成兩個(gè)不同的鏈表，完成rehash
next = e.next; //保存下一個(gè)節(jié)點(diǎn)
if ((e.hash & oldCap) == 0) { //保留在低部分即原索引
if (loTail == null) //第一個(gè)結(jié)點(diǎn)讓loTail和loHead都指向它
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { //hash到高部分即原索引+oldCap
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;
}
進(jìn)行擴(kuò)容技矮，會(huì)重新進(jìn)行內(nèi)存分配抖誉，并且會(huì)遍歷hash表中所有的元素，是非常耗時(shí)的衰倦。在編寫程序中袒炉，要盡量避免resize。
分配內(nèi)存統(tǒng)一放在resize()中樊零，包括創(chuàng)建后首次put時(shí)初始化數(shù)組和存放元素個(gè)數(shù)超過(guò)閾值時(shí)擴(kuò)容我磁。
如果映射很多，創(chuàng)建HashMap時(shí)設(shè)置充足的初始容量(預(yù)計(jì)大小/負(fù)載因子 + 1）會(huì)比讓其自動(dòng)擴(kuò)容獲得更好的效率淹接，一方面減少了碰撞可能十性，另一方面減少了resize的損耗叛溢。
總結(jié)一下：把原數(shù)組在內(nèi)存中的位置置為空塑悼，然后重新分配內(nèi)存，把原來(lái)的一張表分為兩張表
put函數(shù)大致的思路為：
1.對(duì)key的hashCode()做hash楷掉，然后再計(jì)算桶的index;
2.如果沒(méi)碰撞直接放到桶bucket里厢蒜；
3.如果碰撞了，以鏈表的形式存在buckets后烹植；
4.如果碰撞導(dǎo)致鏈表過(guò)長(zhǎng)(大于等于TREEIFY_THRESHOLD)斑鸦，就把鏈表轉(zhuǎn)換成紅黑樹（若數(shù)組容量小于MIN_TREEIFY_CAPACITY，不進(jìn)行轉(zhuǎn)換而是進(jìn)行resize操作）
5.如果節(jié)點(diǎn)已經(jīng)存在就替換old value(保證key的唯一性)
6.如果表中實(shí)際元素個(gè)數(shù)超過(guò)閾值(超過(guò)load factor*current capacity)草雕，就要resize
具體如下：
public V put(K key, V value) {
// 對(duì)key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
* 用于實(shí)現(xiàn)put()方法和其他相關(guān)的方法
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing 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;
if ((tab = table) == null || (n = tab.length) == 0) // table未初始化或者長(zhǎng)度為0巷屿，進(jìn)行擴(kuò)容，n為桶的個(gè)數(shù)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // (n - 1) & hash 確定元素存放在哪個(gè)桶中墩虹，桶為空嘱巾，新生成結(jié)點(diǎn)放入桶中(此時(shí)憨琳，這個(gè)結(jié)點(diǎn)是放在數(shù)組中)
tab[i] = newNode(hash, key, value, null);
else { // 桶中已經(jīng)存在元素
Node<K,V> e; K k; // 比較桶中第一個(gè)元素的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 將第一個(gè)元素賦值給e旬昭，用e來(lái)記錄
else if (p instanceof TreeNode) // hash值不相等或key不相等 紅黑樹
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 放入樹中
else { // 為鏈表結(jié)點(diǎn)
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { // 到達(dá)鏈表的尾部
p.next = newNode(hash, key, value, null); // 在尾部插入新結(jié)點(diǎn)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 結(jié)點(diǎn)數(shù)量達(dá)到閾值篙螟，調(diào)用treeifyBin()做進(jìn)一步判斷是否轉(zhuǎn)為紅黑樹
treeifyBin(tab, hash);
break; // 跳出循環(huán)
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) // 判斷鏈表中結(jié)點(diǎn)的key值與插入的元素的key值是否相等
break; // 相等 跳出循環(huán)
p = e; // 用于遍歷桶中的鏈表，與前面的e = p.next組合问拘，可以遍歷鏈表
}
}
if (e != null) { // existing mapping for key 表示在桶中找到key值遍略、hash值與插入元素相等的結(jié)點(diǎn)
V oldValue = e.value; // 記錄e的value
if (!onlyIfAbsent || oldValue == null) // onlyIfAbsent為false或者舊值為null
e.value = value; //用新值替換舊值
afterNodeAccess(e); // 訪問(wèn)后回調(diào)
return oldValue; // 返回舊值
}
}
++modCount; // 結(jié)構(gòu)性修改
if (++size > threshold) // 實(shí)際大小大于閾值則擴(kuò)容
resize();
afterNodeInsertion(evict); // 插入后回調(diào)
return null;
}
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
將鏈表轉(zhuǎn)換為紅黑樹
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //若數(shù)組容量小于MIN_TREEIFY_CAPACITY，不進(jìn)行轉(zhuǎn)換而是進(jìn)行resize操作
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null); // 將Node轉(zhuǎn)換為TreeNode
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab); // 重新排序形成紅黑樹
}
}
/**
* 將指定映射的所有映射關(guān)系復(fù)制到此映射中
*
* @param m mappings to be stored in this map
* @throws NullPointerException if the specified map is null
*/
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
上面就是這個(gè)HashMap的整個(gè)存儲(chǔ)過(guò)程骤坐。
獲取的時(shí)候有好幾種我們先說(shuō)get方法绪杏，然后再說(shuō)獲取整個(gè)映射集合的方法
get函數(shù)大致思路如下：
- 鏈表結(jié)構(gòu)（bucket）里的第一個(gè)節(jié)點(diǎn)，直接命中纽绍；
- 如果有沖突寞忿，則通過(guò)key.equals(k)去查找對(duì)應(yīng)的entry，若為樹顶岸，復(fù)雜度O(logn)腔彰， 若為鏈表，O(n)
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已經(jīng)初始化辖佣，長(zhǎng)度大于0霹抛，且根據(jù)hash尋找table中的項(xiàng)也不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node 比較桶中第一個(gè)節(jié)點(diǎn)
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) { // 桶中不止一個(gè)節(jié)點(diǎn)
if (first instanceof TreeNode) // 為紅黑樹結(jié)點(diǎn)
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;
}
// 本HashMap 是否包含這個(gè)key
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
// 本HashMap 是否包含這個(gè)值
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
// 外層循環(huán)搜索數(shù)組
for (int i = 0; i < tab.length; ++i) {
// 內(nèi)層循環(huán)搜索鏈表
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value || (value != null && value.equals(v))) // 如果value地址相同卷谈，或者本身的值相同杯拐，然后equals方法
return true;
}
}
}
return false;
}
keySet() 、entrySet()世蔗、values()等方法
// keySet成員初始為null端逼，且并沒(méi)有在構(gòu)造函數(shù)中初始化過(guò)
transient volatile Set<K> keySet = null;
// 返回一個(gè)內(nèi)部引用，并指向一個(gè)內(nèi)部類對(duì)象污淋，該內(nèi)部類重寫了迭代器方法顶滩，當(dāng)在增強(qiáng)for循環(huán)時(shí)才調(diào)用，并從外部類的table中取值
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
所以初次調(diào)用keySet()方法時(shí)會(huì)new KeySet()寸爆，而KeySet()是一個(gè)內(nèi)部類
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() {
return new KeyIterator(); // 指向創(chuàng)建的另一個(gè)內(nèi)部類對(duì)象KeyIterator()礁鲁，該類繼承HashIterator也是HashMap的內(nèi)部類
}
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
// 供KeySet內(nèi)部類調(diào)用的
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
示例：
Map<String,Object> maps = new HashMap<>();
Set<String> strings = maps.keySet();
for (String string: strings) {
System.out.println(string);
}
當(dāng)我們?cè)谠鰪?qiáng)for循環(huán)時(shí)會(huì)調(diào)用該next()方法，它指向的是nextEntry().getKey()赁豆，Entry中不僅存放了key仅醇，value，也存放了next魔种，指向下一個(gè)Entry對(duì)象析二，我們知道，HashMap的數(shù)據(jù)層實(shí)現(xiàn)是數(shù)組+鏈表节预，nextEntry會(huì)先遍歷鏈表叶摄，然后再繼續(xù)遍歷下一個(gè)數(shù)組位置的鏈表漆改，直至全部遍歷完成
// 獲取所有value的集合
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
final class Values extends AbstractCollection<V> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<V> iterator() { return new ValueIterator(); }
public final boolean contains(Object o) { return containsValue(o); }
public final Spliterator<V> spliterator() {
return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
這個(gè)和上面的keySet是類似的，只是多做了一步取值hash碰撞后用equals比較獲取到對(duì)應(yīng)的值value
為什么要用Collection不和keySet一樣使用Set是因?yàn)閗ey是不重復(fù)的准谚，value是可以重復(fù)的.
同時(shí)獲取鍵和值得方法
entrySet()方法來(lái)實(shí)現(xiàn)對(duì)Map.Entry接口對(duì)象實(shí)例的遍歷挫剑，Map.Entry是Map接口里面的一個(gè)內(nèi)部接口，該接口聲明為泛型柱衔。當(dāng)我們獲得了接口對(duì)象后就可以調(diào)用接口方法getKey(), getValue()
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
/**
*在進(jìn)行foreach遍歷EntrySet的時(shí)候?qū)嶋H上是會(huì)遍歷table[],hashmap中實(shí)際具體數(shù)據(jù)都是存儲(chǔ)在這個(gè)數(shù)組中樊破，包括entry。這也進(jìn)一步驗(yàn)證了那句話entrySet() 該方法返回的是map包含的映射集合視圖唆铐，視圖的概念相當(dāng)于數(shù)據(jù)庫(kù)中視圖及提供一個(gè)窗口哲戚，沒(méi)有具體到相關(guān)數(shù)據(jù)，而真正獲取數(shù)據(jù)還是從table[]中來(lái)
*/
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
刪除的方法：
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
* 用于實(shí)現(xiàn) remove()方法和其他相關(guān)的方法
* @param hash 鍵的hash值
* @param key 鍵
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @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;
if ((tab = table) != null && (n = tab.length) > 0 && // table數(shù)組非空艾岂，鍵的hash值所指向的數(shù)組中的元素非空
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v; // node指向最終的結(jié)果結(jié)點(diǎn)顺少，e為鏈表中的遍歷指針
if (p.hash == hash && // 檢查第一個(gè)節(jié)點(diǎn)
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) { //如果第一個(gè)節(jié)點(diǎn)不匹配
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; //保存上個(gè)節(jié)點(diǎn)
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value || //判斷是否存在，如果matchValue為true王浴，需要比較值是否相等
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) //樹
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) //匹配第一個(gè)節(jié)點(diǎn)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
// 清空整個(gè)hashmap
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
本來(lái)想一篇直接寫完的脆炎，后來(lái)發(fā)現(xiàn)太多了，所以這篇先到這里氓辣，后面JDK8映射擴(kuò)展方法的重寫下一篇在分析秒裕。
如有錯(cuò)誤，歡迎指正钞啸，謝謝閱讀几蜻。
續(xù)篇的傳送門：http://www.reibang.com/p/d33dff0f4dd1
