微信公眾號：Lucidastar
如有問題或建議郊楣，請公眾號留言
最近更新：2018-06-27
分析過程
- 簡單使用
- 涉及到的知識點及用到的東西
- 重要變量的解釋
- 提問問題（當(dāng)然蛉顽，在提問問題之前我是看過源碼的，所以我認(rèn)為這是重點或者難點我就進行提問了）
這是我分析源碼的過程佑惠，可以按這我的這個過程進行下去
開始
我們在開發(fā)中径筏，經(jīng)常會使用到集合漏峰，List 膜蠢、set等堪藐，今天我們就對HashMap進行簡單的分析下（基于1.8）。首先從名字上可以看出挑围，他是一個哈希表礁竞，具體什么是哈希表可以查閱相關(guān)資料。而Map就是存儲一個鍵值對Map<Object,Object>杉辙。
下面我們先來一段原理：
HashMap基于hashing原理模捂，我們通過put()和get()方法儲存和獲取對象。當(dāng)我們將鍵值對傳遞給put()方法時蜘矢，它調(diào)用鍵對象的hashCode()方法來計算hashcode枫绅，讓后找到bucket位置 來儲存值對象。當(dāng)獲取對象時硼端，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象寓搬。HashMap使用鏈表來解決碰撞問題珍昨，當(dāng)發(fā)生碰撞了，對象將會儲存在鏈表的下一個節(jié)點中句喷。 HashMap在每個鏈表節(jié)點中儲存鍵值對對象镣典。
好吧，這段是我從網(wǎng)上進行查找的唾琼，下面我們通過提問問題的方式來進行分析兄春。
簡單的使用
Map<String, Integer> map = new HashMap<>();//創(chuàng)建
map.put("科目1", 1);//添加
map.put("科目2", 2);
map.put("科目3", 3);
map.put("科目4", 4);
map.put("科目5", 5);
map.put("科目6", 6);
map.put("科目7", 7);
map.put("科目8", 8);
Integer value = map.put("科目9", 9);//當(dāng)添加新的數(shù)據(jù)時，key值不相同锡溯，那么返回的值就是null
Integer value1 = map.put("科目8", 10);//當(dāng)key值相同時赶舆，會把原來的value給替換掉，并且返回替換掉的value
System.out.println(value);
System.out.println(value1);
boolean empty = map.isEmpty();//判斷map是否為空
map.remove("科目6");//移除一個祭饭，并且返回移除的value
for (Map.Entry<String, Integer> entry : map.entrySet()) {//map的遍歷
System.out.println(entry.getKey()+":"+entry.getValue());
}
其他的api可以自行查閱文檔芜茵。
涉及到的知識點及用到的東西
在開始我們就簡單的介紹了一下，會涉及到數(shù)組倡蝙，鏈表及紅黑樹（也叫平衡樹）的數(shù)據(jù)結(jié)構(gòu)方面的知識九串，如果對這方面不太了解的，可以查些資料簡單了解一下。
紅黑樹的介紹:https://www.sohu.com/a/201923614_466939
鏈表的介紹：鏈表分為單鏈表猪钮，雙鏈表和循環(huán)鏈表:http://www.baike.com/wiki/%E9%93%BE%E8%A1%A8
數(shù)組大家應(yīng)該不陌生品山，這里就略過去了。
涉及到的變量烤低，以及在里頭的作用（我認(rèn)為需要了解和重要的）
transient Node<K,V>[] table;//(表肘交，在首次使用時初始化，并根據(jù)需要調(diào)整大小拂玻。)當(dāng)分配時酸些，長度總是2的冪。
transient int size;(鍵值映射的數(shù)量)
int threshold;//需要擴容的大虚苎痢（容量*負(fù)載因子系數(shù)）threshold = length（長度魄懂，默認(rèn)是16） * Load factor（默認(rèn)是0.75）
final float loadFactor;//負(fù)載因子
transient int modCount;//主要用來記錄HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)(數(shù)組和鏈表的結(jié)構(gòu)發(fā)生改變)
下面我們通過提問問題的方式進行學(xué)習(xí)。
一闯第、HashMap是怎樣的一個結(jié)構(gòu)市栗？
是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體咳短。
二填帽、是如何把數(shù)據(jù)存到數(shù)組當(dāng)中的？
如果我們想把數(shù)據(jù)存入進去咙好，首先我們需要知道他的下標(biāo)位置篡腌，然后找到相應(yīng)的位置放進去，他是如何計算下標(biāo)的呢勾效？
if ((p = tab[i = (n - 1) & hash]) == null) //這個hash值就是通過下面的key算出來的嘹悼，我們來看一下
tab[i] = newNode(hash, key, value, null);
而hash值的計算是通過這個
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
注意：h 在向右移位時，h的值已經(jīng)是hashCode的值了
n 為數(shù)組的長度层宫，第一次是16杨伙，上面已經(jīng)講過，我們來看一下如何計算出來的
我們來測試一下下標(biāo)的計算：（(n - 1) & hash）
int n = 16;
for (int i = 0; i < 12; i++) {
System.out.print(hash(i) & (n - 1));
System.out.print(",");
}
打印結(jié)果：0,1,2,3,4,5,6,7,8,9,10,11這就好比是table下標(biāo)的位置
我們再來測試一個對象：
class Student{
private String name;
private String age;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getAge() {
return age;
}
public void setAge(String age) {
this.age = age;
}
}
int n = 16;
for (int i = 0; i < 12; i++) {
Student student = new Student();
student.setName("張三"+i);
System.out.print(hash(student) & (n - 1));
System.out.print(",");
}
打印結(jié)果：0,10,3,1,2,11,7,6,10,3,3,5
為什么上面的下標(biāo)沒有重復(fù)的萌腿，而測試對象時有重復(fù)的呢?
因為Integer重寫了hashCode方法限匣，而我創(chuàng)建的對象沒有重新hashCode
那他是如何進行操作的呢？先來張圖
^ 代表異或
我們就以第一個例子為例毁菱，假如傳入的是5
h=hashCode()=5: 0000 0000 0000 0000 0000 0000 0000 0101 =5
h >>>16: 0000 0000 0000 0000 0000 0000 0000 0000 = 0
邏輯右移
解釋：比如300 二進制就是 100101100
300>>>1 結(jié)果是：10010110
300>>>2 結(jié)果是：1001011
300>>>3 結(jié)果是：100101
所以當(dāng)16的時候就是0了
hash=h^(h>>>16): 0000 0000 0000 0000 0000 0000 0000 0101 這是異或后的值
^是代表的異或 例子：00=0米死，11=0 ，1^0 = 1贮庞，0^1=1
(n-1) & hash :
0000 0000 0000 0000 0000 0000 0000 1111 (n-1=15)
0000 0000 0000 0000 0000 0000 0000 0101 得到：0101 十進制就是5
&代表的是與：0&0=0哲身，1&1=1 ，1&0 = 0贸伐，0&1=0
兩個都是1時才是1
結(jié)論：那計算出來的下標(biāo)位置就是5 我們就可以驗證上面勘天，5就會存到數(shù)組下標(biāo)為5的位置。
三、什么時候會把數(shù)據(jù)存到數(shù)組中的鏈表中脯丝？
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)//數(shù)組為空時創(chuàng)建
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//插入數(shù)組
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))))//當(dāng)key相等時商膊，就把value賦值
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) {//如果鏈表的下一個是空，就創(chuàng)建一個節(jié)點宠进，
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//當(dāng)鏈表的長度大于16時晕拆，就轉(zhuǎn)為紅黑樹
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))//// key已經(jīng)存在并且相等，就把這個節(jié)點替換
break;
p = e;
}
}
//如果你插入是材蹬，key不為空实幕，并且原來的節(jié)點不為空，并且返回替換掉的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}.
=============================================================
++modCount;//結(jié)構(gòu)發(fā)生變化
if (++size > threshold)//超過最大容量時堤器， 就會進行擴容昆庇。
resize();
afterNodeInsertion(evict);
return null;
}
橫杠之間就是把數(shù)據(jù)存到數(shù)組對應(yīng)的鏈表中了。
四闸溃、什么時候開始擴容整吆？
if ((tab = table) == null || (n = tab.length) == 0)//數(shù)組為空時，就會進行初始化
n = (tab = resize()).length;
if (++size > threshold)//超過最大容量時辉川， 就會進行擴容表蝙。（默認(rèn)shreshold為12 16*0.75=12）
resize();
五、如何進行擴容的乓旗？
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {//如果老的數(shù)組大于零
if (oldCap >= MAXIMUM_CAPACITY) {//大于最大的容量時府蛇，就會返回老的數(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) // initial capacity was placed in threshold（初始容量設(shè)為閾值）
newCap = oldThr;
else { // zero initial threshold signifies using defaults//如果為零的話欲诺，就使用默認(rèn)的閾值
newCap = DEFAULT_INITIAL_CAPACITY;（默認(rèn)的容量）
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);（默認(rèn)的閾值）
}
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];//用新的容量值創(chuàng)建一個新的數(shù)組
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
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;
}
當(dāng)size的數(shù)量大于threshold這個值時，就進行擴容渺鹦。原來的老數(shù)組長度大于零，
newThr = oldThr << 1; // double threshold//向左移動一位蛹含，擴大原來的兩倍
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//用新的閾值創(chuàng)建一個新的數(shù)組
六毅厚、擴容之后做了一些什么操作？
table = newTab;
if (oldTab != null) {//老的數(shù)組不為空
for (int j = 0; j < oldCap; ++j) {//開始遍歷
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;//把老的數(shù)組節(jié)點設(shè)為空
if (e.next == null)//如果這個數(shù)組下沒有鏈表
newTab[e.hash & (newCap - 1)] = e;//就把數(shù)據(jù)這key值的哈希值與上新的數(shù)組長度-1
else if (e instanceof TreeNode)//這是紅黑樹的情況
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order//下面就是數(shù)組下有鏈表浦箱，有值
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {//這個地方就是數(shù)組下面有鏈表吸耿，并且把鏈表下的數(shù)據(jù)放到新的數(shù)組當(dāng)中。
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;
}
}
}
（擴容之后咽安，原來的數(shù)組和鏈表的位置是如何遷移到擴容后的數(shù)組當(dāng)中的呢？以及位置是如何計算的呢蓬推？這一塊的代碼沒有太搞明白）
七妆棒、什么時候生碰撞？
也就是問題三種，部分代碼：
for (int binCount = 0; ; ++binCount) {//這里就是插入鏈表
if ((e = p.next) == null) {//如果鏈表的下一個是空糕珊，就創(chuàng)建一個節(jié)點动分，
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//當(dāng)鏈表的長度大于16時，就轉(zhuǎn)為紅黑樹
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))//// key已經(jīng)存在并且相等红选，就把這個節(jié)點替換
break;
p = e;
}
}
//如果你插入是澜公，key不為空，并且原來的節(jié)點不為空喇肋，并且返回替換掉的value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
也就是說坟乾，首先通過(（n-1）& hash)算出數(shù)組下標(biāo)位置，當(dāng)這個位置已經(jīng)占用的話蝶防，就會插入到這個數(shù)組節(jié)點對應(yīng)的鏈表中甚侣，也就是說這時候發(fā)生了碰撞。
當(dāng)這個鏈表長度大于8時慧脱，就會轉(zhuǎn)換為紅黑樹
這就是我對HashMap的理解渺绒。可以關(guān)注我的公眾號共同學(xué)習(xí)探究
我的公眾號：Lucidastar
