日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
深度！HashMap的底層數(shù)據(jù)結(jié)構(gòu)

一、HashMap基礎(chǔ)機(jī)構(gòu)

HashMap 由數(shù)組和鏈表（或紅黑樹）組成。數(shù)組是 HashMap 的主體，鏈表和紅黑樹則是為了解決哈希沖突而存在的。數(shù)組中的每個(gè)元素都是一個(gè)單向鏈表的頭結(jié)點(diǎn)，每個(gè)鏈表都是由若干個(gè) Node 節(jié)點(diǎn)組成的，每個(gè)節(jié)點(diǎn)都包含了鍵值對(duì)的信息，以及指向下一個(gè)節(jié)點(diǎn)的指針。當(dāng)多個(gè)鍵映射到同一個(gè)位置時(shí)，它們會(huì)被存儲(chǔ)在同一個(gè)鏈表中（或者是同一個(gè)紅黑樹中）。當(dāng)鏈表長(zhǎng)度超過閾值（默認(rèn)為 8）時(shí)，鏈表就會(huì)被轉(zhuǎn)換成紅黑樹，這樣可以提高查找效率。

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供景谷網(wǎng)站建設(shè)、景谷做網(wǎng)站、景谷網(wǎng)站設(shè)計(jì)、景谷網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、景谷企業(yè)網(wǎng)站模板建站服務(wù)，十年景谷做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

在 JDK1.8 中，HashMap 還引入了一個(gè)新的概念，叫做負(fù)載因子(load factor)，它是指哈希表中鍵值對(duì)的數(shù)量與數(shù)組長(zhǎng)度的比值。當(dāng)鍵值對(duì)的數(shù)量超過了負(fù)載因子與數(shù)組長(zhǎng)度的乘積時(shí)，就會(huì)觸發(fā)擴(kuò)容操作，HashMap 會(huì)自動(dòng)將數(shù)組長(zhǎng)度擴(kuò)大一倍，并將原來(lái)的鍵值對(duì)重新分配到新的數(shù)組中。這樣做的目的是為了保證散列表的性能，因?yàn)楫?dāng)負(fù)載因子過高時(shí)，散列表的性能會(huì)急劇下降。

二、HashMap的底層數(shù)據(jù)結(jié)構(gòu)

解答：在jdk1.8以前，HashMa采用鏈表+數(shù)組，自Jdk1.8以后，HashMap采用鏈表+數(shù)組+紅黑樹。在下圖中橫鏈(0-15)表中表示數(shù)組，豎(1-8)表示鏈表，在數(shù)組長(zhǎng)度超過8之后，hashmap將數(shù)組自動(dòng)轉(zhuǎn)為紅黑樹。

HashMapJDK1.8鏈表和紅黑樹轉(zhuǎn)化

三、JDK1.8對(duì)hash算法和尋址算法如何優(yōu)化的？

1、對(duì)Hash值算法的優(yōu)化

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

有一個(gè)key的Hash_1值：

Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100
h >>> 16 // 表示對(duì)該hash值右移16位

右移后的結(jié)果Hash_2為：

Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111

對(duì)上述Hash_1和Hash_2的兩個(gè)值進(jìn)行異或

Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100
Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111
=====>: 1111 1111 1111 1111 0000 0101 1000 0011 =====> 轉(zhuǎn)為10進(jìn)制int值，這個(gè)值就是這個(gè)key的hash值

hash算法的優(yōu)化：對(duì)每個(gè)hash值，在它的低16位中，讓高低16位進(jìn)行異或，讓它的低16位同時(shí)保持了高低16位的特征，盡量避免一些hash值后續(xù)出現(xiàn)沖突，大家可能會(huì)進(jìn)入數(shù)組的同一位置。

2、對(duì)尋址算法的優(yōu)化

