從零開始學java--集合類（2）

集合類

Queue

隊列的使用：

雙端隊列（Deque）

Map和Set

概念：

模型：

Map

常見方法說明：

注意：

TreeMap和HashMap的區別：

Set

常見方法說明：

注意：

TreeSet和HashSet的區別：

Stream流

Collections工具類

常用方法：

Queue

隊列的使用：

在Java中，Queue是個接口，底層是通過鏈表實現的。 ?

方法	功能
boolean add(E e)	入隊列（插入失敗會拋出異常）
boolean offer(E e)	入隊列
E remove( )	出隊列（隊列已經為空會拋出異常）
E poll( )	出隊列
element( )	獲取對頭元素（隊列已經為空會拋出異常）
peek( )	獲取隊頭元素
int size( )	獲取隊列中有效元素個數
boolean isEmpty()	boolean isEmpty()

注意：Queue是個接口，在實例化時必須實例化LinkedList的對象，因為LinkedList實現了Queue接口。

雙端隊列（Deque）

雙端隊列（deque）是指允許兩端都可以進行入隊和出隊操作的隊列，deque 是 “double ended queue” 的簡稱。那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊。

雙端隊列既可以當做普通隊列使用，也可以當做棧來使用。

Deque是一個接口，使用時必須創建LinkedList的對象。

Map和Set

概念：

Map和set是一種專門用來進行搜索的容器或者數據結構，其搜索的效率與其具體的實例化子類有關。以前常見的搜索方式有：

直接遍歷，時間復雜度為O(N)，元素如果比較多效率會非常慢
二分查找，時間復雜度為 ,但搜索前必須要求序列是有序的

上述排序比較適合靜態類型的查找，即一般不會對區間進行插入和刪除操作了，而現實中的查找比如：

根據姓名查詢考試成績
通訊錄，即根據姓名查詢聯系方式
不重復集合，即需要先搜索關鍵字是否已經在集合中

可能在查找時進行一些插入和刪除的操作，即動態查找，那上述兩種方式就不太適合了，本節介紹的Map和Set是一種適合動態查找的集合容器。

模型：

一般把搜索的數據稱為關鍵字（Key），和關鍵字對應的稱為值（Value），將其稱之為Key-value的鍵值對，所以模型會有兩種：

純 key 模型，比如：

有一個英文詞典，快速查找一個單詞是否在詞典中
快速查找某個名字在不在通訊錄中

Key-Value 模型，比如：

統計文件中每個單詞出現的次數，統計結果是每個單詞都有與其對應的次數：<單詞，單詞出現的次數>
梁山好漢的江湖綽號：每個好漢都有自己的江湖綽號

而Map中存儲的就是key-value的鍵值對，Set中只存儲了Key。

Map

Map是一個接口類，該類沒有繼承自Collection，該類中存儲的是結構的鍵值對，并且K一定是唯一的，不能重復。 ?

常見方法說明：

方法	解釋
V get(Object key)	返回 key 對應的 value
V getOrDefault(Object key, V defaultValue)	返回 key 對應的 value，key 不存在，返回默認值
V put(K key, V value)	設置 key 對應的 value
V remove(Object key)	刪除 key 對應的映射關系
void putAll(Map<? extands K, ? extands V)	將另一個Map中的所有鍵值對添加到當前Map中
void clear( )	清空整個Map
Set keySet()	返回所有 key 的不重復集合
Collection values()	返回所有 value 的可重復集合
Set<Map.Entry<K,V>> entrySet()	返回所有的 key-value 映射關系
boolean containsKey(Object key)	判斷是否包含 key
boolean containsValue(Object value)	判斷是否包含 value

注意：

Map是一個接口，不能直接實例化對象，如果要實例化對象只能實例化其實現類TreeMap或者HashMap
Map中存放鍵值對的Key是唯一的，value是可以重復的
在TreeMap中插入鍵值對時，key不能為空，否則就會拋NullPointerException異常，value可以為空。但是HashMap的key和value都可以為空。
Map中的Key可以全部分離出來，存儲到Set中來進行訪問(因為Key不能重復)。
Map中的value可以全部分離出來，存儲在Collection的任何一個子集合中(value可能有重復)。
Map中鍵值對的Key不能直接修改，value可以修改，如果要修改key，只能先將該key刪除掉，然后再來進行重新插入。

TreeMap和HashMap的區別：

Map底層結構	TreeMap	HashMap
底層結構	紅黑樹	哈希桶
插入/刪除/查找時間復雜度	O(log2N)	O(1)
是否有序	關于Key有序	無序
線程安全	不安全	不安全
插入/刪除/查找區別	需要進行元素比較	通過哈希函數計算哈希地址
比較與覆寫	key必須能夠比較，否則會拋出ClassCastException異常	自定義類型需要覆寫equals和hashCode方法
應用場景	需要Key有序場景下	Key是否有序不關心，需要更高的時間性能

