【java 13天進階Day05】數據結構,List,Set ,TreeSet集合,Collections工具類

常見的數據結構種類

集合是基于數據結構做出來的，不同的集合底層會采用不同的數據結構。
不同的數據結構，功能和作用是不一樣的。
數據結構：
- 數據結構指的是數據以什么方式組織在一起。
- 不同的數據結構，增刪查的性能是不一樣的。
- 不同的集合底層會采用不同的數據結構，我們要知道集合的底層是基于哪種數據結構存儲和操作數據的。這樣才能知道具體場景用哪種集合。
Java常見的數據結構即數據存儲的常用結構：棧、隊列、數組、鏈表和紅黑樹。
a.隊列（queue）
- –先進先出，后進后出。
- –場景：各種排隊。叫號系統。
- –有很多集合可以實現隊列。
b.棧（stack）
- –后進先出，先進后出
- – 壓棧==入棧
- – 彈棧 == 出棧
- –場景：手槍的彈夾。
c.數組
- –數組是內存中的連續存儲區域。
- –分成若干等分的小區域（每個區域大小是一樣的）
- –元素存在索引
- –特點：查詢元素快（根據索引快速計算出元素的地址，然后立即去定位）
- 增刪元素慢（創建新數組，遷移元素）
d.鏈表
- –元素不是內存中的連續區域存儲。
- –元素是游離存儲的。每個元素會記錄下個元素的地址。
- –特點：查詢元素慢。
- 增刪元素快（針對于首尾元素，速度極快，一般是雙鏈表）。
e.紅黑樹（待看）
1.
2. 二叉樹：binary tree永遠只有一個根節點**,是每個結點不超過2個節點的樹（tree）。
3. 查找二叉樹,排序二叉樹：小的左邊，大的右邊，但是可能樹很高，性能變差。
4. 為了做排序和搜索會進行左旋和右旋實現平衡查找二叉樹，讓樹的高度差不大于1**。
5. 紅黑樹（就是基于紅黑規則實現了自平衡的排序二叉樹）：樹盡量的保證到了很矮小，但是又排好序了，性能最高的樹。
6. 紅黑樹的增刪查改性能都好。

ArrayList集合

List集合繼承了Collection集合的全部功能，因為List集合多了索引，所以多了很多按照索引操作元素的功能。
ArrayList實現List集合底層基于數組存儲數據的，查詢快，增刪慢！
public void add(int index, E element):將指定的元素，添加到該集合中的指定位置上。
public E get(int index):返回集合中指定位置的元素。
public E remove(int index):移除列表中指定位置的元素,返回的是被移除的元素。
public E set(int index, E element):用指定元素替換集合中指定位置的元素，返回更新前的元素值。
四種遍歷：多了for遍歷，因為有索引。
使用多態List<String> lists = new ArrayList<>();

LinkedList集合

LinkedList也是List的實現類：底層是基于鏈表的，增刪比較快，查詢慢！！
LinkedList是支持雙鏈表，定位前后的元素是非常快的，增刪首尾的元素也是最快的。
public void addFirst(E e):將指定元素插入此列表的開頭。
public void addLast(E e):將指定元素添加到此列表的結尾。
public E getFirst():返回此列表的第一個元素。
public E getLast():返回此列表的最后一個元素。
public E removeFirst():移除并返回此列表的第一個元素。
public E removeLast():移除并返回此列表的最后一個元素。
public E pop():從此列表所表示的堆棧處彈出一個元素。
public void push(E e):將元素推入此列表所表示的堆棧。
放棄多態，使用多態無法調用子類新功能LinkedList<String> linkList = new LinkedList<>();

Set系列集合

Set系列集合是基于哈希表存儲數據的，它的增刪改查的性能都很好。
只有HashSet同父類Set一致都是無序，不重復，無索引的。
使用多態Set<String> sets = new HashSet<>();
兩個問題：
- Set集合添加的元素是不重復的，是如何去重復的？
  - 對于有值特性的，Set集合可以直接判斷進行去重復。
  - 對于引用數據類型的類對象，Set集合是按照如下流程進行是否重復的判斷。
    1. Set集合會讓兩兩對象，先調用自己的hashCode()方法得到彼此的哈希值（所謂的內存地址）a1.hashCode());
    2. 然后比較兩個對象的哈希值是否相同，如果不相同則直接認為兩個對象不重復。
    3. 如果哈希值相同，會繼續讓兩個對象進行equals比較內容是否相同，如果相同認為真的重復了
      如果不相同認為不重復。
    4. 如果希望Set集合認為兩個對象只要內容一樣就重復了，必須重寫對象的hashCode和equals方法。這會使得相同內容的對象哈希值一致且equals比較內容相同。（直接生產即可）
- Set集合元素無序的原因是什么？
  - 根本原因是因為底層采用了哈希表存儲元素。63%6=3
  - JDK 1.8之前：哈希表 = 數組 + 鏈表 + （哈希算法）
  - JDK 1.8之后：哈希表 = 數組 + 鏈表 + 紅黑樹 + （哈希算法）
  - 當鏈表長度超過閾值（8）時，將鏈表轉換為紅黑樹，這樣大大減少了查找時間。

LinkedHashSet