(p = tab[i = (n - 1) & hash] 
 
 // (n-1) & hash ==> 數(shù)組里的一個(gè)位置

hash & (n-1) 效果是跟hash對(duì)n取模是一樣的，但是與運(yùn)算的性能要比hash對(duì)n取模要高很多。數(shù)組的長(zhǎng)度會(huì)一直是2的n次方，只要他保持?jǐn)?shù)組長(zhǎng)度是2的n次方。

  • 尋址為什么不用取模？

對(duì)于上面尋址算法，由于計(jì)算機(jī)對(duì)比取模，與運(yùn)算會(huì)更快。所以為了效率，HashMap 中規(guī)定了哈希表長(zhǎng)度為 2 的 k 次方，而 2^k-1 轉(zhuǎn)為二進(jìn)制就是 k 個(gè)連續(xù)的 1，那么 hash & (k 個(gè)連續(xù)的 1) 返回的就是 hash 的低 k 個(gè)位，該計(jì)算結(jié)果范圍剛好就是 0 到 2^k-1，即 0 到 length - 1，跟取模結(jié)果一樣。

也就是說，哈希表長(zhǎng)度 length 為 2 的整次冪時(shí)， hash & (length - 1) 的計(jì)算結(jié)果跟 hash % length 一樣，而且效率還更好。

  • 為什么不直接用 hashCode() 而是用它的高 16 位進(jìn)行異或計(jì)算新 hash 值？#

int 類型占 32 位，可以表示 2^32 種數(shù)（范圍：-2^31 到 2^31-1），而哈希表長(zhǎng)度一般不大，在 HashMap 中哈希表的初始化長(zhǎng)度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果直接用 hashCode 來(lái)尋址，那么相當(dāng)于只有低 4 位有效，其他高位不會(huì)有影響。這樣假如幾個(gè) hashCode 分別是 210、220、2^30，那么尋址結(jié)果 index 就會(huì)一樣而發(fā)生沖突，所以哈希表就不均勻分布了。

尋址算法的優(yōu)化：用與運(yùn)算替代取模，提升性能。（由于計(jì)算機(jī)對(duì)比取模，與運(yùn)算會(huì)更快）

四、HashMap是如何解決hash碰撞問題

hash沖突問題，鏈表+紅黑樹，O(n)和O(logN)。

hashmap采用的就是鏈地址法（拉鏈法），jdk1.7中，當(dāng)沖突時(shí)，在沖突的地址上生成一個(gè)鏈表，將沖突的元素的key，通過equals進(jìn)行比較，相同即覆蓋，不同則添加到鏈表上，此時(shí)如果鏈表過長(zhǎng)，效率就會(huì)大大降低，查找和添加操作的時(shí)間復(fù)雜度都為O(n)；但是在jdk1.8中如果鏈表長(zhǎng)度大于8，鏈表就會(huì)轉(zhuǎn)化為紅黑樹，時(shí)間復(fù)雜度也降為了O(logn)，性能得到了很大的優(yōu)化。

HashMapJDK1.8鏈表和紅黑樹轉(zhuǎn)化

五、HashMap是如何進(jìn)行擴(kuò)容的

HashMap底層是一個(gè)數(shù)組，當(dāng)這個(gè)數(shù)組滿了之后，他就會(huì)自動(dòng)進(jìn)行擴(kuò)容，變成一個(gè)更大數(shù)組。

1、JDK1.7下的擴(kuò)容機(jī)制

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
 
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

代碼中可以看到，如果原有table長(zhǎng)度已經(jīng)達(dá)到了上限，就不再擴(kuò)容了。如果還未達(dá)到上限，則創(chuàng)建一個(gè)新的table，并調(diào)用transfer方法：

