五大集合(數據結構)要點

來源： https://juejin.im/post/5e8572abf265da47af17ff8d

1. List

1.主要問題

• 瞭解一下ArrayList和CopyOnWriteArrayList的 增刪改查 實現原理
• 看看為什麼說ArrayList查詢快而增刪慢？
• CopyOnWriteArrayList 與 Vector 的選擇
• LinkedList 與 ArrayList
• Arrays.asList(....) 的使用問題
• Collections這個工具類
• java9+ List.of()方法 map , set 同理 都有,不多寫了

2.為什麼arraylist 不安全

• 我們查看源碼發現 arraylist 的 CRUD 操作 並沒有涉及到鎖之類的東西
• 底層是數組，初始大小為10
• 插入時會判斷數組容量是否足夠，不夠的話會進行擴容
• 所謂擴容就是新建一個新的數組，然後將老的數據裡面的元素複製到新的數組裡面(所以增加較慢)

3.CopyOnWriteArrayList 有什麼特點?

• 它是List接口的一個實現類,在 java.util.concurrent ( 簡稱 JUC ,後面我全部改成 juc ,大家注意下)
• 內部持有一個ReentrantLock lock = new ReentrantLock(); 對於 增刪改 操作都是 先加鎖 再 釋放鎖 線程安全.並且鎖只有一把，而讀操作不需要獲得鎖，支持 併發 。
• 讀寫分離，寫時複製出一個新的數組，完成插入、修改或者移除操作後將新數組賦值給array

4.CopyOnWriteArrayList 與 Vector 的選擇

• Vector是 增刪改查 方法都加了 synchronized ，保證同步，但是每個方法執行的時候都要去獲得鎖，性能就會大大下降，而CopyOnWriteArrayList 只是在 增刪改 上加 鎖 ，但是讀不加鎖，在讀方面的性能就好於Vector，CopyOnWriteArrayList支持讀多寫少的併發情況。
• Vector和CopyOnWriteArrayList都是 List接口 的一個實現類

5.CopyOnWriteArrayList適用於什麼情況

• 我們看源碼不難發現他每次增加一個元素都要進行一次拷貝,此時嚴重影響了增刪改的性能,其中和arraylist 差了好幾百倍 我自己測試過,
• 所以對於讀多寫少的操作 CopyOnWriteArrayList 更加適合 ,而且線程安全
• DriverManager 這個類 就使用到了CopyOnWriteArrayList

6. LinkedList 和 ArrayList 對比

<code>LinkedList<integer> lists = new LinkedList<>();

lists.addFirst(1);
lists.push(2);
lists.addLast(3);
lists.add(4);
lists.addFirst(5);

lists.forEach(System.out::println);
// 5 2 1 3 4/<integer>/<code>

addFirst 和 addLast 方法很清楚 ,

push 方法的話 ,默認是 andFirst 實現

add 方法默認是 addLast 實現 ....

所以上面總結一下就是 add和last , push和first ,

其實我們要明白一下 , 鏈表相對於數組來說, 鏈表的添加和刪除速度很快 , 是 順序添加刪除 很快,因為一個linkedList會保存第一個節點和最後一個節點,時間複雜度為 O(1) , 但是你要指定位置添加 add(int index, E element) , 那麼此時他會先遍歷, 然後找到改位置的節點, 將你的節點添加到他前面 , 此時時間複雜度最大值為 O(n) ,

數組呢 , 我們知道ArrayList底層實現就是數組 , 數組優點就是由於內存地址是順序的, 屬於一塊整的 , 此時遍歷起來很快 , 添加刪除的話 ,他會複製數組, 當數組長度特別大時,所消耗的時間會很長

這是一張圖 , 大家可以看一下 ,

7. Arrays.asList() 方法返回的數組是不可變得嗎 ?

<code>List<integer> integers = Arrays.asList(1, 2, 3, 4, 5);
integers.set(2, 5); // 這個操作可以
//integers.add(6);  這個會拋出異常
integers.forEach(System.out::println); // 1 2 5 4 5

1. 很顯然我們是可以修改 list集合的 可以使用set方法
2. 但是當我們嘗試去使用add() 方法時,會拋出 java.lang.UnsupportedOperationException 的異常,
不支持操作的異常
3.當我們使用 java9+時  可以使用 List.of()方法 ,他就是徹徹底底的不可修改的/<integer>/<code>

