集合框架（重點）

第十五天

集合框架

1.什么是集合 Collections

集合Collection，也是一個數據容器，類似于數組，但是和數組是不一樣的。集合是一個可變的容器，可以隨時向集合中添加元素，也可以隨時從集合中刪除元素。另外，集合還提供了若干個用來操作集合中數據的方法。

集合里的數據，我們稱之為元素(elements)；集合只能用來存儲引用類型的數據，不能存儲八大基本**數據類型的數據**。

Java SE 5.0以前，集合的元素只要是Object類型就行，那個時候任何對象都可以存放在集合內，但是從集合中獲取對象后，需要進行正確的強制類型轉換。但是，Java SE 5.0 以后，可以使用新特性”泛型”，用來指定要存放在集合中的對象類型。避免了強制轉換的麻煩。

2.集合與數組

數組是定長的容器，一旦實例化完成，長度不能改變。集合是變長的，可以隨時的進行增刪操作。
數組中可以存儲基本數據類型和引用數據類型的元素，集合中只能存儲引用數據類型的元素。
數組的操作比較單一，只能通過下標進行訪問。集合中提供了若干個方便對元素進行操作的方法。

3.集合框架體系圖

父接口Collection

Collection 接口是 List、Set 和 Queue 接口的父接口，該接口里定義了他們三個子接口的共同方法。既可用于操作 Set 集合，也可用于操作 List 和 Queue 集合。作為父接口，其子類集合的對象，存儲元素的特點，可能是無序的，也可能是有序的，因此在父接口中并沒有定義通過下標獲取元素的方法功能。

// 1、實例化一個  ArrayList 對象，并向上轉型為  Collection 類型。 
// ?  向上轉型后的對象，只能訪問父類或者接口中的成員
// ?  在這里，collection 將只能夠訪問  Collection 接口中的成員。
Collection<String> collection = new ArrayList<>();
?
// 2、向集合中添加元素
collection.add("lily");
collection.add("lucy");
collection.add("Uncle wang");
collection.add("Polly");
?
// 3、向集合中批量的添加元素（將一個集合中的元素依次添加到這個集合中）
collection.addAll(collection);
// 4、刪除從前往后第一個匹配的元素
collection.remove("lily");
?
// 5、準備另外一個集合
Collection<String> list = new ArrayList<>();
list.add("Han Meimei");
list.add("Li Lei");
list.add("Uncle wang");
list.add("Polly");
?
// 6、刪除所有的在另外一個集合中存在的元素
// ? 刪除邏輯：遍歷集合，將每一個元素帶入到參數集合中判斷是否存在，如果存在，就刪除這個元素。
//刪除的是list中的集合元素
collection.removeAll(list);
?
// 7、刪除所有的滿足條件的元素
// ? 刪除邏輯：遍歷集合，將每一個元素帶入到參數方法中，如果返回值是true，需要刪除這個元素。
collection.removeIf(ele -> ele.startsWith("lu"));
?
// 8、清空所有
collection.clear();
?
// 9、保留在另外一個集合中存在的元素
// ? 邏輯：遍歷集合，將每一個元素帶入到參數集合中，判斷是否存在，如果存在則保留這個元素，如果 不存在，刪除
collection.retainAll(list);
?
// 10、判斷集合中是否包含指定的元素
boolean ret = collection.contains("Uncle wang");
System.out.println(ret);
?
// 11、判斷參數集合中的每一個元素是否都在當前集合中包含
boolean ret1 = collection.containsAll(list);
System.out.println(ret1);
?
// 12、判斷兩個集合是否相同（依次比較兩個集合中的每一個元素，判斷是否完全相同） 
// ?  只有當兩個集合中的元素數量、元素一一對應
boolean ret2 = collection.equals(list);
System.out.println(ret2);
?
// 13、判斷一個集合是否為空
boolean ret3 = collection.isEmpty();
System.out.println(ret3);
?
// 14、獲取一個集合中元素的數量，類似于數組長度
int size = collection.size();
System.out.println(size);
?
// 15、轉成  Object 數組
Object[] array = collection.toArray();
System.out.println(Arrays.toString(array));
?
// 16、轉成指定類型的數組
String[] arr = collection.toArray(new String[0]);
System.out.println(Arrays.toString(arr));
?
System.out.println(collection);

1.集合的迭代

在進行集合的遍歷的時候，方式其實很多。但是，基本上所有的遍歷，都與 Iterable 接口有關。這個接口提供了對集合進行迭代的方法。只有實現了這個接口，才可以使用增強for循環進行遍歷。

1）增強for循環

for (String ele : collection) {System.out.println(ele);
}

注意事項：

