hashMap的數(shù)據(jù)結(jié)構(gòu)

眾所周知，java1.7的時(shí)候hashMap結(jié)構(gòu)還是【數(shù)組+鏈表】，而在1.8版本結(jié)構(gòu)變?yōu)榱恕緮?shù)組+鏈表/紅黑樹】，當(dāng)鏈表長度達(dá)到8時(shí)，自動(dòng)轉(zhuǎn)換為紅黑樹結(jié)構(gòu)。

那么為什么java1.8要對hashMap的數(shù)據(jù)結(jié)構(gòu)中加入樹呢？

答案：提高查找效率。此前hashMap中的數(shù)據(jù)采取【數(shù)組+鏈表】的存儲(chǔ)結(jié)構(gòu)，桶數(shù)組會(huì)將通過hash算法將key值計(jì)算得來的相同哈希值數(shù)據(jù)存儲(chǔ)在對應(yīng)的鏈表中，而隨著鏈表的數(shù)據(jù)增多，在檢索結(jié)點(diǎn)方面，性能會(huì)下降，因?yàn)殒湵黼m然插入刪除的時(shí)間復(fù)雜度是O(1)，但它遍歷的時(shí)間復(fù)雜度達(dá)到了O(n)。為了使得時(shí)間復(fù)雜度更優(yōu)，因此引入了樹形結(jié)構(gòu)，因?yàn)闃洳檎铱彀。?/p>

為什么那么多已經(jīng)存在的樹形結(jié)構(gòu)，比如二叉查找樹、平衡二叉樹，為啥還需要紅黑樹？

首先，我們已經(jīng)明確了，因?yàn)椴檎倚蕟栴}，hashMap的結(jié)構(gòu)中需要樹來提升性能。

而為什么不直接引入二叉查找樹，或者二叉平衡樹，這是因?yàn)樗麄冇心撤N方面的致命缺陷。

• 1、為了提高查找性能，引入二叉查找樹

二叉查找樹的特點(diǎn)：左結(jié)點(diǎn) < 根結(jié)點(diǎn) < 右結(jié)點(diǎn)

基于這個(gè)特點(diǎn)，查找某個(gè)節(jié)點(diǎn)的時(shí)候，可以采取類似于 二分查找的思想，快速找到某個(gè)節(jié)點(diǎn)，因此時(shí)間復(fù)雜度為O(log n)

但有一種極端情況需要考慮到：

這種情況也是滿足 二叉查找樹 的條件，然而，此時(shí)的二叉查找樹已經(jīng)近似退化為一條鏈表，這樣的二叉查找樹的查找時(shí)間復(fù)雜度頓時(shí)變成了 O(n)

• 2、為了解決二叉查找樹的極端情況下重新轉(zhuǎn)化為鏈表問題，引入平衡二叉樹

1、具有二叉查找樹的全部特性。

2、每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1。

針對二叉查找樹的缺點(diǎn)，我們考慮到可以引入二叉平衡樹，因?yàn)樗哂校鹤笥易訕涓叨认嗖钭疃嗖怀^1的特點(diǎn)。

這種情況雖然能解決上述問題，但又會(huì)引出其他的問題。因?yàn)槠胶舛鏄湟?每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1 ，這個(gè)要求實(shí)在是太嚴(yán)了，導(dǎo)致每次進(jìn)行插入/刪除節(jié)點(diǎn)的時(shí)候，幾乎都會(huì)破壞平衡樹的第二個(gè)規(guī)則，進(jìn)而我們都需要通過 左旋 和 右旋 來進(jìn)行調(diào)整，使之再次成為一顆符合要求的平衡樹。真是成也蕭何敗也蕭何呀！

那么，有沒有一種樹形結(jié)構(gòu)，既能在二叉查找樹上優(yōu)化左右子樹高度差，又能在二叉平衡樹上優(yōu)化其嚴(yán)苛的特性呢？

• 3、紅黑樹，一種非嚴(yán)格意義上平衡的二叉查找樹，完美解決問題。

紅黑樹，就是為了解決引入上述兩個(gè)樹帶來的問題而產(chǎn)生的，用以在結(jié)點(diǎn)查找和樹形旋轉(zhuǎn)的性能優(yōu)化中，尋求折中方案。

1、具有二叉查找樹的特點(diǎn)。

2、根節(jié)點(diǎn)是黑色的；

3、每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL），也就是說，葉子節(jié)點(diǎn)不存數(shù)據(jù)。

4、任何相鄰的節(jié)點(diǎn)都不能同時(shí)為紅色，也就是說，紅色節(jié)點(diǎn)是被黑色節(jié)點(diǎn)隔開的。

5、每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到達(dá)其可達(dá)的葉子節(jié)點(diǎn)是所有路徑，都包含相同數(shù)目的黑色節(jié)點(diǎn)。

正是由于紅黑樹的這種特點(diǎn)，使得它能夠在最壞情況下，也能在 O(logn) 的時(shí)間復(fù)雜度查找到某個(gè)節(jié)點(diǎn)。至于為什么就能夠保證時(shí)間復(fù)雜度為 O(logn)。

最后總結(jié)：

二叉查找樹是為了解決鏈表查找的性能問題，平衡二叉樹是為了解決二叉查找樹退化為鏈表的情況，而紅黑樹是為了解決平衡樹在插入、刪除等操作需要頻繁調(diào)整的情況。