8.怎麼將一個不安全數組換成安全數組

<code>1. 使用 Collections這個工具類
List<integer> integers1 = Collections.synchronizedList(integers);

2. java5+ 變成 CopyOnWriteArrayList
CopyOnWriteArrayList<integer> integers2 = (CopyOnWriteArrayList<integer>) integers;

3. java9+ ,使用 List.of() 變成只讀對象/<integer>/<integer>/<integer>/<code>

10. Collections 工具類

<code>1. 創建一個安全的空集合,防止NullPointerException異常
List<string> list = Collections.<string>emptyList();

2. 拷貝集合
Collections.addAll(list, 2,3, 4, 5, 6);

3. 構建一個安全的集合
List<integer> safeList = Collections.synchronizedList(list); 


4. 二分查找
Collections.binarySearch(list, 2);

5.翻轉數組
Collections.reverse(list);/<integer>/<string>/<string>/<code>

翻轉有很多方法 java.util.Collections , 可以去學一下, 有學習能力的可以去學習一下 Google的 Guava 很強的工具類 , 裡面很多

2. Set

1. 問題

• HashSet、TreeSet和 LinkedHashSet三種類型什麼時候使用它們
• Hashset的實現方式? HashSet去重方式 ? TreeSet 去重方式?
• 那怎麼實現一個線程安全的 HashSet , 因為JDK沒有 ConcurrentHashSet
• CopyOnWriteArraySet的實現

2.HashSet、TreeSet和LinkedHashSet三種類型什麼時候使用它們

• 如你的需求是要一個能快速訪問的Set，那麼就要用HashSet , HashSet底層是 HashMap 實現的 ，其中的元素沒有按順序排列.
• 如果你要一個可排序Set，那麼你應該用TreeSet, **TreeSet的底層實現是 TreeMap **
• 如果你要記錄下插入時的順序時，你應該使用LinedHashSet
• Set集合中不能包含重複的元素 ，每個元素必須是唯一的，你只要將元素加入set中，重複的元素會自動移除。所以 可以去重 , 很多情況下都需要使用 (但是去重方式不同)
• LinkedHashSet正好介於HashSet和TreeSet之間，它也是一個基於 HashMap 和雙向鏈表的集合，但它同時維護了一個雙鏈表來記錄插入的順序，基本方法的複雜度為O(1)。
• 三者都是線程不安全的, 需要使用 Collections.synchronizedSet(new HashSet(…));

3. HashSet和LinkedHashSet 判定元素重複的原則是相同的

• 會先去執行hashCode() 方法 ,判斷是否重複
• 如果hashCode() 返回值相同 , 就會去判斷equals方法,
• 如果equals() 方法還是相同, 那麼就認為重複

4. TreeSet 判斷元素重複原則

TreeSet的元素必須是實現了 java.lang.Comparable 接口 , 所以他是根據此個接口的方法 compareTo 方法進行判斷重複的, 當返回值一樣的時,認定重複

5. 怎麼實現一個線程安全的 hashset

​ 我們看源碼 會發現 他裡面有一個 HashMap ,那為什麼要用(用transient關鍵字標記的成員變量不參與序列化過程。) 為什麼呢 ,因為 HashMap 已經實現了Serializable,

怎麼實現一個 ConcurrentHashSet

• 自己寫一個 實現類 實現 Set ,裡面 定義一個 ConcurrentHashSet ,和 hashset的方式一樣
• 直接用 第三方庫 ----- com.alibaba.dubbo.common.utils.ConcurrentHashSet ,阿里的庫 ....

<code>package com.alibaba.dubbo.common.utils;
import java.util.AbstractSet;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

public class ConcurrentHashSet extends AbstractSet implements Set, java.io.Serializable {

    private static final long serialVersionUID = -8672117787651310382L;

    private static final Object PRESENT = new Object();

    private final ConcurrentMap map;

    public ConcurrentHashSet() {
        map = new ConcurrentHashMap();
    }

    public ConcurrentHashSet(int initialCapacity) { 

        map = new ConcurrentHashMap(initialCapacity);
    }
    
 ...............   
}/<code>

很顯然跟我說的好像 一模一樣 ,哈哈哈 ,我也是看別人學的,只是看你用的巧不巧,他繼承了AbstractSet這個抽象類,重寫了 他部分想要改的方法, 同時也實現了 set接口