增強for循環中不允許對集合中的元素進行修改，修改是無效的
增強for循環中不允許對集合的長度進行修改，否則會出現 ConcurrentModi?cationException

2）迭代器

迭代器Iterator，是一個接口， Collection集合中有一個方法 iterator() 可以獲取這個接口的實現類對象。在這個迭代器中，維護了一個引用，指向集合中的某一個元素。默認指向一個集合前不存在的元素，可以認為是下標為-1的元素。

迭代器的工作原理：循環調用 next() 方法進行向后的元素指向，并返回新的指向的元素。同時，在向后進行遍歷的過程中，使用 hasNext() 判斷是否還有下一個元素可以迭代。

在迭代器使用的過程中，需要注意：

不應該對集合中的元素進行修改
不應該對集合的長度進行修改
如果非要修改，需要使用迭代器的方法，不能使用的集合的方法。

// 1、獲取迭代器對象，這里的 ? iterator 是一個  Iterator 接口的實現類對象
Iterator<String> iterator = collection.iterator();
?
// 2、使用迭代器進行集合的遍歷
while (iterator.hasNext()) {// 讓迭代器向后指向一位，并返回這一位的元素String element = iterator.next();System.out.println(element);
}

子接口List

List 是一個元素有序、且可重復的集合，集合中的每個元素都有其對應的順序索引，從0開始
List 允許使用重復元素，可以通過索引來訪問指定位置的集合元素。
List 默認按元素的添加順序設置元素的索引。
List 集合里添加了一些根據索引來操作集合元素的方法

1.ArrayList和LinkedList的區別

ArrayList是一個可變大小組，初始容量為10，當數組滿時，容量擴大1.5倍。新建一個更大的數組，將老數組復制到新數組上。他在查找元素更高效，因為數組是由一塊連續區域的內存實現，可以通過地址索引計算出值的位置。而當刪除或新增一個元素時，其他元素都要移動。
LinkedList是一個雙向鏈表，不考慮內存大小，原則上是可以無限大的，鏈表由不連續內存實現，鏈表中的每個節點都包含了前一個和后一個節點的引用，所以他在新增上是高效的。當查找時，它需要通過一個以知元素向下遍歷才能找到要找到的值，

2.ArrayList線程安全嗎?想要線程安全怎么辦?

非線程安全的
使用Collections.synchronizedList方法可以得到一個線程安全的List，但在ArrayList的所有公共方法上加鎖
使用CopyOnWriteArrayList或手動加鎖

3.CopyOnWriteArrayList怎么保證線程安全?它的優點和缺點呢?

讀不加鎖，寫加鎖
優點：

- 讀高效

- 線程安全

- 高并發性

缺點：

- 寫性能低

- 內存占用高

- 不適合實時性要求高的場景

4.數組和鏈表的區別

數組每個元素都是連續的，通過下標進行訪問
鏈表中的元素不連續的，必須獲得某個元素后，才能訪問后續元素
數組可以由一塊連續區域的內存實現，數組從申請之后就會固定
鏈表可以由不連續內存實現，內存足夠時可以任意申請空間
數組：查詢O(1)，插入/刪除O(n)
鏈表：查詢O(n)，插入/刪除O(1)

5.常用方法

1）添加元素

boolean add(E e)

作用：向列表末尾添加指定的元素

void add(int index, E element)

作用：在列表的指定位置添加元素

boolean addAll(Collection c)

作用：將集合c中的所有元素添加到列表的結尾

boolean addAll(int index, Collection c)

作用：：將集合c中的所有元素添加到列表的指定位置

2）獲取元素

E get(int index)

作用：返回列表指定位置的元素

3）查找元素

int indexOf(Object obj)

作用：返回列表中指定元素第一次出現的位置，如果沒有該元素，返回-1

int lastIndexOf(Object obj)

作用：返回列表中指定元素最后一次出現的位置，如果沒有該元素，返回-1

4）移除元素

E remove(int index)

作用：移除集合中指定位置的元素，返回被移除掉的元素對象

5）修改元素

E set(int index, E element)

作用：用指定元素替換指定位置上的元素，返回被替換出來的元素對象

6）截取子集

List subList(int fromIndex, int toIndex)

作用：截取子集，返回集合中指定的fromIndex 到 toIndex之間部分視圖，包前不包后

7）案例演示

