- 本文是根據源碼進行學習的,如果我有什麼了解不對的地方請多指正,謝謝您
- 上面基本就是List集合類的類圖關系了,圖中省略掉了比如
Cloneable
ArrayList
Vector
LinkedList
Stack
ArrayList
LinkedList
ArrayList
- 這是最常用的List的實作類,那麼這個類的存儲是由數組實作的,如果超過數組規定閥值,那麼就會進行自動擴容,自動擴容其實就是将數組資料複制到一個新的更大的數組中以達到擴容的目的,我們來看一下ArrayList的部分屬性源碼
//預設容量,将在添加第一個元素時擴充為 DEFAULT_CAPACITY private static final int DEFAULT_CAPACITY = 10; //共享空數組執行個體 private static final Object[] EMPTY_ELEMENTDATA = {}; //這是儲存資料的數組,非私有以簡化嵌套類通路 //arraylist 的容量是此array數組的長度 //當第一個元素被添加時,當任何一個空ArrayList的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA都會被擴充為DEFAULT_CAPACITY transient Object[] elementData; //共享空數組執行個體，用于預設大小的空執行個體 //将其與 EMPTY_ELEMENTDATA 區分開來,以了解添加第一個元素時要增加多少 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; private int size; ...
初始化
- ArrayList提供了三種構造方法,如下
public ArrayList() {...} public ArrayList(int initialCapacity) {...} public ArrayList(Collection<? extends E> c) {...} - 空參 : 我們從第一個ArrayList的空參的構造方法介紹,下面是源碼的實作
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } - 怎麼了解之前的代碼注釋
當第一個元素被添加時,任何一個空ArrayList的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA都會被擴充為DEFAULT_CAPACITY
- 是以說當我們建構空參對象的時候,初始值數組長度是為0的,并沒有直接擴充為長度為10的數組,代碼驗證
public static void main(String[] args) throws Exception { ArrayList<String> arrayList = new ArrayList<>(); getSize(arrayList); arrayList.add("x"); getSize(arrayList); } private static void getSize(ArrayList<String> arrayList) throws Exception { Field elementData = arrayList.getClass().getDeclaredField("elementData"); elementData.setAccessible(true); Object[] o = (Object[]) elementData.get(arrayList); System.out.println(o.length); } //0 10 //而當我們以0為初始化長度參數建立ArrayList的時候,其實就是告訴他我一個都不存,是以他就建立了一個0長度的數組,而當我們添加資料的時候,就會自動擴容一個 //驗證 : 可以将初始化改成這樣 ArrayList<String> arrayList = new ArrayList<>(0); //然後輸出為 0 1 //是以這也就是為什麼要區分DEFAULTCAPACITY_EMPTY_ELEMENTDATA 與 EMPTY_ELEMENTDATA - 從中我們可以看到,隻是初始化空參的ArrayList的話,那麼隻是将一個空數組指派給elementData屬性,那麼
EMPTY_ELEMENTDATA
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
//使用EMPTY_ELEMENTDATA List<String> arrayList = new ArrayList<>(0); //使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA List<String> arrayList = new ArrayList<>(); - 我們還注意到
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
EMPTY_ELEMENTDATA
private static final
public static void main(String[] args) throws Exception { ArrayList<String> list1 = new ArrayList<>(); Field elementData1 = list1.getClass().getDeclaredField("elementData"); elementData1.setAccessible(true); Object o1 = elementData1.get(list1); ArrayList<String> list2 = new ArrayList<>(); Field elementData2 = list2.getClass().getDeclaredField("elementData"); elementData2.setAccessible(true); Object o2 = elementData1.get(list2); System.out.println(o1 == o2); } //true - 是以ArrayList其實已經想好了為我們的空集合做一個緩存,而當我們向空集合中添加資料的時候,elementData就會指向其他的對象,這個是add方法的源碼範圍,是以一會再說,到這第一個空參的構造方法已經介紹的差不多了,下面是有int類型參數的構造方法的源碼實作
public ArrayList(int initialCapacity) { //不為0,按照指定長度建立數組 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //為0就直接指向建立好的數組 this.elementData = EMPTY_ELEMENTDATA; } else { //參數不合法 throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); } } - 不用細說,這個是很容易的,也可以看出來為什麼ArrayList要設計兩個空數組以備使用,這個構造沒什麼可說的,那麼下面就是以集合為參數的建立方式的源碼
//将參數轉換為ArrayList public ArrayList(Collection<? extends E> c) { //因為Collection中就定義了toArray方法,是以他的實作類就都會實作自己的toArray,是以可以直接調用傳回數組而不會出錯 elementData = c.toArray(); //如果傳回的數組的長度不是空的數組的話 if ((size = elementData.length) != 0) { //防範c.ToArray錯誤不傳回Object[] if (elementData.getClass() != Object[].class) //那麼就将elementData中的元素都轉換為Object類型 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { //到這就是空數組,是以直接引用建立好的空數組即可,還能節省空間 this.elementData = EMPTY_ELEMENTDATA; } } - 到這ArrayList的建立方式大概的就過了一邊,那麼下面的ArrayList的實作方法,我就隻挑幾個核心方法來看一下源碼
add
- 首當其沖的就是add,我們使用一下ArrayList來add元素,然後我們進行代碼走讀,那麼我們看一下源碼
//使用 ArrayList<String> arrayList = new ArrayList<>(); arrayList.add("A"); //源碼開始 public boolean add(E e) { modCount++; //代表操作ArrayList的次數,有關于fast-fail機制,之後再說 //參數值:并不是A參數是一個URL, 數組對象 , 2 add(e, elementData, size); //調用類中方法 return true; //傳回結果 } // 結束代碼 - 上面可以說是很簡單了,但是在debug的時候我發現存儲元素的elementData數組中其實已經有東西了,如下圖
- 然後當我debug step over到結束代碼的時候,程式跳到這這樣一個代碼
public synchronized void addURL(URL url) { if (closed || url == null) return; synchronized (unopenedUrls) { if (! path.contains(url)) { unopenedUrls.addLast(url); path.add(url); } } } //再跳 public InternalError(String message) { super(message); } //還跳 static { System.loadLibrary("instrument"); } //還有很多... - 上面的一些代碼其實不用知道其意思,但是可以告訴我們的是,ArrayList中的elementData不單純是存儲我們需要存儲的元素的,而是在首次add的時候會借助elementData這個數組去加載一些檔案或者其他東西,而在第二次add的時候就不需要這個步驟了,并且在首次加載完一些路徑後或者庫後,elementData就會将他們清除,以為已經加載上了,然後這時候才會來存儲我們的元素,錄了一段小視訊,可以下載下傳來看一下
- 經過後面再次實驗, 除了首次使用ArrayList的add方法會加載一些東西,當我們再次new出ArrayList的時候,首次使用add方法就不會再家在任何東西了,如下的測試代碼
List<String> list = new ArrayList<>(); list.add("X"); List<String> list2 = new ArrayList<>(); list2.add("X"); - 其中在我debug時候會看到很多
getLoader
一些方法或者屬性,那麼在這感覺是首次使用ArrayList的類加載機制在起作用,我在社群提問題了,是以大家可以看一下,聯想到類加載機制非常感謝回複我的
- 回到add方法上來,我們發現它會調用類中的另一個add方法.源碼如下
private void add(E e, Object[] elementData, int s) { //如果滿了就擴容 if (s == elementData.length) elementData = grow(); //然後将要存的元素存入到數組指定位置 elementData[s] = e; //加一 size = s + 1; } - 這個方法中用到的grow方法源碼如下
private Object[] grow() { return grow(size + 1); } private Object[] grow(int minCapacity) { return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity)); } //傳回至少與給定最小容量相同的容量 private int newCapacity(int minCapacity) { int oldCapacity = elementData.length; //10+(10>>1)=15 ,即擴容1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); //擴容後如果還比最小的容量小或者相等的話 if (newCapacity - minCapacity <= 0) { //判斷是否是初始化的情況 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) //是的話就直接傳回預設容量10,從這就可以看出來才剛開始初始化大小 return Math.max(DEFAULT_CAPACITY, minCapacity); if (minCapacity < 0) // overflow錯誤,最小值不可能是負數 throw new OutOfMemoryError(); //如果不是初始化也不是參數錯誤,那麼就傳回最小的容量 return minCapacity; } //到這表示擴容後的容量比最小容量要大 //是否達到了最大長度,如果沒到達就傳回擴容後的長度,否則就調用hugeCapacity return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow錯誤 throw new OutOfMemoryError(); //如果達到了規定的最大數組長度,那麼就擴容到整數的最大長度,否則就是目前預設的數組最大長度 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; - 還有一個指定位置的add方法,下面是源碼實作
public void add(int index, E element) { //檢查是否數組越界 rangeCheckForAdd(index); modCount++; final int s; //臨時儲存size Object[] elementData; //臨時儲存elementData if ((s = size) == (elementData = this.elementData).length) elementData = grow(); //如果長度等于size代表要擴容了 //核心方法System.arraycopy,他會将你要操作的index地方的位置空出了 System.arraycopy(elementData, index, elementData, index + 1, s - index); //然後index空出來的位置指派 elementData[index] = element; //加一 size = s + 1; } - 好了ArrayList的add方法已經介紹完了,如果有不對的地方請指正
addAll
- 源碼實作
public boolean addAll(Collection<? extends E> c) { //轉換數組 Object[] a = c.toArray(); modCount++; //擷取傳入集合的長度 int numNew = a.length; //是空集合的話直接傳回 if (numNew == 0) return false; Object[] elementData; final int s; //如果傳入集合的長度大于elementData中空餘的位置個數就增長 if (numNew > (elementData = this.elementData).length - (s = size)) elementData = grow(s + numNew); //增長完了就将傳入的資料copy進去 System.arraycopy(a, 0, elementData, s, numNew); //元素個數修改 size = s + numNew; //傳回成功 return true; }
Get
-
public E get(int index) { //檢查index Objects.checkIndex(index, size); //然後調用方法 return elementData(index); } E elementData(int index) { //直接下标取元素 return (E) elementData[index]; } - 很簡單就不說了
remove
- 源碼實作按照索引删除
public E remove(int index) { //檢查index Objects.checkIndex(index, size); final Object[] es = elementData; //用于傳回值 E oldValue = (E) es[index]; fastRemove(es, index); return oldValue; } private void fastRemove(Object[] es, int i) { modCount++; final int newSize; //去掉一個元素後的長度如果大于指定删除的索引的位置 if ((newSize = size - 1) > i) //把删除元素後面的元素往前挪一位 System.arraycopy(es, i + 1, es, i, newSize - i); //避免記憶體洩露 es[size = newSize] = null; } - 源碼實作按照對象删除
public boolean remove(Object o) { final Object[] es = elementData; final int size = this.size; int i = 0; //元素首次出現位置記錄 //尋找元素的邏輯 found: { if (o == null) { for (; i < size; i++) if (es[i] == null) break found; } else { for (; i < size; i++) if (o.equals(es[i])) break found; } //到這代表沒找到.傳回false return false; } //找到了就按照下标删除 fastRemove(e s, i); return true; }
indexOf
-
public int indexOf(Object o) { return indexOfRange(o, 0, size); } int indexOfRange(Object o, int start, int end) { Object[] es = elementData; if (o == null) { for (int i = start; i < end; i++) { if (es[i] == null) { //尋找到首個想等元素的時候傳回索引 return i; } } } else { for (int i = start; i < end; i++) { if (o.equals(es[i])) { //尋找到首個想等元素的時候傳回索引 return i; } } } //未找到傳回-1 return -1; } - 這個實作比較簡單,并且ArrayList的一些
*indexOf*
writeObject
- 這是序列化的方法
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { //将操作次數記錄 int expectedModCount = modCount; //将類中的no-static和no-transient屬性寫到流中 s.defaultWriteObject(); s.writeInt(size); //依次寫出元素 for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } //如果再次過程中數組中内容遭到改變,序列化停止并且抛出異常 if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }
readObject
- 這是反序列化的方法
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // 讀取大小和其他的内容 s.defaultReadObject(); //讀取容量 s.readInt(); //如果讀取到size>0 if (size > 0) { // 與clone()一樣,根據大小而非容量配置設定數組 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size); //建立存儲數組 Object[] elements = new Object[size]; //依次将資料讀出來并指派 for (int i = 0; i < size; i++) { elements[i] = s.readObject(); } //然後指派給本類的全局變量 elementData = elements; } else if (size == 0) { //size為0代表空集合,那麼就直接使用常量替換 elementData = EMPTY_ELEMENTDATA; } else { //非法的,出異常 throw new java.io.InvalidObjectException("Invalid size: " + size); } } - 好了到這我自己認為比較重要的方法源碼就都列出來的,是以将ArrayList的介紹就告一段落了,那麼到這我就隻有一個疑問就是關于elementData在首次add時加載jar或者路徑是做什麼用的,如果您知道,請評論在下面,非常謝謝您
- 總結一下ArrayList,我們在分析源碼的時候,除了在首次add時會添加路徑之類的資訊會設計到其他類的同步加載方法,但是本類的方法并沒有涉及同步,是以ArrayList并不是線程安全的,并且他是懶加載的,首次預設初始化并不會就初始化為初始化容量,而是在之後才會初始化為初始化容量,這個類的核心就是
System.arraycopy
LinkedList
- 可以先參考一下這篇關于連結清單的文章,如果你有了解一點就可以不用看了 : 連結清單
- 這是一個連結清單實作的List的實作類,對于ArrayList這個類要并不存在擴容copy的問題,如果你了解一點連結清單内容就會知道,增加元素在連結清單中無非就是改變引用的事情,是以它并沒有這樣的問題,好了讓我們直接上源碼吧
- 依舊先看一下他的成員屬性
//元素個數 transient int size = 0; //頭節點 transient Node<E> first; //尾節點 transient Node<E> last; - transient代表不會被序列化,那麼Node是啥東西,看一下源碼
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; } } - 從中可以LinkedList實作是一個雙連結清單,我們接下來看看他的初始化方法的實作
public LinkedList() { } - 空參構造什麼都沒做,接下來看其他的初始化方法
public LinkedList(Collection<? extends E> c) { this(); addAll(c); } - 那麼這個有參的構造方法其實主要邏輯是addAll方法,我暫時先不說這個方法,那麼我們先來看看其他的核心實作方法
- 源碼如下
public boolean add(E e) { linkLast(e); //添加到連結清單最後面 return true; } void linkLast(E e) { //将最後一個元素引用保留 final Node<E> l = last; //建立一個新的元素根據傳入的add參數,新的對象的前一個元素的引用 //就是之前的最後一個元素 final Node<E> newNode = new Node<>(l, e, null); //将最後的元素指針指向新元素 last = newNode; //如果之前的尾元素是空的代表是空連結清單, if (l == null) //即首尾都是此元素 first = newNode; else //就不是空連結清單,那麼倒數第二個的元素的下一個元素就是新元素 l.next = newNode; size++; modCount++; } - 還有一種是根據index位置插入的
public void add(int index, E element) { //是否越界 checkPositionIndex(index); //如果index等于元素個數 if (index == size) //那麼就添加到尾部 linkLast(element); else //否則就按位置添加 //node方法,傳入index,傳回指定元素索引處的（非空）節點 linkBefore(element, node(index)); } void linkBefore(E e, Node<E> succ) { //已經確定了succ不為空,在上面node方法中確定的 //取出指定index索引上的元素的前一個元素引用 final Node<E> pred = succ.prev; //建立新的元素,新元素的前一個元素就是目前指定index上的元素的前一個元素 //下一個元素是index上面的元素 final Node<E> newNode = new Node<>(pred, e, succ); //将指定索引位置的原元素的前指針指向新元素 succ.prev = newNode; //如果是在頭部添加,那麼目前元素的前一個元素肯定為空 if (pred == null) //然後新元素就成為了頭元素 first = newNode; else //否則就将index-1位置的元素的後指針指向新元素 pred.next = newNode; size++; modCount++; } - 如果你熟悉連結清單,那麼上面的代碼就很簡單就能了解了,如果看不懂,可以自己畫一下圖,瞬間明白
- 這也是構造中調用的方法,我們來看一下實作
public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { //檢查位置是否越界 checkPositionIndex(index); //集合轉數組 Object[] a = c.toArray(); //确定集合元素個數 int numNew = a.length; //如果是空集合傳回 if (numNew == 0) return false; //記錄前指向和目前節點 Node<E> pred, succ; //如果相等代表在最後追加 if (index == size) { //在最後追加,就不需要目前元素了,因為last已經指向了 succ = null; //添加集合的時候的,集合中首個被添加的元素的前一個節點就是目前連結清單中的最後一個節點 pred = last; } else { //到這就代表不是在尾部追加,而是将元素追加到連結清單中間位置 //node方法之前說過就是根據index來傳回index位置上的節點 //node傳回節點後儲存引用 succ = node(index); //記錄目前index節點的前節點的引用 pred = succ.prev; //到這就記錄好了目前節點和前節點的引用 } //開始循環建立集合中的元素的節點了,然後修改相關指向 for (Object o : a) { //将集合元素強轉一下,泛型限制不會classcast E e = (E) o; //建立節點,此節點的前一個元素指向已經确定 Node<E> newNode = new Node<>(pred, e, null); //代表從頭開始添加 if (pred == null) //新節點就是first節點 first = newNode; else //新節點前指向是pred,perd.next指向新元素,是以到這形成了前元素和新元素的雙向連結 pred.next = newNode; //到這就連接配接好了舊節點和新節點,需要移動pred指向,指向新節點 //然後将新節點當做舊節點,然後在于新建立的節點做雙向連結 pred = newNode; } //到這就把連結清單從頭到集合所有元素都連接配接完成了,需要處理集合的尾節點和連結清單的原index節點的連結問題了 //如果原來的尾index節點沒有 if (succ == null) { //那麼last就指向集合的尾節點 last = pred; } else { //代表之前的連結清單有index節點,那麼就修改index節點和集合的尾節點的連結 pred.next = succ; succ.prev = pred; } //做一些計數操作 size += numNew; modCount++; return true; } - 到這其實add方法基本就解析完了,那麼順便前面的構造也就沒有問題了,下面是其他方法的源代碼
-
remove()
public E remove() { return removeFirst(); } //可以看到預設從頭開始删除 public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } private E unlinkFirst(Node<E> f) { // assert f == first && f != null; //取出頭元素屬性值 final E element = f.item; //取出頭元素的下一個元素的引用 final Node<E> next = f.next; //将頭元素的屬性值置空 f.item = null; f.next = null; // help GC //然後将first指針指向下一個元素 first = next; //如果存在就隻有一個元素的情況 if (next == null) //first和last都是null last = null; else //否則就将原來頭節點的下一個節點的前引用取消,因為不存在了,自己已經變成了頭結點 next.prev = null; size--; modCount++; return element; } -
remove(Object)
public boolean remove(Object o) { //周遊,邏輯比較簡單,就不一句代碼一句代碼的說了 if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } //整體邏輯就是:已經獲得了一個node,那麼node的前後引用關系就找到了,然後剩下的就是改引用關系 E unlink(Node<E> x) { // assert x != null; //取出元素的所有屬性值 final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; //如果前引用是null,就代表是頭元素 if (prev == null) { //頭指針,指向下一個元素 first = next; } else { //那麼前引用就不是空的 //就将此元素的前元素的後指針指向此元素的後一個元素 prev.next = next; //此節點的前置引用可以取消了 x.prev = null; } //如果後置引用為空 if (next == null) { //代表是尾節點,尾指針,指向前一個 last = prev; } else { //代表不是尾節點,就将次元素的後一個元素的前引用指向次元素的前一個元素 next.prev = prev; //次元素的後置引用可以取消了 x.next = null; } //到這x節點已經完全脫離連結清單,置空 x.item = null; size--; modCount++; return element; } -
removeFirst()
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); //方法實作上面已經寫出了 } -
removeLast()
public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); // 跟之前的unlinkFirst類似就不再詳細說了 } -
remove(int)
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); //實作有說明在前面 } -
removeFirstOccurrence&removeLastOccurrence
- 其源碼就不去實作了,這個方法的作用是在于:如果指定的删除元素在連結清單中就删除,(差別:删除最開始出現的&删除最後一個出現的),如果不存在連結清單不變
-
getFirst() & getLast()
public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } -
get(int)
public E get(int index) { checkElementIndex(index); return node(index).item; }
set
-
set(int,E)
public E set(int index, E element) { //檢查索引 checkElementIndex(index); //利用node方法取出index上的節點 Node<E> x = node(index); //儲存作為傳回 E oldVal = x.item; //替換 x.item = element; return oldVal; }
隊列操作
- 對于LinkedList還支援隊列操作,其實作也是比較簡單的,都是依靠于之前介紹的add方法和remove方法(unlink),是以不打算貼出源碼了,所支援的操作有類似
peek
poll
push
pop
writeObject&readObject
- 至于LinkedList的序列化機制也是類似ArrayList的序列化方式和步驟,都是先将類中no-static和no-transient屬性寫到流中,然後寫size,然後依次寫元素,反序列化即相同步驟即可
- 總結:我們可以看到LinkedList是雙向連結清單的實作,并沒有首尾相連,是以也不是環形連結清單,并且其中不存在初始化容量概念,并且不存在ArrayList中的容量限制常量,是以說這個類可以做到理論上的無限大,并且從中沒發現同步代碼塊,是以這個類也不是同步的,需要我們在使用的時候注意使用場景,對于其他的操作就是正常的連結清單操作