集合前篇—List 源碼分析
- 2020 年 3 月 10 日
- 筆記
這裡的部落格都是筆者初學時寫下，一段時間後有其他的理解就再次回來修訂 所以排版，文字，圖片會有錯亂，但重寫一篇太過耗費時間，所以只能修修補補又重發
1. 什麼是集合
- 集合是一個用來存放數據的容器（數組也是），但集合不同的是可以存放不同類型的對象，並且大小可變
- 其常用類型有Set，List，Map。這些常用的類型往上提取就有了Collection和Map介面
1.1 Collection介面的方法
add(E):添加一個對象 addAll(Collection<? extengds E>):添加指定集合里的全部對象 clear():清空集合 remove(Object):移除一個對象 removeAll(Collection<?>):移除集合里的全部對象 contains(Object):是否包含某個對象 containsAll(Collection<?>):是否包含某集合的全部對象 isEmpty():集合是否為空 size():集合對象的個數 retainAll(Collection<?>):交集，結果放在調用方法的集合 iterator():獲取迭代器
1.2 Iterator迭代器
Collection介面繼承Iterable介面，而Iterable介面有iterator()方法，該方法返回一個迭代器（用於遍歷集合）
1.3 iterator也是一個介面
裡面有四個方法，由於不同的集合有不同遍歷方式，所以迭代器抽取成介面，讓集合自己實現該介面
1.4 Map介面的方法
entrySet():獲取包含鍵值對的Set集合，形式為Set<Entry<K,V>> containsKey(Object):是否包含該Key containsValue(Object):是否包含該Value get(Object):根據Key獲取Value put(K,V):添加一個鍵值對 remove(Object):根據Key移除一個鍵值對
2. List集合
一. List——有序（指存取順序一致）,可重複
1. ArrayList (底層是Object數組，下標訪問賊快)
- 定義的變數
- elementData存放元素
- size是集合的實際大小
- 集合的總大小用elementData.length數組長度來表示
- ArrayList 默認構造函數是一個空的數組
- add 是最常用的方法了，從尾部添加，我們來看看源碼
- 其中add( index，E )按下標插入元素稍有不同，其用System.arraycopy方法，由下圖也可看出用
native修飾，底層用C/C++編寫的且沒有返回值，所以猜測是操作原數組進行擴容，埋坑以後回來看能不能理解這個
- get
- set
get 和set都比較簡單，和普通操作數組一樣，就是操作之前多了檢查數組下標
- remove，也用到底層函數，不解釋，不過要注意移動後，最後一個元素設置為空，取消引用，使之垃圾回收
- 刪除元素時不會減少容量，若希望減少容量則可調用trimToSize()，是集合大小為實際大小
- toArray，也是複製一個新數組過去
2. vector（類似於ArrayList）
- 與ArrayList最大區別是執行緒安全，但我們一般都是用ArryaList代替它
- 二者有些其他微小區別，比如擴容時為2倍這些等，但不影響
- vector實現同步的方法是加上
synchronized修飾符，所以這裡犧牲時間換取同步 - 如要ArrayList同步，可用
Collections.synchronizedList(new ArrayList()) - 還有其他執行緒安全的集合，後面幾篇部落格會說明，這裡不再贅述
3. LinkedList (底層是雙向鏈表)
- 定義的變數及節點
- first、last頭尾節點
- Node 節點，內部維護值，前後節點的指向
這裡重點說明一下（與後面的迭代器有關），這個集合有關鏈表遍歷的功能都會把當前節點之前的數據遍歷一邊，損耗性能
- add國際慣例，看源碼
- remove
鏈表實現移除元素的圖示
- get
- set
4. 二者遍歷
- ArrayList底層是數組，用for、foreach（底層用Iterator）、Iterator訪問速度差不多
- 而LinkedList 底層是雙向鏈表，從get方法源碼可知，需要遍歷該位置前面的所有數據，所以得用Iterator、foreach
- 為什麼用Iterator？因為會保存當前節點，不用從頭遍歷，不截圖了直接上源碼
//LinkedList 返回一個專屬的迭代器 public Iterator iterator() { return new LinkedListIterator(); } //實現該介面 private class LinkedListIterator implements Iterator{ private Node currentNode = head; private int nextIndex = 0; public Object next() { Object data = currentNode.getData(); currentNode = currentNode.getNext(); //從這裡可以看出，會保存當前節點，不用從頭遍歷 nextIndex ++; return data; } }
總結：
- ArrayList適用於隨機查詢次數多的情況
- LinkedList適用於隨機增刪
- 源碼基於JDK1.8
- 腦圖用XMind
