前言

本章主要是講數(shù)據(jù)結(jié)構(gòu)與集合，這章內(nèi)容涉及到非常基礎(chǔ)的知識，內(nèi)容相對較多，首先從數(shù)組講起，引申到集合框架，之后再到集合源碼，最后介紹了高并發(fā)集合框架

成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)的開發(fā)，更需要了解用戶，從用戶角度來建設(shè)網(wǎng)站，獲得較好的用戶體驗。創(chuàng)新互聯(lián)建站多年互聯(lián)網(wǎng)經(jīng)驗，見的多，溝通容易、能幫助客戶提出的運營建議。作為成都一家網(wǎng)絡(luò)公司，打造的就是網(wǎng)站建設(shè)產(chǎn)品直銷的概念。選擇創(chuàng)新互聯(lián)建站，不只是建站，我們把建站作為產(chǎn)品，不斷的更新、完善，讓每位來訪用戶感受到浩方產(chǎn)品的價值服務(wù)。集合

集合在代碼中是collection，對應(yīng)英文為set，具有確定性，無序性，互異性的特點。java中的集合元素可以是有序的，也可以是重復(fù)的，與數(shù)學(xué)中的要求不同，這章的內(nèi)容都是指collection，用來保存各種對象的集合

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

• 定義：數(shù)據(jù)結(jié)構(gòu)是一種邏輯上的數(shù)據(jù)組織和處理方式，這里的邏輯意義很關(guān)鍵，以二叉樹為例，它不是像一顆樹形進行存儲，物理保存時是一個格子存一個節(jié)點；數(shù)據(jù)組織方式就是那些樹，圖，隊列，哈希之類，這些都是組織方式；處理方式指的是以特定的算法進行數(shù)據(jù)的增加，刪除，修改，查找和遍歷，這些不同的處理方式間會有性能差異
• 數(shù)據(jù)結(jié)構(gòu)的分類：數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)，如果有缺陷就會造成系統(tǒng)風(fēng)險高，可拓展性差，根據(jù)直接前后繼的角度可以把數(shù)據(jù)結(jié)構(gòu)分為以下四類
  1.線性結(jié)構(gòu)：0到1個直接前驅(qū)和后繼，非空時有唯一的首尾元素，包括順序表，鏈表，棧，隊列等
  2.樹結(jié)構(gòu)：0到1個直接前驅(qū)和0到n個直接后繼（n>=2）
  3.圖結(jié)構(gòu)：0到n個直接前驅(qū)和直接后繼
  4.哈希結(jié)構(gòu)：沒有直接前驅(qū)和后繼，通過哈希函數(shù)索引，查找效率很高
• 衡量數(shù)據(jù)處理性能：時間復(fù)雜度和空間復(fù)雜度，量級描述有
  
  
  實際場景中數(shù)據(jù)規(guī)模大了以后，算法性能差異會變得很明顯

集合框架圖

java集合是一種用于存儲對象的容器，提供增刪改查和遍歷方法，下圖為java中實際的集合框架圖

藍色是抽象類，紅色是接口，綠色是并發(fā)包里的類，灰色是一些線程安全的類，基本已經(jīng)棄用
其中最主要的就是四個：List，Set，Queue，Map

list集合

List是線性數(shù)據(jù)結(jié)構(gòu)，存在明確的前驅(qū)后繼元素，明確的首尾元素，遍歷結(jié)果穩(wěn)定，常用集合類有arraylist和linkedlist

• arraylist容量可改變，線程不安全，支持對元素快速隨機訪問，但插入刪除時很慢，因為需要移動元素
• linkedlist是雙向鏈表，相比arraylist，它插入刪除速度更快，但隨機訪問很慢，它繼承了AbstractList抽象類和Deque接口，Deque接口具有隊列和棧的性質(zhì)
  LinkedList有三個重要成員：size，first，last；size是節(jié)點個數(shù)，first指向頭節(jié)點，last指向最后一個節(jié)點，LinkedList的優(yōu)點在于把零散內(nèi)存單元關(guān)聯(lián)起來，提高了內(nèi)存利用率

