ArrayList
我們先了解一下陣列Array的概念
陣列是一種順序儲存的線性表，所有的元素的內容地址都是連續的
陣列有個致命缺點，就是無法動態的修改容量
而 ArrayList 的底層是基于陣列實作的，其容量大小可動態變化
Arraylist 與 LinkedList 區別
1.是否保證執行緒安全：ArrayList 和 LinkedList 都是不同步的，也就是不保證執行緒安全
2.底層資料結構： Arraylist 底層使用的是 Object 陣列；LinkedList 底層使用的是 雙向鏈表 資料結構
3.是否支持快速隨機訪問：** LinkedList 不支持高效的隨機元素訪問，而 ArrayList 支持，快速隨機訪問就是通過元素的序號快速獲取元素物件(對應于get(int index)方法)，
4.記憶體空間占用： ArrayList的空間浪費主要體現在在list串列的結尾會預留一定的容量空間，而LinkedList的空間浪費則體現在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接后繼和直接前驅以及資料），
ArrayList和Vector的區別
這兩個類都實作了List介面，他們都是有序集合，即存盤在這兩個集合中的元素的位置都是有順序的
（1）同步性：
Vector是執行緒安全的，它的方法之間是執行緒同步的，ArrayList是執行緒式不安全的，它的方法之間是執行緒不同步的，在不考慮執行緒安全的情況下，使用ArrayList，因為它效率高；如果考慮執行緒安全的安全，使用Vector
（2）資料增長：
ArrayList與Vector都有一個初始的容量大小，10，
當添加元素超過集合的長度時，會對原陣列進行擴容
Vector擴容的長度為原來陣列 ? 2 ，ArrayList擴容的長度為原來陣列 ? 1.5
ArrayList 常用屬性
// ArrayList默認初始容量 10
private static final int DEFAULT_CAPACITY = 10;
// 記錄ArrayList集合中元素個數
private int size;
// 定義一個Object[]型別的空陣列
private static final Object[] EMPTY_ELEMENTDATA = {};
// ArrayList集合用來儲存物件元素的陣列
transient Object[] elementData;
ArrayList 構造器
// 無參構造器
public ArrayList() {
// 空參創建空的ArrayList陣列
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
// 把傳入的集合轉換為陣列 給Object型別的陣列elementData
elementData = c.toArray();
//
if ((size = elementData.length) != 0) {
// 當c.toArray轉換的陣列型別不等object[]型別時
if (elementData.getClass() != Object[].class)
// 使用Arrays.copyOf(original,newLength,newType)方法
// @param original 要復制的陣列
// @param newLength 新陣列的長度
// @param newType 新陣列的型別
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 否則弄個空的陣列給他
this.elementData = EMPTY_ELEMENTDATA;
}
}
public ArrayList(int initialCapacity) {
// 創建指定長度的陣列
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
ArrayList的擴容機制
當ArrayList呼叫 add() 方法時，當 size == elementData.length 的時候，會呼叫 grow() 方法對ArrayList進行擴容
// 陣列擴容方法
// minCapacity = size + 1
private int newCapacity(int minCapacity) {
// 當前陣列長度
int oldCapacity = elementData.length;
// 新的陣列容量 = 舊陣列長度 + 舊陣列長度 / 2
// oldCapacity = 10 oldCapacity >> 1 --- 5
// 例如10的二進制為 : 0000 1010 >> 1 -----> 0000 0101 = 5
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// 如果一開始沒有定義初始容量這時newCapacity=0,回傳默認容量10
// 可以得出當無參new 一個ArrayList()時候，這個ArrayList()為空集合，size為0
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity // 這里回傳的長度為原陣列的1.5倍
: hugeCapacity(minCapacity);
}
由此可得出結論
通過無參構造器實體化的ArrayList初始容量為 0
在首次呼叫add()方法之后，回傳一個容量為10的陣列，后面每次擴容后新陣列的長度為原陣列長度的 1.5 倍
可以簡單理解為：首次擴容為10 ，后面每次擴容為原陣列的1.5倍
ArrayList頻繁擴容導致添加性能極具下降，該如何處理
解決方案：通過有參構造器 ，提前設定好容量， 空間換時間
public static void main(String[] args) {
// 創建集合物件
ArrayList<String> list = new ArrayList<>();
// 添加元素
list.add("A");
list.add("B");
list.add("C");
Long startTime = System.currentTimeMillis();
// 需求：需要添加100W跳資料
for (int i = 0; i < 1000000; i++) {
list.add(i+"");
}
Long endTime = System.currentTimeMillis();
// 添加100W條資料用時：129
System.out.println("添加100W條資料用時：" + (endTime - startTime));
// ArrayList(initialCapacity) 通過有參構造器指定ArrayList集合容量
ArrayList<String> list1 = new ArrayList<>(1000000);
startTime = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
list1.add(i+"");
}
endTime = System.currentTimeMillis();
// 提前宣告陣列長度后,添加100W條資料用時：51
System.out.println("提前宣告陣列長度后,添加100W條資料用時：" + (endTime - startTime));
}
ArrayLis插入或洗掉元素一定比LinkedList慢么
不一定
先看下ArrayList洗掉功能的原始碼
public E remove(int index) {
// 范圍校驗
Objects.checkIndex(index, size);
// 將源陣列賦給es
final Object[] es = elementData;
// 將index對應的元素賦值給 oldValue
E oldValue = (E) es[index];
// 呼叫fastRemove方法
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
// 修改次數+1
modCount++;
// newSize新陣列的長度
final int newSize;
if ((newSize = size - 1) > i)
// 如果新陣列長度newSize 大于 源陣列size所要洗掉元素的索引
// 使用arraycopy方法進行拷貝
//注意 ：這里源陣列跟目標陣列都為es,說明沒有創建新陣列
System.arraycopy(es, i + 1, es, i, newSize - i);
// 將源陣列最后一個元素設定為null，今早讓垃圾回識訓制對其進行回收
es[size = newSize] = null;
}
通過原始碼分析，我們得出一個結論
ArrayList洗掉元素的時候，并沒有創建一個新的陣列
而是把陣列中要洗掉的元素從后往前給覆寫了，然后把最后一個元素設為值null
在對比一下LinkedList洗掉功能的原始碼
public E remove(int index) {
// 校驗索引
checkElementIndex(index);
/*
if(return index >= 0 && index < size){
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
*/
return unlink(node(index));
}
看下unlink()方法里的node()方法
Node<E> node(int index) {
// 如果洗掉索引index小于LinkedList集合長度的一半
if (index < (size >> 1)) {
// 如果小于，那么把第一個節點賦值給x
Node<E> x = first;
// 從頭開始往后找
for (int i = 0; i < index; i++)
x = x.next;
// 回傳找到的節點
return x;
} else {
// 把最后一個節點賦值給x
Node<E> x = last;
// 從最后一個位置往前找
for (int i = size - 1; i > index; i--)
x = x.prev;
// 回傳找到的節點
return x;
}
}
根據原始碼得出結論，LinkedList每次洗掉元素的時候都要逐個檢索元素
如果LinkedList容量很大，洗掉的元素索引處于中間部位
這時LinkedList洗掉效率并不見的比ArrayList效率快
如何賦值某個ArrayList到另一個ArrayList中去
1. 使用clone()方法
這里是淺拷貝操作，不是添加操作
public Object clone() {
try {
// 把源集合中的成員資訊拷貝到 V
ArrayList<?> v = (ArrayList<?>) super.clone();
// 把源集合中的陣列元素拷貝到v的陣列元素中
v.elementData = Arrays.copyOf(elementData, size);
// 把v中的修改次數變數重置為0
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
2. 使用ArrayList構造方法
這里回顧之前ArrayList的有參構造方法
public ArrayList(Collection<? extends E> c) {
// ArrayList的toArray()回傳結果是object型別的陣列
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// 當c.toArray轉換的陣列型別不是object[]型別時
// 即c可能為其他型別的toArray()方法回傳的不是object型別
if (elementData.getClass() != Object[].class)
// 這時就使用Arrays.copyOf(original,newLength,newType)方法
// 通過Arrays.copyOf()方法把 c 轉換為object型別的陣列 (對應ArrayList的陣列型別)
// @param original 要復制的陣列
// @param newLength 新陣列的長度
// @param newType 新陣列的型別
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 否則弄個空的陣列給他
this.elementData = EMPTY_ELEMENTDATA;
}
}
3. 使用addAll用法
這里不是拷貝操作，而是將新集合添加到ArrayList集合的后面
public boolean addAll(Collection<? extends E> c) {
// 把傳入的集合轉換為陣列 給Object型別的陣列elementData
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
// 這里判斷，如果新集合長度加上源集合的元素個數 大于源集合容量時，進行grow()擴容
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
// 呼叫 System.arraycopy ()方法進行陣列的拷貝
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
ArrayList（int initialCapacity）會不會初始化陣列大小？
會初始化陣列大小
但是ArrayList大小沒有變，即 size = 0
因為在ArrayList的有參建構式中，沒有把int initialCapacity賦值給size
ArrayList中獲得元素個數 size()方法
這里我們猜想一下，當呼叫set，remove方法時，肯定會有索引校驗的方法
如果這個時候呼叫set()方法，就會出現索引越界例外
這是Java Bug里面的一個經典問題了，大家仔細品讀一下，
結尾
可能大家會覺得
那也只能硬啃，慢慢品
ArrayList在面試里面問的頻率沒HashMap，ConcurrentHashMap高，但是也有一定概率問到的，還是那句話，小心使得萬年船
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/87632.html
標籤：python
上一篇：Java注解實作機制