java學習筆記（11）——集合
1 概述
數組和集合優缺點？
- 相同點：集合、數組都是對多個資料進行存儲操作的結構，簡稱Java容器
-
數組弊端：
數組一旦定義好，其元素的類型也就确定了
一旦初始化以後，其長度就不可修改。
數組中提供的方法非常限，對于添加、删除、插入資料等操作，非常不便，同時效率不高。
擷取數組中實際元素的個數的需求，數組沒有現成的屬性或方法可用
數組存儲資料的特點：有序、可重複。對于無序、不可重複的需求，不能滿足。
》》》》》集合：解決數組存儲資料方面的弊端。
2 單列集合架構結構Collection
2.1 Collection接口常用方法
- add(Object e):将元素e添加到集合coll中
- size():擷取添加的元素的個數
- addAll(Collection coll1):将coll1集合中的元素添加到目前的集合中
- clear():清空集合元素
- isEmpty():判斷目前集合是否為空
public void test1(){
Collection coll = new ArrayList();
//add(Object e):将元素e添加到集合coll中
coll.add("AA");
coll.add("BB");
coll.add(123);//自動裝箱
coll.add(new Date());
//size():擷取添加的元素的個數
System.out.println(coll.size());//4
//addAll(Collection coll1):将coll1集合中的元素添加到目前的集合中
Collection coll1 = new ArrayList();
coll1.add(456);
coll1.add("CC");
coll.addAll(coll1);
System.out.println(coll.size());//6
System.out.println(coll);
//clear():清空集合元素
coll.clear();
//isEmpty():判斷目前集合是否為空
System.out.println(coll.isEmpty());
}
- contains(Object obj):判斷目前集合中是否包含obj
- containsAll(Collection coll1):判斷形參coll1中的所有元素是否都存在于目前集合中
- remove(Object obj):從目前集合中移除obj元素。
- removeAll(Collection coll1):差集：從目前集合中移除coll1中所有的元素
- retainAll(Collection coll1):交集：擷取目前集合和coll1集合的交集，并傳回給目前集合
- equals(Object obj):要想傳回true，需要目前集合和形參集合的元素都相同。
- hashCode():傳回目前對象的哈希值
- 集合 —>數組：toArray()
- 數組 —>集合:調用Arrays類的靜态方法asList()
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
// Person p = new Person("Jerry",20);
// coll.add(p);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//1.contains(Object obj):判斷目前集合中是否包含obj
//我們在判斷時會調用obj對象所在類的equals()。
boolean contains = coll.contains(123);
System.out.println(contains);//true
System.out.println(coll.contains(new String("Tom")));//true
// System.out.println(coll.contains(p));//true
System.out.println(coll.contains(new Person("Jerry",20)));//false -->true
//2.containsAll(Collection coll1):判斷形參coll1中的所有元素是否都存在于目前集合中。
Collection coll1 = Arrays.asList(123,4567);
System.out.println(coll.containsAll(coll1));
}
@Test
public void test2(){
//3.remove(Object obj):從目前集合中移除obj元素。
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
coll.remove(1234);
System.out.println(coll);
coll.remove(new Person("Jerry",20));
System.out.println(coll);
//4. removeAll(Collection coll1):差集：從目前集合中移除coll1中所有的元素。
Collection coll1 = Arrays.asList(123,456);
coll.removeAll(coll1);
System.out.println(coll);
}
@Test
public void test3(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//5.retainAll(Collection coll1):交集：擷取目前集合和coll1集合的交集，并傳回給目前集合
// Collection coll1 = Arrays.asList(123,456,789);
// coll.retainAll(coll1);
// System.out.println(coll);
//6.equals(Object obj):要想傳回true，需要目前集合和形參集合的元素都相同。
Collection coll1 = new ArrayList();
coll1.add(456);
coll1.add(123);
coll1.add(new Person("Jerry",20));
coll1.add(new String("Tom"));
coll1.add(false);
System.out.println(coll.equals(coll1));
}
@Test
public void test4(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//7.hashCode():傳回目前對象的哈希值
System.out.println(coll.hashCode());
//8.集合 --->數組：toArray()
Object[] arr = coll.toArray();
for(int i = 0;i < arr.length;i++){
System.out.println(arr[i]);
}
//拓展：數組 --->集合:調用Arrays類的靜态方法asList()
List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
System.out.println(list);
List arr1 = Arrays.asList(new int[]{123, 456});
System.out.println(arr1.size());//1
List arr2 = Arrays.asList(new Integer[]{123, 456});
System.out.println(arr2.size());//2
//9.iterator():傳回Iterator接口的執行個體，用于周遊集合元素。放在IteratorTest.java中測試
}
2.2Iterator 和 foreach循環
- 作用：周遊Collection
- 實作：
2.2.1 lterator ：
- 内部的方法：hasNext() 和 next()
- 集合對象每次調用iterator()方法都得到一個全新的疊代器對象，預設遊标都在集合的第一個元素之前。
- 内部定義了remove(),可以在周遊的時候，删除集合中的元素。此方法不同于集合直接調用remove()
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
Iterator iterator = coll.iterator();
//方式一：
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// System.out.println(iterator.next());
// //報異常：NoSuchElementException
// System.out.println(iterator.next());
//方式二：不推薦
// for(int i = 0;i < coll.size();i++){
// System.out.println(iterator.next());
// }
//方式三：推薦
hasNext():判斷是否還有下一個元素
while(iterator.hasNext()){
//next():①指針下移 ②将下移以後集合位置上的元素傳回
System.out.println(iterator.next());
}
}
@Test
public void test2(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//錯誤方式一：
// Iterator iterator = coll.iterator();
// while((iterator.next()) != null){
// System.out.println(iterator.next());
// }
//錯誤方式二：
//集合對象每次調用iterator()方法都得到一個全新的疊代器對象，預設遊标都在集合的第一個元素之前。
while (coll.iterator().hasNext()){
System.out.println(coll.iterator().next());
}
}
//測試Iterator中的remove()
//如果還未調用next()或在上一次調用 next 方法之後已經調用了 remove 方法，
// 再調用remove都會報IllegalStateException。
@Test
public void test3(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//删除集合中"Tom"
Iterator iterator = coll.iterator();
while (iterator.hasNext()){
// iterator.remove();
Object obj = iterator.next();
if("Tom".equals(obj)){
iterator.remove();
// iterator.remove();
}
}
//周遊集合
iterator = coll.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
2.2.2 foreach循環
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("Jerry",20));
coll.add(new String("Tom"));
coll.add(false);
//for(集合元素的類型 局部變量 : 集合對象)
//内部仍然調用了疊代器。
for(Object obj : coll){
System.out.println(obj);
}
}
@Test
public void test2(){
int[] arr = new int[]{1,2,3,4,5,6};
//for(數組元素的類型 局部變量 : 數組對象)
for(int i : arr){
System.out.println(i);
}
}
2.3 List接口
- 存儲的資料特點： 存儲序的、可重複的資料。
2.3.1 常用方法
- 增：add(Object obj)
- 删：remove(int index) / remove(Object obj)
- 改：set(int index, Object ele)
- 查：get(int index)
- 插：add(int index, Object ele)
- 長度：size()
- 周遊：① Iterator疊代器方式② 增強for循環③ 普通的循環
2.3.2 ArrayList的源碼分析：
jdk 7情況下:
-
ArrayList list = new ArrayList();//底層建立了長度是10的Object[]數組elementData
list.add(11);//如果此次的添加導緻底層elementData數組容量不夠，則擴容。
預設情況下，擴容為原來的容量的1.5倍，同時需要将原有數組中的資料複制到新的數組中。
jdk 8中ArrayList的變化：
-
ArrayList list = new ArrayList();//底層Object[] elementData初始化為{}.并沒建立長度為10的數組
list.add(123);//第一次調用add()時，底層才建立了長度10的數組，并将資料123添加到
後續的添加和擴容操作與jdk 7 無異。
jdk7中的ArrayList的對象的建立類似于單例的餓漢式，而jdk8中的ArrayList的對象的建立類似于單例的懶漢式，延遲了數組的建立，節省記憶體。
2.3.3 LinkedList的源碼分析：
LinkedList list = new LinkedList(); 内部聲明了Node類型的first和last屬性，預設值為null
list.add(123);//将123封裝到Node中，建立了Node對象。
其中，Node定義為：展現了LinkedList的雙向連結清單的說法
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
2.3.3 Vector的源碼分析：
jdk7和jdk8中通過Vector()構造器建立對象時，底層都建立了長度為10的數組。
在擴容方面，預設擴容為原來的數組長度的2倍。
2.3.4 Arraylist 與 LinkedList 差別?
- 是否保證線程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；
-
底層資料結構： Arraylist 底層使⽤的是 Object 數組； LinkedList 底層使⽤的是 雙向鍊
表 資料結構
-
插⼊和删除是否受元素位置的影響： ① ArrayList 采⽤數組存儲，是以插⼊和删除元素的
時間複雜度受元素位置的影響。 ⽐如：執⾏ add(E e) ⽅法的時候， ArrayList 會預設在将
指定的元素追加到此清單的末尾，這種情況時間複雜度就是 O(1)。但是如果要在指定位置 i
插⼊和删除元素的話（ add(int index, E element) ）時間複雜度就為 O(n-i)。因為在進⾏上述操作的時候集合中第 i 和第 i 個元素之後的(n-i)個元素都要執⾏向後位/向前移⼀位的操作。 ②
LinkedList 采⽤連結清單存儲，是以對于 add(E e) ⽅法的插⼊，删除元素時間複雜度不受元素
位置的影響，近似 O(1)，如果是要在指定位置 i 插⼊和删除元素的話（ (add(int index, E
element) ） 時間複雜度近似為 o(n)) 因為需要先移動到指定位置再插⼊。
-
是否⽀持快速随機通路： LinkedList 不⽀持⾼效的随機元素通路，⽽ ArrayList ⽀持。快
速随機通路就是通過元素的序号快速擷取元素對象(對應于 get(int index) ⽅法)。
-
記憶體空間占⽤： ArrayList 的空 間浪費主要展現在在 list 清單的結尾會預留⼀定的容量空
間，⽽ LinkedList 的空間花費則展現在它的每⼀個元素都需要消耗⽐ ArrayList 更多的空間
（因為要存放直接後繼和直接前驅以及資料）。
2.4 Set接口
存儲的資料特點：無序的、不可重複的元素
2.4.1 HashSet
1.無序性： 不等于随機性。存儲的資料在底層數組中并非照數組索引的順序添加，而是根據資料的哈希值決定的。
2.不可重複性： 保證添加的元素照equals()判斷時，不能傳回true.即：相同的元素隻能添加一個。
3.底層原理
-
我們向HashSet中添加元素a,首先調用元素a所在類的hashCode()方法，計算元素a的哈希值，此哈希值接着通過 (n - 1) & hash（這⾥的 n 指的是數組的⻓度） 計算出在HashSet底層數組中的存放位置（即為：索引位置，判斷
數組此位置上是否已經元素：
- 如果此位置上沒其他元素，則元素a添加成功。 —>情況1
-
如果此位置上其他元素b(或以連結清單形式存在的多個元素，則比較元素a與元素b的hash值：
如果hash值不相同，則元素a添加成功。—>情況2
-
如果hash值相同，進而需要調用元素a所在類的equals()方法：
equals()傳回true,元素a添加失敗
equals()傳回false,則元素a添加成功。—>情況3
-
對于添加成功的情況2和情況3而言：元素a 與已經存在指定索引位置上資料以連結清單的方式存儲。
jdk 7 :元素a放到數組中，指向原來的元素。
jdk 8 :原來的元素在數組中，指向元素a
總結：七上八下
- HashSet底層：數組+連結清單的結構。（前提：jdk7)
4.要求：向Set(主要指：HashSet、LinkedHashSet)中添加的資料，其所在的類一定要重寫hashCode()和equals() 要求：重寫的hashCode()和equals()盡可能保持一緻性：相等的對象必須具有相等的散列碼
2.4.2 TreeSet的使用
- 向TreeSet中添加的資料，要求是相同類的對象。
- 兩種排序方式：自然排序（實作Comparable接口 和 定制排序（Comparator）
3 雙列集合架構：Map
Map中的key:無序的、不可重複的，使用Set存儲所的key —> key所在的類要重寫equals()和hashCode() （以HashMap為例)
Map中的value:無序的、可重複的，使用Collection存儲所的value —>value所在的類要重寫equals()
一個鍵值對：key-value構成了一個Entry對象。
Map中的entry:無序的、不可重複的，使用Set存儲所的entry
常用方法
- 添加：put(Object key,Object value)
- 删除：remove(Object key)
- 修改：put(Object key,Object value)
- 查詢：get(Object key)
- 長度：size()
- 周遊：keySet() / values() / entrySet()
3.1 HashMap
作為Map的主要實作類；線程不安全的，效率高；存儲null的key和value
HashMap在jdk7中實作原理：
- HashMap map = new HashMap():在執行個體化以後，底層建立了長度是16的一維數組Entry[] table。
- map.put(key1,value1):首先，調用key1所在類的hashCode()計算key1哈希值，此哈希值經過某種算法計算以後，得到在Entry數組中的存放位置。 如果此位置上的資料為空，此時的key1-value1添加成功。 ----情況1
- 如果此位置上的資料不為空，(意味着此位置上存在一個或多個資料(以連結清單形式存在)),比較key1和已經存在的一個或多個資料的哈希值： 如果key1的哈希值與已經存在的資料的哈希值都不相同，此時key1-value1添加成功。----情況2
- 如果key1的哈希值和已經存在的某一個資料(key2-value2)的哈希值相同，繼續比較：調用key1所在類的equals(key2)方法，比較： 如果equals()傳回false:此時key1-value1添加成功。如果equals()傳回true:使用value1替換value2。----情況3
- 補充：關于情況2和情況3：此時key1-value1和原來的資料以連結清單的方式存儲。
- 在不斷的添加過程中，會涉及到擴容問題，當超出臨界值(且要存放的位置非空)時，擴容。預設的擴容方式：擴容為原來容量的2倍，并将原的資料複制過來。
HashMap在jdk8中相較于jdk7在底層實作方面的不同：
- new HashMap():底層沒建立一個長度為16的數組
- jdk 8底層的數組是：Node[],而非Entry[]
- 首次調用put()方法時，底層建立長度為16的數組
- jdk7底層結構隻：數組+連結清單。jdk8中底層結構：數組+連結清單+紅黑樹。
- 形成連結清單時，七上八下（jdk7:新的元素指向舊的元素。jdk8：舊的元素指向新的元素）
- 當數組的某一個索引位置上的元素以連結清單形式存在的資料個數 > 8 且目前數組的長度 > 64時，此時此索引位置上的所資料改為使用紅黑樹存儲。
HashMap底層典型屬性的屬性的說明：
- DEFAULT_INITIAL_CAPACITY : HashMap的預設容量，16
- DEFAULT_LOAD_FACTOR：HashMap的預設加載因子：0.75
- threshold：擴容的臨界值，=容量*填充因子：16 * 0.75 => 12
- TREEIFY_THRESHOLD：Bucket中連結清單長度大于該預設值，轉化為紅黑樹:8
- MIN_TREEIFY_CAPACITY：桶中的Node被樹化時最小的hash表容量:64
3.2 LinkedHashMap
-
LinkedHashMap底層使用的結構與HashMap相同，因為LinkedHashMap繼承于HashMap.
差別就在于：LinkedHashMap内部提供了Entry，替換HashMap中的Node.
TreeMap的使用
- 向TreeMap中添加key-value，要求key必須是由同一個類建立的對象
- 因為要照key進行排序：自然排序 、定制排序
4 Collection 和 Collections的差別？
- java.util.Collection 是一個集合接口（集合類的一個頂級接口）。它提供了對集合對象進行基本操作的通用接口方法。Collection接口在Java 類庫中有很多具體的實作。Collection接口的意義是為各種具體的集合提供了最大化的統一操作方式，其直接繼承接口有List與Set。
-
Collections則是集合類的一個工具類/幫助類，其中提供了一系列靜态方法，用于對集合中元素進行排序、搜尋以及線程安全等各種操作。
- 常用方法：
reverse(List)：反轉 List 中元素的順序
shuffle(List)：對 List 集合元素進行随機排序
sort(List)：根據元素的自然順序對指定 List 集合元素升序排序
sort(List，Comparator)：根據指定的 Comparator 産生的順序對 List 集合元素進行排序
swap(List，int， int)：将指定 list 集合中的 i 處元素和 j 處元素進行交換
5 常見面試題
5.1 HashMap 和 Hashtable 的差別
-
線程是否安全： HashMap 是⾮線程安全的， HashTable 是線程安全的,因為 HashTable 内
部的⽅法基本都經過 synchronized 修飾。（如果你要保證線程安全的話就使⽤
ConcurrentHashMap 吧！）；
-
效率： 因為線程安全的問題， HashMap 要⽐ HashTable 效率⾼⼀點。另外， HashTable
基本被淘汰，不要在代碼中使⽤它；
-
對 Null key 和 Null value 的⽀持： HashMap 可以存儲 null 的 key 和 value，但 null 作為
鍵隻能有⼀個，null 作為值可以有多個；HashTable 不允許有 null 鍵和 null 值，否則會抛出
NullPointerException 。
-
初始容量⼤⼩和每次擴充容量⼤⼩的不同 ： ① 建立時如果不指定容量初始值， Hashtable
預設的初始⼤⼩為 11，之後每次擴充，容量變為原來的 2n+1。 HashMap 預設的初始化⼤
⼩為 16。之後每次擴充，容量變為原來的 2 倍。② 建立時如果給定了容量初始值，那麼
Hashtable 會直接使⽤你給定的⼤⼩，⽽ HashMap 會将其擴充為 2 的幂次⽅⼤⼩
（ HashMap 中的 tableSizeFor() ⽅法保證，下⾯給出了源代碼）。也就是說 HashMap 總
是使⽤ 2 的幂作為哈希表的⼤⼩,後⾯會介紹到為什麼是 2 的幂次⽅。
-
底層資料結構： JDK1.8 以後的 HashMap 在解決哈希沖突時有了⼤的變化，當連結清單⻓度
⼤于門檻值（預設為 8）（将連結清單轉換成紅⿊樹前會判斷，如果目前數組的⻓度⼩于 64，那麼
會選擇先進⾏數組擴容，⽽不是轉換為紅⿊樹）時，将連結清單轉化為紅⿊樹，以減少搜尋時
間。Hashtable 沒有這樣的機制。
5.2 HashMap 和 HashSet差別
HashSet 底層就是基于 HashMap 實作的
5.3 HashMap 的⻓度為什麼是2的幂次⽅
采⽤%取餘的操作來實作。但是，重點來了：“取餘(%)操作中如果除數是2的幂次則等價于與其除數減⼀的與(&)操作（也就是說 **hash%length==hash&(length-1)**的前提是 length 是2的 n 次⽅；）。” 并且 采⽤⼆進制位操作 &，相對于%能夠提⾼運算效率，這就解釋了 HashMap 的⻓度為什麼是2的幂次⽅。
5.4 ConcurrentHashMap
JDK1.7
- ⾸先将資料分為⼀段⼀段的存儲，然後給每⼀段資料配⼀把鎖，當⼀個線程占⽤鎖通路其中⼀個段資料時，其他段的資料也能被其他線程通路。ConcurrentHashMap 是由 Segment 數組結構和 HashEntry 數組結構組成。**Segment 實作了 ReentrantLock ,**是以 Segment 是⼀種可重⼊鎖，扮演鎖的⻆⾊。 HashEntry ⽤于存儲鍵值對資料。
- ⼀個 ConcurrentHashMap ⾥包含⼀個 Segment 數組。 Segment 的結構和 HashMap 類似，是⼀種數組和連結清單結構，⼀個 Segment 包含⼀個 HashEntry 數組，每個 HashEntry 是⼀個連結清單結構的元素，每個 Segment 守護着⼀個 HashEntry 數組⾥的元素，當對 HashEntry 數組的資料進⾏修改時，必須⾸先獲得對應的 Segment 的鎖。
JDK1.8
- ConcurrentHashMap 取消了 Segment 分段鎖，采⽤ CAS 和 synchronized 來保證并發安全。資料結構跟 HashMap1.8 的結構類似，數組+連結清單/紅⿊⼆叉樹。
- Java 8 在連結清單⻓度超過⼀定門檻值（8）時将連結清單（尋址時間複雜度為 O(N)）轉換為紅⿊樹（尋址時間複雜度為 O(log(N))）synchronized 隻鎖定目前連結清單或紅⿊⼆叉樹的⾸節點，這樣隻要 hash 不沖突，就不會産⽣并發，效率⼜提升 N 倍
5.5 ConcurrentHashMap 和 Hashtable 的差別
ConcurrentHashMap 和 Hashtable 的差別主要展現在實作線程安全的⽅式上不同。
-
底層資料結構： JDK1.7 的 ConcurrentHashMap 底層采⽤ 分段的數組+連結清單 實作，JDK1.8
采⽤的資料結構跟 HashMap1.8 的結構⼀樣，數組+連結清單/紅⿊⼆叉樹。 Hashtable 和
JDK1.8 之前的 HashMap 的底層資料結構類似都是采⽤ 數組+連結清單 的形式，數組是
HashMap 的主體，連結清單則是主要為了解決哈希沖突⽽存在的；
-
**實作線程安全的⽅式（重要）： ① 在 JDK1.7 的時候， ConcurrentHashMap （分段鎖）
對整個桶數組進⾏了分割分段( Segment )，每⼀把鎖隻鎖容器其中⼀部分資料，多線程通路
容器⾥不同資料段的資料，就不會存在鎖競争，提⾼并發通路率。 到了 JDK1.8 的時候已經
摒棄了 Segment 的概念，⽽是直接⽤ Node 數組+連結清單+紅⿊樹的資料結構來實作，并發
控制使⽤ synchronized 和 CAS 來操作。（JDK1.6 以後 對 synchronized 鎖做了很多優
化） 整個看起來就像是優化過且線程安全的 HashMap ，雖然在 JDK1.8 中還能看到
Segment 的資料結構，但是已經簡化了屬性，隻是為了相容舊版本；② Hashtable (同⼀把
鎖) :使⽤ synchronized 來保證線程安全，效率⾮常低下。**當⼀個線程通路同步⽅法時，其
他線程也通路同步⽅法，可能會進⼊阻塞或輪詢狀态，如使⽤ put 添加元素，另⼀個線程不
能使⽤ put 添加元素，也不能使⽤ get，競争會越來越激烈效率越低。