Queue集合

Queue即隊列，是一種先進先出的線性表，兩端分別只能獲取和插入，沒有元素稱為空隊列
BlockingQueue阻塞隊列可在高并發(fā)的場景下作為數(shù)據(jù)緩沖區(qū)使用

Map集合

Map集合是以Key-value鍵值對存儲元素的哈希結(jié)構(gòu)，key不可重復(fù)，值可重復(fù)；
KeySet（）查看所有key，values（）查看所有value，entryset（）查看所有鍵值對，hashtable已經(jīng)被淘汰，HashMap線程不安全，ConcurrentHashMap線程安全，JDK8中對鎖進行了優(yōu)化，TreeMap是Key有序的Map集合,多線程并發(fā)中推薦使用ConcurrentHashMap而非HashMap

Set集合

元素不重復(fù)，常用HashSet，TreeSet和LinkedHashSet
HashSet是HashMap把Value固定住，用Key保證集合元素唯一性，不保證有序性
TreeSet是TreeMap實現(xiàn)，底層為樹結(jié)構(gòu)，插入時會比較保證有序性
LinkedHashSet繼承HashSet，有HashSet的優(yōu)點，內(nèi)部用鏈表保證元素插入順序

集合初始化

集合初始化需要分配容量，設(shè)置參數(shù)，比如ArrayList和HashMap，分別是順序表和哈希結(jié)構(gòu)，從源碼可以看到他們的初始化邏輯
ArrayList




這段代碼可以看出：

• 擴容時，可能超出int的大值，超出就返回原來的長度
  擴容時是利用位移運算，二進制下右移一位，再加到舊的長度上
  在JDK7之前，擴容方式是舊容量x3÷2+1,也就是1.5倍加1
  初始化時默認為10，那么第一次add后每次擴容都使用array.copyof，會創(chuàng)建一個新的數(shù)組再復(fù)制，如果是1000個元素，就會擴容13次，很影響性能，但如果初始化1000長度，就不需擴容，對于更大的值，甚至?xí)衞om風(fēng)險
• HashMap放1000個元素，需要擴容7次，擴容需要重建hash表，很影響性能，
  HashMap有兩個參數(shù)，Capacity和LoadFactor；Capacity決定存儲容量，默認16，LoadFactor決定填充比例，默認0.75，兩者之積是threshold，就是能放入的元素個數(shù)
  HashMap不會在new時分配，而是在第一次put時完成創(chuàng)建
  HashMap的容量大小為2的n次方，就是為了在運算時能充分散列，這塊詳細在之前的面試題里有講
  初始化ArrayList是10，HashMap是16，默認值最好是預(yù)估一個范圍，避免擴容造成的損耗

數(shù)組與集合

數(shù)組是一種順序表，下標(biāo)從0開始，這樣設(shè)計是為了方便計算偏移量，否則就要-1，提倡類型緊挨著中括號，比如int[]來定義數(shù)組,就相當(dāng)于定義數(shù)組對象
可以用兩種方法定義

args3是靜態(tài)初始化，args4是動態(tài)初始化，動態(tài)初始化new后面要給初始容量，動態(tài)數(shù)組有Vector和
Arraylist操作，分別是線程安全但性能差，線程不安全但使用頻繁
數(shù)組遍歷優(yōu)先推薦使用foreach方法，for（元素：數(shù)組名），可以不使用下標(biāo)
需要使用下標(biāo)可以用for循環(huán)，數(shù)組用length屬性獲取長度
也可以用jdk8的函數(shù)式接口遍歷

• 數(shù)組與集合的互相轉(zhuǎn)換：Arrays.asList （）可以把數(shù)組轉(zhuǎn)換為集合，但注意不能使用修改集合的方法，例如add/remove/clear,否則報Uns upportedOperationException異常，因為aslit方法是一種適配器模式，后臺數(shù)據(jù)仍是原有數(shù)組，set方法可以修改，但其他就會拋出異常
• 