// 1、實例化一個  List 接口的實現類對象，并向上轉型為接口類型
List<Integer> list = new ArrayList<>();
// 2、增
list.add(10);
list.add(20);
// 3、在指定的位置插入元素
list.add(1, 15);
// 4、刪除元素
list.remove(Integer.valueOf(15));
// 5、按照下標刪除元素
list.remove(0);
// 6、通過下標設置元素
list.set(0, 200);
// 7、通過下標獲取元素
Integer element = list.get(0);
// 8、獲取某一個元素出現的下標
int index = list.indexOf(200);
// 9、獲取某一個元素最后一次出現的下標
int index = list.lastIndexOf(200);
?
System.out.println(element);

6.ListIterator

ListIterator是Iterator接口的子接口，繼承到了Iterator中所有的方法，同時自己也添加了若干個方法。允許使用ListIterator在進行元素迭代的時候，對集合中的數據進行修改，或者對集合的長度進行修改。同時，使用ListIterator還可以進行倒序的迭代。

// 3、在迭代的過程中，修改集合
while (iterator.hasNext()) {// 向后指向一位，并返回當前指向的元素String ele = iterator.next();if (ele.equals("Vertu")) {// 在迭代的過程中，刪除這個元素iterator.remove();// 在迭代的過程中，添加一個元素（加在當前迭代的這個元素的后面）iterator.add("HTC");// 在迭代的過程中，對當前迭代的元素進行修改iterator.set("Nokia");}
}
?
//倒敘
ArrayList<String> objects2 = new ArrayList<>();objects2.add("lily");objects2.add("lucy");objects2.add("Uncle wang");objects2.add("Polly");ListIterator<String> iterator = objects2.listIterator();
// ? ? ?  ListIterator<String> iterator = objects2.listIterator(4); //不寫值，不正序就不會找到while (iterator.hasNext()){Object next = iterator.next();System.out.println(next+" ");}while (iterator.hasPrevious()){Object previous = iterator.previous();System.out.println(previous+" ");System.out.println(1);}

子接口Set

Set集合中的元素是無序的(取出或者打印的順序與存入的順序無關)
Set集合中的元素不能重復
底層實現是hashmap

1.HashSet

HashSet 具有以下特點：

不能保證元素的排列順序
HashSet 不是線程安全的
集合元素可以是 null

2.LinkedHashSet

LinkedHashSet 是 HashSet 的子類
LinkedHashSet 集合根據元素的 hashCode 值來決定元素的存儲位置，但它同時使用鏈表維護元素的次序，這使得元素看起來是以插入順序保存的。
LinkedHashSet 性能插入性能略低于 HashSet，但在迭代訪問 Set 里的全部元素時有很好的性能。
LinkedHashSet 不允許集合元素重復。

3.TreeSet

TreeSet 是 SortedSet 接口的實現類， TreeSet集合是用來對元素進行排序的,同樣他也可以保證元素的唯一。TreeSet 可以確保集合元素處于排序狀態。
TreeSet 支持兩種排序方法：自然排序和定制排序。默認情況下，TreeSet 采用自然排序。
必須實現Comparable，否則會報Exception in thread "main" java.lang.ClassCastException: com.youcai.day10._01.teacher cannot be cast to java.lang.Comparable

4.set去重

子接口Queue

隊列Queue也是Collection的一個子接口，它也是常用的數據結構，可以將隊列看成特殊的線性表，隊列限制對線性表的訪問方式：只能從一端添加(offer)元素，從另一端取出（poll）元素。
隊列遵循先進先出（FIFO first Input First Output）的原則
實現類LinkedList也實現了該接口，選擇此類實現Queue的原因在于Queue經常要進行添加和刪除操作，而LinkedList在這方面效率比較高。
其主要方法如下：
- 方法解析
  boolean offer(E e) 作用：將一個對象添加到隊尾，如果添加成功返回true
  E poll() 作用：從隊首刪除并返回這個元素
  E peek() 作用：查看隊首的元素

方法	解析
boolean offer(E e)	作用：將一個對象添加到隊尾，如果添加成功返回true
E poll()	作用：從隊首刪除并返回這個元素
E peek()	作用：查看隊首的元素

public void testQueue(){Queue<String> queue = new LinkedList<>();queue.offer("a");queue.offer("b");queue.offer("c");System.out.println(queue); // [a,b,c]String str = queue.peek();System.out.println(str); // awhile(queue.size() > 0){str = queue.poll();System.out.println(str+" "); // a b c}
}

子接口Deque

Deque是Queue的子接口，定義了所謂的”雙端隊列”，即從隊列的兩端分別可以入隊（offer）和出隊（poll）。同樣，LinkedList實現了該接口

如果將Deque限制為只能一端入隊和出隊，則可以實現“棧”(Stack)的數據結構,對于棧而言，入棧被稱為push，出棧被稱為pop。遵循先進后（FILO）出原則