LinkedHashMap按照插入順序遍歷

    public static void main(String[] args){Map<Integer,String> map=new HashMap<>();map.put(1,"小紅");map.put(2,"小明");map.forEach((k,v)->System.out.println(k+"="+v));Map<Integer,String>map1=new TreeMap<>((a,b)->b-a); //按倒序輸出map1.put(2,"m");map1.put(1,"j");map1.put(3,"a");map1.forEach((k1,v1)->System.out.println(k1+"="+v1));}
/*
1=小紅
2=小明
3=a
2=m
1=j
*/

Set

常見方法說明：

方法	解釋
boolean add(E e)	添加元素，但重復元素不會被添加成功
void clear()	清空集合
boolean contains(Object o)	判斷o是否在集合中
Iterator<E> iterator()	返回迭代器
boolean remove(Object o)	刪除集合中的o
int size()	返回set中元素的個數
boolean isEmpty()	檢測set是否為空，空返回true，否則返回false
Object[] toArray()	將set中的元素轉換為數組返回
boolean containsAll(Collection<?> c)	集合c中的元素是否在set中全部存在，是返回true,否則返回false
boolean addAll(Collection<?extends E>c)	將集合c中的元素添加到set中，可以達到去重的效果

注意：

Set是繼承自Collection的一個接口類
Set中只存儲了key，并且要求key一定要唯一
不支持隨機訪問（不允許通過下標訪問）
TreeSet的底層是使用Map來實現的，其使用key與Object的一個默認對象作為鍵值對插入到Map中的
Set最大的功能就是對集合中的元素進行去重
實現Set接口的常用類有TreeSet和HashSet，還有一個LinkedHashSet，LinkedHashSet是在HashSet的基礎上維護了一個雙向鏈表來記錄元素的插入次序。?
Set中的Key不能修改，如果要修改，先將原來的刪除掉，然后再重新插入
TreeSet中不能插入null的key，HashSet可以。

TreeSet和HashSet的區別：

Set底層結構	TreeSet	HashSet
底層結構	紅黑樹	哈希桶
插入/刪除/查找時間復雜度	O	O(1)
是否有序	關于key有序	不一定有序
線程安全	不安全	不安全
插入/刪除/查找區別	按照紅黑樹的特性來進行插入和刪除	1、先計算key哈希地址 2、然后進行插入和刪除
比較與覆寫	key必須能夠比較，否則會拋出ClassCastException異常	自定義類型需要覆寫equals和hashCode方法
應用場景	需要Key有序場景下	Key是否有序不關心，需要更高的時間性能

Stream流

Java 8 API添加了一個新的抽象稱為流Stream，可以讓你以一種聲明的方式處理數據。Stream使用一種類似用SQL語句從數據庫查詢數據的直觀方式來提供一種對Java集合運算和表達的高階抽象。這種風格將要處理的元素集合看作一種流，流在管道中傳輸，并且可以在管道的節點上進行處理，比如篩選、排序、聚合等。

    public static void main(String[] args){List<String> list =new ArrayList<>(Arrays.asList("aaaa","Saaaa","Saaaa","xx","Xss","Lxxx"));//刪除長度不大于3的字符串//刪除首字母不為大寫的字母//去掉重復的字符串list=list.stream().filter(str ->str.length()>3) //保留的條件.filter(str ->str.charAt(0)>='A'&&str.charAt(0)<='Z').distinct()  //去重，用equals判斷.collect(Collectors.toList());System.out.println(list);List<Integer>collect=list.stream().map(String::length).collect(Collectors.toList());System.out.println(collect);}
//輸出[Saaaa, Lxxx]
//[5, 4]

不能認為每一步是直接依次執行的。Stream會先記錄每一步操作，而不是直接開始執行內容，當整個鏈式調用完成后，才會依次執行，也就是說需要的時候，工廠的機器才會按照預定的流程啟動。

生成隨機數：

    public static void main(String[] args){Random random=new Random();random.ints(-100,100).limit(10).filter(i -> i<0) //只保留小于0的數字.sorted()  //默認從小到大排序.forEach(System.out::println);}

Collections工具類

Arrays是一個用于操作數組的工具類

Collections類是專用于集合的工具類

常用方法：

    public static void main(String[] args){List list1=new ArrayList<>(Arrays.asList(1,4,5,2,9,0));//求最大值最小值Collections.max(list1);Collections.min(list1);//對集合進行二分搜索（注意：集合的具體類型必須是實現Comparable接口的類）Collections.sort(list1);System.out.println(Collections.binarySearch(list1,4));
//輸出3//對集合的元素進行快速填充，注意這個填充是對集合中的已有元素進行覆蓋//如果集合中本身沒有元素，那么fill操作不會生效Collections.fill(list1,0);System.out.println(list1);
//輸出[0, 0, 0, 0, 0, 0]//emptyXXX快速生成一個只讀的空集合List<Integer>list2=Collections.emptyList();//Collections.singletonList()會生成一個只有一個元素的Listlist2.add(10); //不支持，會直接拋出異常//將一個可修改的集合變成只讀的集合：List<Integer>list3=new ArrayList<>(Arrays.asList(1,3,3,24));List<Integer>newList=Collections.unmodifiableList(list3);newList.add(10); //不支持，會拋出異常//尋找子集合的位置System.out.println(Collections.indexOfSubList(list3,Arrays.asList(3,3)));
//輸出1}

由于泛型機制上的一些漏洞，實際上對應類型的集合類有可能會存放其他類型的值，泛型的檢查值存在于編譯階段，我們只要繞過這個階段，在實際運行時，并不會真的進行類型檢查，要解決這些問題就是在運行時進行類型檢查：

    public static void main(String[] args){List list1=new ArrayList<>(Arrays.asList(1,4,5,2,9,0));list1=Collections.checkedList(list1,Integer.class);list1.add("aaa");System.out.println(list1);}
//在輸出時會報錯