如圖，這是arraylist的內(nèi)部類，實際返回的是這個類，它只實現(xiàn)了部分方法，這個異常由其父類拋出

實際業(yè)務(wù)中，為避免數(shù)組轉(zhuǎn)集合時添加元素引發(fā)異常，可以用java.util.arrayList直接創(chuàng)建一個新集合
，參數(shù)就是aslist方法返回的不可變集合

• 集合轉(zhuǎn)數(shù)組，相對更加可控，通常用于適配別人的數(shù)組接口，或者進行局部方法計算
  
  
  如圖，不要用toarray（）無參方法轉(zhuǎn)換集合，會導(dǎo)致泛型丟失
  也要注意數(shù)組容量是否分配足夠，書中實驗了不同容量對性能影響，結(jié)果如下
  
  可見，數(shù)組容量正好時，運行最快，使用toArray()時，注意兩點
  1，傳入類型完全一致的數(shù)組
  2.它的容量應(yīng)該為list.size()

集合和泛型

泛型用在集合上，有很強效果，但也要注意類型轉(zhuǎn)換異常

這種放入不同類型元素，轉(zhuǎn)換就會出現(xiàn)類型轉(zhuǎn)換異常

賦給object是可以的，也可以繼續(xù)添加不同類型的元素


但賦給integer后，再賦值不同類型就會不允許

這里問號在正則表達式里可以匹配任何字符，這個list也就可以接受任何類型引用賦值，可以remove和clear，但不可以添加元素，一般用作為參數(shù)接收外部集合或者返回未知類型的集合

• List只能放置一種類型，不能隨意轉(zhuǎn)換，如果需要放置多種受泛型約束的類型，則可以用＜？ extends T＞與＜？ super T＞，前者是get first，適合消費為主的集合，后者是put first，適合生產(chǎn)為主的集合
• 集合內(nèi)。
• 的操作。選舉代表時，你只能往里投選票，取數(shù)據(jù)時，根本不知道誰的票，相當(dāng)于泛型丟失；比如一些評價問卷，提交后不能再訪問鏈接修改評價
• 總結(jié)：extends put受限，super get 受限，如果經(jīng)常往出取的話，使用extends，經(jīng)常放的話，使用super

元素的比較

• comparable和comparator
  java元素的排序經(jīng)常用到比較，比較有兩個常用接口：Comparable和Comparator，分別用compare to和compare方法實現(xiàn)比較
  自然排序，也就是123，abc這種，Integer和String中實現(xiàn)的就是Comparable自然排序，有時需要自己定義排序規(guī)則，就可這樣做
  
  
  實現(xiàn)Comparable，可以加上泛型限定，這樣就可以在編譯期間檢查傳入?yún)?shù)是否是SearchResult對象，免去類型檢查和強轉(zhuǎn)，如果是封包類或者是開閉原則，就可以利用外部比較器，Comparator，代碼如下
  
  JDK中Arrays.sort的比較器參數(shù)排序就是Comparator實現(xiàn)的
  
  
  這里的是泛型限制為T及其父類，直到Object

兩個比較器返回值都是小于-1，等于0，大于1；在集合中比較器排序，直接使用正負返回比較結(jié)果

• 上面的TimSort方法是歸并排序加插入排序，避免了兩者缺點，減少了歸并次數(shù)，引入了二分排序概念，加快了效率，對于部分有序的數(shù)組，時間復(fù)雜度可達O（n），隨機排序數(shù)組則是nlogn，它主要有兩個優(yōu)化
  1.歸并排序的分段不再從單個元素開始，而是每次先查找大的有序數(shù)組片段run，然后利用二分排序，將該run與其他有序的run進行歸并
  2.引入二分排序，使得插入排序中每次不再從后向前比較，時間復(fù)雜度由n降低到nlogn

hashCode和equals

這兩個方法用來判斷兩個對象是否相同，通常協(xié)同工作，首先Object.hashcode生成哈希值，相同則進一步比較equals，不同則直接返回不同
如下是object類對這兩個方法的要求