6.CopyOnWriteArraySet的實現

<code>public CopyOnWriteArraySet() {
     al = new CopyOnWriteArrayList();
 }/<code>

很顯然翻源碼我們發現 他實現了 CopyOnWriteArrayList();

3. Map

1. 問題

• 最常見的問題就是 HashMap的底層實現 , JDK1.7和JDK1.8的差別 ,這個我不講了,如果想要看,自己百度我提供一個我自己寫的一個HashMap簡單實現
• Hashtable、HashMap 以及ConcurrentHashMap 的區別
• 深度學習 ConcurrentHashMap 和 HashMap 靠你們自己了 ,這倆研究透, 你已經向大神進階了
• ConcurrentSkipListMap 與 TreeMap 的選擇
• LinkedHashMap的使用

2. Hashtable的學習

• Hashtable和ConcurrentHashMap以及ConcurrentSkipListMap 以及TreeMap 不允許key 和 value值 為空,但是 HashMap 可以 key 和value值都可以為空,
• Hashtable的方法 都加了Synchronized 關鍵字修飾 , 所以線程安全
• 它是 數組+鏈表的實現

3.ConcurrentHashMap 問題

• 取消segments字段，直接採用transient volatile HashEntry[] table保存數據，
• 採用table數組元素作為鎖，從而實現了對每一行數據進行加鎖，進一步減少併發衝突的概率。
• 把Table數組＋單向鏈表的數據結構 變成為 Table數組 ＋ 單向鏈表 ＋ 紅黑樹的結構。
• 當鏈表長度超過8以後，單向鏈表變成了紅黑數； 在哈希表擴容時，如果發現鏈表長度小於 6，則會由紅黑樹重新退化為鏈表。
• 對於其他詳細我不吹,看懂的麼幾個 ,他比HashMap 還要難,
• 對於線程安全環境下 介意使用 ConcurrentHashMap 而不去使用 Hashtable

4. 為什麼不去使用 Hashtable,而去使用ConcurrentHashMap ?

HashTable容器使用synchronized來保證線程安全，但在線程競爭激烈的情況下HashTable的效率非常低下。因為當一個線程訪問HashTable的同步方法時，其他線程訪問HashTable的同步方法時，可能會進入阻塞或輪詢狀態。如線程1使用put進行添加元素，線程2不但不能使用put方法添加元素，並且也不能使用get方法來獲取元素，所以競爭越激烈效率越低。

5. HashMap 問題

• 其中部分信息咱們還能聊聊,不會的我就算了
• 內部節點分為 Node 和 TreeNode , 都直接間接的實現與 Map.Entry , 後者所佔用的空間較大,所以是一種空間換時間的想法 , 前者只要保存兩個節點信息, 後者需要保存四個
• 存儲結構是 數組+鏈表 或者 數組+ 紅黑樹 實現,有個閾值,當鏈表長度大於8，大於8的話把鏈表轉換為紅黑樹,當小於等於6時會自動轉成鏈表原因： (反正我看不懂,只是解決碰撞概率的問題,數學問題這個是)紅黑樹的平均查找長度是log(n)，長度為8，查找長度為log(8)=3，鏈表的平均查找長度為n/2，當長度為8時，平均查找長度為8/2=4，這才有轉換成樹的必要；鏈表長度如果是小於等於6，6/2=3，雖然速度也很快的，但是轉化為樹結構和生成樹的時間並不會太短。還有選擇6和8的原因是：中間有個差值7可以防止鏈表和樹之間頻繁的轉換。假設一下，如果設計成鏈表個數超過8則鏈表轉換成樹結構，鏈表個數小於8則樹結構轉換成鏈表，如果一個HashMap不停的插入、刪除元素，鏈表個數在8左右徘徊，就會頻繁的發生樹轉鏈表、鏈表轉樹，效率會很低。
• Node[] table的初始化長度length(默認值是16)，LoadFactor為負載因子(默認值是0.75), 例如為1，雖然減少了空間開銷，提高了空間利用率，但同時也增加了查詢時間成本；加載因子過低，例如0.5，雖然可以減少查詢時間成本，但是空間利用率很低，同時提高了rehash操作的次數
• 實現鏈接,大家不會寫可以看看
• HashMap是非synchronized ,線程不安全
• 大家可以看看高能講解:

