Collection筆記

在數學中，集合就是在一個

List , Set, Map都是接口，前兩個繼承至Collection接口，Map為獨立接口

List（清單）有序且可重複

優點：底層資料結構是數組，可以根據下标直接的找到對應的元素，是以查詢快。

缺點：但是因為數組增删需要移動元素，是以增删的效率低。

線程不安全，效率高

Vector的底層是 數組，優點和ArrayList一樣，但是線程安全，是以效率低下

1.iterator()

2.forEach(Consumer)

3.foreach 增強for循環

ps：Set.add 相同内容的元素時會失敗，但是程式正常運作

底層資料結構是哈希表（HashTable）

為了確定元素不重複，需要依賴兩個方法：重寫hashCode比較，比較hash值，然後重寫equals，若哈希值相同，則繼續比較相同hash值的 内容是否一緻

支援自定義排序

底層資料結構是紅黑樹（不可重複，有序）

確定有序：

1.排序對象可以實作Comparable接口

2.或者 new TreeSet時，設定Comparator比較器，自定義排序規則

同時，根據比較的傳回值是否為0來確定元素的唯一性

————————————————————————————

那麼在使用Collection集合時，我們選擇用誰呢？

元素是否不可重複（是否唯一），唯一的話，用Set 不唯一用List

用Set考慮是否有排序，排序用TreeSet或LinkedHashSet，不排序用HashSet

不确定的話預設用HashSet。

不唯一用List

用List考慮是否需要安全性，需要就用Vector，不需要就用ArrayList或者LinkedList（查詢多用：ArrayList

增删多用：LinkedList）

不确定的話預設用ArrayList。

ArrayList 和 LinkedList 的差別

ArraysList底層采用的是動态 數組 進行存儲，數組單向關聯。

LinkedList使用的是連結清單結構，每個元素由 ： 向前關聯節點，向後關聯節點，元素值組成

如果頻繁進行查詢操作，優先使用ArraysList，

因為ArraysList可以直接傳回數組中index位置的元素，通路集合元素時性能更高

如果進行修改操作較多，應該使用LinkedList

因為LinkedList，不需要改變數組的大小，

也不需要在數組裝滿的時候要将所有的資料重新裝入一個新的數組，LinkedList中插入或删除的時間複雜度僅為O(1)。

相同點：

1、ArrayList和Vector都是繼承了相同的父類和實作了相同的接口List

2、底層都是數組實作的

3、初始預設長度都為10。

不同點：

1、 Vector的方法都是同步的(Synchronized),是線程安全的(thread-safe)，

而ArrayList的方法不是，由于線程的同步必然要影響性能，是以,ArrayList的性能比Vector好。

2、 當Vector或ArrayList中的元素超過它的初始大小時,Vector會将它的容量翻倍

而ArrayList隻增加50%的大小，這樣,ArrayList就有利于節約記憶體空間。

3、HashSet 是如何 實作 值的去重的

調用HashSet中的add方法時，hashCode方法來擷取哈希值，

如果哈希值相同，再會繼續比較 equals 如果相同，說明兩個元素相同，不會存儲對應的元素

如果不同，則進行存儲。

在使用的時候，需要注意什麼事項

1.TreeSet存儲資料 有序，不重複

2.調用 add() 方法時會調用對象類實作的 Comparable 接口的 compareTo()方法

來與集合中的對象比較，根據方法傳回的結果有序存儲

使用TreeSet存儲時，對象類需要實作 Comparable 接口 或者

在使用構造器時，傳入一個 compartor 接口的實作類對象，自己規定排序規則。

1.HashMap允許空值作為鍵和值，而HashTable不允許空)。

2.HashMap是非同步的 非線程安全。

Hashtable是同步的，線程安全。

HashMap 的底層原理 （明天講、提前了解，現在能掌握最好）

HashMap是數組+連結清單+紅黑樹（JDK1.8增加了紅黑樹部分）實作的

HashMap基于Map接口實作，元素以鍵值對的方式存儲，并且允許使用null 建和null值，

因為key不允許重複，是以隻能有一個鍵為null,另外HashMap不能保證放入元素的順序，它是無序的，和放入的順序并不能相同。HashMap是線程不安全的。

HashMap的初始容量為16，HashMap擴容時是目前容量翻倍即:capacity*2

第一步首先将k,v封裝到Node對象當中（節點）。

第二步它的底層會調用K的hashCode()方法得出hash值

第三步通過哈希表函數/雜湊演算法，将hash值轉換成數組的下标，下标位置上如果沒有任何元素，就把Node添加到這個位置上。如果說下标對應的位置上有連結清單。

此時，就會拿着k和連結清單上每個節點的k進行equal。如果所有的equals方法傳回都是false，那麼這個新的節點将被添加到連結清單的末尾。如其中有一個equals傳回了true，那麼這個節點的value将會被覆寫。

第一步：先調用k的hashCode()方法得出哈希值，并通過雜湊演算法轉換成數組的下标。

第二步：通過上一步雜湊演算法轉換成數組的下标之後，在通過數組下标快速定位到某個位置上。重點了解如果這個位置上什麼都沒有，則傳回null。

如果這個位置上有單向連結清單，那麼它就會拿着參數K和單向連結清單上的每一個節點的K進行equals，如果所有equals方法都傳回false，則get方法傳回null。

如果其中一個節點的K和參數K進行equals傳回true，那麼此時該節點的value就是我們要找的value了，get方法最終傳回這個要找的value。

集合筆記，借鑒部落客：檾辭

https://www.yuque.com/docs/share/b742c60a-886c-4f0d-8677-cb0c13db0fec?#