ArrayList的基本存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)為數(shù)組
ArrayList 的add源碼為:
? ? ?public boolean add(E e){
? ? ? ? ? ensureCapacityInternal(size +1);
? ?? ?????elementData[size++]==e;
? ? ? ? ? return true;
?????}
``在當(dāng)前存儲(chǔ)結(jié)構(gòu)足夠存儲(chǔ)的時(shí)候谜悟,就直接把數(shù)組的size+1項(xiàng)的元素設(shè)為e即可怕轿。
其中的ensureCapacityInternal函數(shù)的源碼為:
private void ensureCapacityInternal(int minCapacity){
? ? ?if(elementData == EMPTY_ELEMENTDATA){
? ? ? ? ? minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
? ? ?}
? ? ?ensureExplicitCapacity(minCapacity);
}
``其中DEFULT_CAPACITY為10欧漱,即當(dāng)你初始化ArrayList的時(shí)候最小初始大小為10弊知,ensureExplicitCapacity函數(shù)的源碼為:
? ? ?private void ensureExplicitCapacity(int minCapacity){
? ? ? ? ? modCount++;
? ?? ?????if(minCapacity - elementData.length>0){
? ? ? ? ? ? ? ?grow(minCapacity);
? ? ? ? ? }
? ? ?}
``這里判斷了當(dāng)前需要的size即minCapacity是否大于element的長度,若供小于需戴已,則需要擴(kuò)容固额。
grow()的源碼為:
private void grow(int minCapacity){
? ? ?int oldCapacity = elementData.length;
? ? ?int newCapacity = oldCapacity+(oldCapacity>>1);
? ? ?if(newCapacity - minCapacity<0)
? ? ? ? ? newCapacity=minCapacity;
? ? ?if(newCapacity-MAX_ARRAY_SIZE>0)
? ? ? ? ? newCapacity = hugeCapacity(minCapacity);
? ? ? elementData = Arrays.copyof(element,newCapacity);
}
這里就是先確定擴(kuò)容后的ArrayList數(shù)組的大小头谜,然后在調(diào)用coryof狐蜕,拷貝到新的數(shù)組中后賦給elementData宠纯。從這段源碼可以知道ArrayList的存儲(chǔ)數(shù)量是有限的,通過hugeCapacity函數(shù)得知為Integer的MAX_VALUE层释,想想也是婆瓜,當(dāng)存儲(chǔ)超過Integer的最大值時(shí),數(shù)組的下標(biāo)無法表示的啊贡羔。
以上講完ArrayList的add函數(shù)后廉白,我們看看remove的源碼:
public E remove(int index){
? ? ?rangeCheck(index);
? ? ?modCount++;
? ? ?E oldValue=elementData(index);
? ? ?int numMoved = size -index -1;
? ? ?if(numMoved>0){
? ? ? ? ? System.arraycopy(elementData,index+1,elementData,index,numMoved);
? ? ?}
? ? ?elementData[--size]=null;
? ? ?return oldValue;
?}
從以上源碼可以得知,當(dāng)刪除元素時(shí)是非常耗時(shí)的治力,他會(huì)把要?jiǎng)h除的元素的后面所有元素都向前復(fù)制(移動(dòng))一位蒙秒,然后ArrayList的size-1,之前位置的value置為null,方便GC回收。
我們?cè)倏磄et的源碼:
public E get(int index){
? ? ?rangeCheck(index);
? ? ?checkForComodification();
? ? ?return ArrayList.this.elementData(offset+index);
}
就是檢查的下標(biāo)是否越界宵统,然后拿出來從初始存儲(chǔ)位置加上index的元素值。
public E set(int index,E e){
? ? ?rangeCheck(index);
?????checkForComodification();
?????E oldValue = Array.this.elementData(offset + index);
?????ArrayList.this.elementData[offset +index]=e;
?????return oldValue;
}
這段源碼比較容易理解,也是先檢查了是否數(shù)組越界马澈。
contains的源碼為:
public boolean contains(Object o){
? ? ?return indexOf(o)>=0;
}
public int indexOf(Object o){
? ? ?if(o==null){
? ? ? ? ? for(int i=0;i<size;i++){
? ? ? ? ? ? ? ?if(elementData[i]==null)
? ? ? ? ? ? ? ? ? ? return i;
? ? ? ? ? }
? ? ?}else {
? ? ? ? ? for(int i=0;i<size;i++){
? ? ? ? ? ? ? ?if(o.equals(elementData[i))
? ? ? ? ? ? ? ? ? ? return i;
? ? ? ? ? }
? ? ?}
?????return -1;
}
通過以上源碼得知瓢省,檢查是否包含某元素的方式就是遍歷所有元素,效率不高痊班。indexOf返回的是第一個(gè)等于該值的下標(biāo)勤婚,還有l(wèi)astIndexOf返回的是最后一個(gè)等于該值的下標(biāo)。
還有clone的源碼:
public Object clone(){
? ? ?try{
? ? ? ? ? ArrayList<E> v = (ArrayList<E>) supper.clone();
? ? ? ? ? v.elementData = Arrays.copyof(elementData,size);
? ? ? ? ? v.modCount = 0;
? ? ?}catch(CloneNotSupportedException e){
? ? ? ? ? throw new InternalError();
? ? ?}
}
由此可見ArrayList的clone的克隆只是簡單的克隆一下指向涤伐,并不會(huì)把所有的值再復(fù)制一份馒胆。