JAVA_集合

• 2022 年 2 月 4 日
• 筆記
• JAVA

一.體系

• Collection：單列
  • list：有序可重複，可以放多個Null
    • Arraylist ；Linkedlist ；Vector
  • Set：無序不可重複，只能放一個Null
    • HashSet ；LinkedHashSet ；TreeSet
  • Queue:
    • Deque:雙端隊列 ；BlockingQueue:阻塞隊列 ；AbstractQueue:非阻塞隊列
• Map：雙列，k-v鍵值對
  • HashMap
    • linkedHashMap
  • TreeMap
  • HashTable
    • Properties     

二.ArrayList、LinkedList、Vector三者的異同(使用場景)？    

• 同：存儲有序可重複的數據 就像數組一樣
• 異：
  • ArrayList
    
    • 底層默認創建長度為10的數組：new Object[10]；(數組就需要連續的記憶體空間)
      
    • 空間不夠自動擴容，擴展為原來 容量*1.5，同時將原有的元素複製到新的數組中
    • jdk1.7：類似餓漢式，new Arraylist()就直接你創建一個數組
    • jdk1.8：類似懶漢式，new Arraylist()還不創建數組,只有使用add()才創建。延遲數組的創建,節省記憶體
    • 數組結構適合遍歷和查找，不適合插入/刪除(但可以優化)
    • 執行緒不安全(效率高)，可以使用Collections工具類變為執行緒安全，或使用juc
  • Vector
    • 底層默認創建長度為10的數組：new Object[10];
    • 空間不夠自動擴容,擴展為原來 容量*2，同時將原有的元素複製到新的數組中
    • 執行緒安全(所有方法synchronized修飾)，但是效率太低，很少使用
  • LinkedList
    • 底層創建一個雙向鏈表 (鏈表不需要連續的記憶體空間)
    • 定義了一個Node內部類，裡面有prev，element，next屬性
    • 鏈表結構適合插入和刪除，遍歷和查找比較慢
    • 鏈表當然不需要擴容
    • 只能使用iterator遍歷,不能使用增強for遍歷,因為需要get每一個值,遍歷所有的元素,效率極低

ArrayList和LinkedList性能對比?  建議使用ArrayList

• LinkedList底層維護一個內部類Node，每次添加新的元素創建一個Node對象，耗費資源。 而且使用不方便(遍歷時)
• 對於ArrayList不適合插入/刪除的特性，可以進行優化。 採用尾插法並指定初始容量可以極大的提升性能,甚至超過LinkedList。
• ArrayList 的空間浪費主要體現在在list列表的結尾預留一定的容量空間； LinkedList 的空間花費則體現在它的每一個元素都需要消耗存儲指針節點對象的空間。

如何實現ArrayList和Array的轉換?

• Arrays.asList(str)； //轉變為list
• list.toArray；　　   //轉變為array    

三.阻塞隊列

這裡只說明api的使用

四.HashMap

前提知識：HashCode和equals，提前說明這兩個東西，有助於理解HashMap

hashCode()相同，equals()也一定為true嗎？
不是,這兩個是配合使用的。

HashCode()是Object提供的一個native的方法，用來獲取哈希碼
記憶體中維護一個很大的哈希表,每一個對象存儲到記憶體的時候，都在這個表中進行記錄
這個表就相當於一個"記錄表",記錄著每個對象的地址。

什麼是哈希表?
哈希表本質是一個升級版的數組,每一個對象都有一個關鍵字(k-v中的k),根據內部的"哈希演算法"得出一個"哈希碼"。
這個哈希碼就相當於數組的索引(哈希表沒有0,1那樣的索引。哈希碼就是索引),可以直接通過哈希碼找到一個對象。
這樣做就是為了提高執行的效率,快速定位對象。因為哈希表的初衷就是升級數組，數組已經很合適查詢了，
但是哈希表"更塊"。哈希表就是一種數據結構
(哈希表其實就是對數組的索引進行優化,"讓索引和關鍵字(傳入的對象)產生關係,從而快速找到對象的位置")

注意點:
    相同的對象一定產生相同的哈希碼
    不同的對象也可能產生相同的哈希碼 (產生哈希衝突，有對應的解決方案)   
    //上面這兩條主要是因為哈希演算法導致的,正因為這樣,才需要用到equals
    equals()被覆蓋,hashCode()也必須被覆蓋
    