public void testDeque(){Deque<String> stack = new LinkedList<>();stack.push("a");stack.push("b");stack.push("c");System.out.println(push); // [c,b,a]String str = queue.peek();System.out.println(str); // cwhile(stack.size() > 0){str = stack.pop();System.out.println(str+" "); // c b a}
}

父接口Map

Map是集合框架中的另一個父接口，它用來保存具有映射(一對一)關系的數據，這樣的數據稱之為鍵值對(Key-Value-Pair）。key可以看成是value的索引。特點如下：

key和value必須是引用類型的數據
作為key，在Map集合中不允許重復，Value可以重復
key可以為null
key和value之間存在單向一對一關系，通過指定的key總能找到唯一，確定的value

1.常用方法

/ 1、實例化一個 ?Map 接口的實現類的對象，并向上轉型為 ?Map 接口類型
Map<String, String> map = new HashMap<>();
?
// 2、增，向集合中添加一個鍵值對
map.put("name", "xiaoming");
map.put("age", "12");
map.put("gender", "male");
?
// 3、增，如果增的這個鍵在Map中已經存在，此時會用新的值覆蓋原來的值
map.put("age", "20");
?
// 4、增，當這個鍵不存在的時候，才會增 ; 如果存在，這個方法沒有任何效果
map.putIfAbsent("age", "30");
?
// 5、增，從一個Map集合中添加鍵值對，如果兩個Map中存在相同的鍵，則會用新值覆蓋原來的值
Map<String, String> tmp = new HashMap<>();
tmp.put("name", "xiaobai");
tmp.put("java", "89");
tmp.put("mysql", "78");
map.putAll(tmp);
System.out.println(map);
?
// 6、刪，按照鍵刪除鍵值對
map.remove("age");
System.out.println(map);
?
// 7、刪，刪除指定的鍵值對，只有當鍵和值都能夠匹配上的時候，才會刪除
map.remove("name", "xiaobai");
?
// 8、刪，清空所有的鍵值對
map.clear();
?
?
// 9、改，通過鍵，修改值
map.replace("gender", "female");
System.out.println(map);
?
// 10、改，只有當鍵和值都能夠匹配上，才會修改值
map.replace("gender", "female", "Unknown");
System.out.println(map);
?
// 11、 /*
V apply(K key, V oldValue):
將Map集合中的每一個鍵值對都帶入到這個方法中，用返回值替換原來的值 */
// 需求 : 將現在所有的成績后面添加上"分 "
map.replaceAll((k, v) -> {
if (k.matches("java|scala|linux|mysql|hadoop")) { return v + "分 ";
}
return v;
});
System.out.println(map);
// 12、查詢（通過鍵，查詢值）（如果不存在這個鍵，則結果是  null）
String value = ?map.get("java1");
System.out.println(value);
?
// 13、查詢（通過鍵查詢值，如果不存在這個鍵，會返回默認的值）
String value2 = map.getOrDefault("java1", "0");
System.out.println(value2);
?
// 1、判斷集合中是否包含指定的鍵
map.containsKey("java");
?
// 2、判斷集合中是否包含指定的值
map.containsValue(98);
?
// 3、獲取集合中元素的數量（鍵值對的數量）
map.size();
?
// 4、判斷集合是否是一個空集合
map.isEmpty();
?
// 5、獲取所有的值
Collection<Integer> values = map.values();

2.Map遍歷

Map提供了三種遍歷方式

1)遍歷所有的key

Set<K> keySet();

該方法會將當前Map中的所有key存入一個Set集合后返回

2)遍歷所有的key-value

Set<Entry<K,V>>  entrySet()Map<Object, Object> objectObjectMap = new HashMap<>();
objectObjectMap.put("1", "1");
objectObjectMap.put("2", "2");
objectObjectMap.put("3", "3");
Set<Map.Entry<Object, Object>> entries = objectObjectMap.entrySet();
for (Map.Entry<Object, Object> s:  entries){System.out.println(s.getKey()+"--"+s.getValue());
}

該方法會將當前Map中的每一組key-value封裝成Entry對象存入Set集合后返回

3)遍歷所有的value(不常用)

Collection<V> values

3.hashMap實現原理

在1.8之前是用鏈表加數組實現的，并使用頭插法插入元素，在1.8之后使用數組鏈表紅黑樹實現的，當數組大于64，鏈表大于8，鏈表會轉成紅黑樹，為了解決頭插法產生的死循環，改為尾插法。hashMap是通過hash方法找到對應的存儲位置。如果hash值相同，key值相同覆蓋，不同會將數組插入鏈表或紅黑樹，Hashmap的初始值是17加載因子是0.75，所以當已將使用12個空間時，會擴大2倍，并且已有的數據會根據新的長度計算出對應的位置。HashMap是線程不安全的，會發生數據覆蓋，size不準確，數據不一致問題。線程安全替代類：ConcurrentHashMap。

