hashmap containsvalue时间复杂度_不看看HashMap源码，怎么和面试官谈薪资
HashMap 是日常開(kāi)發(fā)中，用的最多的集合類(lèi)之一，也是面試中經(jīng)常被問(wèn)到的 Java 類(lèi)之一。同時(shí)，HashMap 在實(shí)現(xiàn)方式上面又有十分典型的范例。不管是從哪一方面來(lái)看，學(xué)習(xí) HashMap 都可以說(shuō)是有利無(wú)害的。
分析 HashMap 的源碼的文章在網(wǎng)上面已經(jīng)數(shù)不勝數(shù)了，本文另辟蹊徑來(lái)分析 HashMap 的設(shè)計(jì)思想。
底層數(shù)據(jù)結(jié)構(gòu)
說(shuō)到 HashMap 的數(shù)據(jù)庫(kù)，我們需要從兩個(gè) JDK 版本來(lái)分析：JDK7 和 JDK8。
JDK7 版本的 HashMap 的數(shù)據(jù)結(jié)構(gòu)為：數(shù)組 + 鏈表。而 JDK8 ?版本的 HashMap 的數(shù)據(jù)結(jié)構(gòu)為：數(shù)組 + 鏈表 + 紅黑樹(shù)。可以看到 7 和 8 中 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)最主要的區(qū)別就是 Java8 多了紅黑樹(shù)。
為何是數(shù)組加鏈表
上文中說(shuō)到了 不管是 7 或者8 ，底層數(shù)據(jù)結(jié)構(gòu)都是 數(shù)組 + 鏈表，但這又是為什么呢？
數(shù)組是一個(gè)鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)。put時(shí)，通過(guò)特定的哈希算法將key映射成數(shù)組下標(biāo)，這樣子就可以將數(shù)據(jù)保存在對(duì)應(yīng)的槽中，這個(gè)槽在 HashMap 中被稱(chēng)為 Entry。在 get 時(shí)候，通過(guò)相同的哈希函數(shù)，將 key 進(jìn)行哈希運(yùn)算，可以得到對(duì)應(yīng)的下標(biāo)，就可以快速找到該 key 對(duì)應(yīng)的 value。這時(shí)候， get 的時(shí)間復(fù)雜度還是 O(1)。
但，哈希算法就避免不了有哈希沖突，不同的值通過(guò)哈希運(yùn)算之后可能得到同一個(gè)值。在散列表的相關(guān)概念中，介紹了幾種解決哈希沖突的方案，而HashMap就是使用的鏈表法。
在發(fā)生了哈希沖突之后，我們?cè)贓ntry中形成一個(gè)單鏈表。但是這里還存在了一個(gè)問(wèn)題，如果鏈表過(guò)長(zhǎng)，檢索起來(lái)的效率同樣也會(huì)很低。于是，在 Java8 中，通過(guò)鏈表轉(zhuǎn)紅黑樹(shù)來(lái)解決這個(gè)問(wèn)題。
為何要加上紅黑樹(shù)
為什么要鏈表轉(zhuǎn)紅黑樹(shù)，我們需要從數(shù)據(jù)結(jié)構(gòu)來(lái)解析。
如果從一個(gè)無(wú)序單鏈表中檢索數(shù)據(jù)，我們只能從頭到尾一個(gè)一個(gè)檢索，一旦數(shù)據(jù)量很大的情況下，檢索的效率就很低(O(n))。這時(shí)，我們想到了紅黑樹(shù)，從目前的情況來(lái)看，紅黑樹(shù)能很好地解決這個(gè)問(wèn)題(時(shí)間復(fù)雜度度為O(logn))。
我們先來(lái)看看紅黑樹(shù)的定義：
紅黑樹(shù)是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹(shù)，顏色為紅色或黑色。在二叉查找樹(shù)強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹(shù)我們?cè)黾恿巳缦碌念~外要求：
要是紅黑樹(shù)，首先得是二叉查找樹(shù)：
二叉查找樹(shù)(英語(yǔ)：Binary Search Tree)，也稱(chēng)為二叉搜索樹(shù)、有序二叉樹(shù)(ordered binary tree)或排序二叉樹(shù)(sorted binary tree)，是指一棵空樹(shù)或者具有下列性質(zhì)的二叉樹(shù)：
簡(jiǎn)單總結(jié)一下，紅黑樹(shù)的左節(jié)點(diǎn)要比父節(jié)點(diǎn)小，右節(jié)點(diǎn)要比父節(jié)點(diǎn)大。如果要檢索一個(gè)數(shù)字，可以將時(shí)間復(fù)雜度從 O(n) 降低到 O(logn)。
當(dāng)然了，添加了紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)之后，代碼實(shí)現(xiàn)要比 只用數(shù)組 + 鏈表要復(fù)雜了好幾倍。看代碼的時(shí)候簡(jiǎn)直是不能再痛苦了。
什么時(shí)候轉(zhuǎn)成紅黑樹(shù)，有什么轉(zhuǎn)成鏈表
在源碼中有這么一個(gè)字段，static final int TREEIFY_THRESHOLD = 8;，見(jiàn)字知義，這個(gè)字段的意思鏈表轉(zhuǎn)紅黑樹(shù)的閾值，也就是 8。同樣的，還有這么一個(gè)字段，static final int UNTREEIFY_THRESHOLD = 6;，它意思是紅黑樹(shù)轉(zhuǎn)鏈表的閾值。
這里還需要再注意一個(gè)字段static final int MIN_TREEIFY_CAPACITY = 64。這個(gè)字段意思是鏈表轉(zhuǎn)紅黑樹(shù)的最小數(shù)組大小，也就是說(shuō)只有在 **鏈表長(zhǎng)度大于8且數(shù)組長(zhǎng)度大于64的時(shí)候，鏈表才會(huì)轉(zhuǎn)成紅黑樹(shù)。**但在本節(jié)這不是重點(diǎn)，也就不多做闡述，大家只需要知道這肯定是為了性能就是了。
為什么是 8 呢？在源碼的注釋中也有解釋，英文翻譯過(guò)來(lái)就是下面的意思。
鏈表查詢(xún)的時(shí)間復(fù)雜度是 O (n)，紅黑樹(shù)的查詢(xún)復(fù)雜度是 O (log n)。在鏈表數(shù)據(jù)不多的時(shí)候，使用鏈表進(jìn)行遍歷也比較快，只有當(dāng)鏈表數(shù)據(jù)比較多的時(shí)候，才會(huì)轉(zhuǎn)化成紅黑樹(shù)，但紅黑樹(shù)需要的占用空間是鏈表的 2 倍，考慮到轉(zhuǎn)化時(shí)間和空間損耗，所以我們需要定義出轉(zhuǎn)化的邊界值。
在考慮設(shè)計(jì) 8 這個(gè)值的時(shí)候，我們參考了泊松分布概率函數(shù)，由泊松分布中得出結(jié)論，鏈表各個(gè)長(zhǎng)度的命中概率為：
* 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)鏈表的長(zhǎng)度是 8 的時(shí)候，出現(xiàn)的概率是 0.00000006，不到千萬(wàn)分之一，所以說(shuō)正常情況下，鏈表的長(zhǎng)度不可能到達(dá) 8 ，而一旦到達(dá) 8 時(shí)，肯定是 hash 算法出了問(wèn)題，所以在這種情況下，為了讓 HashMap 仍然有較高的查詢(xún)性能，所以讓鏈表轉(zhuǎn)化成紅黑樹(shù)，我們正常寫(xiě)代碼，使用 HashMap 時(shí)，幾乎不會(huì)碰到鏈表轉(zhuǎn)化成紅黑樹(shù)的情況，畢竟概念只有千萬(wàn)分之一。
為什么兩個(gè)閾值不一樣的，大家想想，如果一樣的，在鏈表達(dá)到8 的時(shí)候，會(huì)轉(zhuǎn)成紅黑樹(shù)，但紅黑樹(shù)轉(zhuǎn)鏈表的閾值也是8，這時(shí)候就會(huì)出現(xiàn)循環(huán)轉(zhuǎn)換。
擴(kuò)容的條件
對(duì)比 HashMap 在 7 和 8 中初始化，我發(fā)現(xiàn)兩個(gè)版本的初始化做的事情并不一樣。
在 Java 7 中，HashMap 初始化的時(shí)候，會(huì)有個(gè)默認(rèn)容量 (16)。但在 Java8 中，HashMap 初始化的時(shí)候，默認(rèn)容量為0，只有在第一次 put 的時(shí)候，才會(huì)擴(kuò)容到 16。
在 HashMap 源碼中，有一個(gè)字段定義 static final float DEFAULT_LOAD_FACTOR = 0.75f;。這個(gè)字段的意思是，當(dāng)HashMap 的長(zhǎng)度 = HashMap 當(dāng)前容量 * 0.75的時(shí)候，就會(huì)發(fā)生擴(kuò)容。
關(guān)于為什么負(fù)載因子是0.75，我們可以在源碼注釋找到一定的答案。
load factor大致意思就是說(shuō)負(fù)載因子是0.75的時(shí)候，空間利用率比較高，而且避免了相當(dāng)多的Hash沖突，使得底層的鏈表或者是紅黑樹(shù)的高度比較低，提升了空間效率。
最后，我們要知道HashMap的擴(kuò)容是變成原先容量的 2 倍。
Hash函數(shù)
我們來(lái)看看 Java 8 的 hash 函數(shù)。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }這里的大概意思就是，先計(jì)算出 key 的 hashCode h。然后計(jì)算計(jì)算 h ^ (h >>> 16)。無(wú)符號(hào)右移16位。這么做的好處是使大多數(shù)場(chǎng)景下，算出來(lái)的 hash 值比較分散。
一般來(lái)說(shuō)，hash 值算出來(lái)之后，要計(jì)算當(dāng)前 key 在數(shù)組中的索引下標(biāo)位置時(shí)，可以采用取模的方式，就是索引下標(biāo)位置 = hash 值 % 數(shù)組大小，這樣做的好處，就是可以保證計(jì)算出來(lái)的索引下標(biāo)值可以均勻的分布在數(shù)組的各個(gè)索引位置上，但取模操作對(duì)于處理器的計(jì)算是比較慢的，數(shù)學(xué)上有個(gè)公式，當(dāng) b 是 2 的冪次方時(shí)，a % b = a &(b-1)，所以此處索引位置的計(jì)算公式我們可以更換為：(n-1) & hash。
此問(wèn)題可以延伸出三個(gè)小問(wèn)題：
為什么不用 key % 數(shù)組大小，而是需要用 key 的 hash 值 % 數(shù)組大小。
如果 key 是數(shù)字，直接用 key % 數(shù)組大小是完全沒(méi)有問(wèn)題的，但我們的 key 還有可能是字符串，是復(fù)雜對(duì)象，這時(shí)候用 字符串或復(fù)雜對(duì)象 % 數(shù)組大小是不行的，所以需要先計(jì)算出 key 的 hash 值。
計(jì)算 hash 值時(shí)，為什么需要右移 16 位？
hash 算法是 h ^ (h >>> 16)，為了使計(jì)算出的 hash 值更分散，所以選擇先將 h 無(wú)符號(hào)右移 16 位，然后再于 h 異或時(shí)，就能達(dá)到 h 的高 16 位和低 16 位都能參與計(jì)算，減少了碰撞的可能性。
為什么把取模操作換成了 & 操作？
key.hashCode() 算出來(lái)的 hash 值還不是數(shù)組的索引下標(biāo)，為了隨機(jī)的計(jì)算出索引的下表位置，我們還會(huì)用 hash 值和數(shù)組大小進(jìn)行取模，這樣子計(jì)算出來(lái)的索引下標(biāo)比較均勻分布。
取模操作處理器計(jì)算比較慢，處理器對(duì) & 操作就比較擅長(zhǎng)，換成了 & 操作，是有數(shù)學(xué)上證明的支撐，為了提高了處理器處理的速度。
hash 沖突時(shí)怎么辦？
hash 沖突指的是 key 值的 hashcode 計(jì)算相同，但 key 值不同的情況。
如果桶中元素原本只有一個(gè)或已經(jīng)是鏈表了，新增元素直接追加到鏈表尾部；
如果桶中元素已經(jīng)是鏈表，并且鏈表個(gè)數(shù)大于等于 8 時(shí)，此時(shí)有兩種情況：
這里不僅僅判斷鏈表個(gè)數(shù)大于等于 8，還判斷了數(shù)組大小，數(shù)組容量小于 64 沒(méi)有立即轉(zhuǎn)化的原因，猜測(cè)主要是因?yàn)榧t黑樹(shù)占用的空間比鏈表大很多，轉(zhuǎn)化也比較耗時(shí)，所以數(shù)組容量小的情況下沖突嚴(yán)重，我們可以先嘗試擴(kuò)容，看看能否通過(guò)擴(kuò)容來(lái)解決沖突的問(wèn)題。
總結(jié)
以上是生活随笔為你收集整理的hashmap containsvalue时间复杂度_不看看HashMap源码，怎么和面试官谈薪资的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 马踏过河卒
- 下一篇： 电脑开机启动修复无法自动修复此计算机,W