1.概念
? ? HashMap是Java中最常用的集合類之一轨奄，以<K,V>的形式來進(jìn)行數(shù)據(jù)存儲挽铁。常用來比較的還有HashTable袋倔，ConcurrentHashMap 等坦辟。
2.數(shù)據(jù)結(jié)構(gòu)? ?
? ? ? ? 什么是數(shù)據(jù)結(jié)構(gòu)鳄橘，在我的認(rèn)識中声离，我們的數(shù)據(jù)需要存儲在計算機(jī)中，那么它的存儲形式瘫怜，就是一個個的數(shù)據(jù)結(jié)構(gòu)抵恋。常見的數(shù)據(jù)結(jié)構(gòu)包括：數(shù)組，鏈表宝磨，二叉樹弧关，紅黑樹等等
? ? ? ? 提起hashMap內(nèi)部的數(shù)據(jù)結(jié)構(gòu) 那么大多數(shù)開發(fā)者都可以說出 在其內(nèi)部是維護(hù)了一個數(shù)組，數(shù)組的每個元素又是一個單向鏈表唤锉。在1.7之前的版本中世囊，這是沒錯的，但是維護(hù)單向鏈表由此帶來的一個缺點就是當(dāng)我們的hashMap發(fā)生大量的指針碰撞之后窿祥，當(dāng)我們需要get其中的一個值的時候株憾，就有可能需要遍歷單向鏈表，那么時間復(fù)雜度就是O(n),為解決這一問題，在1.7之后嗤瞎，hashMap中引入了紅黑樹墙歪，將達(dá)到一定條件的鏈表轉(zhuǎn)變?yōu)橐粋€紅黑樹，此時時間復(fù)雜度就變?yōu)榱薕(logn)贝奇。
問虹菲，為何不使用比如線性探測法 往數(shù)組的其他位置放 如果長度不夠 則進(jìn)行擴(kuò)容
答：第一，這樣有可能導(dǎo)致 本來數(shù)組還有空余位置就觸發(fā)了擴(kuò)容掉瞳，內(nèi)存浪費(fèi)毕源。第二，擴(kuò)容時 需要根據(jù)hash值和數(shù)組長度重新計算每一個key的hash值陕习，然后重新排列整個map霎褐，消耗系統(tǒng)資源「昧停總體上來說冻璃，是一個時間換空間的操作。
3.hashMap如何存儲數(shù)據(jù)
? ? 接下來就是本文的重點了损合，hashMap到底是如何存儲數(shù)據(jù)的呢省艳？
? ? 讓我們帶著幾個問題來看代碼
? ? （1）數(shù)組是什么時候進(jìn)行初始化的
? ? （2）數(shù)組在內(nèi)存中為一塊連續(xù)的內(nèi)存地址，所以要求我們在初始化數(shù)組是設(shè)定數(shù)組的長度塌忽。那么數(shù)組的大小設(shè)置為多少呢
? ? （3）hash值如何計算
? ? （4）什么是hash沖突拍埠，發(fā)生后沖突后hashMap是如何處理的
public V put(K key,V value) {
return putVal(hash(key), key, value,false,true);
}
這就是在hashMap中進(jìn)行put的方法失驶，我們需要關(guān)注兩個點 第一土居，putVal(hash(key), key, value,false,true) 這是進(jìn)行存儲操作的方法；第二嬉探，hash（key）這是計算hash值的方法 擦耀。
我們先來看第一個
transient Node[]table;
Node[] tab; Node p;int n, I;? ? ?
//聲明了一個Node對象，Node元素中包含了如下變量
final int hash;
final K key;
V value;
Nodenext;? //下一個元素的地址引用 佐證了這是一個單向鏈表
if ((tab =table) ==null || (n = tab.length) ==0)? ? //此處為判斷聲明的Node[]是否為空
n = (tab = resize()).length;? ? //為空執(zhí)行resize() 方法
在resize（）方法中 涩堤，當(dāng)判斷oldTab.length==0時 有如下代碼
newCap=DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR *DEFAULT_INITIAL_CAPACITY);
//下面兩行是類中聲明的常量
static final int DEFAULT_INITIAL_CAPACITY =1 <<4;// aka 16? 位運(yùn)算 即初始化的數(shù)組長度
static final float DEFAULT_LOAD_FACTOR =0.75f;// 負(fù)載因子
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
我們可以看到眷蜓，當(dāng)首次進(jìn)行put時，進(jìn)行了數(shù)組的初始化胎围，并定義了數(shù)組的長度為16吁系，那么問題來了，數(shù)組的長度給定了之后白魂，tab[]下標(biāo)為0-15汽纤。如果我們不斷插入數(shù)據(jù)，當(dāng)key的hash值不在這16個長度之內(nèi)時會發(fā)生什么呢福荸，讓我們繼續(xù)看源碼蕴坪，還是putval（）
if ((p = tab[i = (n -1) & hash]) ==null)
tab[i] = newNode(hash, key, value,null);
通過這兩行代碼我們可以看到 去計算了一次hash值 當(dāng)tab[i]==null時，new了Node元素 放了進(jìn)去 完成了數(shù)據(jù)存儲
如果此時tab[i]不為null則執(zhí)行下面的代碼。
else {
Node e;K k;
if (p.hash == hash &&
((k = p.key) == key || (key !=null && key.equals(k))))
e = p;
在這我們看到? 當(dāng) k的hash值相等且 equals（）相等的時候背传，進(jìn)行了覆蓋
else if (pinstanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
k不相等的時候 如果當(dāng)前Node對象包含了紅黑樹 那么就把它放在了樹里
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?
TREEIFY_THRESHOLD =8
? ? ? ? ? ? ? ? treeifyBin(tab, hash);
break;
}
對單向鏈表進(jìn)行遍歷呆瞻。當(dāng)p.next==null 是說明這是單向鏈表的尾結(jié)點，指針null径玖。記錄單向鏈表的遍歷的次數(shù)痴脾。 TREEIFY_THRESHOLD=8 當(dāng)鏈表長度》=8-1時， 將鏈表轉(zhuǎn)為紅黑樹
if (e.hash == hash &&
((k = e.key) == key || (key !=null && key.equals(k))))
break;
//同樣是進(jìn)行key的hash判斷 一致則覆蓋掉原有值
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;? ? //記錄put的次數(shù)
if (++size >threshold)
resize();
//重點來了 在此時挺狰，如果數(shù)組需要進(jìn)行擴(kuò)容數(shù)組在什么時候擴(kuò)容呢明郭，就是代碼中的threshold = newThr
在resize()方法中 如果原有tab長度＞0且＜2的30次方，則tab長度變?yōu)樵瓉淼?lt;1 即原來的2倍
size這個值在哪計算還沒發(fā)現(xiàn) 待我稍后進(jìn)行補(bǔ)充
afterNodeInsertion(evict);
return null;
4.完整的源碼
final V putVal(int hash,K key,V value,boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p;int n, i;
if ((tab =table) ==null || (n = tab.length) ==0)
n = (tab = resize()).length;
if ((p = tab[i = (n -1) & hash]) ==null)
tab[i] = newNode(hash, key, value,null);
else {
Node e;K k;
if (p.hash == hash &&
((k = p.key) == key || (key !=null && key.equals(k))))
e = p;
else if (pinstanceof TreeNode)
e = ((TreeNode)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;
}
本篇解決了1.2.4三個問題 至于第3個問題 改日在敘丰泊。如有謬誤如疏漏之處煩請各位看官多多指正
