后端学习 - Java容器
文章目錄
- 一 簡介
- 二 底層數據結構總結
- 1 List
- 2 Set
- 3 Queue
- 4 Map
- 三 Collection 的子接口 List
- 1 ArrayList 與 Vector
- 2 ArrayList 與 LinkedList
- 3 ArrayList 的 JDK 7/8 差異
- 4 List 的 remove() 方法
- 5 ArrayList 的構造方法與擴容機制*
- 四 Collection 的子接口 Set
- 1 Comparable 與 Comparator
- 2 Set 的無序性
- 3 HashSet、LinkedHashSet 和 TreeSet
- 4 HashSet 加入實例時,查重的方式(類似實例間的相等比較)**
- 5 HashSet 存儲原理的實例**
- 五 Collection 的子接口 Queue
- 1 Queue 與 Deque
- 2 PriorityQueue
- 3 ArrayDeque 與 LinkedList
- 六 Collection 的子接口 Map
- 1 HashMap 和 Hashtable
- 2 HashMap 和 HashSet
- 3 HashMap 的長度為什么是 2 的冪次方
- 4 ConcurrentHashMap 和 Hashtable
- 5 CAS (Compare And Swap)
- 6 HashMap 的底層實現
- 7 HashMap 底層實現的參數
- 8 JDK 8 HashMap 的擴容
- 七 Iterator
- 1 Iterator的使用方法
- 2 遍歷中刪除元素
- 八 Collections 工具類的常用靜態方法
一 簡介
Java容器可大致分為 List、Queue、Set、Map 四種。
- List:存儲的元素是有序的、可重復的
- Set:存儲的元素是無序的、不可重復的
- Queue:按特定的排隊規則來確定先后順序,存儲的元素是有序的、可重復的
- Map:使用鍵值對(key-value)存儲,類似于數學上的函數 y=f(x),“x” 代表 key,“y” 代表 value,key 是無序的、不可重復的,value 是無序的、可重復的,每個鍵最多映射到一個值
二 底層數據結構總結
使用紅黑樹的底層結構,根本目的是增強數據結構搜索和排序的能力
1 List
- Arraylist: Object[] 數組
- Vector:Object[] 數組
- LinkedList: 雙向鏈表(JDK1.6 之前為循環鏈表,JDK1.7 取消了循環)
2 Set
- HashSet(無序,唯一):底層采用 HashMap 來保存元素
- LinkedHashSet:LinkedHashSet 是 HashSet 的子類,并且其內部是通過 LinkedHashMap 來實現的
- TreeSet(有序,唯一):紅黑樹(自平衡的排序二叉樹)
3 Queue
- PriorityQueue: Object[] 數組來實現二叉堆
- ArrayQueue: Object[] 數組 + 雙指針
4 Map
-
HashMap: JDK1.8 之前 HashMap 由數組+鏈表組成的,數組是 HashMap 的主體,鏈表則是主要為了解決哈希沖突而存在的(“拉鏈法”解決沖突)。JDK1.8 以后在解決哈希沖突時有了較大的變化,當鏈表長度大于閾值(默認為 8)(將鏈表轉換成紅黑樹前會判斷,如果當前數組的長度小于 64,那么會選擇先進行數組擴容,而不是轉換為紅黑樹)時,將鏈表轉化為紅黑樹,以減少搜索時間
-
LinkedHashMap: LinkedHashMap 繼承自 HashMap,所以它的底層仍然是基于拉鏈式散列結構即由數組和鏈表或紅黑樹組成。另外,LinkedHashMap 在上面結構的基礎上,增加了一條雙向鏈表,使得上面的結構可以 保持鍵值對的插入順序。同時通過對鏈表進行相應的操作,實現了訪問順序相關邏輯
-
HashTable: 數組+鏈表組成的,數組是 HashTable 的主體,鏈表則是主要為了解決哈希沖突而存在的
-
TreeMap: 紅黑樹(自平衡的排序二叉樹)
三 Collection 的子接口 List
1 ArrayList 與 Vector
- ArrayList 和 Vector 的底層都是 Object[ ] 存儲的,即對數組進行封裝
- ArrayList 是 List 的主要實現類,適用于頻繁的查找工作,線程不安全
- Vector 是 List 的古老實現類,線程安全
2 ArrayList 與 LinkedList
- 都是線程不安全的
- ArrayList 底層使用 Object[ ] 存儲(支持隨機訪問),LinkedList 使用雙向鏈表存儲(不支持隨機訪問)。
- ArrayList 的空間浪費主要體現在列表的結尾會預留一定的容量空間,而 LinkedList 的空間花費則體現在它的每一個元素都需要消耗比 ArrayList 更多的空間(因為要存放直接后繼和直接前驅以及數據)
- 插入/刪除 元素時的時間復雜度不同,體現在數組與鏈表的區別
3 ArrayList 的 JDK 7/8 差異
- JDK 7
- JDK 8中 ArrayList 的變化:
- JDK7 中的 ArrayList 的對象的創建類似于單例的餓漢式,而 JDK8 中的 ArrayList 的對象的創建類似于單例的懶漢式,延遲了數組的創建,節省內存
4 List 的 remove() 方法
- 傳遞 int 類型則刪除對應下標的內容,傳遞引用類型則刪除具體的實例
5 ArrayList 的構造方法與擴容機制*
參考鏈接
- 容量增加 1 的情況:
原來的容量為 0,而且是有參構造器創建的 ArrayList(傳入 0 或者是空 Collection ,不能是無參構造器創建) - 容量變為原來1.5倍的情況:
原來的容量大于 0 - 容量變為 max(DEFAULT_CAPACITY, minCapacity) 的情況:
原來的容量為 0,而且是無參構造器創建的 ArrayList(其中 DEFAULT_CAPACITY = 10)
也就是說,用默認無參構造方法創建的數組在添加元素前,ArrayList 的容量為0,添加一個元素后,ArrayList 的容量就變為 10
四 Collection 的子接口 Set
1 Comparable 與 Comparator
- Comparable 接口實際上是出自java.lang包,它有一個 compareTo(Object obj)方法用來排序 (類中蘊含的比較大小的方法)。
- Comparator 接口實際上是出自 java.util 包,有一個 compare(Object obj1, Object obj2) 方法用來排序(比較器,用于比較兩個對象的大小)。
2 Set 的無序性
- 無序性是指存儲的數據在底層數組中并非按照數組索引的順序添加 ,而是根據數據的哈希值決定的
3 HashSet、LinkedHashSet 和 TreeSet
- 都不是線程安全的
- HashSet 的底層數據結構是哈希表(基于 HashMap 實現);
- LinkedHashSet 的底層數據結構是鏈表和哈希表(基于 LinkedHashMap 實現),元素的插入和取出順序滿足 FIFO;
- LinkedHashSet 是 HashSet 的子類,在添加數據的同時,每個數據還維護了兩個引用,記錄此數據前一個數據和后一個數據。優點是對于頻繁的遍歷操作,LinkedHashSet 效率高于 HashSet
- TreeSet 底層數據結構是紅黑樹,元素是有序的,排序的方式有自然排序和定制排序。自然排序中,比較兩個對象是否相同的標準為:compareTo() 返回0,而不再是equals();定制排序中,比較兩個對象是否相同的標準為:compare() 返回0,而不再是equals();所以不能放入無法排序的對象
- 因此,底層數據結構不同又導致這三者的應用場景不同。HashSet 用于不需要保證元素插入和取出順序的場景,LinkedHashSet 用于保證元素的插入和取出順序滿足 FIFO 的場景,TreeSet 用于支持對元素自定義排序規則的場景
4 HashSet 加入實例時,查重的方式(類似實例間的相等比較)**
- 當對象加入HashSet 時,HashSet 會先計算對象的 hashcode值來判斷對象加入的位置
- 如果該位置無對象,則 HashSet 中無重復元素,加入成功
- 如果該位置有對象(下標相同的兩個對象, hashcode不一定相同),與相同位置的其他的對象的 hashcode 值作比較,如果沒有相符的 hashcode,則無重復元素,加入成功
- 但是如果發現有相同 hashcode 值的對象,這時會調用 equals() 方法來檢查 hashcode 相等的對象是否真的相同。如果兩者相同,HashSet 就不會讓加入操作成功
5 HashSet 存儲原理的實例**
典中典
public void test3(){HashSet set = new HashSet();Person p1 = new Person(1001,"AA");Person p2 = new Person(1002,"BB");set.add(p1);set.add(p2);System.out.println(set);p1.name = "CC";set.remove(p1);System.out.println(set); // BB, CCset.add(new Person(1001,"CC"));System.out.println(set); // BB, CC, CCset.add(new Person(1001,"AA"));System.out.println(set); // BB, CC, CC, AA}五 Collection 的子接口 Queue
1 Queue 與 Deque
-
Queue 是單端隊列,只能從一端插入元素,另一端刪除元素,實現上一般遵循 FIFO 規則
-
Queue 的兩套方法:
-
Deque 是雙端隊列,在隊列的兩端均可以插入或刪除元素
-
Deque 的兩套方法:
2 PriorityQueue
- PriorityQueue 利用了二叉堆的數據結構來實現的,底層使用可變長的數組來存儲數據
- PriorityQueue 通過堆元素的上浮和下沉,實現了在 O(logn) 的時間復雜度內插入元素和刪除堆頂元素。
- PriorityQueue 是非線程安全的,且不支持存儲 NULL 和 non-comparable 的對象(因為無法比較就無法排序)
- PriorityQueue 默認是小頂堆,但可以接收一個 Comparator 作為構造參數,從而來自定義元素優先級的先后
3 ArrayDeque 與 LinkedList
- ArrayDeque 和 LinkedList 都實現了 Deque 接口,兩者都具有隊列的功能
- ArrayDeque 是基于可變長的數組和雙指針來實現,而 LinkedList 則通過鏈表來實現
- ArrayDeque 插入時可能存在擴容過程, 不過均攤后的插入操作依然為 O(1)。雖然 LinkedList 不需要擴容,但是每次插入數據時均需要申請新的堆空間,均攤性能相比更慢。從性能的角度上,選用 ArrayDeque 來實現隊列要比 LinkedList 更好
六 Collection 的子接口 Map
1 HashMap 和 Hashtable
- Hashtable 基本被淘汰,不要在代碼中使用它
- HashMap 是非線程安全的,Hashtable 是線程安全的,因為 Hashtable 內部的方法基本都經過 synchronized 修飾
- HashMap 可以存儲 null 的 key 和 value,但 null 作為鍵只能有一個,null 作為值可以有多個;Hashtable 不允許有 null 鍵和 null 值,否則會拋出 NullPointerException
- 都采用數組+鏈表的形式。HashMap 在解決哈希沖突時有了較大的變化,當鏈表長度大于閾值(默認為 8)(將鏈表轉換成紅黑樹前會判斷,如果當前數組的長度小于 64,那么會選擇先進行數組擴容,而不是轉換為紅黑樹)時,將鏈表轉化為紅黑樹,以減少搜索時間。Hashtable 沒有這樣的機制
- HashMap 總是使用 2 的冪作為哈希表的大小。創建時如果給定了容量初始值,那么 Hashtable 會直接使用給定的大小,而 HashMap 會將其擴充為 2 的冪次方大小
2 HashMap 和 HashSet
- HashSet 是基于 HashMap 實現的。
3 HashMap 的長度為什么是 2 的冪次方
-
為了能讓 HashMap 存取高效,盡量較少碰撞,也就是要盡量把數據分配均勻。Hash 值的范圍值-2147483648 到 2147483647,前后加起來大概 40 億的映射空間,只要哈希函數映射得比較均勻松散,一般應用是很難出現碰撞的。但問題是一個 40 億長度的數組,內存是放不下的。所以這個散列值是不能直接拿來用的。用之前還要先做對數組的長度取模運算,得到的余數才能用來要存放的位置也就是對應的數組下標。這個數組下標的計算方法是“ (n - 1) & hash”(n 代表數組長度)
-
hash%length == hash&(length-1)的前提是 length 是 2 的 n 次方。所以要求 HashMap 的長度是 2 的冪次方
4 ConcurrentHashMap 和 Hashtable
- 均線程安全
- 數據結構:
| ConcurrentHashMap JDK1.7 | Segment 數組 + HashEntry 數組 + 鏈表/紅黑樹 | Segment(本質是 ReentrantLock),每次鎖若干 HashEntry |
| ConcurrentHashMap JDK1.8 | Node 數組 + 鏈表/紅黑樹 | synchronized,每次鎖一個 Node |
| Hashtable | 數組+鏈表 | synchronized,每次鎖全表 |
JDK1.8 的時候已經摒棄了 Segment 的概念,synchronized 只鎖定當前鏈表或紅黑二叉樹的首節點,并發控制使用 synchronized 和 CAS 來操作,雖然在 JDK1.8 中還能看到 Segment 的數據結構,但是已經簡化了屬性,只是為了兼容舊版本
Hashtable(同一把鎖) :使用 synchronized 來保證線程安全,效率非常低下。當一個線程訪問同步方法時,其他線程也訪問同步方法,可能會進入阻塞或輪詢狀態,如使用 put 添加元素,另一個線程不能使用 put 添加元素,也不能使用 get,競爭會越來越激烈效率越低
5 CAS (Compare And Swap)
V:要更新的變量(var)
E:預期值(expected)
N:新值(new)
- 比較并交換的過程:判斷V是否等于E,如果等于,將V的值設置為N;如果不等,說明已經有其它線程更新了V,則當前線程放棄更新,什么都不做
- 當多個線程同時使用CAS操作一個變量時,只有一個會勝出,并成功更新,其余均會失敗,但失敗的線程并不會被掛起,僅是被告知失敗,并且允許再次嘗試,當然也允許失敗的線程放棄操作
6 HashMap 的底層實現
- 和 HashSet 相同,因為 HashSet 是基于 HashMap 實現的
- 以JDK7為例說明:
- 首先,調用key1所在類的 hashCode() 計算key1哈希值,此哈希值經過某種算法計算以后,得到在Entry數組中的存放位置。如果此位置上的數據為空,此時的 key1-value1 添加成功。
- 如果此位置上的數據不為空,(意味著此位置上存在一個或多個數據(以鏈表形式存在)),比較key1和已經存在的一個或多個數據的哈希值:如果key1的哈希值與已經存在的數據的哈希值都不相同,此時 key1-value1 添加成功。
- 如果key1的哈希值和已經存在的某一個數據 key2-value2 的哈希值相同,繼續比較:調用 key1 所在類的 equals(key2) 方法,比較:
如果 equals() 返回false:此時 key1-value1 添加成功
如果 equals() 返回true:使用 value1 替換 value2
JDK8 相較于 JDK7 在底層實現方面的不同:
- new HashMap():底層沒有創建一個長度為16的數組(懶漢式),首次調用 put() 方法時,底層創建長度為16的數組
- JDK8 底層的數組是:Node[](因為支持了鏈表轉紅黑樹),而非 HashEntry[]
- JDK7 底層結構是 HashEntry 數組+鏈表;JDK8 中底層結構:Node 數組 + 鏈表 / 紅黑樹。當數組的某一個索引位置上的元素以鏈表形式存在的數據個數 > 8 且當前數組的長度 > 64時,此時此索引位置上的所數據改為使用紅黑樹存儲
7 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
8 JDK 8 HashMap 的擴容
- HashMap 在創建時不創建 Node 數組,而在首次添加 (k, v) 時申請長度為 16 的數組
- HashMap 的數組長度一定是 2 的冪次,目的是方便計算哈希值對數組長度取模
- HashMap 只有在插入元素時才會初始化(創建 Node 數組),或者擴容;具體地,擴容還要滿足兩個條件之一:
- 當前存入數據大于閾值
- 存入數據到某一條鏈表時,該鏈表數據個數大于 8,且數組長度小于 64
- 擴容的具體操作:
- 將 Node 數組長度變為原來的 2 倍
- 調整原數據在新數組中的索引,調用 resize 方法,根據原來的 hash 值新增的 bit 是0還是1,0=索引不變,1=原來的索引 + 原來哈希表的長度
七 Iterator
1 Iterator的使用方法
public class IteratorTest {@Testpublic void test1(){Collection coll = new ArrayList();coll.add(123);coll.add(456);Iterator iterator = coll.iterator();while(iterator.hasNext()){//next():①指針下移 ②將下移以后集合位置上的元素返回System.out.println(iterator.next());}2 遍歷中刪除元素
- 只能使用 Iterator
- 如果還未調用 next() 或在上一次調用 next() 方法之后已經調用了 remove() 方法,再調用 iterator.remove() 都會 IllegalStateException
- iterator 調用的 remove() ,和集合對象的 remove() 不同
八 Collections 工具類的常用靜態方法
- reverse(List):反轉 List 中元素的順序
- shuffle(List):對 List 集合元素進行隨機排序
- sort(List):根據元素的自然順序對指定 List 集合元素按升序排序
- sort(List,Comparator):根據指定的 Comparator 產生的順序對 List 集合元素進行排序
- swap(List,int, int):將指定 list 集合中的 i 處元素和 j 處元素進行交換
- Object max(Collection):根據元素的自然順序,返回給定集合中的最大元素
- Object max(Collection,Comparator):根據 Comparator 指定的順序,返回給定集合中的最大元素
- int frequency(Collection,Object):返回指定集合中指定元素的出現次數
- void copy(List dest,List src):將src中的內容復制到dest中
- boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替換 List 對象的所有舊值
總結
以上是生活随笔為你收集整理的后端学习 - Java容器的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 联通手机卡里的积分怎么在中国联通APP商
- 下一篇: 后端学习 - 并发编程