TreeMap源碼分析 紅黑樹

今天嘗試刨一下TreeMap的祖墳。

底層結構對比

先來看一下與HashMap、LinkedHashMap和TreeMap的對比，同時就當是復習一下：

  1. HashMap使用數組存儲數據，并使用單向鏈表結構存儲hash沖突數據，同一個沖突桶中數據量大的時候（默認超過8）則使用紅黑樹存儲沖突數據。
  2. LinkedHashMap使用數組+雙向鏈表存儲數據，沖突數據存儲方式同HashMap。
  3. TreeMap使用紅黑樹存儲數據，注意是直接使用紅黑樹，不使用table數組。

關于排序特性

  1. HashMap無順序，不能保持順序。
  2. LinkedHashMap能保持寫入的順序，遍歷的時候可以按照寫入順序獲取數據。
  3. TreeMap是有序的Map，自動按照key值排序存儲，遍歷時獲取到的是有序數據。

需要注意LinkedHashMap和TreeMap在順序方面的區別，LinkedHashMap只能保持寫入順序，從“排序”的角度講，他實際是無序的。

只有TreeMap是可以實現自動排序的。

TreeMap按照什么排序？

TreeMap底層支持兩種排序方式：

  1. TreeMap對象實例化時傳入comparator對象。
  2. key值對象實現Comparable接口。

如果以上兩點都不能滿足的話，向TreeMap對象put數據的時候會拋出運行時異常。

比如TreeMap<String,Object>，由于String實現了Comparable接口，所以是沒有問題的。

但是如果自定義的對象，沒有實現Comparable接口，同時在TreeMap實例化的時候沒有設置comparator對象，則該TreeMap對象實際是不可用的。

TreeMap是否可以存儲null？

指的是，是否可以存儲key為空的數據？我們知道HashMap是可以支持唯一一個null對象的。

很多人都說不可以，但是我覺得有條件可以，但是沒做測試（因為感覺則個問題其實有點扯）。

條件是實例化TreeMap對象的時候指定comparator對象，同時，該comparator對象的compare方法可以支持null。

研究TreeMap的put源碼，也可以發現對以上說法的支持：

