Hash

目前創(chuàng)新互聯(lián)公司已為近1000家的企業(yè)提供了網(wǎng)站建設(shè)、域名、雅安服務(wù)器托管、網(wǎng)站改版維護、企業(yè)網(wǎng)站設(shè)計、陵城網(wǎng)站維護等服務(wù)，公司將堅持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。Map 是日常開發(fā)中，用的最多的集 合類之一，也是面試中經(jīng)常被問到的 Java 類之一。同時，HashMap 在實現(xiàn)方式上面又有十分典型的范例。不管是從哪一方面來看，學(xué)習(xí) HashMap 都可以說是有利無害的。 分析 HashMap 的源碼的文章在網(wǎng)上面已經(jīng)數(shù)不勝數(shù)了，本文另辟蹊徑來分析 HashMap 的設(shè)計思想。 **底層數(shù)據(jù)結(jié)構(gòu)** 說到 HashMap 的數(shù)據(jù)庫，我們需要從兩個 JDK 版本來分析：JDK7 和 JDK8。 JDK7 版本的 HashMap 的數(shù)據(jù)結(jié)構(gòu)為：數(shù)組 + 鏈表。而 JDK8 版本的 HashMap 的數(shù)據(jù)結(jié)構(gòu)為： 數(shù)組 + 鏈表 + 紅黑樹?？梢钥吹?7 和 8 中 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)最主要的區(qū)別就是 Java8 多了紅黑樹。 **為何是數(shù)組加鏈表？** 上文中說到了 不管是 7 或者8 ，底層數(shù)據(jù)結(jié)構(gòu)都是 數(shù)組 + 鏈表，但這又是為什么呢？ 數(shù)組是一個鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)。put的時候，通過哈希函數(shù)將數(shù)據(jù)進行 哈希運算 之后，就得到數(shù)組的下標(biāo)，這樣子就可以將數(shù)據(jù)保存在對應(yīng)的槽中，這個槽在 HashMap 中被稱為 En try。在 get 時候，通過相同的哈希函數(shù)，將 key 進行哈希運算，可以得到對應(yīng)的下標(biāo)，就可以快速找到該 key 對應(yīng)的 value。這時候， get 的時間復(fù)雜度還是 O(1)。 但，哈希運算就避免不了有哈希沖突，也就說，不同的值通過哈希運算之后可能得到同一個值。在散列表的相關(guān)概念中，我們說了幾種解決哈希沖突的方案，在 HashMap中，則是采用了鏈表法。 也就是說，發(fā)生了沖突之后，我們在En try中形成一個單鏈表。但是這里有存在了一個問題，如果鏈表過長，檢索起來的效率同樣也會很低。于是，在 Java8 中，通過鏈表轉(zhuǎn)紅黑樹來解決這個問題。 **為何要加上紅黑樹** 為什么要鏈表轉(zhuǎn)紅黑樹，我們需要從數(shù)據(jù)結(jié)構(gòu)來解析。 如果從一個無序單鏈表中檢索數(shù)據(jù)，我們只能從頭到尾一個一個檢索，一旦數(shù)據(jù)量很大的情況下，檢索的效率就很低。這時，我們想到了紅黑樹，從目前的情況來看，紅黑樹能很好地解決這個問題。 我們先來看看紅黑樹的定義： 紅黑樹是每個節(jié)點都帶有顏色屬性 的二叉查找樹，顏色為紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求： - 節(jié)點是紅色或黑色。根是黑色。 - 所有葉子都是黑色（葉子是NIL節(jié)點）。 - 每個紅色節(jié)點必須有兩個黑色 的子節(jié)點。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。） - 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。 紅黑樹 要是紅黑樹，首先得是二叉查找樹： 二叉查找樹（英語：Binary Search Tree），也稱為二叉搜索樹、有序二叉樹（ordered binary tree）或排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質(zhì)的二叉樹： - 若任意節(jié)點的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值； - 若任意節(jié)點的右子樹不空，則右子樹上所有節(jié)點的值均大于或等于它的根節(jié)點的值； - 任意節(jié)點的左、右子樹也分別為二叉查找樹； 簡單做一個總結(jié)，紅黑樹的左節(jié)點要比父節(jié)點小，右節(jié)點要比父節(jié)點大。如果要檢索一個數(shù)字，可以將時間復(fù)雜度從 O(n) 降低到 O(logn)。 **當(dāng)然了，添加了紅黑樹的數(shù)據(jù)結(jié)構(gòu)之后，代碼實現(xiàn)要比 只用數(shù)組 + 鏈表要復(fù)雜了好幾倍?？创a的時候簡直是不能再痛苦了。** **什么時候轉(zhuǎn)成紅黑樹，有什么轉(zhuǎn)成鏈表** 在源碼中有這么一個字段，static final int TREEIFY_THRESHOLD = 8;，見字知義，這個字段的意思鏈表轉(zhuǎn)紅黑樹的閾值，也就是 8。同樣的，還有這么一個字段，static final int UN TREEIFY_THRESHOLD = 6;，它意思是紅黑樹轉(zhuǎn)鏈表的閾值。 為什么是 8 呢？在源碼的注釋中也有解釋，英文翻譯過來就是下面的意思。 鏈表查詢的時間復(fù)雜度是 O (n)，紅黑樹的查詢復(fù)雜度是 O (log n)。在鏈表數(shù)據(jù)不多的時候，使用鏈表進行遍歷也比較快，只有當(dāng)鏈表數(shù)據(jù)比較多的時候，才會轉(zhuǎn)化成紅黑樹，但紅黑樹需要的占用空間是鏈表的 2 倍，考慮到轉(zhuǎn)化時間和空間損耗，所以我們需要定義出轉(zhuǎn)化的邊界值。 在考慮設(shè)計 8 這個值的時候，我們參考了泊松分布概率函數(shù)，由泊松分布中得出結(jié)論，鏈表各個長度的命中概率為： ``` * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 ``` 意思是，當(dāng)鏈表的長度是 8 的時候，出現(xiàn)的概率是 0.00000006，不到千萬分之一，所以說正常情況下，鏈表的長度不可能到達 8 ，而一旦到達 8 時，肯定是 hash 算法出了問題，所以在這種情況下，為了讓 HashMap 仍然有較高的查詢性能，所以讓鏈表轉(zhuǎn)化成紅黑樹，我們正常寫代碼，使用 HashMap 時，幾乎不會碰到鏈表轉(zhuǎn)化成紅黑樹的情況，畢竟概念只有千萬分之一。 為什么兩個閾值不一樣的，大家想想，如果一樣的，在鏈表達到8 的時候，會轉(zhuǎn)成紅黑樹，但紅黑樹轉(zhuǎn)鏈表的閾值也是8，這時候就會出現(xiàn)循環(huán)轉(zhuǎn)換。 **鏈表轉(zhuǎn)紅黑樹還有一個條件，就是當(dāng)數(shù)組容量大于 64 時，鏈表才會轉(zhuǎn)化成紅黑樹** **擴容的條件** 在說擴容之前，先來說說 HashMap 在 7 和 8 中初始化時的不同表現(xiàn)。 在 Java 7 中，HashMap 初始化的時候，會有個默認(rèn)容量 （16）。但在 Java8 中，HashMap 初始化的時候，默認(rèn)容量為0，只有在第一次 put 的時候，才會擴容到 16。（其實 ArrayList 在 Java8 也是這么表現(xiàn)的）。 在 HashMap 源碼中，有一個字段定義 static final float DEFAULT_LOAD_FACTOR = 0.75f;。這個字段的意思是，當(dāng)HashMap 的長度 = HashMap 當(dāng)前容量 * 0.75的時候，就會發(fā)生擴容。 關(guān)于為什么負載因子是 0.75，我們可以在源碼注釋找到一定的答案。 load factor 大致意思就是說負載因子是0.75的時候，空間利用率比較高，而且避免了相當(dāng)多的Hash沖突，使得底層的鏈表或者是紅黑樹的高度比較低，提升了空間效率。 HashMap的擴容是變成原先容量的 2 倍。 **Hash函數(shù)** 我們先來看看 Java 8 的 hash 函數(shù)。 ``` static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>>16); } ``` 這里的大概意思就是，先計算出 key 的 hashCode h。然后計算計算 h ^ (h >>>16)。無符號右移16位。這么做的好處是使大多數(shù)場景下，算出來的 hash 值比較分散。 一般來說，hash 值算出來之后，要計算當(dāng)前 key 在數(shù)組中的索引下標(biāo)位置時，可以采用取模的方式，就是索引下標(biāo)位置 = hash 值 % 數(shù)組大小，這樣做的好處，就是可以保證計算出來的索引下標(biāo)值可以均勻的分布在數(shù)組的各個索引位置上，但取模操作對于處理器的計算是比較慢的，數(shù)學(xué)上有個公式，當(dāng) b 是 2 的冪次方時，a % b = a &（b-1），所以此處索引位置的計算公式我們可以更換為： (n-1) & hash。 此問題可以延伸出三個小問題： **1：為什么不用 key % 數(shù)組大小，而是需要用 key 的 hash 值 % 數(shù)組大小。** 答：如果 key 是數(shù)字，直接用 key % 數(shù)組大小是完全沒有問題的，但我們的 key 還有可能是字符串，是復(fù)雜對象，這時候用 字符串或復(fù)雜對象 % 數(shù)組大小是不行的，所以需要先計算出 key 的 hash 值。 **2：計算 hash 值時，為什么需要右移 16 位？** 答：hash 算法是 h ^ (h >>>16)，為了使計算出的 hash 值更分散，所以選擇先將 h 無符號右移 16 位，然后再于 h 異或時，就能達到 h 的高 16 位和低 16 位都能參與計算，減少了碰撞的可能性。高防服務(wù)器租用 **3：為什么把取模操作換成了 & 操作？** 答：key.hashCode() 算出來的 hash 值還不是數(shù)組的索引下標(biāo)，為了隨機的計算出索引的下表位置，我們還會用 hash 值和數(shù)組大小進行取模，這樣子計算出來的索引下標(biāo)比較均勻分布。 取模操作處理器計算比較慢，處理器對 & 操作就比較擅長，換成了 & 操作，什么叫軟文營銷？是有數(shù)學(xué)上證明的支撐，為了提高了處理器處理的速度。 **hash 沖突時怎么辦？** hash 沖突指的是 key 值的 hashcode 計算相同，但 key 值不同的情況。 - 如果桶中元素原本只有一個或已經(jīng)是鏈表了，新增元素直接追加到鏈表尾部； - 如果桶中元素已經(jīng)是鏈表，并且鏈表個數(shù)大于等于 8 時，此時有兩種情況： 如果此時數(shù)組大小小于 64，數(shù)組再次擴容，鏈表不會轉(zhuǎn)化成紅黑樹;如果數(shù)組大小大于 64 時，鏈表就會轉(zhuǎn)化成紅黑樹。 這里不僅僅判斷鏈表個數(shù)大于等于 8，還判斷了數(shù)組大小，數(shù)組容量小于 64 沒有立即轉(zhuǎn)化的原因，猜測主要是因為紅黑樹占用的空間比鏈表大很多，轉(zhuǎn)化也比較耗時，所以數(shù)組容量小的情況下沖突嚴(yán)重，我們可以先嘗試擴容，看看能否通過擴容來解決沖突的問題。 >【云棲號在線課堂】每天都有產(chǎn)品技術(shù)專家分享！ >課程地址：https://yqh.aliyun.com/live >立即加入社群，與專家面對面，及時了解課程最新動態(tài)！ >【云棲號在線課堂 社群】https://c.tb.cn/F3.Z8gvnK 原文發(fā)布時間：2020-07-08 本文作者：飛翔的竹蜻蜓 本文來自：“”，了解相關(guān)信息可以關(guān)注“掘金”

分享標(biāo)題：要看HashMap源碼，先來看看它的設(shè)計思想
本文路徑：http://www.rwnh.cn/article20/scoeco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、手機網(wǎng)站建設(shè)、靜態(tài)網(wǎng)站、ChatGPT、做網(wǎng)站、App設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)