6. ConcurrentSkipListMap 與 TreeMap 的選擇

• ConcurrentSkipListMap提供了一種線程安全的併發訪問的排序映射表。內部是SkipList（跳錶）結構實現，利用底層的插入、刪除的CAS原子性操作，通過死循環不斷獲取最新的結點指針來保證不會出現競態條件。在理論上能夠在O(log(n))時間內完成查找、插入、刪除操作。調用ConcurrentSkipListMap的size時，由於多個線程可以同時對映射表進行操作，所以映射表需要遍歷整個鏈表才能返回元素個數，這個操作是個O(log(n))的操作。
• 在JDK1.8中，ConcurrentHashMap的性能和存儲空間要優於ConcurrentSkipListMap，但是ConcurrentSkipListMap有一個功能： 它會按照鍵的自然順序進行排序 。
• 故需要對 鍵值排序 ，則我們可以使用TreeMap，在 併發場景 下可以使用ConcurrentSkipListMap。
• 所以 我們並不會去 糾結 ConcurrentSkipListMap 和 ConcurrentHashMap 兩者的選擇,因為我解釋的很好了

7. LinkedHashMap的使用

• 主要是為了解決讀取的有序性,
• 基於 HashMap 實現的
• 可以看看我的 這篇文章 : anthony-dong.github.io/post/linked…

4. Queue

<code>​ 隊列在於你走向高級工程師必須走的一步 . 一開始我們對於他並不瞭解,但是你會發現併發包裡面一堆關於隊列的類,你就知道了他的關鍵所在,先進先出的使用場景很常見的
​ 通過我這段時間的學習,我發現在線程池這塊,還有這消息隊列,還有在數據庫連接池這塊都需要隊列.這些中間件對於隊列的依賴性太過於強烈.
​ 所以學會隊列是很重要的一步.這些內容我會慢慢補充的. 

/<code>

1. 隊列是什麼

我們都知道 隊列 (Queue)是一種 先進先出 (FIFO)的數據結構，Java中定義了 java.util.Queue 接口用來表示隊列。Java中的 Queue 與 List 、 Set 屬於同一個級別接口，它們都是實現了 Collection 接口。注意: HashMap沒有實現 Collection 接口

2.Deque 是什麼

• 它是一個雙端隊列
• 我們用到的 linkedlist 就是 實現了 deque的接口
• 支持在兩端插入和移除元素
• 區別與 循環隊列 循環隊列實現講解

3.常見的幾種隊列實現

1. LinkedList

LinkedList 是鏈表結構，隊列呢也是一個列表結構,繼承關係上 , LinkedList實現了Queue , 所以對於Queue來說 ,

添加是 offer(obj) , 刪除是 poll() , 獲取隊頭(不刪除)是 peek() .

<code>public static void main(String[] args) { 

    Queue<integer> queue = new LinkedList<>();

    queue.offer(1);
    queue.offer(2);
    queue.offer(3);

    System.out.println(queue.poll());
    System.out.println(queue.poll());
    System.out.println(queue.poll());
}
// 1, 2 , 3 /<integer>/<code>

2. PriorityQueue

PriorityQueue維護了一個有序列表,插入或者移除對象會進行Heapfy操作, 默認情況下可以稱之為小頂堆 。當然，我們也可以給它指定一個實現了 java.util.Comparator 接口的排序類來指定元素排列的順序。

PriorityQueue 是一個無界隊列 , 當你設置初始化大小還是不設置 , 都不影響他繼續添加元素

3. ConcurrentLinkedQueue

ConcurrentLinkedQueue 是基於鏈接節點的並且線程安全的隊列。因為它在隊列的尾部添加元素並從頭部刪除它們，所以只要不需要知道隊列的大小 ConcurrentLinkedQueue 對公共集合的共享訪問就可以工作得很好。收集關於隊列大小的信息會很慢，需要遍歷隊列。

4. ArrayBlockingQueue與LinkedBlockingQueue的區別,哪個性能好呢

