HashMap中為什么引入紅黑樹，而不是AVL樹呢

1. 概述

開始學習這個知識點之前我們需要知道，在JDK1.8 以及之前，針對HashMap有什么不同。

• JDK 1.7的時候，HashMap的底層實現(xiàn)是數(shù)組 + 鏈表
• JDK1.8的時候，HashMap的底層實現(xiàn)是數(shù)組 + 鏈表 + 紅黑樹

我們要思考一個問題，為什么要從鏈表轉為紅黑樹呢。

首先先讓我們了解下鏈表有什么不好？？？

2. 鏈表

上述的截圖其實就是鏈表的結構，我們來看下鏈表的增刪改查的時間復雜度

• 增：因為鏈表不是線性結構，所以每次添加的時候，只需要移動一個節(jié)點，所以可以理解為復雜度是N(1)
• 刪：算法時間復雜度跟增保持一致
• 查：既然是非線性結構，所以查詢某一個節(jié)點的時候，最起碼要遍歷一遍，所以時間復雜度為O(n).

所以問題就來了，我們的目的就是優(yōu)化鏈表查詢效率，結果就是轉換數(shù)據結構，從而引出了我們的平衡二叉樹

3. 平衡二叉樹

平衡二叉樹是一種結構相對平衡的二叉搜索樹。既然是二叉樹結構，比較理想的狀態(tài)如上圖所示，節(jié)點分布相對平衡

但是還有一種情況：

這種也是一種平衡二叉樹的結構，而我們實際的業(yè)務中出現(xiàn)這種狀態(tài)概率很多，而那種理想的平衡二叉樹的狀態(tài)就很少。

所以我們?yōu)榱吮ＷC，如果生成一個平衡二叉樹，我們要求這個二叉樹無論有多少節(jié)點，都一定要保持相對平衡。

所以我們使用了紅黑樹來滿足這個需求