如上是HashMap的get方法代碼判斷，先比較hash值，后執(zhí)行陰影部分，equals一般不要求hashcode相同，但hashcode散列充分，降低沖突，有利于提高執(zhí)行效率

如上是沒有重寫hashcode的案例，之后放到hashset里

本該結(jié)果是，但執(zhí)行結(jié)果是3，說明不重寫hashcode，重寫了equals毫無意義，如果想要存儲不重復(fù)元素，重寫hashcode版本如下

這個name是String類型，自帶hashcode重寫，直接調(diào)用即可

• equals的判定邏輯與類的具體情況有關(guān)，
  
  上面代碼的var就是動態(tài)類型，jdk10引入的語法糖，它會檢測右邊類型，并應(yīng)用于左側(cè)
  第2處可能拋出空指針npe異常，推薦使用jdk7自帶equals方法，代碼如下
  

上面這段代碼可以看出它是類型可變化的，也有類型限定格式

fail-fast機制

• fail-fast機制是一種錯誤檢測機制，主要用于遍歷集合元素過程中

• 書中舉了個例子，班長點全班同學(xué)的名，這里是遍歷的意思，然后有人進進出出，就老是需要重新點名，這就是fail-fast機制
  多線程時，維護一個expectedModCount，記錄已經(jīng)修改的次數(shù)，進入遍歷前把實時修改次數(shù)modCount付給eMC，如果兩個值不同就報異常

• java.util包下都是fail-fast，concurrent下都是fail-safe，failsafe就是相當(dāng)于班長直接拍照，然后用照片點名，不管進出

• 比如arraylist.sublist（），獲取子列表時，主列表的元素變化會引起子列表的遍歷和元素增刪，進而出現(xiàn)fail-fast異常
  
  如上代碼，通常比較常見的是修改子列表會影響父列表，但比較少見的是父列表改動會導(dǎo)致子列表操作異常
  subList返回Sublist類的對象，它是ArrayList的內(nèi)部類，沒有實現(xiàn)序列化接口，無法網(wǎng)絡(luò)傳輸

• 在foreach循環(huán)中測試fail-fast機制，如下

• 這段代碼運行沒有報異常，這是一個特例，因為游標(biāo)遍歷到size的時候，退出了遍歷，執(zhí)行remove后，size=size-1=2，這時cursor也等于2，執(zhí)行hasnext時值為false，也就不會執(zhí)行next（）的checkForComodification方法，這個方法就是用來判斷expectedMod和modcount的，不同會拋異常，都沒有執(zhí)行，也就不報異常

• 

• 為了避免刪除元素引起fail-fast，可以用Iteator進行遍歷時刪除，多線程并發(fā)時，還需要加鎖，如下

• - 也可以使用并發(fā)容器CopyOnWriteArrayList代替ArrayList，內(nèi)部對迭代器進行了加鎖操作
  它的原理是讀寫分離，在寫操作時分出一個新集合，在里面操作添加刪除，之后把原集合引用指向新集合，用COW的時候要注意1.設(shè)置合理初始值，擴容代價較大2.添加刪除可以攢一下，積累一些再操作，避免頻繁復(fù)制整個幾個，導(dǎo)致內(nèi)存占用，進而頻繁GC影響服務(wù)器性能
  如上代碼，20萬次循環(huán)數(shù)據(jù)插入花費了97.8秒，ArrayList只需39毫秒，這樣就得不償失了，所以COW只適合于讀多寫少的場景

• COW是fail-safe的，并發(fā)包中的集合都是這種機制實現(xiàn)的，也就是在安全的副本中遍歷，集合修改與副本遍歷無關(guān)，缺點就是讀取不到最新數(shù)據(jù)，這反映了一致性和可用性的矛盾

Map集合

