數(shù)組簡(jiǎn)介

數(shù)組對(duì)于我們來(lái)說(shuō)并不陌生，在內(nèi)存中是一塊連續(xù)的內(nèi)存空間，通過(guò)下標(biāo)可以隨機(jī)訪(fǎng)問(wèn)數(shù)組元素 如圖一所示，而在JDK中提供了功能更加強(qiáng)大的ArrayList其底層是基于數(shù)據(jù)實(shí)現(xiàn)的，為什么JDK已經(jīng)提供了數(shù)據(jù)還要使用ArrayList呢?我們通過(guò)比較兩者之間的差異來(lái)聊聊ArrayList的優(yōu)勢(shì)

java數(shù)組中如何獲取數(shù)組實(shí)際元素

在面試中經(jīng)常會(huì)問(wèn)在java中數(shù)組長(zhǎng)度和ArrayList中的size的區(qū)別?

通過(guò)下面的代碼我們其實(shí)已經(jīng)看出來(lái)數(shù)組獲取其長(zhǎng)度的時(shí)候永遠(yuǎn)是在聲明的時(shí)候定義的長(zhǎng)度，即使數(shù)組中只有一個(gè)元素，通過(guò)下面的輸出有人會(huì)問(wèn)arr[1]輸出的是0，這個(gè)是因?yàn)? int 類(lèi)型在java中為基本類(lèi)型所以在初始化數(shù)組時(shí)會(huì)默認(rèn)用0填充

在ArrayList中的長(zhǎng)度為list中實(shí)際元素的數(shù)量，這一點(diǎn)跟數(shù)組有著明顯的差別，具體如何實(shí)現(xiàn)后面會(huì)根據(jù)源碼分析

數(shù)組刪除元素和添加元素

在數(shù)組中刪除一個(gè)元素后需要移動(dòng)元素保證數(shù)組的連續(xù)性，如果刪除的是數(shù)組最后一個(gè)元素則不需要移動(dòng)，如果刪除了下標(biāo)為3的元素后使數(shù)組連續(xù)則需要將3號(hào)元素后的元素依次向前移動(dòng)

刪除元素后下標(biāo)為7的元素不再含有有效元素，如果我們使用的數(shù)組刪除數(shù)據(jù)后這些移動(dòng)的操作需要我們寫(xiě)相關(guān)的代碼來(lái)完成，使用ArrayList刪除與數(shù)據(jù)移動(dòng)都將自動(dòng)完成不需要我們手動(dòng)處理

在數(shù)組中添加元素如果插入元素后元素個(gè)數(shù)超過(guò)了數(shù)組的長(zhǎng)度則會(huì)報(bào)數(shù)組越界的錯(cuò)誤，這是因?yàn)閿?shù)組的容量是固定的不能動(dòng)態(tài)的增加

如下圖原數(shù)組容量為8如果想要成功添加第9個(gè)元素則需要將原來(lái)數(shù)組容量擴(kuò)大為9然后移動(dòng)指定位置的元素并將9插入，正因?yàn)檫@樣數(shù)組不具有動(dòng)態(tài)性因此在使用數(shù)據(jù)時(shí)需要額外考慮很多數(shù)組本身的問(wèn)題導(dǎo)致不能專(zhuān)注于核心代碼的編寫(xiě)

ArrayList的出現(xiàn)正式解決了數(shù)組存在以下問(wèn)題

• 動(dòng)態(tài)擴(kuò)容
• 有效數(shù)據(jù)長(zhǎng)度
• 增加刪除元素后數(shù)據(jù)移動(dòng)
• 數(shù)據(jù)遍歷

結(jié)合ArrayList一些面試問(wèn)題來(lái)看下具體源代碼

• ArrayList的默認(rèn)初始化容量
• 何時(shí)擴(kuò)容
• 擴(kuò)容容量大小
• 遍歷刪除fast fail原理
• 迭代器刪除為什么不越界

首先看下ArrayList的兩個(gè)重要的屬性

• elementData 存儲(chǔ)數(shù)據(jù)的數(shù)組
• size 數(shù)組中實(shí)際元素個(gè)數(shù)

transient Object[] elementData; // non-private to simplify nested class access 
 /** 
  * The size of the ArrayList (the number of elements it contains). 
  * 
  * @serial 
  */ 
 private int size; 

ArrayList 的構(gòu)造函數(shù)分為有參和無(wú)參兩種方式

• 無(wú)參構(gòu)造函數(shù)為ArrayList()其初始化后并未分配內(nèi)存空間而是在第一次add操作時(shí)分配
• 有參構(gòu)造函數(shù)ArrayList(int initialCapacity)初始化即分配制定大小內(nèi)存
• 有參構(gòu)造函數(shù)ArrayList(Collection c) 初始化即分配內(nèi)存

