微信公眾號: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