Map是與Collection平級的一個借口，它也與Collection有關(guān)聯(lián)：部分方法比如values（）會返回Collection視圖，一個vaule的列表。Map集合的存儲單位是KV鍵值對，就是用哈希算法做一組比較均勻的Key，然后把Vaule掛在上面
特點有：
取代了Dictionary類，性能更好
Key不重復(fù)，Vaule可重復(fù)
Vaule可以試List，Map，Set類對象
KV是否允許為空，以實現(xiàn)類約束為準(zhǔn)

• Map接口除了crud，還有KeySet，values，EntrySet方法
• 在這里插入圖片描述
  
  這些返回的視圖支持刪除，但修改添加元素會報異常，因為AbstractCollection沒有add操作，但有remove，clear等操作
  這些集合類見證了java進化的過程，線程不安全到線程安全
  使用時，直接用ConcurrentHashMap代替HashMap大多數(shù)時間可行，性能差別不大，線程安全，但是盡量要避免設(shè)置KV為空值或者做好空值判斷，避免NPE

紅黑樹

首先介紹樹，樹是一種有限節(jié)點（結(jié)點）組成的層次集合，數(shù)據(jù)存在節(jié)點中，頂層的唯一節(jié)點稱為根節(jié)點，底層沒有分支的稱為葉子節(jié)點，。從某節(jié)點出發(fā)，到葉子節(jié)點為止，最長簡單路徑上的條數(shù)稱為該節(jié)點的高度，從根節(jié)點出發(fā)，到某節(jié)點邊的條數(shù)，稱為該節(jié)點的深度

