一篇了解三大集合的特點

集合

集合的前提：資料結構

1. 動态數組

   

   特點：查詢和修改開，增加和删除相對較慢

   特殊點：數組的初始長度預設為10，如果長度不夠了，則會建立一個新的長度，然後通過copy方法把原有的資料搬到新的數組中，這個過程成為擴容。擴容的擴容算法就是(目前數組長度*3)/2+1

   為什麼查改快、增删慢？

   因為數組有下标，我們可以通過下标直接找到；

   因為我們的數組是一個連續的塊型記憶體，增加和删除都是要改變數組的長度，進而使得後面的資料都需要進行移動，他就是慢在這個移動資料上

2. 連結清單

特點：增加删除快，查詢和修改慢

為什麼增删快，修改慢？

因為連結清單中的資料隻需要指向下一個資料就可以了，是以查詢和修改的方式就需要從頭開始挨個找，

增删就是隻需要修改一下上一個的指向修改資料和修改資料指向下一個即可，如果修改資料時删除的話，就直接上一個指向下一個

1. 紅黑樹

簡介：紅黑樹是一個平衡二叉查找樹，此處需要你去百度了解一下紅黑樹的

紅黑樹特性：

特性1：每個節點要麼紅色要麼黑色

特性2：最上面的節點叫根節點，是黑色的

特性3：每個葉子節點如果為Nil就是黑色的

特性4：紅色的子節點一定是黑色

特性5：任意一個節點到每個葉子節點的路徑都包含同數量的黑色節點

1. 哈希表(hash表)

   

   特點：增删改查性能都很好的一種資料結構

   哈希表在JDK8前，采用的數組+連結清單的形式

   JDK8後，采用數組+連結清單+紅黑樹的形式

   哈希表存儲：根據對象位址計算的int類型的值進行存儲

集合分為三種

List、Set和Map

其中List和Set繼承了java.utils.Collection接口，而map則是java.utils.map

List

list的顯著特點就是 添加元素是有序，可重複，有索引

常用子類：ArrayList、LinkedList

ArrayList：底層資料結構是數組，查詢快，增删滿，且線程不安全，效率高

LinkedList：底層資料結構是連結清單，查詢慢，增删快，且線程不安全，效率高

Vector：底層資料結構是數組，查詢快，增删慢，且線程安全，效率低

對比

Vector和ArrayList差別

相同：底層資料結構都是數組

不同：Vector因為是線程安全的，是以效率低

​ ArrayList因為線程不安全，是以效率高

ArrayList和LinkedList的差別

ArrayList：底層數組，查詢快，增删慢 線程不安全

LinkedList：底層連結清單，增删快，查改慢 線程安全

如果需要線程安全：

可以用Collections工具類中的synchronizeList為ArrayList加鎖，進而變成線程安全的

LinkedList也同上

當然，我們亦可以使用java.util.concurrent下的CopyOnWriteArrayList替代Arraylist

Set

特點：添加元素無序、不重複，無索引

常用：HashSet、TreeSet

HashSet：無序、不重複、無索引；

ListedHashSet：有序，不重複，無索引；底層資料結構為hash表，但是采用的雙連結清單

TreeSet：按照大小預設升序排序、不重複、無索引；排序也可根據字元串首個字元編号升序

HashSet1.7版本原了解析:數組+連結清單+(結合雜湊演算法)

1. 建立一個預設長度為16的數組，數組名為table
2. 根據元素的哈希值跟數組的長度求餘計算出應存入的位置(雜湊演算法)
3. 判斷目前位置是否為null，如果是null直接存入
4. 如果位置不為null，表示有元素，則會調用equals方法比較
5. 如果一樣，則不存，如果不一樣，則存儲數組
   1. JDK7新元素指向老元素位置，指向老元素
   2. JDK8中尋元素放在老元素下面
6. 目前挂在同意索引下的元素如果過多的時候，查詢性能降低，從JDK8起，當連結清單長度超過8的時候，會自動轉換為紅黑樹
7. 當數組存滿(數組長度*0.75)的時候，會自動擴容，每次擴容原先的兩倍

結論：

1. 哈希表是一種對增删改查資料性能都較好的結構
2. 如果希望set認為兩個對象的内容完全相同，我們需要重寫equals和hashcode方法

以上使用情況

1. 如果希望元素可以重複，又有索引，索引查詢要快
   1. 使用ArrayList集合，基于數組的(使用最多)
2. 如果希望元素可以重複，又有索引，增删首尾要快
   1. 使用LinkedList集合，基于連結清單
3. 如果希望增删改查都快，但是元素不能重複，且無索引，無序
   1. 使用HashSet集合，基于哈希表的
4. 如果希望增删改查都快，但是元素不能重複，且無索引，有序
   1. 用LinkHashSet集合，基于哈希表的雙連結清單
5. 如果要對對象進行排序
   1. 用TreeSet集合，基于紅黑樹，後續也可以用List集合實作排序

Map

Map是雙列集合的祖宗接口，他的功能是雙列集合都可以繼承使用的

特點：鍵值對

HashMap

特點：HashMap是Map裡面的一個實作類，特點都是由鍵決定的：無序、不重複、無索引

實際上:Set系列集合的底層就是Map實作的，隻是Set集合中的元素隻要鍵資料，不要值資料而已

LinkedList

特點：由鍵決定是否有序，不重複，無索引(此處有序僅保證存入和取出先後順序一緻)

原理：底層hash表，但是多了一個雙連結清單

TreeMap

特點：由鍵決定特性：不重複，無索引、可排序；(按鍵排序，預設從小到大)

以上圖檔資源來源網絡；如涉及盜版侵權請聯系作者處理