/**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry e : table) {
            while(null != e) {
                Entry next = e.next;              //注釋1
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity); //注釋2
                e.next = newTable[i];                  //注釋3
                newTable[i] = e;                       //注釋4
                e = next;                              //注釋5
            }
        }
    }

transfer方法的作用是把原table的Node放到新的table中，使用的是頭插法，也就是說，新table中鏈表的順序和舊列表中是相反的，在HashMap線程不安全的情況下，這種頭插法可能會(huì)導(dǎo)致環(huán)狀節(jié)點(diǎn)。

2、JDK1.8下的擴(kuò)容機(jī)制

源碼如下：

final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length; // 記錄原來(lái)的數(shù)組長(zhǎng)度
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold // 重新計(jì)算TREEIFY_THRESHOLD
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        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[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {  // 重新計(jì)算原來(lái)鏈表中的值的hash值在新表對(duì)應(yīng)的hash值
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)  // 如果元素e的下一個(gè)位置沒有值，則說明可以存放元素
                        newTab[e.hash & (newCap - 1)] = e; 
                    else if (e instanceof TreeNode) // 如果已經(jīng)是紅黑樹的節(jié)點(diǎn)，那就對(duì)其重新劃分
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        // loHead: 下標(biāo)不變情況下的鏈表頭
                        // loTail: 下標(biāo)不變情況下的鏈表尾
                        // hiHead: 下標(biāo)改變情況下的鏈表頭
                        // hiTail: 下標(biāo)改變情況下的鏈表尾
                        // 如果
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) { // 元素e的最新hash如果與原來(lái)的值與計(jì)算之后如果值為0，就說明是使用原來(lái)的index
                                // 尾插法插入元素e
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                // 與運(yùn)算不等于0則說明使用新的index
                                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;
    }

正常情況下，計(jì)算節(jié)點(diǎn)在table中的下標(biāo)的方法是：hash&(oldTable.length-1)，擴(kuò)容之后，table長(zhǎng)度翻倍，計(jì)算table下標(biāo)的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)，于是我們有了這樣的結(jié)論：這新舊兩次計(jì)算下標(biāo)的結(jié)果，要不然就相同，要不然就是新下標(biāo)等于舊下標(biāo)加上舊數(shù)組的長(zhǎng)度。

數(shù)組長(zhǎng)度為16時(shí)，有兩個(gè)keyA和keyB。

KeyA：
n-1:   0000 0000 0000 0000 0000 0000 0000 1111
hash1: 1111 1111 1111 1111 0000 1111 0000 0101
&結(jié)果:  0000 0000 0000 0000 0000 0000 0000 0101 = 5

KeyB:
n-1:   0000 0000 0000 0000 0000 0000 0000 1111 
hash1: 1111 1111 1111 1111 0000 1111 0001 0101
&結(jié)果:  0000 0000 0000 0000 0000 0000 0000 0101 = 5

在數(shù)組長(zhǎng)度為16的時(shí)候，他們兩個(gè)hash值沖突會(huì)使用拉鏈發(fā)解決沖突。

當(dāng)數(shù)組長(zhǎng)度擴(kuò)容到32之后，需要重新對(duì)每個(gè)hash值進(jìn)行尋址，也就是每個(gè)hash值跟新的數(shù)組length-1 進(jìn)行操作。

KeyA：
n-1:   0000 0000 0000 0000 0000 0000 000*1* 1111
hash1: 1111 1111 1111 1111 0000 1111 0000 0101
&結(jié)果:  0000 0000 0000 0000 0000 0000 0000 0101 = 5

KeyB:
n-1:   0000 0000 0000 0000 0000 000*1* 0000 1111 
hash1: 1111 1111 1111 1111 0000 1111 0001 0101
&結(jié)果:  0000 0000 0000 0000 0000 000*1* 0000 0101 = 21

判斷二進(jìn)制結(jié)果是否多出一個(gè)bit的1，如果沒有多，那就用原來(lái)的index，如果多出來(lái)了那就用index+oldCap，通過這個(gè)方式，避免了rehash的時(shí)候，用每個(gè)hash對(duì)新數(shù)組的length取模，取模性能不高，位運(yùn)算性能比較高。


網(wǎng)站標(biāo)題：深度！HashMap的底層數(shù)據(jù)結(jié)構(gòu)
網(wǎng)頁(yè)鏈接：http://www.5511xx.com/article/djjgeco.html