問(wèn)題一： 無(wú)參初始化默認(rèn)容量是多少，何時(shí)擴(kuò)容，擴(kuò)容大小為多少都在下面的注釋中可以找到

具體分析請(qǐng)看下面注釋

// 默認(rèn)初始化elementData為空數(shù)組 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 
public ArrayList() { 
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 
} 
//接下來(lái)進(jìn)行add操作 
public boolean add(E e) { 
    // 檢查當(dāng)前數(shù)據(jù)容量是否充足 
    ensureCapacityInternal(size + 1);  // Increments modCount!! 
    // size 自增可以保證有效元素的個(gè)數(shù) 
    elementData[size++] = e; 
    return true; 
 } 
//計(jì)算容量大小主要用于默認(rèn)初始化第一次add操作 
private static int calculateCapacity(Object[] elementData, int minCapacity) { 
    //默認(rèn)初始化時(shí)elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA 
    // 此處返回默認(rèn)容量DEFAULT_CAPACITY，此值大小為10 
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        return Math.max(DEFAULT_CAPACITY, minCapacity); 
     } 
    return minCapacity; 
} 
private void ensureCapacityInternal(int minCapacity) { 
     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); 
} 
private void ensureExplicitCapacity(int minCapacity) { 
     modCount++; 
    //檢查是否擴(kuò)容，如果當(dāng)前容量大于數(shù)組長(zhǎng)度進(jìn)行擴(kuò)容 
    // overflow-conscious code 
     if (minCapacity - elementData.length > 0) 
        grow(minCapacity); 
} 
//根據(jù)原來(lái)數(shù)據(jù)長(zhǎng)度進(jìn)行擴(kuò)容 
//oldCapacity >> 1 位運(yùn)算相當(dāng)于 oldCapacity=oldCapacity/2 
//新容量為 newCapacity = oldCapacity + (oldCapacity >> 1);即為原來(lái)的1.5倍 
//將老數(shù)組中的數(shù)據(jù)移動(dòng)到新數(shù)組中 
//此處解釋下為何為1.5倍，這是一種折中是對(duì)擴(kuò)容次數(shù)和空間大小的折中，如果擴(kuò)容次數(shù)太多會(huì)降低效率如果空間太大會(huì)浪費(fèi)空間 
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 = Arrays.copyOf(elementData, newCapacity); 
} 

問(wèn)題二：數(shù)據(jù)遍歷，fast-fail，迭代器刪除為什么不越界

在如下代碼注釋中將找到答案

• ArrayList 遍歷支持for，foreach，迭代器遍歷
• fail-fast 機(jī)制是java集合(Collection)中的一種錯(cuò)誤機(jī)制。當(dāng)多個(gè)線(xiàn)程對(duì)同一個(gè)集合的內(nèi)容進(jìn)行操作時(shí)，就可能會(huì)產(chǎn)生fail-fast事件。

例如：當(dāng)某一個(gè)線(xiàn)程A通過(guò)iterator去遍歷某集合的過(guò)程中，若該集合的內(nèi)容被其他線(xiàn)程所改變了;那么線(xiàn)程A訪(fǎng)問(wèn)集合時(shí)，就會(huì)拋出ConcurrentModificationException異常，產(chǎn)生fail-fast事件。

//ArrayList 迭代器是通過(guò)兩個(gè)游標(biāo)數(shù)組的下標(biāo) 
 private class Itr implements Iterator<E> {         // 代表下一個(gè)元素的游標(biāo) 
        int cursor;       // index of next element to return 
        int lastRet = -1; // index of last element returned; -1 if no such 
        int expectedModCount = modCount; 
        Itr() {}        // 如果游標(biāo)不等于size 代表還有下一個(gè)元素        public boolean hasNext() {            return cursor != size; 
        }       //        @SuppressWarnings("unchecked") 
        public E next() { 
            checkForComodification();            int i = cursor; 
            // 在此處判斷當(dāng)前游標(biāo)是超過(guò)了數(shù)組有效元素個(gè)數(shù) 
            if (i >= size) 
                throw new NoSuchElementException();            Object[] elementData = ArrayList.this.elementData;            //檢查是否數(shù)組越界 
            if (i >= elementData.length) 
                throw new ConcurrentModificationException();            cursor = i + 1; 
            // 更新lastRet游標(biāo)為當(dāng)前數(shù)組下標(biāo) 
            return (E) elementData[lastRet = i]; 
        }        public void remove() {         // 檢查刪除元素下標(biāo)是否合法 
            if (lastRet < 0) 
                throw new IllegalStateException();            checkForComodification();            try {            // 刪除原數(shù)組中制定下標(biāo)元素 
                ArrayList.this.remove(lastRet);                //更新游標(biāo) 
                cursor = lastRet;                lastRet = -1; 
                expectedModCount = modCount;            } catch (IndexOutOfBoundsException ex) {                throw new ConcurrentModificationException();            }        }       }