HashMap的原理及分析

微信公眾號:Lucidastar
如有問題或建議郊楣,請公眾號留言
最近更新:2018-06-27

分析過程
  1. 簡單使用
  2. 涉及到的知識點及用到的東西
  3. 重要變量的解釋
  4. 提問問題(當(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)市栗?

圖注:Lucidastar

是一個“鏈表散列”的數(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

那他是如何進行操作的呢?先來張圖


圖注:圖片來自于網(wǎng)上

^ 代表異或
我們就以第一個例子為例毁菱,假如傳入的是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

image
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末菱鸥,一起剝皮案震驚了整個濱河市宗兼,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌氮采,老刑警劉巖殷绍,帶你破解...
    沈念sama閱讀 222,946評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異鹊漠,居然都是意外死亡主到,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3 399
  • 文/潘曉璐 我一進店門躯概,熙熙樓的掌柜王于貴愁眉苦臉地迎上來登钥,“玉大人,你說我怎么就攤上這事娶靡∧晾危” “怎么了?”我有些...
    開封第一講書人閱讀 169,716評論 0 364
  • 文/不壞的土叔 我叫張陵姿锭,是天一觀的道長塔鳍。 經(jīng)常有香客問我,道長呻此,這世上最難降的妖魔是什么轮纫? 我笑而不...
    開封第一講書人閱讀 60,222評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮焚鲜,結(jié)果婚禮上掌唾,老公的妹妹穿的比我還像新娘放前。我一直安慰自己,他們只是感情好郑兴,可當(dāng)我...
    茶點故事閱讀 69,223評論 6 398
  • 文/花漫 我一把揭開白布犀斋。 她就那樣靜靜地躺著,像睡著了一般情连。 火紅的嫁衣襯著肌膚如雪叽粹。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,807評論 1 314
  • 那天却舀,我揣著相機與錄音虫几,去河邊找鬼。 笑死挽拔,一個胖子當(dāng)著我的面吹牛辆脸,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播螃诅,決...
    沈念sama閱讀 41,235評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼啡氢,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了术裸?” 一聲冷哼從身側(cè)響起倘是,我...
    開封第一講書人閱讀 40,189評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎袭艺,沒想到半個月后搀崭,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,712評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡猾编,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,775評論 3 343
  • 正文 我和宋清朗相戀三年瘤睹,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片答倡。...
    茶點故事閱讀 40,926評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡轰传,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出瘪撇,到底是詐尸還是另有隱情获茬,我是刑警寧澤,帶...
    沈念sama閱讀 36,580評論 5 351
  • 正文 年R本政府宣布设江,位于F島的核電站,受9級特大地震影響攘轩,放射性物質(zhì)發(fā)生泄漏叉存。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,259評論 3 336
  • 文/蒙蒙 一度帮、第九天 我趴在偏房一處隱蔽的房頂上張望歼捏。 院中可真熱鬧稿存,春花似錦、人聲如沸瞳秽。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽练俐。三九已至袖迎,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間腺晾,已是汗流浹背燕锥。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留悯蝉,地道東北人归形。 一個月前我還...
    沈念sama閱讀 49,368評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像鼻由,于是被迫代替她去往敵國和親暇榴。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,930評論 2 361

推薦閱讀更多精彩內(nèi)容