為什麼要有HashCode?(為什麼搞一個"記錄表")
以HashSet如何檢查重複來說明為什麼要有HashCode：
對象加入HashSet時,HashSet會計算對象的哈希碼,從哈希表中檢查是否索引的位置上有值(對象)，
沒有:就認為對象不重複,允許添加;
有值:就會調用equals()來判斷兩個對象是否相等:
        相等：不允許添加
        不相等:說明哈希衝突了,採用對應的解決方案放到其他的位置上,允許添加
這樣做主要為了避免多次equals比較,提高效率。

HashSet底層就是創建一個HashMap,所以直接對hashMap進行解釋

底層實現：

• jdk7：數組+鏈表
  • new HashMap()；//創建一個長度為16的數組
• jdk8：數組+鏈表+紅黑樹 (改為紅黑樹為了加快查詢的速度)
  • new HashMap()；//類似於懶漢式，還沒有創建數組，當調用put()時創建長度為16的數組
  • 只有當 鏈表高度>8且數組長度>64,就把鏈表改為紅黑樹。數組長度<6就將紅黑樹轉回鏈表

put添加過程(如何保證不重複)

• 添加的過程和上面hashSet使用哈希表添加的過程一樣，只是哈希衝突問題採用七上八下。
  • 注意：發現hashCode相同，equals相同，不是不允許添加，而是覆蓋之前的元素
• 七上八下：遇到哈希衝突時
  • jdk7是把新元素放在數組上，舊元素放在鏈表上，指向舊元素
  • jdk8是把新元素放在鏈表上，舊元素指向新元素

擴容機制

• 數組超過臨界值(臨界值0.75) 擴展為原來的2倍， 將舊的元素複製到新的數組中，重新計算hash，按照列表/紅黑樹的方式排序起來         

源碼中重要的常量

• DEFAULT_INITIAL_CAPACITY：默認數組容量 16
• MAXIMUM_CAPACITY：最大的容量 2^30
• DEFAULT_LOAD_FACTOR：默認的載入因子 0.75(一個經過科學計算的數)   臨界值=容量*0.75  比如16*0.75=12 容量達到12時,考慮擴容
• TREEIFY_THRESHOLD：鏈錶轉化為紅黑樹的 鏈表最低高度 8
• MIN_TREEIFY_CAPACITY： 鏈錶轉化為紅黑樹的 數組最小長度 64
• UNTREEIFY_THRESHOLD：紅黑樹轉回鏈表的 數組長度 6  

開發中你是怎麼使用hashMap?

• 根據實際業務指定hashMap的長度,因為這樣可以避免多次擴容，提高性能
• HashMap<String，Object> map = new HashMap<>(長度)
  • 注意：new HashMap<>(7)；//這種我們自定義長度的hashmap，在創建數組的時候,長度經過tableSizeFor(initialCapacity)方法變為大於指定長度的最低二次冪數，
  • 比如1就變為2；7就變為8；11就變為16 等，所以上述是創建了一個長度為8的數組     

Hashmap為什麼不安全?

• jdk 1.7 hashmap底層使用數組 + 鏈表，當擴容時會調用transfer函數 ，在對table進行擴 容，需要將原來的數據複製到newtable中，採用頭插法，會將鏈表反轉，這個過程可能會導致死循環和數據丟失，也有可能造成數據覆蓋
• jdk 1.8中 hashmap底層使用數組 + 鏈表 + 紅黑樹，採用尾插法，優化了死循環和數據丟失的 問題，但是還是會有數據覆蓋的問題   

HashMap和HashTable的區別?

• 底層不同
  • HashMap：初始化16，擴容2倍
  • HashTable：初始化11，擴容2倍+1
• HashMap執行緒不安全，HashTable執行緒安全(效率低)。 (即使需要執行緒安全也不用HashTable，而是使用concurrentHashMap，後面解釋)
• HashMap可以存儲null的k-v;HashTable不能存儲null的k-v

寄語：任何你的不足，在你成功的那刻，都會被人說為特色。所以，堅持做你自己，而不是在路上被別人修改的面目全非