4.紅黑樹介紹

一種自平衡的二叉搜索樹：

- 節點紅或黑

- 根節點黑色

- 每個葉子節點黑色

- 如果一個節點是紅色，則它的子節點必須是黑色

- 從任一節點到其每個子節點的所有路徑會有相同數目的黑色節點

- 通過變色和旋轉保持平衡

5.HashMap與HashTable、ConcurrentHashMap

Hashtable線程安全通過方法使用synchronized關鍵字進行同步，保證了多線程的并發安全性。由于方法的同步鎖機制，性能低于HashMap。不允許null鍵和null值，插入null鍵值會拋出NullPointerException
HashMap：非線程安全的，沒有線程同步機制。單線程性能高于Hashtable，允許一個null鍵和多個null值
ConcurrentHashMap底層由數組+鏈表+紅黑樹組成，是線程安全的，使用了分段鎖技術，將哈希表分成很多段，每個段有獨立的鎖。多個線程同時訪問，只需鎖住操作的那個段而不是整個表，提高并發性能。在JDK1.8后采用CAS+synchronized保證線程安全，鎖粒度更細，從段鎖到桶鎖，添加元素時判斷某個桶是否為空，空使用CAS添加，不空使用synchronized。key和value都不允許null。

6.HashMap的hash方法是如何實現的?

hash方法的功能是根據Key來定位這個K-V在鏈表數組中的位置的。也就是hash方法的輸入應該是個Object類型的Key，輸出應該是個int類型的數組下標。最簡單的話，我們只要調用Object對象的hashCode()方法，該方法會返回一個整數，然后用這個數對HashMap或者HashTable的容量進行取模就行了。
在這里面，HashMap的hash方法為了提升效率，主要用到了以下技術手段：
1. 使用位運算(&)來代替取模運算(%)，因為位運算(&)效率要比代替取模運算(%)高很多，主要原因是位運算直接對內存數據進行操作，不需要轉成十進制，因此處理速度非常快。
2. 對hashcode進行擾動計算，防止不同hashCode的高位不同但低位相同導致的hash沖突。簡單點說，就是為了把高位的特征和低位的特征組合起來，降低哈希沖突的概率，也就是說，盡量做到任何一位的變化都能對最終得到的結果產生影響。

7.hash沖突通常怎么解決?

1.開放定址法開放定址法就是一旦發生了沖突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。這種方法的缺點是可能導致“聚集”問題，降低哈希表的性能。 2.鏈地址法最常用的解決哈希沖突的方法之一。每個哈希桶（bucket）指向一個鏈表。當發生沖突時，新的元素將被添加到這個鏈表的末尾。在Java中，HashMap就是通過這種方式來解決哈希沖突的。Java 8之前，HashMap使用鏈表來實現；從Java 8開始，當鏈表長度超過一定閾值時，鏈表會轉換為紅黑樹，以提高搜索效率。 3.再哈希法當哈希地址發生沖突用其他的函數計算另一個哈希函數地址，直到沖突不再產生為止。這種方法需要額外的計算，但可以有效降低沖突率。 4.建立公共溢出區將哈希表分為基本表和溢出表兩部分，發生沖突的元素都放入溢出表中。 5.一致性hash 主要用于分布式系統中，如分布式緩存。它通過將數據均勻分布到多個節點上來減少沖突。

8.LinkedHashMap

LinkedHashMap 是 HashMap 的子類

LinkedHashMap 可以維護 Map 的迭代順序：迭代順序與 Key-Value 對的插入順序一致

9.TreeMap

TreeMap 存儲 Key-Value對時，需要根據 Key 對 key-value 對進行排序。TreeMap 可以保證所有的 Key-Value 對處于有序狀態。

注意：TreeMap里的key，是使用comparaTo來確定是否唯一的，而不是調用HashCode和equals的

TreeMap 的 Key 的排序：

自然排序：TreeMap 的所有的 Key 必須實現 Comparable 接口，而且所有的 Key 應該是同一個類的對象，否則將會拋出 ClassCastException
定制排序：創建 TreeMap 時，傳入一個 Comparator 對象，該對象負責對 TreeMap 中的所有 key 進行排序。此時不需要 Map 的 Key 實現 Comparable 接口

10.Properties

Properties 類是 Hashtable 的子類，該對象用于處理屬性文件

由于屬性文件里的 key、value 都是字符串類型，所以 properties 里的 Key 和 Value 都是字符串類型的