arraylist源碼分析 1.數組介紹 數組是數據結構中很基本的結構，很多編程語言都內置數組，類似於數據結構中的線性表 在java中當創建數組時會在記憶體中劃分出一塊連續的記憶體，然後當有數據進入的時候會將數據按順序的存儲在這塊連續的記憶體中。當需要讀取數組中的數據時，需要提供數組中的索引，然後數組根據 ...
arraylist源碼分析
1.數組介紹
數組是數據結構中很基本的結構，很多編程語言都內置數組，類似於數據結構中的線性表
在java中當創建數組時會在記憶體中劃分出一塊連續的記憶體，然後當有數據進入的時候會將數據按順序的存儲在這塊連續的記憶體中。當需要讀取數組中的數據時，需要提供數組中的索引，然後數組根據索引將內
存中的數據取出來，返回給讀取程式。在Java中並不是所有的數據都能存儲到數組中，只有相同類型的數據才可以一起存儲到數組中。
因為數組在存儲數據時是按順序存儲的，存儲數據的記憶體也是連續的，所以他的特點就是：定址讀取數據比較容易，插入和刪除比較困難。
帶參構造方法
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);} //如果既不大於零，也不小於零，就會報錯拋出異常
}
空參構造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //給一個成員變數賦值
}
private static final Object[] DEFAULTCAPACITY EMPTY ELEMENTDATA={}; //空參構造方法創建的數組就是一個空的
下麵這個用的不多，能看懂即可
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); //把Collection這個集合也變成了一個數組，傳給了當前數組elementData
//大於0，就拷貝數組
if ((size = elementData.length) != 0) { //判斷當前elementData數組的長度，如果不等於0
if (elementData.getClass() != Object[].class) //判斷類型是不是Object數組類型，如果不是這個類型
elementData = Arrays.copyOf(elementData, size, Object[].class); //拷貝一個數組，然後長度，然後把Object[].class數組傳進去，然後生成一個elementData數組
//不是大於0，就拷貝一個空的
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA; //設置為空數組
}
}
添加元素
public boolean add(E e) {
//檢測是否需要擴容
下¹ensureCapacityInternal(minCapacity：size + 1); // size是當前存的數據個數
//數組賦值
elementData[size++] = e;
return true;
}
擴容的入口方法，計算容量
private void 上¹ensureCapacityInternal(int minCapacity){ //minCapacity最小值，傳的時候就是+1後的
下下³ensureExplicitCapacity(下²calculateCapacity(elementData,minCapacity)); //計算容量，傳入一個數組elementData，再傳一個最小容量minCapacity
計算最小容量
private static int 上²calculateCapacity(Object[] elementData, int minCapacity){
//如果elementData是空的
if(elementData==DEFAUL TCAPACITY EMPTY EL EMENTDAT)|
//返回一個預設或者minCapacity，最後是返回其中最大的
return Math. max(DEFAULT_CAPACIT minCapacity);
//不是空，就返回size+1的值
return minCapacity;
}
private void 上上³ensureExplicitCapacity(int minCapacityp{
//只要發生修改就+1
modCount++;
//是否滿足擴容的條件 最小容量（當前數組存值得容量？） - object數組的長度
if(minCapacity-elementData. length〉0）//elementData.lenth=10 （預設容量為10）
下¹grow(minCapacity);
數組擴容方法
private void 上¹grow(int minCapacity){
//計算當前數組容量，也就是老的容量
int oldCapacity=elementData. length;
//新的數組容量 = 老容量 + 老容量/2 （老容量的1.5倍）
int newCapacity=oldCapacity+(oldCapacity >>1); >>1 除二
// oldcapacity=10
// oldcapacity >>1
// 0000 1010 >> 1
// 0000 0101 = 5
//判斷新的數組容量-之前最小容量
if(newCapacity-minCapacity<0)
newCapacity=minCapacity;
if (newCapacity - MAX_ARRAY_SIZE>0) //MAX_ARRAY_SIZE：值特別大，如果新的數組比它還大，就越界了，或者直接返回最大長度
newCapacity = hugeCapacity(minCapacity);
elementData=Arrays. copyof(elementData, newCapacity);
public void add(int index, E element) {
//判斷下標是否越界 下1rangeCheckForAdd(index); //檢測是否需要擴容 ensureCapacityInternal(size + 1);
//把index之後的所有元素向後移動一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
//將index位置覆蓋上新值
elementData[index] = element; size++; }
private void 上1rangeCheckForAdd(int index){
if(index>size || index<0)
throw new IndexOutofBoundsException(outofBoundsMsg(index));
System.arraycopy(elementData, index, elementData, index + 1,size - index); 舉例
int[] elementData = new int[10];
for(int i=0;i<5;i++){ //數組的下標 0,1,2,3,4
elementData[i]=i+1; //數組的值 1,2,3,4,5
System. out. println("=="+Arrays. toString(elementData));
int size=5;
int index=1; //插入數組下標位置
System. arraycopy(elementData, index, elementData, destPos: index+1, length: size-index); 原數組，插入指定的位置，又指定的數組，指定的位置為當前位置+1，到5-1=4的位置 >>從插入位置往後算
System. out. println("--"+Arrays. toString(elementData));
列印結果
== [1，2，3，4，5，0，0，0，0，0]
一 [1，2，2，3，4，5，0，0，0，0] 2：是要插入的數值
向ArrayList添加對象時，原對象數目加1如果大於原底層數組長度，則以適當長度新建一個原數組的拷貝，並修改原數組，指向這個新建數組。
原數組自動拋棄（java垃圾回收機制會自動回收）。size則在向數組添加對象，自增1。
刪除方法
指定位置刪除
public E remove(int index) {
檢測當前下標是否越界
下1rangeCheck(index);
modCount++;
E oldValue = elementData(index);
將index+1及之後的元素向前移動一位，覆蓋被刪除的值
int numMoved = size - index - 1;
if (numMoved > 0)
下下2System.arraycopy(elementData, index+1, elementData, index,
numMoved);
將最後一個位置的元素清空
elementData[--size] = null;
return oldValue;
}
private void 上1rangeCheck(int index){
if(index >=size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
上上2 System.arraycopy(elementData, index+1, elementData, index, numMoved); 舉例int[] elementData = new int[10];
for(int i=0;i<10;i++){ //數組的下標 0,1,2,3,4,5,6,7,8,9 elementData[i]=i+1; //數組的值 1,2,3,4,5,6,7,8,9,10
}
int size = elementData.lengh; //數組裡有幾個數，長度就是幾 elementData.lengh = 10
int index = 2;
int numMoved = size - index - 1; System. out. println("==" + Arrays. toString(elementData)); System. arraycopy(elementData, srcPos: index+1, elementData, index, numMoved); 原數組，指定的位置為要刪除的下標往後一個位置，又指定的數組，刪除位置的下標，10-2-1=7 >>從指定刪除下標位置往後數，全部向前移動一位
System. out. println("--" + Arrays. toString(elementData)); 列印結果 == [1，2，3，4，5，6，7,8,9,10] 3：要刪除的數字 一 [1，2，4,5,6,7,8,9,10,10]
指定元素刪除
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
下1fastRemove(index);
return true;} //從0開始遍歷，大小為數組長度，找到後直接刪除
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
如果沒有匹配元素，返回false
return false;
}
快速刪除， 沒有檢測index下標的原因：因為之前需要指定下標刪除，現在是直接指定刪除某個元素，如果元素不存在，for語句遍歷也不會找到這個元素，所有，只要能滿足兩個if語句其中一個，那這個元素一定在我的合理範圍內的，所以就不需要檢測有沒有下標
快速刪除，沒有檢測index下標
private void 上1fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
ArrayList<Integer> list=new Arraylist（）；
1ist.add（10）；
1ist.add（11）；
1ist.add（12）；
1ist.add（13）；
1ist.add（15）；
for（Integer num：1ist）{ if（num==12）{ 1ist.remove（num）；
} }I //報錯 //Exception in thread"main"java.util.concurrentModificationException
final void checkForComodification）{
if（modcount != expectedModcount） //modcount：6 expectedModcount：5 >> 使用迭代器時，同步了一下 expectedModCount = modCount,迭代的時候一直在判斷，如果此時調用了 ArrayList.remove，modCount變化了，expectedModCount還是初始同步的值，也就throw new ConcurrentModificationException();
throw new ConcurrentModificationException（）；
}
modCount++ : 該欄位表示list結構上被修改的次數。在對集合進行新增或移除操作時會使modCount+1,這是一個記錄集合變化次數的變數。
作用是在使用迭代器Iterator對集合進行遍歷時，用modCount來判斷集合內數據沒有發生變化，否則會拋出異常。
解決辦法：用迭代器刪除
//解決刪除異常問題 Iterator<Integer> it = list.iterator（）；
while(it.hasNext()){ //hasNext（）方法 ： 檢驗後面還有沒有元素。 從前往後查找。 Integer num=it.next（）； //next（）方法：獲取下一個元素
if（num == 12）{
//使用迭代器的刪除方法
it.remove（）；
} }
public void remove（）{ if（lastRet<0） throw new I1legalstateException（）；
checkForComodification（）；
try{ ArrayList.this.remove（lastRet）；
cursor=lastRet； 1astRet=-1；
//修改expectedModcound 和 modcount一樣
expectedModcount = modcount； }catch（IndexoutofBoundsException ex）{ throw new ConcurrentModificationException（）； }
