一、ArrayList的底層實作
- ArrayList實作與List、RandomAccess介面，是順序介面，即元素存放的資料與放進去的順序相同，允許放入null元素，也支持隨機訪問
- 底層通過陣列實作，除該類未實作同步外，其余跟Vector大致相同
- ArrayList相當于動態資料，其中最重要的兩個屬性分別是：elementData陣列以及siz
二、ArrayList可以實作同步嗎
為了追求效率，ArrayList沒有實作同步（synchronizd），如果需要逗哥執行緒并發訪問，用戶可以手動同步，也可以使用Vector代替，如可以先采用Collections.synchronizedList()方法對其進行包裝
三、ArrayList的add()方法
在呼叫add()方法的時候首先進行擴容校驗，將插入的值放在尾部，并將size+1.
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
四、ArrayList的add(index,e)方法
如果呼叫add(index,e)在指定位置添加的話也是首先擴容校驗，接著對資料進行復制，目的是把index位置空出來放本次插入的資料，并將后面的資料向后移動一個位置，
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//復制，向后移動
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
其實擴容最終呼叫的代碼
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData =https://www.cnblogs.com/houqx/p/ Arrays.copyOf(elementData, newCapacity);
}
也是一個陣列復制的程序，
注意：
由此可見ArrayList的主要消耗時陣列擴容以及在指定位置添加資料，在日常使用時最好是指定大小，盡量減少擴容，更要減少在指定位置插入資料的操作，
五、ArrayList的序列化
由于ArrayList是基于動態宿主實作的，所以并不是所有的空間都被使用，因此使用了transient修飾，可以防止被自動序列化
transient Object[] elementData; // non-private to simplify nested class access
因此ArrayList自定義了序列化和反序列化
//序列化
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject(); // Write out size as capacity for behavioural compatibility with clone() s.writeInt(size); // Write out all elements in the proper order. //只序列化了被使用的資料 for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } //反序列化 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // Read in size, and any hidden stuff s.defaultReadObject(); // Read in capacity s.readInt(); // ignored if (size > 0) { // be like clone(), allocate array based upon size not capacity int capacity = calculateCapacity(elementData, size); SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); ensureCapacityInternal(size); Object[] a = elementData; // Read in all elements in the proper order. for (int i=0; i<size; i++) { a[i] = s.readObject(); } } }
當物件中自定義了writeObject和readObject方法時，JVM會呼叫這兩個自定義方法來實作序列化和反序列化
從實作中可以看出ArrayList值序列化了被使用的資料
六、ArrayList和Vector的比較
Vector也會是實作List介面，底層資料結構和ArrayList類似，也是一個動態陣列存放的資料，不過在add()方法的時候使用synchronized進行同步資料，但是開銷較大，所以Vector是一個同步容器并不是并發容器，
add()方法
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
add(index,e)方法：指定位置插入資料
public void add(int index, E element) {
insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}
七、ArrayList的擴容機制
- 假如有20個資料需要添加，那么會分別在第一次的時候將ArrayList
- 之后擴容會按照1.5倍增長，也就是當添加第11個資料的時候，ArrayList繼續擴容變為10*1.5=15；
- 當添加第16個資料時，繼續擴容15*1.5=22個
- 不能超過int的最大值（231-1）-8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
八、LinkedList的底層實作
-
LinkedList底層是基于雙向鏈表實作的；
-
本身實作了List和Deque（雙端佇列）介面
-
擁有List的一些特性（jdk1.7/1.8之后取消了回圈，修改為雙向鏈表）
既可以看做一個順序容器，又可以看做一個佇列（Queue)，同時又可以看做一個堆疊（stack），這樣看來，LinkedList簡直是個全能冠軍，當你需要使用堆疊或者佇列時，可以考慮使用LinkedList，一方面是因為Java官方已經宣告不建議使用Stack類，更遺憾的是，Java里根本沒有一個叫做Queue的類（它是一個介面名），關于堆疊或者佇列，現在的首選是ArrayDeque，他有著比LinkedList（當做堆疊或者佇列使用時）更好的性能，
九、LinkedList的add()方法
public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
可見每次插入都是移動指標，和ArrayList的拷貝陣列來說效率要高上不少
十、LinkedList的查詢方法get(index)
public E get(int index) { checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
上述代碼，利用了雙向鏈表的特性，如果index離鏈表頭比較近，就從節點頭部遍歷，否則就從節點尾部開始遍歷，使用空間（雙向鏈表）來換取時間
- node會以O(n/2）的性能去獲取一個節點
- 如果索引值大于鏈表大小的一半，那么將從尾節點開始遍歷，這樣的效率是非常低的，特別是當index越接近size的中間值
十一、LinkedList優缺點
LinkedList插入、洗掉都是移動指標效率很高
產訊需要遍歷進行查詢，效率較低
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/124092.html
標籤：Java
上一篇：springcloud~微服務里的oauth2集成總結
下一篇：Stream流