您好,歡迎來到賦能網(wǎng)!

HahMap在Java7和Java8中的實(shí)現(xiàn)有什么不同?具體分析

賦能網(wǎng) 2023-05-09 82

hashmap最關(guān)鍵的操作就是hash的邏輯,也就是把各種給了鍵值對的節(jié)點(diǎn)node,對應(yīng)到數(shù)組中的邏輯,然后才能談沖突后的存儲和處理方式。那HashMap在java7和Java8中的實(shí)現(xiàn)有什么不同?下面來我們就來給大家講解一下。

Java 7 中Hashmap擴(kuò)容機(jī)制

一、什么時(shí)候擴(kuò)容:

網(wǎng)上總結(jié)的會有很多,但大多都總結(jié)的不夠完整或者不夠準(zhǔn)確。大多數(shù)可能值說了滿足我下面條件一的情況。

擴(kuò)容必須滿足兩個(gè)條件:

1、 存放新值的時(shí)候當(dāng)前已有元素的個(gè)數(shù)必須大于等于閾值

2、 存放新值的時(shí)候當(dāng)前存放數(shù)據(jù)發(fā)生hash碰撞(當(dāng)前key計(jì)算的hash值換算出來的數(shù)組下標(biāo)位置已經(jīng)存在值)

二、下面我們看源碼,如下:

首先是put()方法

public V put(K key, V value)
{
    //判斷當(dāng)前Hashmap(底層是Entry數(shù)組)是否存值(是否為空數(shù)組)
    if (table == EMPTY_TABLE)
    {
        inflateTable(threshold); //如果為空,則初始化
    }
    //判斷key是否為空
    if (key == null)
        return putForNullKey(value); //hashmap允許key為空
    //計(jì)算當(dāng)前key的哈希值
    int hash = hash(key);
    //通過哈希值和當(dāng)前數(shù)據(jù)長度,算出當(dāng)前key值對應(yīng)在數(shù)組中的存放位置
    int i = indexFor(hash, table.length);
    for (Entrye = table[i]; e != null; e = e.next)
    {
        Object k;
        //如果計(jì)算的哈希位置有值(及hash沖突),且key值一樣,則覆蓋原值value,并返回原值value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
        {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //存放值的具體方法
    addEntry(hash, key, value, i);
    return null;
}
在put() 方法中有調(diào)用addEntry() 方法, 這個(gè)方法里面是具體的存值, 在存值之前還要判斷是否需要擴(kuò)容
void addEntry(int hash, K key, V value, int bucketIndex)
{
    //1、判斷當(dāng)前個(gè)數(shù)是否大于等于閾值
    //2、當(dāng)前存放是否發(fā)生哈希碰撞
    //如果上面兩個(gè)條件否發(fā)生,那么就擴(kuò)容
    if ((size >= threshold) && (null != table[bucketIndex]))
    {
        //擴(kuò)容,并且把原來數(shù)組中的元素重新放到新數(shù)組中
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}
如果需要擴(kuò)容, 調(diào)用擴(kuò)容的方法resize()
void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    //判斷是否有超出擴(kuò)容的最大值,如果達(dá)到最大值則不進(jìn)行擴(kuò)容操作
    if (oldCapacity == MAXIMUM_CAPACITY)
    {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    // transfer()方法把原數(shù)組中的值放到新數(shù)組中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    //設(shè)置hashmap擴(kuò)容后為新的數(shù)組引用
    table = newTable;
    //設(shè)置hashmap擴(kuò)容新的閾值
    threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer() 在實(shí)際擴(kuò)容時(shí)候把原來數(shù)組中的元素放入新的數(shù)組中
void transfer(Entry[] newTable, boolean rehash)
{
    int newCapacity = newTable.length;
    for (Entrye: table)
    {
        while (null != e)
        {
            Entrynext = e.next;
            if (rehash)
            {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //通過key值的hash值和新數(shù)組的大小算出在當(dāng)前數(shù)組中的存放位置
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

Java8的擴(kuò)容機(jī)制:

Java8不再像Java7中那樣需要滿足兩個(gè)條件,Java8中擴(kuò)容只需要滿足一個(gè)條件:當(dāng)前存放新值(注意不是替換已有元素位置時(shí))的時(shí)候已有元素的個(gè)數(shù)大于等于閾值(已有元素等于閾值,下一個(gè)存放后必然觸發(fā)擴(kuò)容機(jī)制)

注:

(1)擴(kuò)容一定是放入新值的時(shí)候,該新值不是替換以前位置的情況下(說明:put(“name”,"zhangsan"),而map里面原有數(shù)據(jù)<"name","lisi">,則該存放過程就是替換一個(gè)原有值,而不是新增值,則不會擴(kuò)容)

(2)擴(kuò)容發(fā)生在存放后,即是數(shù)據(jù)存放后(先存放后擴(kuò)容),判斷當(dāng)前存入對象的個(gè)數(shù),如果大于閾值則進(jìn)行擴(kuò)容。

Java7中Hashmap底層采用的是Entry對數(shù)組,而每一個(gè)Entry對又向下延伸是一個(gè)鏈表,在鏈表上的每一個(gè)Entry對不僅存儲著自己的key/value值,還存了前一個(gè)和后一個(gè)Entry對的地址。

Java8中的Hashmap底層結(jié)構(gòu)有一定的變化,還是使用的數(shù)組,但是數(shù)組的對象以前是Entry對,現(xiàn)在換成了Node對象(可以理解是Entry對,結(jié)構(gòu)一樣,存儲時(shí)也會存key/value鍵值對、前一個(gè)和后一個(gè)Node的地址),以前所有的Entry向下延伸都是鏈表,Java8變成鏈表和紅黑樹的組合,數(shù)據(jù)少量存入的時(shí)候優(yōu)先還是鏈表,當(dāng)鏈表長度大于8,且總數(shù)據(jù)量大于64的時(shí)候,鏈表就會轉(zhuǎn)化成紅黑樹,所以你會看到Java8的Hashmap的數(shù)據(jù)存儲是鏈表+紅黑樹的組合,如果數(shù)據(jù)量小于64則只有鏈表,如果數(shù)據(jù)量大于64,且某一個(gè)數(shù)組下標(biāo)數(shù)據(jù)量大于8,那么該處即為紅黑樹。

此外需要注意一點(diǎn)java7是在存入數(shù)據(jù)前進(jìn)行判斷是否擴(kuò)容,而java8是在存入數(shù)據(jù)庫在進(jìn)行擴(kuò)容的判斷。最后大家如果想要了解更多java面試題知識,敬請關(guān)注賦能網(wǎng)。


本文鏈接:

本文章“HahMap在Java7和Java8中的實(shí)現(xiàn)有什么不同?具體分析”已幫助 82 人

免責(zé)聲明:本信息由用戶發(fā)布,本站不承擔(dān)本信息引起的任何交易及知識產(chǎn)權(quán)侵權(quán)的法律責(zé)任!

本文由賦能網(wǎng) 整理發(fā)布。了解更多培訓(xùn)機(jī)構(gòu)》培訓(xùn)課程》學(xué)習(xí)資訊》課程優(yōu)惠》課程開班》學(xué)校地址等機(jī)構(gòu)信息,可以留下您的聯(lián)系方式,讓課程老師跟你詳細(xì)解答:
咨詢熱線:4008-569-579

如果本頁不是您要找的課程,您也可以百度查找一下: