資訊專欄INFORMATION COLUMN
摘要：并且，我們的底層都是紅黑樹來實現的。紅黑樹是一種平衡二叉樹因此它沒有節點。
前言
聲明，本文用得是jdk1.8
前面已經講了Collection的總覽和剖析List集合：
Collection總覽
List集合就這么簡單【源碼剖析】
原本我是打算繼續將Collection下的Set集合的，結果看了源碼發現：Set集合實際上就是HashMap來構建的！
所以，就先介紹Map集合、散列表和紅黑樹吧！
看這篇文章之前最好是有點數據結構的基礎：
Java實現單向鏈表
棧和隊列就是這么簡單
二叉樹就這么簡單
當然了，如果講得有錯的地方還請大家多多包涵并不吝在評論去指正～
一、Map介紹 1.1為什么需要Map前面我們學習的Collection叫做集合，它可以快速查找現有的元素。
而Map在《Core Java》中稱之為-->映射..
映射的模型圖是這樣的：
那為什么我們需要這種數據存儲結構呢？？？舉個例子
作為學生來說，我們是根據學號來區分不同的學生。只要我們知道學號，就可以獲取對應的學生信息。這就是Map映射的作用！
生活中還有很多這樣的例子：只要你掏出身份證(key)，那就可以證明是你自己(value)
1.2Map與Collection的區別 1.3Map的功能下面我們來看看Map的源碼：
簡單常用的Map功能有這么一些：
下面用紅色框框圈住的就是Map值得關注的子類：
二、散列表介紹無論是Set還是Map，我們會發現都會有對應的-->HashSet,HashMap
首先我們也先得回顧一下數據和鏈表：
鏈表和數組都可以按照人們的意愿來排列元素的次序，他們可以說是有序的(存儲的順序和取出的順序是一致的)
但同時，這會帶來缺點：想要獲取某個元素，就要訪問所有的元素，直到找到為止。
這會讓我們消耗很多的時間在里邊，遍歷訪問元素~
而還有另外的一些存儲結構：不在意元素的順序，能夠快速的查找元素的數據
其中就有一種非常常見的：散列表
2.1散列表工作原理散列表為每個對象計算出一個整數，稱為散列碼。根據這些計算出來的整數(散列碼)保存在對應的位置上！
在Java中，散列表用的是鏈表數組實現的，每個列表稱之為桶。【之前也寫過桶排序就這么簡單，可以回顧回顧】
一個桶上可能會遇到被占用的情況(hashCode散列碼相同，就存儲在同一個位置上)，這種情況是無法避免的，這種現象稱之為：散列沖突
此時需要用該對象與桶上的對象進行比較，看看該對象是否存在桶子上了~如果存在，就不添加了，如果不存在則添加到桶子上
當然了，如果hashcode函數設計得足夠好，桶的數目也足夠，這種比較是很少的~
在JDK1.8中，桶滿時會從鏈表變成平衡二叉樹
如果散列表太滿，是需要對散列表再散列，創建一個桶數更多的散列表，并將原有的元素插入到新表中，丟棄原來的表~
裝填因子(load factor)決定了何時對散列表再散列~
裝填因子默認為0.75，如果表中超過了75%的位置已經填入了元素，那么這個表就會用雙倍的桶數自動進行再散列
當然了， 在后面閱讀源碼的時候會繼續說明的，現在簡單了解一下即可~
擴展閱讀：
https://www.cnblogs.com/s-b-b/p/6208565.html
https://www.cnblogs.com/chinajava/p/5808416.html
三、紅黑樹介紹上面散列表中已經提過了：如果桶數滿的時候，JDK8是將鏈表轉成紅黑樹的~。并且，我們的TreeSet、TreeMap底層都是紅黑樹來實現的。
所以，在這里學習一波紅黑樹到底是啥玩意。
之前涉及過二叉樹的文章：
二叉樹就這么簡單
堆排序就這么簡單
在未學習之前，我們可能是聽過紅黑樹這么一個數據結構類型的，還有其他什么B/B+樹等等，反正是比較復雜的數據結構了~~~
各種常見的樹的用途：
來源：
https://www.zhihu.com/question/30527705/answer/52527887
首先我們來回顧一下：利用二叉查找樹的特性，我們一般來說可以很快地查找出對應的元素。
二叉樹就這么簡單
可是二叉查找樹也有個例(最壞)的情況(線性)：
上面符合二叉樹的特性，但是它是線性的，完全沒樹的用處~
樹是要“均衡”才能將它的優點展示出來的~，比如下面這種：
因此，就有了平衡樹這么一個概念~紅黑樹就是一種平衡樹，它可以保證二叉樹基本符合矮矮胖胖(均衡)的結構
3.2知新2-3樹講到了平衡樹就不得不說最基礎的2-3樹，2-3樹長的是這個樣子：
在二叉查找樹上，我們插入節點的過程是這樣的：小于節點值往右繼續與左子節點比，大于則繼續與右子節點比，直到某節點左或右子節點為空，把值插入進去。這樣無法避免偏向問題
而2-3樹不一樣：它插入的時候可以保持樹的平衡！
在2-3樹插入的時可以簡單總結為兩個操作：
合并2-節點為3-節點，擴充將3-節點擴充為一個4-節點
分解4-節點為3-節點，節點3-節點為2-節點
........至使得樹平衡~
合并分解的操作還是比較復雜的，要分好幾種情況，代碼量很大~這里我就不介紹了，因為要學起來是一大堆的，很麻煩~
3.3從2-3樹到紅黑樹由于2-3樹為了保持平衡性，在維護的時候是需要大量的節點交換的！這些變換在實際代碼中是很復雜的，大佬們在2-3樹的理論基礎上發明了紅黑樹(2-3-4樹也是同樣的道理，只是2-3樹是最簡單的一種情況，所以我就不說2-3-4樹了)。
紅黑樹是對2-3查找樹的改進，它能用一種統一的方式完成所有變換。
紅黑樹是一種平衡二叉樹,因此它沒有3-節點。那紅黑樹是怎么將3-節點來改進成全都是二叉樹呢？
紅黑樹就字面上的意思，有紅色的節點，有黑色的節點：
我們可以將紅色節點的左鏈接畫平看看：
一顆典型的二叉樹：
將紅色節點的左鏈接畫平之后：得到2-3平衡樹:
3.4紅黑樹基礎知識前面已經說了，紅黑樹是在2-3的基礎上實現的一種樹，它能夠用統一的方式完成所有變換。很好理解：紅黑樹也是平衡樹的一種，在插入元素的時候它也得保持樹的平衡，那紅黑樹是以什么的方式來保持樹的平衡的呢？
紅黑樹用的是也是兩種方式來替代2-3樹不斷的節點交換操作：
旋轉：順時針旋轉和逆時針旋轉
反色：交換紅黑的顏色
這個兩個實現比2-3樹交換的節點(合并，分解)要方便一些
紅黑樹為了保持平衡，還有制定一些約束，遵守這些約束的才能叫做紅黑樹：
紅黑樹是二叉搜索樹。
根節點是黑色。
每個葉子節點都是黑色的空節點（NIL節點）。
每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點(每一條樹鏈上的黑色節點數量（稱之為“黑高”）必須相等)。
3.5紅黑樹總結紅黑樹可以說是十分復雜的，我在學習的時候并沒有去認真細看當中的處理細節，只是大概的過了一遍，知道了整體~
有了前輩很多優質的資料，相信要等到想要理解其中的細節，花點力氣和時間還是可以掌握一二的。
紅黑樹參考資料：
https://blog.csdn.net/chen_zhang_yu/article/details/52415077
https://riteme.github.io/blog/2016-3-12/2-3-tree-and-red-black-tree.html#fn:red-is-left
http://www.sohu.com/a/201923614_466939
https://www.jianshu.com/p/37c845a5add6
https://www.cnblogs.com/nullzx/p/6111175.html
https://blog.csdn.net/fei33423/article/details/79132930
四、總結這篇主要介紹了Map集合的基礎知識，了解Map的常用子類~
簡單介紹了散列表和紅黑樹，他倆作為Hashxxx和Treexxx的底層，了解其整體思想和相關基礎在后續看源碼也不至于那么懵~
后續會去看Map常用子類的源碼，文章敬請期待~~~~
文章的目錄導航：https://zhongfucheng.bitcron.com/post/shou-ji/gong-zhong-hao-wen-zhang-zheng-li
如果文章有錯的地方歡迎指正，大家互相交流。習慣在微信看技術文章，想要獲取更多的Java資源的同學，可以關注微信公眾號:Java3y。為了大家方便，剛新建了一下qq群：742919422，大家也可以去交流交流。謝謝支持了！希望能多介紹給其他有需要的朋友
參考資料：
《Core Java》
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68995.html
前言 聲明，本文用得是jdk1.8 前面已經講了Collection的總覽和剖析List集合以及散列表、Map集合、紅黑樹的基礎了： Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、散列表、紅黑樹介紹 本篇主要講解HashMap，以及涉及到一些與hashtable的比較~ 看這篇文章之前最好是有點數據結構的基礎： Java實現單向鏈表 棧和隊列就是這么簡單 二叉樹就...
摘要：下面總結一下集合常用的三個子類吧無序，允許為，底層是散列表紅黑樹，非線程同步有序，不允許為，底層是紅黑樹非線程同步迭代有序，允許為，底層是雙向鏈表，非線程同步從結論而言我們就可以根據自己的實際情況來使用了。 前言 聲明，本文用的是jdk1.8 前面章節回顧： Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、散列表、紅黑樹介紹 HashMap就是這么簡單【源碼...
摘要：哈希表哈希表是根據關鍵碼值而直接進行訪問的數據結構。這樣做的原因是和都是的次冪，并且是的倍，表示轉換為二進制的唯一一個向高位移位一次。 一、HashMap簡介 HashMap是基于拉鏈法實現的散列表。一般用于單線程程序中，JDK 1.8對HashMap進行了比較大的優化，底層實現由之前的數組+鏈表改為數組+鏈表+紅黑樹。下面先介紹HashMap中一些關鍵的知識點。 1、哈希表 哈希表是...
摘要：下面我來簡單總結一下的核心要點底層結構是散列表數組鏈表紅黑樹，這一點和是一樣的。是將所有的方法進行同步，效率低下。而作為一個高并發的容器，它是通過部分鎖定算法來進行實現線程安全的。 前言 聲明，本文用的是jdk1.8 前面章節回顧： Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、散列表、紅黑樹介紹 HashMap就是這么簡單【源碼剖析】 LinkedHas...
摘要：判斷該首節點是否與插入的鍵值對的和一致，若一致則替換該節點的值為，否則進入下一步判斷首節點是否為樹節點，若是則調用樹節點的方法遍歷紅黑樹，否則遍歷鏈表。中的方法會在鏈表超過樹化閾值的時候，將鏈表轉化為紅黑樹。 前言 由于Java 1.7和Java 1.8的HashMap的HashMap中的put()和get()方法在實現上差異很大，所以本文將于分別分析這兩個版本的put()和get()...
閱讀 889·2023-04-25 19:17
閱讀 2191·2021-09-10 11:26
閱讀 1906·2019-08-30 15:54
閱讀 3417·2019-08-30 15:53
閱讀 2685·2019-08-30 11:20
閱讀 3402·2019-08-29 15:12
閱讀 1237·2019-08-29 13:16
閱讀 2394·2019-08-26 12:19