• ArrayBlockingQueue 是有界隊列
• LinkedBlockingQueue 看構造方法區分 , 默認構造方法最大值是 2^31-1
• 但是當 take 和 put操作時 ,ArrayBlockingQueue速度要快於 LinkedBlockingQueue原因是什麼1.隊列中的鎖的實現不同 ​ ArrayBlockingQueue中的鎖是沒有分離的，即生產和消費用的是同一個鎖； ​ LinkedBlockingQueue中的鎖是分離的，即生產用的是putLock，消費是takeLock 2.在生產或消費時操作不同 ​ ArrayBlockingQueue基於數組，在生產和消費的時候，是直接將枚舉對象插入或移除的，不會產生或銷燬任何額外的對象實例； ​ LinkedBlockingQueue基於鏈表，在生產和消費的時候，需要把枚舉對象轉換為Node進行插入或移除，會生成一個額外的Node對象，這在長時間內需要高效併發地處理大批量數據的系統中，其對於GC的影響還是存在一定的區別。
• 問題有哪些在使用LinkedBlockingQueue時，若用默認大小且當生產速度大於消費速度時候，有可能會內存溢出。在使用ArrayBlockingQueue和LinkedBlockingQueue分別對1000000個簡單字符做入隊操作時，​ LinkedBlockingQueue的消耗是ArrayBlockingQueue消耗的10倍左右，​ 即LinkedBlockingQueue消耗在1500毫秒左右，而ArrayBlockingQueue只需150毫秒左右。按照實現原理來分析， ArrayBlockingQueue完全可以採用分離鎖，從而實現生產者和消費者操作的完全並行運行 。Doug Lea之所以沒這樣去做，也許是因為ArrayBlockingQueue的數據寫入和獲取操作已經足夠輕巧，以至於引入獨立的鎖機制，除了給代碼帶來額外的複雜性外，其在性能上完全佔不到任何便宜。
• 我們測試的是 ArrayBlockingQueue 會比 LinkedBlockingQueue性能好 , 好差不多50%起步 ,

5. BlockingQueue的問題 以及 ConcurrentLinkedQueue 的問題

• BlockingQueue 可以是限定容量的。
• BlockingQueue 實現主要用於生產者-使用者隊列，但它另外還支持collection接口。
• BlockingQueue 實現是線程安全的
• BlockingQueue 是阻塞隊列 (看你使用的方法) , ConcurrentLinkedQueue 是非阻塞隊列區別​ LinkedBlockingQueue 是一個線程安全的阻塞隊列，基於鏈表實現，一般用於生產者與消費者模型的開發中。採用鎖機制來實現多線程同步，提供了一個構造方法用來指定隊列的大小，如果不指定大小，隊列採用默認大小（Integer.MAX_VALUE，即整型最大值）。​ ConcurrentLinkedQueue 是一個線程安全的非阻塞隊列，基於鏈表實現。java並沒有提供構造方法來指定隊列的大小，因此它是無界的。為了提高併發量，它通過使用更細的鎖機制，使得在多線程環境中只對部分數據進行鎖定，從而提高運行效率。他並沒有阻塞方法,take和put方法.注意這一點

6. 簡要概述BlockingQueue常用的七個實現類

​ 有一個是 JDK1.7才加入的, 所以常見的就六個

1. ArrayBlockingQueue

構造函數必須傳入指定大小, 所以他是一個有界隊列

2. LinkedBlockingQueue

分為兩種情況 , 第一種構造函數指定大小, 他是一個有界隊列 , 第二種情況,不指定大小他可以稱之為無界隊列, 隊列最大值為 Integer.MAX_VALUE

3. PriorityBlockingQueue (還有一個雙向的LinkedBlockingDeque)

他是一個無界隊列 , 不管你使用什麼構造函數 ..

一個內部由優先級堆支持的、基於時間的調度隊列。隊列中存放Delayed元素，只有在延遲期滿後才能從隊列中提取元素。當一個元素的getDelay()方法返回值小於等於0時才能從隊列中poll中元素，否則poll()方法會返回null。

4. SynchronousQueue

這個隊列類似於Golang的channel , 也就是chan ,跟無緩衝區的chan很相似. 比如take和put操作就跟chan一模一樣. 但是區別在於他的poll和offer操作可以設置等待時間.

如果你學過golang的話. 應該理解 . 我寫個例子