這棵樹，根節(jié)點高度為5，深度為0，節(jié)點2的深度是1.高度是4
樹結(jié)構(gòu)有五個特點
( I ）一個節(jié)點，即使只有根節(jié)點，也可以是一棵樹。
( 2 ）其中任何一個節(jié)點與下方所有節(jié)點構(gòu)成的樹稱為子樹。
( 3 ）根節(jié)點沒有父節(jié)點，而子節(jié)點沒有父節(jié)點。
( 4 ）除根幣點外任何節(jié)點有且僅有個1父節(jié)點。
( 5 ）任何節(jié)點可以有0 ～ n 個子節(jié)點（0-n叉樹）。
在二叉樹世界中，最重要的是平衡二叉樹，二叉查找樹，紅黑樹

平衡二叉樹

如果把一棵樹的樹枝砍到只剩一條路徑，那么它就變成一個類似鏈表，約束一棵樹具有層次結(jié)構(gòu)，就是平衡二叉樹
平衡二叉樹的性質(zhì)如下
( 1 ）樹的左右高度差不能超過1。
( 2 ）任何往下遞歸的左子樹與右子樹，必須符合第一條性質(zhì)。
( 3 ）沒有任何節(jié)點的空樹或只有根節(jié)點的樹也是平衡二叉樹。

二叉查找樹

• 二叉查找樹又稱二叉搜索樹，BST（BinarySearchTree），或者Sort，二叉排序樹，節(jié)點的左子樹比它小，右子樹比它大。
  從根節(jié)點開始，大于往右，小于往左，直到葉子節(jié)點就是沒找到。
  遍歷所有節(jié)點的方法有三種：前序遍歷，中序遍歷，后序遍歷
  這些遍歷規(guī)律有：1.任何遍歷，左節(jié)點一定先于右節(jié)點2.前中后序，指的是根節(jié)點在遍歷序列中的位置
  前序就是根左右，中序就是左根右，后序就是左右根，下面這張圖非常直觀
  
  下面是一個普通樹轉(zhuǎn)換為二叉查找樹的過程，它的子樹也是查找樹
  
  二叉查找樹的元素有增刪時可能會失衡，比如用AVL樹，紅黑樹，SRB，樹堆就是用來解決這個問題的

AVL樹

avl樹是一種平衡二叉樹算法，可以讓二叉樹的使用效率大化，增刪元素后，就會通過旋轉(zhuǎn)重新達到平衡。
下圖展示了右旋和左旋的過程，一般是左長右短右旋，反之左旋，有一些右邊的左子樹失衡，需要lr或者rl旋轉(zhuǎn)，比較復(fù)雜

紅黑樹

72年發(fā)明了對稱二叉B樹，后來改名為紅黑樹，主要特征是每個節(jié)點有一個顏色屬性，紅或者黑色
紅黑樹也是插入刪除后進行旋轉(zhuǎn)保持平衡，但它的平衡不是左右高度差不大于1，而是從根節(jié)點到葉子節(jié)點的最長路徑不超過最短路徑的二倍
它有五個約束條件
1、節(jié)點都是紅或者黑色
2、根節(jié)點必須是黑色
3、所有NIL（葉子節(jié)點下掛的兩個虛節(jié)點）節(jié)點都是黑色
4、一條路徑不能有兩個紅節(jié)點相連
5、任何遞歸子樹中，根節(jié)點到葉子節(jié)點的黑節(jié)點數(shù)目相等
總結(jié)：有紅必有黑，紅紅不相連，這些條件的意義在于可以控制最壞時間復(fù)雜度為logn，紅黑樹任何旋轉(zhuǎn)均可在三次內(nèi)

紅黑樹與AVL樹相比

紅黑樹的黑深度滿足Black Depth小于等于 height / 2，也就是含有n個節(jié)點的紅黑樹，根節(jié)點高度一定小于2log2( n + l )
常規(guī)BST的操作，時間復(fù)雜度為h，取決于樹高度
紅黑樹平衡性不如AVL樹，它維持的是大致的平衡，而失衡時恢復(fù)也比avl更簡單，最差時間復(fù)雜度更低
結(jié)論：頻繁插入刪除時，紅黑樹更好；低頻修改，大量查詢時，AVL樹更好
如下圖是按順序插入36.34.37.33.35.32

可以看到紅黑樹不是絕對平衡的

TreeMap

TreeMap用Key的排序重新組織了Map的結(jié)構(gòu)，相比ConcurrentHashMap和HashMap，插入刪除效率降低了，但在要求Key排序的場景下，TreeMap更加高效，它與另外兩個都繼承與AbstractMap抽象類

TreeMap有繼承這兩個接口：SortedMap和NavigableMap，前者Key是有序不可重復(fù)的，插入Key時需要比較，所以key不可為空，value可空
NavigableMap接口繼承了繼承了SortedMap，根據(jù)搜索條件提供適合的KV元素，同時TreeMap可以不重寫Hashcode和equals來去重Key

上面的代碼hashmap下size是1，因為兩者使用的去重辦法不同，如果要用TreeMap要對Key排序，調(diào)用方法如下

Comparator為空則調(diào)用compareto方法，不為空調(diào)用compare方法
都不滿足就拋出異常：
TreeMap的crud操作的最好最壞時間復(fù)雜度均為（logn），特點是key有序


TreeMap通過put和deleteEntry方法實現(xiàn)紅黑樹的增刪節(jié)點操作，刪除類似插入，只講插入操作
需要調(diào)整的新節(jié)點一定是紅色的
插入的新節(jié)點是黑色的，無需調(diào)整
插入新節(jié)點是紅色的，由于紅黑樹不能紅紅相鄰，就要重著色，或者左右旋轉(zhuǎn)

根節(jié)點直接退出，設(shè)置為黑色即可，不是根節(jié)點且父節(jié)點是紅色，則一直調(diào)整直到退出循環(huán)
TreeMap的插入操作是正常比較，小于向左，按照二叉查找樹規(guī)則，無需關(guān)心顏色平衡，后續(xù)會調(diào)整

插入時要之前為非空樹并且新節(jié)點的Key和任何節(jié)點都不同，才能運行到FixAfterInsertion進行著色并且旋轉(zhuǎn)

后記

這篇字數(shù)已經(jīng)一萬三左右，后續(xù)寫在第二篇

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站標(biāo)題：《碼出高效：java開發(fā)手冊》六-數(shù)據(jù)結(jié)構(gòu)與集合（一）-創(chuàng)新互聯(lián)
文章網(wǎng)址：http://weahome.cn/article/djeidh.html