Java基礎(chǔ) (5) - 集合

Java集合大致分為 List、Set、Queue和Map 四種體系，
List代表有序、重復(fù)的集合；（ArrayList、LinkedList、Vector）
Set代表無序、不可重復(fù)的集合; （HashSet、LInkedHashSet、TreeSet）
Queue Java5增加，代表一種隊(duì)列的集合 (priorityqueue)
Map則代表具有映射關(guān)系的集合

Collection接口
1.Set、LIst、Queue都繼承Collection接口。
2.HashSet不能存重復(fù)的值（元素可以為null）,線程不安全，且是無序的,如果想有序使用LinkedHashSet。(由于使用了鏈表 插入和刪除速度變快 但遍歷速度降低)
3.ArryaList能存重復(fù)的值（元素可以為null），有序的，線程不安全，如果想線程安全可以使用Vector(有序)。還有個(gè)常用的LinkedList，插入和刪除速度快，但遍歷速度慢。
4.queue

Map
1.HashMap 可以存重復(fù)的值（元素可以為null） 線程不安全，且是無序的。想要線程安全可以使用HashTable。但HashTable不能使用null作為鍵或值 ， 想要有序 可以使用LinkedHashMap。
2.HashMap和HashTab的區(qū)別https://blog.csdn.net/mynameishuangshuai/article/details/52748731
3.區(qū)別點(diǎn)https://blog.csdn.net/xiamiflying/article/details/73050577
4.HashMap原理 https://blog.csdn.net/visant/article/details/80045154
https://www.jianshu.com/p/8b372f3a195d/
參考:
https://www.jianshu.com/p/589d58033841
https://blog.csdn.net/world_snow/article/details/79073234

線程安全
同步集合類: vector 、HashTable、 同步集合包裝類 - Collections.synchronizedMap()和Collections.synchronizedList()?
并發(fā)集合類: ConcurrentHashMap 、CopyOnWriteArrayList、CopyOnWriteHashSet

同步集合比并發(fā)集合會(huì)慢得多，主要原因是鎖，同步集合會(huì)對(duì)整個(gè)Map或List加鎖
ConcurrentHashMap：把整個(gè)Map 劃分成幾個(gè)片段，只對(duì)相關(guān)的幾個(gè)片段上鎖，同時(shí)允許多線程訪問其他未上鎖的片段。
CopyOnWriteArrayList：CopyOnWriteArrayList、CopyOnWriteArraySet類（沒有CopyOnWriteMap實(shí)現(xiàn)）允許多個(gè)線程以非同步的方式讀，當(dāng)有線程寫的時(shí)候它會(huì)將整個(gè)List復(fù)制一個(gè)副本給它(寫在副本)，適合讀多寫少這種場景，這會(huì)比使用同步集合更具有可伸縮性。

Collection和Collections的區(qū)別
1.java.util.Collection 是一個(gè)集合接口（集合類的一個(gè)頂級(jí)接口）。它提供了對(duì)集合對(duì)象進(jìn)行基本操作的通用接口方法。List、Set、Vector都繼承了他。
2.Collections則是集合類的一個(gè)工具類/幫助類，其中提供了一系列靜態(tài)方法，用于對(duì)集合中元素進(jìn)行排序、搜索、線程安全等各種操作。

排序
void reverse(List list)：反轉(zhuǎn)
void shuffle(List list),隨機(jī)排序
void sort(List list),按自然排序的升序排序
void sort(List list, Comparator c);定制排序，由Comparator控制排序邏輯
void swap(List list, int i , int j),交換兩個(gè)索引位置的元素
void rotate(List list, int distance),旋轉(zhuǎn)。當(dāng)distance為正數(shù)時(shí)，將list后distance個(gè)元素整體移到前面。當(dāng)distance為負(fù)數(shù)時(shí)，將 list的前distance個(gè)元素整體移到后面。

查找，替換操作
int binarySearch(List list, Object key), 對(duì)List進(jìn)行二分查找，返回索引，注意List必須是有序的
int max(Collection coll),根據(jù)元素的自然順序，返回最大的元素。 類比int min(Collection coll)
int max(Collection coll, Comparator c)，根據(jù)定制排序，返回最大元素，排序規(guī)則由Comparatator類控制。類比int min(Collection coll, Comparator c)
void fill(List list, Object obj),用元素obj填充list中所有元素
int frequency(Collection c, Object o)，統(tǒng)計(jì)元素出現(xiàn)次數(shù)
int indexOfSubList(List list, List target), 統(tǒng)計(jì)targe在list中第一次出現(xiàn)的索引，找不到則返回-1，類比int lastIndexOfSubList(List source, list target).
boolean replaceAll(List list, Object oldVal, Object newVal), 用新元素替換舊元素。

同步控制
Collections.SynchronizedList()
Collections.SynchronizedSet()
Collections.synchronizedMap()

備注:
2個(gè)數(shù)組求全集可以轉(zhuǎn)成hashSet 交集可以用Collections的retainAll 差集可以用Collection的removeAll方法
參考:https://www.cnblogs.com/a2b1/p/7520099.html

TreeSet和TreeMap的關(guān)系
　　與HashSet完全類似，TreeSet里面絕大部分方法都是直接調(diào)用TreeMap方法來實(shí)現(xiàn)的。
相同點(diǎn)：

• TreeMap和TreeSet都是非同步集合，都是線程不安全，可使用方法Collections工具類方法來實(shí)現(xiàn)同步
• 查詢速度都要比Hash集合慢，他們內(nèi)部對(duì)元素的操作時(shí)間復(fù)雜度為O(logN)，而HashMap/HashSet則為O(1)。
• TreeMap和TreeSet都是有序的集合，也就是說他們存儲(chǔ)的值都是排好序的。
  不同點(diǎn)：
• 最主要的區(qū)別就是TreeSet和TreeMap分別實(shí)現(xiàn)Set和Map接口
• TreeSet只存儲(chǔ)一個(gè)對(duì)象，而TreeMap存儲(chǔ)兩個(gè)對(duì)象Key和Value（僅僅key對(duì)象有序）
• TreeSet中不能有重復(fù)對(duì)象，而TreeMap中可以存在
• TreeMap的底層采用紅黑樹的實(shí)現(xiàn)，完成數(shù)據(jù)有序的插入，排序

參考:https://www.cnblogs.com/pony1223/p/7907173.html

PriorityQueu
https://www.cnblogs.com/Elliott-Su-Faith-change-our-life/p/7472265.html