<code>func main() {
\tch := make(chan int, 0)
\tstart := time.Now().UnixNano()
\tgo func() {
\t\ttime.Sleep(time.Millisecond * 500)
\t\tch \t}()
\tx := \tfmt.Printf("msg : %d , spend : %dms\\n", x, (time.Now().UnixNano()-start)/1e6)
}
// 輸出
// msg : 1 , spend : 500ms/<code>

那麼換而言之 , Java呢

<code>public class TestSync {

    public static void main(String[] args) throws InterruptedException {
        SynchronousQueue<integer> queue = new SynchronousQueue<>();
        long start = System.currentTimeMillis();
        new Thread(() -> {
            try {
                Integer poll = queue.take();
                System.out.printf("receive : %d , spend : %dms.\\n", poll, System.currentTimeMillis() - start);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

        }).start();

        new Thread(() -> {
            try {
                //sleep 2000ms
                TimeUnit.SECONDS.sleep(2);
                queue.put(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }).start();
    }
}

// 輸出 
//receive : 1 , spend : 2060ms./<integer>/<code>

但是他和chan不同的是, 他的poll操作吧, (類似於golang的 select case 操作) , 等不到放棄, 返回一個null.

但是唯一不同的是 他可以指定等待時間.超過等待時間再放棄.

<code>Integer poll = queue.poll(1000,TimeUnit.MILLISECONDS);/<code>

這個就是等待1000ms , 等不到放棄了 .

像線程池中用 SynchronousQueue 使用的是 offer(obj) 操作, 也就是說乾脆插入不進去.因為他懶得等 , 但是offer可以指定等待時間的.

總結一下. take 和 put 一對,是死等待 , poll和offer靈活, 活著來

5. DelayQueue

Java延遲隊列提供了在指定時間才能獲取隊列元素的功能，隊列頭元素是最接近過期的元素。沒有過期元素的話，使用poll()方法會返回null值，超時判定是通過getDelay(TimeUnit.NANOSECONDS)方法的返回值小於等於0來判斷。延時隊列不能存放空元素。

​ 添加的元素必須實現 java.util.concurrent.Delayed 接口

<code>@Test
public void testLinkedList() throws InterruptedException {

    DelayQueue<person> queue = new DelayQueue<>();

    queue.add(new Person());

    System.out.println("queue.poll() = " + queue.poll(200,TimeUnit.MILLISECONDS));
}


static class Person implements Delayed {

    @Override
    public long getDelay(TimeUnit unit) {
        // 這個對象的過期時間
        return 100L;
    } 


    @Override
    public int compareTo(Delayed o) {
        //比較
        return o.hashCode() - this.hashCode();
    }
}

輸出 : 
queue.poll() = null/<person>/<code>

6. LinkedTransferQueue (重點)

​ JDK1.7 加入的無界隊列 , 亮點就是無鎖實現的,性能高 .

Doug Lea 說這個是最有用的 BlockingQueue 了 , 性能最好的一個 . Doug Lea說 從功能角度來講，LinkedTransferQueue實際上是ConcurrentLinkedQueue、SynchronousQueue（公平模式）和LinkedBlockingQueue的超集。

他的 transfer方法 表示生產必須等到消費者消費才會停止阻塞. 生產者會一直阻塞直到所添加到隊列的元素被某一個消費者所消費（不僅僅是添加到隊列裡就完事）

同時我們知道 上面那些BlockingQueue使用了大量的 condition和 lock , 這樣子效率很低 , 而LinkedTransferQueue則是無鎖隊列.

他的核心方法其實就是 xfer()方法 ,基本所有方法都是圍繞著這個進行的 , 一般就是 SYNC ,ASYNC,NOW ,來區分狀態量. 像put,offer,add 都是 ASYNC , 所以不會阻塞. 下面幾個狀態對應的變量.

<code>private static final int NOW   = 0; // for untimed poll, tryTransfer(不阻塞)
private static final int ASYNC = 1; // for offer, put, add(不阻塞)
private static final int SYNC  = 2; // for transfer, take(阻塞) 

private static final int TIMED = 3; // for timed poll, tryTransfer (waiting)/<code>

7.(小頂堆) 優先隊列 PriorityQueue 的實現

​ 小頂堆是什麼 : 任意一個非葉子節點的權值，都不大於其左右子節點的權值

• PriorityQueue是非線程安全的，PriorityBlockingQueue是線程安全的
• 兩者都使用了堆，算法原理相同
• PriorityQueue 的邏輯結構是一棵完全二叉樹，就是因為完全二叉樹的特點, 他實際存儲確實可以為一個數組的, 所以他的
  存儲結構其實是一個數組 。​ 1. 首先java 中的 PriorityQueue 是優先隊列,使用的是小頂堆實現什麼是小頂堆 (父節點,永遠小於左右子節點) ,因此結果不一定是完全升序什麼是大頂堆 跟 小頂堆相反,優先隊列中 對於當offer操作,當插入的元素此時長度大於默認長度會進行數組擴容(system.copyarr()方法) 所以他其實是一個無界數列所以 優先隊列 是數組實現,他不需要佔用太大的物理空間,而是進行了深度的排序

1. 自己實現一個大頂堆

<code>/**
 * 構建一個 大頂堆
 *
 * @param tree
 * @param n
 */
static void build_heap(int[] tree, int n) {

    // 最後一個節點
    int last_node = n - 1;

    // 開始遍歷的位置是 : 最後一個堆的堆頂 , (以最小堆為單位)
    int parent = (last_node - 1) / 2;

    // 遞減向上遍歷
    for (int i = parent; i >= 0; i--) {
        heapify(tree, n, i);
    }
}


/**
 * 遞歸操作
 * @param tree 代表一棵樹 

 * @param n    代表多少個節點
 * @param i    對哪個節點進行 heapify
 */
static void heapify(int[] tree, int n, int i) {

    // 如果當前值 大於 n 直接返回了 ,一般不會出現這種問題 .....
    if (i >= n) {
        return;
    }

    // 子節點
    int c1 = 2 * i + 1;
    int c2 = 2 * i + 2;

    // 假設最大的節點 為 i (父節點)
    int max = i;

    // 如果大於  賦值給 max
    if (c1 < n && tree[c1] > tree[max]) {
        max = c1;
    }

    // 如果大於  賦值給 max
    if (c2 < n && tree[c2] > tree[max]) {
        max = c2;
    }

    // 如果i所在的就是最大值我們沒必要去做交換
    if (max != i) {

        // 交換最大值 和 父節點 的位置
        swap(tree, max, i);

        // 交換完以後 , 此時的max其實就是 i原來的數 ,就是最小的數字 ,所以需要遞歸遍歷
        heapify(tree, n, max);
    }

} 


// 交換操作
static void swap(int[] tree, int max, int i) {
    int temp = tree[max];
    tree[max] = tree[i];
    tree[i] = temp;
}/<code>

8.常用的幾個方法

• offer 添加一個元素並返回true 如果隊列已滿，則返回false
• poll 移除並返問隊列頭部的元素 如果隊列為空，則返回null
• peek 返回隊列頭部的元素 如果隊列為空，則返回null
• put 添加一個元素 如果隊列滿，則阻塞 BlockQueue特有的
• take 移除並返回隊列頭部的元素 如果隊列為空，則阻塞 (像隊頭移除一個元素,並且整體向前移動,保證對頭不為空) BlockQueue特有的

5. Stack

棧結構屬於一種先進者後出,類似於一個瓶子 , 先進去的會壓到棧低(push操作) , 出去的時候只有一個出口就是棧頂 , 返回棧頂元素,這個操作稱為pop ,

1. Stack類

​ stack 繼承自 Vector , 所有方法都加入了 sync 修飾, 使得效率很低 ,線程安全.

<code>@Test
public void testStack() {

    Stack<integer> stack = new Stack<>();

    // push 添加
    stack.push(1);

    stack.push(2);

    // pop 返回棧頂元素 , 並移除
    System.out.println("stack.pop() = " + stack.pop());

    System.out.println("stack.pop() = " + stack.pop());

}

輸出 : 
2 , 1 /<integer>/<code>

2. 通過LinkedList 實現

​ 但是LInkedList很好的實現了這個 , 同時他是個線程不安全的類.

<code>@Test
public void testStack() {

    LinkedList<integer> stack = new LinkedList<>();

    stack.push(1);
    stack.push(2);


    System.out.println("stack.pop() = " + stack.pop());
    System.out.println("stack.pop() = " + stack.pop());
}

輸出 
2 , 1 /<integer>/<code> 

閱讀更多 木子莫 的文章

關鍵字: 數據結構 鏈表 樹結構