Comparator<? super K> cpr = comparator;if (cpr != null) {do {parent = t;cmp = cpr.compare(key, t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}else {if (key == null)throw new NullPointerException();...省略若干代碼

可以發現如果有comparator的話，put方法不會立即拋出異常。但是如果comparator對象的compare方法不能支持null的話，一樣會拋出異常。

put方法

由于TreeMap支持自動排序，所以put方法會檢查是否滿足規則。

不滿足排序規則，拋出異常。

否則，按照紅黑樹算法規則要求，創建紅黑樹，存儲數據。

所以這里就涉及到一個重要的數據結構：紅黑樹。

二叉樹BST & 平衡二叉樹AVL

紅黑樹是樹結構的一種，是比二叉樹和平衡二叉樹更加復雜的一種數據結構。所以我們先從簡單的入手，了解一下二叉樹。

樹結構其實是實現了子排序的一種數據結構，我們說到的樹結構一般指的是二叉樹、也叫二叉搜索樹（BST - Binary Search Tree），定義：它或者是一棵空樹，或者是具有下列性質的二叉樹： 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 它的左、右子樹也分別為二叉排序樹。

二叉搜索樹的插入、搜索操作所花的時間都和樹的高度成正比。因此，如果共有n個元素，那么平均每次操作需要O(logn)的時間。

二叉搜索樹的特性并不能保證他是平衡的，也就是說，極端情況下，一顆二叉搜索樹從根節點開始，只有左節點、沒有右節點（比如一直按照從大到小或者相反順序插入二叉樹），這種情況下，二叉樹就蛻變成了鏈表，查詢時間復雜度就會下降為O(n)。

改善二叉樹這一缺點的經典數據結構是平衡二叉樹AVL（Adelson-Velsky and Landis Tree，以兩位發明者命名）。平衡二叉樹的特性：

1.本身首先是一棵二叉搜索樹。
2.帶有平衡條件：每個結點的左右子樹的高度之差的絕對值（平衡因子）最多為1。

一顆平衡二叉樹在新節點插入之后可能會失衡，包括以下四種場景：

左左失衡LL

插入的數據在左側不平衡樹的左側，這種情況下需要進行右旋操作再次平衡：
在這里插入圖片描述
我們需要記住一個概念：平衡二叉樹失衡之后通過旋轉動作使得它再次平衡的處理，只是針對失衡的子樹、不需要對整個樹進行操作。比如上圖新的節點1加入之后，導致pivot節點7一側的樹失衡，我們需要處理的是包含pivot節點的root節點的左側樹這一部分子樹，右側節點18下即使有再多的節點，也不需要處理。

右旋操作的實質是：以pivot節點7為支點做順時針旋轉，旋轉之后7變為自己原來父節點的父節點、7的左節點不變，7的右節點變為7原來的父節點的左節點。

右右失衡RR

插入的節點在右側不平衡樹的右側，這種情況下需要左旋：
在這里插入圖片描述
左旋操作的實質是：以pivot節點18為支點做逆時針旋轉，旋轉之后18變為自己原來父節點的父節點、18的右節點不變，18的左節點變為18原來的父節點的右節點。

左右失衡LR

插入的新節點在左側不平衡樹的右側。先左旋再右旋
在這里插入圖片描述

右左失衡LR

插入的節點在右側不平衡樹的左側，先右旋再左旋：
在這里插入圖片描述
平衡二叉樹具有：每個結點的左右子樹的高度之差的絕對值（平衡因子）最多為1 這一特性，這一嚴格條件會導致每次插入新節點之后總會大概率破壞平衡、從而必須要通過上述的旋轉操作使其再次達到平衡，旋轉操作會影響數據插入的效率。

紅黑樹可以解決這一問題。

紅黑樹

紅黑樹是一種帶顏色（節點是紅色或者黑色）的平衡二叉樹，具有以下特性：
性質1. 結點是紅色或黑色。
性質2. 根結點是黑色。
性質3. 所有葉子都是黑色。（葉子是NIL結點）
性質4. 每個紅色結點的兩個子結點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的紅色結點）
性質5. 從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點。

紅黑樹新加入節點的顏色默認為黑色，因為根據紅黑樹性質4，每個紅色節點的兩個子節點都是黑色。所以，新加入節點如果是黑色的話，可以檢查其父節點如果是紅色的話，可以自動滿足性質4從而減少再平衡操作、提高數據加入的效率。這一點可以通過TreeMap的put方法源碼得到驗證：

public V put(K key, V value) {Entry<K,V> t = root;if (t == null) {compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;if (cpr != null) {do {parent = t;cmp = cpr.compare(key, t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}else {if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;do {parent = t;cmp = k.compareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;fixAfterInsertion(e);size++;modCount++;return null;}

put方法前半部分邏輯比較簡單，為新節點找到合適的位置加入，之后會調用fixAfterInsertion檢查是否破壞了紅黑樹的規則從而需要執行再平衡操作：

private void fixAfterInsertion(Entry<K,V> x) {x.color = RED;while (x != null && x != root && x.parent.color == RED) {if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {Entry<K,V> y = rightOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateRight(parentOf(parentOf(x)));}} else {Entry<K,V> y = leftOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == leftOf(parentOf(x))) {x = parentOf(x);rotateRight(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateLeft(parentOf(parentOf(x)));}}}root.color = BLACK;}

fixAfterInsertion方法首先判斷其父節點是紅色的話，則不做任何操作。

get方法

根據紅黑樹查找算法查找并返回數據，紅黑樹是平衡二叉樹，查詢時間復雜度為O(log(n))。

key遍歷

比如調用TreeMap.keySet方法，采用遍歷二叉樹算法，按照從小到大的順序返回所有key值組成的循環器。

我該使用哪一個？

需要用到Map的時候，到底該使用哪一個的問題：

  1. 我只需要一個存儲數據的容器，沒有具體要求的話，用HashMap。
  2. 存儲數據后，有按照存儲順序獲取數據的需求，采用LinkedHashMap。
  3. 希望存儲數據的同時，幫助實現自動排序，采用TreeMap。

性能的問題，其實幾乎不需要考慮，不過我們還是需要知道：

  1. HashMap和LinkedHashMap查詢速度快，理想情況下時間復雜度幾乎是O(1)。
  2. HashMap寫入速度最快，LinkedHashMap寫入速度與HashMap幾乎相同，TreeMap寫入速度最慢（理論上，實際數據量小的情況下未必慢）。
  3. 遍歷速度相差無幾，理論上HashMap會慢一點，因為需要遍歷空桶。

并發問題尚待研究，但是我們清楚地知道，以上三種均不具備線程安全性。

好夢！

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/89033.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/89033.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/89033.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

華為云Flexus+DeepSeek征文｜基于Dify構建拍照識題智能學習助手

華為云Flexus+DeepSeek征文｜基于Dify構建拍照識題智能學習助手

華為云FlexusDeepSeek征文&#xff5c;基于Dify構建拍照識題智能學習助手 一、構建拍照識題智能學習助手前言二、構建拍照識題智能學習助手環境2.1 基于FlexusX實例的Dify平臺2.2 基于MaaS的模型API商用服務 三、構建拍照識題智能學習助手實戰3.1 配置Dify環境3.2 配置Dify工具…
閱讀更多...
題解：CF2120E Lanes of Cars

題解：CF2120E Lanes of Cars

根據貪心&#xff0c;不難想到每次會把最長隊伍末尾的那輛車移動到最短隊伍的末尾。但由于 k k k 的存在&#xff0c;會導致一些冗余移動的存在。設需要挪動 C C C 輛車&#xff0c;則怒氣值可以表示為 f ( C ) k C f(C) kC f(C)kC&#xff0c;其中 f ( C ) f(C) f(C) 是…
閱讀更多...
Excel基礎：選擇和移動

Excel基礎：選擇和移動

本文演示Excel中基礎的選擇和移動操作&#xff0c;并在最后提供了一張思維導圖&#xff0c;方便記憶。 文章目錄 一、選擇1.1 基礎選擇1.1.1 選擇單個單元格1.1.2 選擇連續范圍 1.2 行列選擇1.2.1 選擇整行整列1.2.2 選擇多行多列 1.3 全選1.3.1 全選所有單元格1.3.2 智能選擇…
閱讀更多...
Java面試寶典：基礎四

Java面試寶典：基礎四

80. int vs Integer 維度intInteger類型基本數據類型（8種之一）包裝類默認值0null應用場景性能敏感場景（計算密集）Web表單、ORM框架（區分null和0）特殊能力無提供工具方法（如parseInt()）和常量（如MAX_VALUE）示例：
閱讀更多...
RabbitMQ + JMeter 深度集成指南：中間件性能優化全流程解析！

RabbitMQ + JMeter 深度集成指南：中間件性能優化全流程解析！

在 2025 年的數字化浪潮中&#xff0c;中間件性能直接決定系統的穩定性和用戶體驗&#xff0c;而 RabbitMQ 作為消息隊列的“老大哥”&#xff0c;在分布式系統中扮演著關鍵角色。然而&#xff0c;高并發場景下&#xff0c;消息堆積、延遲激增等問題可能讓系統不堪重負&#xf…
閱讀更多...
uniapp image引用本地圖片不顯示問題

uniapp image引用本地圖片不顯示問題

1. uniapp image引用本地圖片不顯示問題 在uniapp 開發過程中采用image引入本地資源圖片。 1.1. 相對路徑和絕對路徑問題 在UniApp中開發微信小程序時&#xff0c;引入圖片時&#xff0c;相對路徑和絕對路徑可能會有一些差異。這差異主要涉及到小程序和UniApp框架的文件結構、…
閱讀更多...
論文閱讀：arxiv 2025 ThinkSwitcher: When to Think Hard, When to Think Fast

論文閱讀：arxiv 2025 ThinkSwitcher: When to Think Hard, When to Think Fast

總目錄 大模型安全相關研究&#xff1a;https://blog.csdn.net/WhiffeYF/article/details/142132328 ThinkSwitcher: When to Think Hard, When to Think Fast https://arxiv.org/pdf/2505.14183#page2.08 https://www.doubao.com/chat/10031179784579842 文章目錄 速覽一、…
閱讀更多...
智能體記憶原理-prompt設計

智能體記憶原理-prompt設計

智能體記憶的管理與設計開發分為以下幾步&#xff1a; 1.記憶的抽取&#xff1b; 2.記憶的存儲&#xff1b; 3.記憶的搜索&#xff1b; 一、記憶抽取一&#xff1a; FACT_RETRIEVAL_PROMPT f"""你是一位個人信息整理助手&#xff0c;專門負責準確存儲事實、用…
閱讀更多...
026 在線文檔管理系統技術架構解析：基于 Spring Boot 的企業級文檔管理平臺

026 在線文檔管理系統技術架構解析：基于 Spring Boot 的企業級文檔管理平臺

在線文檔管理系統技術架構解析&#xff1a;基于Spring Boot的企業級文檔管理平臺 在企業數字化轉型的進程中&#xff0c;高效的文檔管理系統已成為提升協作效率的核心基礎設施。本文將深入解析基于Spring Boot框架構建的在線文檔管理系統&#xff0c;該系統整合公告信息管理、…
閱讀更多...
AWTK-MVVM的一些使用技巧總結（1）

AWTK-MVVM的一些使用技巧總結（1）

在項目中用了一段時間的AWTK-MVVM框架&#xff0c;由于AWTK-MVVM本身的文檔十分欠缺&#xff0c;自己經過一段時間的研究折騰出了幾個技巧&#xff0c;在此記錄總結。 用fscript啟用傳統UI代碼 AWTK-MVVM里面重新設計了navigator機制&#xff0c;重定位了navigator_to的調用方…
閱讀更多...
openwrt使用quilt工具制作補丁

openwrt使用quilt工具制作補丁

前言&#xff1a;簡單聊一下為什么需要制作補丁&#xff0c;因為openwrt的編譯是去下載很多組件放到dl目錄下面&#xff0c;這些組件都是壓縮包。如果我們要修改這些組件里面的源碼&#xff0c;就需要對這些組件打pacth&#xff0c;也就是把我們的差異點在編譯的時候合入到對應…
閱讀更多...
強化學習 （1）基本概念

強化學習 （1）基本概念

grid-world example 一個由多個格子組成的二維網格 三種格子&#xff1a;accessible可通行的&#xff1b; forbidden禁止通行的&#xff1b; target目標 state狀態 state是智能體相對于環境的狀態&#xff08;情況&#xff09; 在grid-world example里&#xff0c;state指的…
閱讀更多...
【Typst】縱向時間軸

【Typst】縱向時間軸

概述 6月10日實驗了一個縱向時間軸排版效果&#xff0c;當時沒有做成單獨的模塊&#xff0c;也存在一些Bug。 今天(6月29日)在原基礎上進行了一些改進&#xff0c;并總結為模塊。 目前暫時發布出來&#xff0c;可用&#xff0c;后續可能會進行大改。 使用案例 導入模塊使用…
閱讀更多...
【Visual Studio Code上傳文件到服務器】

【Visual Studio Code上傳文件到服務器】

在 Visual Studio Code (VS Code) 中上傳文件到 Linux 系統主要通過 SSH 協議實現&#xff0c;結合圖形界面&#xff08;GUI&#xff09;或命令行工具操作。以下是具體說明及進度查看、斷點續傳的實現方法&#xff1a; ?? 一、VS Code 上傳文件到 Linux 的機制 SSH 遠程連接 …
閱讀更多...
手機控車一鍵啟動汽車智能鑰匙

手機控車一鍵啟動汽車智能鑰匙

手機一鍵啟動車輛的方法 手機一鍵啟動車輛是一種便捷的汽車啟動方式&#xff0c;它通過智能手機應用程序實現對車輛的遠程控制。以下是詳細的步驟&#xff1a; 完成必要的認證與激活步驟。打開手機上的相關移動管家手機控車APP&#xff0c;并與車載藍牙建立連接。在APP的主界面…
閱讀更多...
基于深度學習的語音增強技術：時間增強多尺度頻域卷積網絡模型解析

基于深度學習的語音增強技術：時間增強多尺度頻域卷積網絡模型解析

基于深度學習的語音增強技術&#xff1a;時間增強多尺度頻域卷積網絡模型解析 近年來&#xff0c;隨著語音處理技術的不斷發展&#xff0c;語音增強&#xff08;Speech Enhancement&#xff09;逐漸成為研究熱點。語音增強的主要目標是通過消除噪聲和改善信噪比來提高語音質量…
閱讀更多...
計算機組成原理-數據表示與運算（三）

計算機組成原理-數據表示與運算（三）

### 文字提取結果&#xff1a; #### 題目內容&#xff1a; 34. 【2009 統考真題】浮點數加、減運算過程一般包括對階、尾數運算、規格化、舍入和判斷溢出等步驟。設浮點數的階碼和尾數均采用補碼表示&#xff0c;且位數分別為 5 和 7&#xff08;均含 2 位符號位&#xff09;。…
閱讀更多...
Learning Fully Convolutional Networks for Iterative Non-blind Deconvolution論文閱讀

Learning Fully Convolutional Networks for Iterative Non-blind Deconvolution論文閱讀

Learning Fully Convolutional Networks for Iterative Non-blind Deconvolution 1. 研究目標與實際問題1.1 研究目標1.2 實際意義2. 創新方法與模型設計2.1 核心框架：迭代式梯度域處理2.1.1 模型架構2.2 關鍵技術實現2.2.1 梯度域去噪網絡2.2.2 解卷積模塊（核心公式實現）2.…
閱讀更多...
Vue3——組件傳值

Vue3——組件傳值

父傳子 props ——最推薦的方法&#xff08;TOP1級別&#xff09; 父組件文件 <sidebar :text"textname" ></sidebar> //父組件通過 :text 將父組件的數據textname傳遞給子組件 const textname:Ref<dataFather[]> ref([{name:劉亦菲,age:18 },…
閱讀更多...
DOP數據開放平臺(真實線上項目)

DOP數據開放平臺(真實線上項目)

什么是數據開放平臺&#xff1f; 數據開放平臺是一種通過公開應用程序編程接口&#xff08;API&#xff09;或結構化數據&#xff0c;允許第三方開發者或機構訪問、使用和共享數據的平臺?&#xff0c;旨在促進數據流通、打破信息孤島并激發創新應用。 DOP數據開放平臺簡單演示…
閱讀更多...
最新文章

Copyright @ 2022~2023