ArrayList 認(rèn)識
ArrayList是最常見以及每個Java開發(fā)者最熟悉的集合類了
| 關(guān)注點 | 結(jié)論 |
|---|---|
| ArrayList是否允許空 | 允許 |
| ArrayList是否允許重復(fù)數(shù)據(jù) | 允許 |
| ArrayList是否有序 | 有序 |
| ArrayList是否線程安全 | 非線程安全 |
- elementData ：ArrayList 是基于數(shù)組的實現(xiàn)，底層是一個數(shù)組elementData
- size：ArrayList 里面元素的個數(shù)，當(dāng) 執(zhí)行add() 方法時 size 會自增，執(zhí)行 remove() 方法時，會自減，
所以add了一個null進(jìn)入ArrayList，size也會加1
ArrayList 構(gòu)造方法
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
//假如 c.toArray() 返回的不是Object[]
if (elementData.getClass() != Object[].class)
//通過 Arrays.copyOf() 轉(zhuǎn)化為 Object[]
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
第一個構(gòu)造方法 首先將elementData 數(shù)組初始化，數(shù)組開始默認(rèn)長度為 DEFAULT_CAPACITY = 10
第二個構(gòu)造方法接受一個int類型的參數(shù) ，能夠自定義elementData 數(shù)組的長度
第三個構(gòu)造方法一個Collection 類型的參數(shù)
ArrayList添加元素
1 public boolean add(E e) {
2 ensureCapacityInternal(size + 1); // Increments modCount!!
3 elementData[size++] = e;
4 return true;
5 }
暫不考慮第二行 ensureCapacityInternal 方法，它只是擴容用的
底層實際上在調(diào)用add方法的時候只是給elementData的某個位置添加了一個數(shù)據(jù)而已
elementData中存儲的應(yīng)該是堆內(nèi)存中元素的引用，而不是實際的元素
ArrayList 擴容
private void ensureCapacityInternal(int minCapacity) {
// 如果 elementData 是空的集合
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//修改次數(shù)自增
modCount++;
如果下一個元素的 size 大于數(shù)組的長度 那么就要進(jìn)行擴容了
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
//獲取數(shù)組的長度
int oldCapacity = elementData.length;
//將數(shù)組的長度擴大 比如默認(rèn)的數(shù)組長度是10 擴大后 長度就是 15 了
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果擴大后的長度 依然小于 下一個元素的 size 比如：剛開始時是一個空數(shù)組，
//數(shù)組的長度為0，經(jīng)過上一行代碼擴大后 還是0
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//假如擴大后的長度 大于 限定的數(shù)組最大長度
if (newCapacity - MAX_ARRAY_SIZE > 0)
//最大容量可以是 Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
//最后調(diào)用到的是Arrays的copyOf方法，將元素組里面的內(nèi)容復(fù)制到新的數(shù)組里面去
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList 刪除元素
ArrayList支持兩種刪除方式：
- 按照下標(biāo)刪除
public E remove(int index) {
//檢查 index 是否合法
rangeCheck(index);
//修改次數(shù)自增
modCount++;
E oldValue = elementData(index);
//需要移動元素的個數(shù)
int numMoved = size - index - 1;
if (numMoved > 0)
//將index 后面 的所有元素 都向前移動一位
System.arraycopy(elementData, index+1, elementData, index,numMoved);
//將元素最后一個元素置為null
elementData[--size] = null; // clear to let GC do its work
//返回刪除的元素
return oldValue;
}
- 按照元素刪除，這會刪除ArrayList中與指定要刪除的元素匹配的第一個元素
public boolean remove(Object o) {
//判斷要刪除的元素是否為null
if (o == null) {
for (int index = 0; index < size; index++)
//假如元素 == null
if (elementData[index] == null) {
// 刪除元素 算法 跟 remove(int index) 差不多
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
ArrayList 插入元素
- 按指定索引插入
public void add(int index, E element) {
//檢查 index 的 值是否合法
rangeCheckForAdd(index);
//修改次數(shù)自增
//是否需要擴容操作
ensureCapacityInternal(size + 1); // Increments modCount!!
//index 后面的元素都要向后移動一個位置
System.arraycopy(elementData, index, elementData, index + 1,size - index);
//在index位置上添加源
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
- 默認(rèn)的索引插入
public boolean add(E e) {
//修改次數(shù)自增
//是否需要擴容
ensureCapacityInternal(size + 1); // Increments modCount!!
//往數(shù)組中添加元素
elementData[size++] = e;
return true;
}
ArrayList的優(yōu)缺點
從上面的幾個過程總結(jié)一下ArrayList的優(yōu)缺點。ArrayList的優(yōu)點如下：
ArrayList底層以數(shù)組實現(xiàn)，是一種隨機訪問模式，再加上它實現(xiàn)了RandomAccess接口，因此查找也就是get的時候非?？?/p>
ArrayList在順序添加一個元素的時候非常方便，只是往數(shù)組里面添加了一個元素而已
不過ArrayList的缺點也十分明顯：
刪除元素的時候，涉及到一次元素復(fù)制，如果要復(fù)制的元素很多，那么就會比較耗費性能
插入元素的時候，涉及到一次元素復(fù)制，如果要復(fù)制的元素很多，那么就會比較耗費性能
ArrayList和Vector的區(qū)別
ArrayList是線程非安全的，這很明顯，因為ArrayList中所有的方法都不是同步的，在并發(fā)下一定會出現(xiàn)線程安全問題。那么我們想要使用ArrayList并且讓它線程安全怎么辦？一個方法是用Collections.synchronizedList方法把你的ArrayList變成一個線程安全的List，比如
List<String> synchronizedList = Collections.synchronizedList(list);
另一個方法就是Vector，它是ArrayList的線程安全版本，其實現(xiàn)90%和ArrayList都完全一樣
為什么ArrayList的elementData是用transient修飾的
看一下ArrayList中的數(shù)組，是這么定義的：
private transient Object[] elementData;
看一下ArrayList的定義：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
看到ArrayList實現(xiàn)了Serializable接口，這意味著ArrayList是可以被序列化的，用transient修飾elementData意味著我不希望elementData數(shù)組被序列化。這是為什么？因為序列化ArrayList的時候，ArrayList里面的elementData未必是滿的，比方說elementData有10的大小，但是我只用了其中的3個，那么是否有必要序列化整個elementData呢？顯然沒有這個必要，因此ArrayList中重寫了writeObject方法：
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();
}
}
每次序列化的時候調(diào)用這個方法，先調(diào)用defaultWriteObject()方法序列化ArrayList中的非transient元素，elementData不去序列化它，然后遍歷elementData，只序列化那些有的元素