是HashSet的子類，元素是**“有序”** 不重復，無索引。
LinkedHashSet底層依然是使用哈希表存儲元素的，但是每個元素都額外帶一個鏈來維護添加順序！！不光增刪查快，還有序。
缺點是多了一個存儲順序的鏈會占內存空間!!而且不允許重復，無索引。
總結：
- 如果希望元素可以重復，又有索引，查詢要快用ArrayList集合。（用的最多）
- 如果希望元素可以重復，又有索引，增刪要快要用LinkedList集合。（適合查詢元素比較少的情況，經常要首尾操作元素的情況）
- 如果希望增刪改查都很快，但是元素不重復以及無序無索引，那么用HashSet集合。
- 如果希望增刪改查都很快且有序，但是元素不重復以及無索引，那么用LinkedHashSet集合。

TreeSet集合

不重復，無索引，按照大小默認升序排序!!
TreeSet集合稱為排序不重復集合，可以對元素進行默認的升序排序。
使用多態，在Set基礎上基本無新增功能 Set<Double> scores = new TreeSet<>();
TreeSet集合自自排序的方式：
- 1.有值特性的元素直接可以升序排序。（浮點型，整型）
- 2.字符串類型的元素會按照首字符的編號排序。
- 3.對于自定義的引用數據類型，TreeSet默認無法排序，執行的時候直接報錯，因為人家不知道排序規則。

自定義的引用數據類型的排序實現：定制排序的大小規則

a.直接為對象的類實現比較器規則接口Comparable，重寫比較方法（拓展方式）。

如果程序員認為比較者大于被比較者返回正數。
如果程序員認為比較者小于被比較者返回負數。
如果程序員認為比較者等于被比較者返回0。

@Data
public class Employee implements Comparable<Employee> {private String name;private double salary;private int age;// 重寫了比較方法。// e1.compareTo(o)// 比較者：this// 被比較者：o// 需求：按照年齡比較@Overridepublic int compareTo(Employee o) {// 規則：Java規則// 如果程序員認為比較者大于被比較者 返回正數！// 如果程序員認為比較者小于被比較者 返回負數！// 如果程序員認為比較者等于被比較者 返回0！
//        if(this.age > o.age){
//            return 1;
//        }else if(this.age < o.age){
//            return -1;
//        }
//        return 0;return this.age - o.age;}}

b.直接為集合設置比較器Comparator對象,重寫比較方法。

如果程序員認為比較者大于被比較者返回正數。
如果程序員認為比較者小于被比較者返回負數。
如果程序員認為比較者等于被比較者返回0。
使用匿名內部類 public TreeSet(Comparator<? super E> comparator)

Set<Employee> employees1 = new TreeSet<>(new Comparator<Employee>() {@Overridepublic int compare(Employee o1, Employee o2) {// o1比較者   o2被比較者// 如果程序員認為比較者大于被比較者 返回正數！// 如果程序員認為比較者小于被比較者 返回負數！// 如果程序員認為比較者等于被比較者 返回0！return o1.getAge() - o2.getAge();}});

注意：如果類和集合都帶有比較規則，優先使用集合自帶的比較規則。

–

Collections工具類的使用

java.utils.Collections:是集合工具類
Collections并不屬于集合，是用來操作集合的工具類。
Collections有幾個常用的API:
- -public static boolean addAll(Collection<? super T> c, T… elements)：給集合對象批量添加元素！
  - List<String> names = new ArrayList<>();
  - Collections.addAll(names, "曹操", "小亮", "小王");
- - public static void shuffle(List<?> list) ：打亂集合順序，只能打亂有序的List集合。
- - public static void sort(List list)：將集合中元素按照默認規則排序，默認升序。
- - public static void sort(List list，Comparator<? super T> )：將集合中元素按照指定規則排序。
Set是哈希算法存儲的，無法為其排序和升序。

引用數據類型的排序

字符串按照首字符的編號升序排序！

自定義類型的比較方法API

- public static void sort(List list):
- 將集合中元素按照默認規則排序。對于自定義的引用類型的排序人家根本不知道怎么排，直接報錯！
- 如果希望自定義的引用類型排序不報錯，可以給類提供比較規則:Comparable。

- public static void sort(List list，Comparator<? super T>

將集合中元素按照指定規則排序,自帶比較器

//方式1 自定義比較器
Collections.sort(oranges1, new Comparator<Orange>() {@Overridepublic int compare(Orange o1, Orange o2) {if (o1.getWeight() > o2.getWeight()) return -1;if (o1.getWeight() < o2.getWeight()) return 1;return 0;}});

//方式2 類實現Comparable接口
@Data
public class Orange implements Comparable {private String name;private double weight;private String price;@Overridepublic int compareTo(Object o) {Orange o2 = (Orange) o;if (this.weight > o2.weight) return 1;if (this.weight < o2.weight) return -1;return 0;}
}

注意：如果類有比較規則，而sort有比較器，優先使用比較器。

可變參數

可變參數用在形參中可以接收多個數據。
可變參數的格式：數據類型… 參數名稱 public static void sum(int... nums)
可變參數的作用：
- 傳輸參數非常靈活，方便。
- 可以不傳輸參數。
- 可以傳輸一個參數。
- 可以傳輸多個參數。
- 可以傳輸一個數組。
- 可變參數在方法內部本質上就是一個數組。
可變參數的注意事項：
- 1.一個形參列表中可變參數只能有一個。
- 2.可變參數必須放在形參列表的最后面。

ps:b站課程《黑馬程序員Java13天進階》根據官方筆記結合自身情況整理的筆記
視頻鏈接