Java中ArrayList類的源碼解析

前言：在前面我們提到數(shù)據(jù)結(jié)構(gòu)的線性表。那么今天我們?cè)敿?xì)看下Java源碼是如何實(shí)現(xiàn)線性表的，這一篇主要講解順序表ArrayList鏈?zhǔn)奖硐乱黄谔峒啊?/p>

成都創(chuàng)新互聯(lián)從2013年成立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元富蘊(yùn)做網(wǎng)站,已為上家服務(wù),為富蘊(yùn)各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108

1：ArrayList結(jié)構(gòu)圖

Java中ArrayList類的源碼解析

2：關(guān)于Collection和List的區(qū)別

最好的比對(duì)就是查看他們的源碼我們先看Collection的所有接口

public interface Collection<E> extends Iterable<E> {
 int size();
 boolean contains(Object o);
 Iterator<E> iterator();
 Object[] toArray();
 <T> T[] toArray(T[] a);
 boolean add(E e);
 boolean remove(Object o);
 boolean containsAll(Collection<?> c);
 boolean addAll(Collection<? extends E> c);
 boolean retainAll(Collection<?> c);
 void clear(); 
 boolean equals(Object o);
 int hashCode();
}

在看List接口

public interface List<E> extends Collection<E> { 
 int size();
 boolean isEmpty();
 Iterator<E> iterator();
 Object[] toArray();
 <T> T[] toArray(T[] a);
 boolean add(E e);
 boolean remove(Object o);
 boolean containsAll(Collection<?> c);
 boolean addAll(Collection<? extends E> c);
 boolean addAll(int index, Collection<? extends E> c);
 boolean removeAll(Collection<?> c);
 boolean retainAll(Collection<?> c);
 void clear();
 boolean equals(Object o);
 int hashCode();
 E get(int index);
 E set(int index, E element);
 void add(int index, E element);
 E remove(int index);
 int indexOf(Object o); 
 int lastIndexOf(Object o);
 ListIterator<E> listIterator();
 ListIterator<E> listIterator(int index);
 List<E> subList(int fromIndex, int toIndex);
}

由于List是繼承Collection，所有具有Collection所有的功能，從Collection接口中我們也可以看出，Collection不具有索引，不可以取元素的值，而List取可以，List是具有索引的，這樣一來在獲取元素方面遠(yuǎn)遠(yuǎn)好于Collection。

3：Iterable接口

從ArrayList中我們可以看出，最頂端的接口就是Iterable這個(gè)接口，這個(gè)是一個(gè)迭代器，接口如下

public interface Iterable<T> {
 Iterator<T> iterator();
}

這個(gè)接口主要是返回一個(gè)對(duì)象，這個(gè)對(duì)象是Iterator，那么我們?cè)诳纯碔terator接口里面的方法

public interface Iterator<E> {
 boolean hasNext();
 E next();
 void remove();
}

那么我們主要看ArrayList是如何實(shí)現(xiàn)迭代器Iterator的。Iterator的實(shí)現(xiàn)在AbstractList這個(gè)抽象類中的一個(gè)私有類Itr中。我們看看具體實(shí)現(xiàn)

private class Itr implements Iterator<E> {
 int cursor = 0;
 int lastRet = -1;
 int expectedModCount = modCount;
 public boolean hasNext() {
  return cursor != size();
 }

cursor：記錄即將調(diào)用索引的位置

lastRet：最后一個(gè)元素的索引

int expectedModCount = modCount;目的是為了驗(yàn)證modCount后面會(huì)單獨(dú)說下。

判斷這個(gè)集合是否存在最后一個(gè)元素，通過cursor != size();size表示數(shù)組的長(zhǎng)度，因?yàn)閿?shù)組中元素索引從0開始，所以當(dāng)最后一個(gè)索引等于數(shù)組長(zhǎng)度的時(shí)候說明已經(jīng)到數(shù)組的尾部了。

public E next() {
  checkForComodification();
 try {
 E next = get(cursor);
 lastRet = cursor++;
 return next;
 } catch (IndexOutOfBoundsException e) {
 checkForComodification();
 throw new NoSuchElementException();
 }
 }
final void checkForComodification() {
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 }

modCount：記錄所有數(shù)組數(shù)據(jù)結(jié)構(gòu)變動(dòng)的次數(shù)，包括添加、刪除、更改等，為了避免并發(fā)時(shí)候，當(dāng)多個(gè)線程同時(shí)操作時(shí)候，某個(gè)線程修改了數(shù)組結(jié)構(gòu)，而另一個(gè)線程恰恰讀取這個(gè)數(shù)組，這樣一來就會(huì)產(chǎn)生錯(cuò)誤。所以在這段代碼中加入了modCount != expectedModCount，比如A線程對(duì)數(shù)據(jù)結(jié)構(gòu)修改一次，那么modCount比如+1，而expectedModCount并沒有發(fā)生變化，所以這樣就會(huì)拋出異常。

public void remove() {
 if (lastRet == -1)
 throw new IllegalStateException();
  checkForComodification();
 try {
 AbstractList.this.remove(lastRet);
 if (lastRet < cursor)
  cursor--;
 lastRet = -1;
 expectedModCount = modCount;
 } catch (IndexOutOfBoundsException e) {
 throw new ConcurrentModificationException();
 }
 }

我們剛剛說了lastRet記錄的是最后一個(gè)元素，所以刪除的時(shí)候直接按照索引刪除即可，因?yàn)閙odCount會(huì)減一，所以重新對(duì)expectedModCount 進(jìn)行賦值，避免遍歷時(shí)候產(chǎn)生錯(cuò)誤。而且把lastRed在次賦初始值。

4：分析ArrayList

剛剛目的是為了更加連接ArrayList做個(gè)鋪墊，ArrayList和我們以前數(shù)據(jù)結(jié)構(gòu)中提到的順序表一樣，采用Object[] 數(shù)組進(jìn)行存儲(chǔ)元素，用size來記錄元素的元素的個(gè)數(shù)。

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer.
 */
 private transient Object[] elementData;
 /**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
 private int size;

關(guān)于transient，一旦變量被transient修飾，變量將不再是對(duì)象持久化的一部分，那么為啥采用transient修飾呢，由于elementData本身是一個(gè)緩存數(shù)組，通常會(huì)預(yù)留一些容量，當(dāng)容量不夠時(shí)然后進(jìn)行擴(kuò)充，比如現(xiàn)在elementData容量是10，但是只有5個(gè)元素，數(shù)組中的最后五個(gè)元素是沒有實(shí)際意義的，不需要儲(chǔ)存，所以ArrayList的設(shè)計(jì)者將elementData設(shè)計(jì)為transient，然后在writeObject方法中手動(dòng)將其序列化，并且只序列化了實(shí)際存儲(chǔ)的那些元素，而不是整個(gè)數(shù)組。我們看下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 array length
 s.writeInt(elementData.length);
 // 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();
 }
 }

關(guān)于ArrayList的初始化。ArrayList的設(shè)計(jì)者采用3種方式初始化。（默認(rèn)數(shù)組容量是10）

public ArrayList(int initialCapacity) {
 super();
 if (initialCapacity < 0)
  throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
 this.elementData = new Object[initialCapacity];
 }
 public ArrayList() {
 this(10);
 }
 public ArrayList(Collection<? extends E> c) {
 elementData = c.toArray();
 size = elementData.length;
 // c.toArray might (incorrectly) not return Object[] (see 6260652)
 if (elementData.getClass() != Object[].class)
 elementData = Arrays.copyOf(elementData, size, Object[].class);
 }

trimToSize方法，這個(gè)方法可能我們好多人用的少，其實(shí)意義蠻大的，它主要把沒用的容量去除掉，這樣一來可以減少內(nèi)存的開銷

 public void trimToSize() {
 modCount++;
 int oldCapacity = elementData.length;
 if (size < oldCapacity) {
  elementData = Arrays.copyOf(elementData, size);
 }

ensureCapacity方法，我們知道數(shù)組如果滿了就會(huì)進(jìn)行擴(kuò)容，這個(gè)方法就是擴(kuò)容的。

public void ensureCapacity(int minCapacity) {
 modCount++;
 int oldCapacity = elementData.length;
 if (minCapacity > oldCapacity) {
 Object oldData[] = elementData;
 int newCapacity = (oldCapacity * 3)/2 + 1;
  if (newCapacity < minCapacity)
 newCapacity = minCapacity;
  // minCapacity is usually close to size, so this is a win:
  elementData = Arrays.copyOf(elementData, newCapacity);
 }

modCount就是增加因子，記錄操作數(shù)組結(jié)構(gòu)的次數(shù)，首先和容量進(jìn)行比對(duì)，如果不夠了進(jìn)行擴(kuò)容。這是Java1.6版本的就是在原來的基礎(chǔ)上擴(kuò)容1.5倍。1.7采用>>1也就是所有元素像右邊移動(dòng)一位然后加上原來的容量。其中

indexOf方法，這個(gè)方法是獲取元素索引。通過索引然后進(jìn)行查詢?cè)?/p>

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;
 }

從中我們也可以看出ArrayList是支持null的插入的。同樣采用的是循環(huán)遍歷來進(jìn)行查找，時(shí)間復(fù)雜的為n。

contains方法，驗(yàn)證數(shù)組是否包含某元素，直接通過indexOf驗(yàn)證返回值即可

public boolean contains(Object o) {
 return indexOf(o) >= 0;
 }

lastIndexOf方法，和indexOf相對(duì)，indexOf是從前往后，lastIndexOf是從后面往前查找如下

public int lastIndexOf(Object o) {
 if (o == null) {
 for (int i = size-1; i >= 0; i--)
 if (elementData[i]==null)
  return i;
 } else {
 for (int i = size-1; i >= 0; i--)
 if (o.equals(elementData[i]))
  return i;
 }
 return -1;
 }

toArray方法，就是把List轉(zhuǎn)換成數(shù)組形式

public Object[] toArray() {
 return Arrays.copyOf(elementData, size);
 }

get和set方法，這個(gè)就很簡(jiǎn)單了大家看下就行

public E get(int index) {
 RangeCheck(index);
 return (E) elementData[index];
 }
 public E set(int index, E element) {
 RangeCheck(index);
 E oldValue = (E) elementData[index];
 elementData[index] = element;
 return oldValue;
 }

RangeCheck方法是進(jìn)行驗(yàn)證的，查詢的索引不可以超過數(shù)組的長(zhǎng)度如下

 private void RangeCheck(int index) {
 if (index >= size)
 throw new IndexOutOfBoundsException(
 "Index: "+index+", Size: "+size);
 }

add(E e)添加一個(gè)元素，這個(gè)采用尾插入，先驗(yàn)證容量，size+1是加入1個(gè)元素后長(zhǎng)度，看原來數(shù)組容量是否夠。

 public boolean add(E e) {
 ensureCapacity(size + 1); // Increments modCount!!
 elementData[size++] = e;
 return true;
 }

add(int index, E element)按照索引進(jìn)行插入，第一個(gè)還是一樣進(jìn)行擴(kuò)容，然后把索引index后面的元素全部向后面移一位。System.arraycopy(elementData, index, elementData, index + 1,
             size - index);的意思就是將elementData的第index個(gè)元素移到第index+1個(gè)元素上，長(zhǎng)度為size-index。

public void add(int index, E element) {
 if (index > size || index < 0)
 throw new IndexOutOfBoundsException(
 "Index: "+index+", Size: "+size);
 ensureCapacity(size+1); // Increments modCount!!
 System.arraycopy(elementData, index, elementData, index + 1,
  size - index);
 elementData[index] = element;
 size++;
 }

addAll(Collection<? extends E> c)

public boolean addAll(Collection<? extends E> c) {
 Object[] a = c.toArray();
 int numNew = a.length;
 ensureCapacity(size + numNew); // Increments modCount
 System.arraycopy(a, 0, elementData, size, numNew);
 size += numNew;
 return numNew != 0;
 }

首先把集合c轉(zhuǎn)換成a數(shù)組，然后計(jì)算要進(jìn)行添加的數(shù)組長(zhǎng)度，其它的基本和添加元素一致。arraycopy(Object src, int srcPos,Object dest, int destPos,int length)

參數(shù)次數(shù)依次 源數(shù)組，源數(shù)組起始位置，目標(biāo)數(shù)組，目標(biāo)數(shù)組起始位置，復(fù)制數(shù)組元素?cái)?shù)目。

addAll(int index, Collection<? extends E> c)把數(shù)組插入到指定位置

public boolean addAll(int index, Collection<? extends E> c) {
 if (index > size || index < 0)
 throw new IndexOutOfBoundsException(
 "Index: " + index + ", Size: " + size);
 Object[] a = c.toArray();
 int numNew = a.length;
 ensureCapacity(size + numNew); // Increments modCount
 int numMoved = size - index;
 if (numMoved > 0)
 System.arraycopy(elementData, index, elementData, index + numNew,
   numMoved);
 System.arraycopy(a, 0, elementData, index, numNew);
 size += numNew;
 return numNew != 0;
 }

首先判斷是是否越界，然后和上面的基本一樣，就是進(jìn)行擴(kuò)容判斷，然后index后面的值進(jìn)行后移包括index，然后留下的空間插入集合a。所以2次進(jìn)行復(fù)制元素。

E remove(int index)和add相對(duì)，刪除這個(gè)元素然后把index后面的元素往前面移一位size - index - 1其中-1是因?yàn)閕ndex這個(gè)元素會(huì)被刪除，會(huì)少一位元素。

public E remove(int index) {
 RangeCheck(index);
 modCount++;
 E oldValue = (E) elementData[index];
 int numMoved = size - index - 1;
 if (numMoved > 0)
 System.arraycopy(elementData, index+1, elementData, index,
   numMoved);
 elementData[--size] = null; // Let gc do its work
 return oldValue;
 }

remove(Object o)這個(gè)就需要先進(jìn)性驗(yàn)證然后找到這個(gè)元素的位置最后進(jìn)行刪除

public boolean remove(Object o) {
 if (o == null) {
  for (int index = 0; index < size; index++)
 if (elementData[index] == null) {
  fastRemove(index);
  return true;
 }
 } else {
 for (int index = 0; index < size; index++)
 if (o.equals(elementData[index])) {
  fastRemove(index);
  return true;
 }
 }
 return false;
 }
private void fastRemove(int index) {
 modCount++;
 int numMoved = size - index - 1;
 if (numMoved > 0)
  System.arraycopy(elementData, index+1, elementData, index,
    numMoved);
 elementData[--size] = null; // Let gc do its work
 }

clear就是把所有的原素置空

public void clear() {
 modCount++;
 // Let gc do its work
 for (int i = 0; i < size; i++)
 elementData[i] = null;
 size = 0;
 }

subList方法，我們知道ArrayList是有這個(gè)方法，在ArrayList源碼并不存在，因?yàn)槭抢^承AbstractList而來的

 public List<E> subList(int fromIndex, int toIndex) {
 return (this instanceof RandomAccess ?
  new RandomAccessSubList<E>(this, fromIndex, toIndex) :
  new SubList<E>(this, fromIndex, toIndex));
 }
class SubList<E> extends AbstractList<E> {
 private AbstractList<E> l;
 private int offset;
 private int size;
 private int expectedModCount;
 SubList(AbstractList<E> list, int fromIndex, int toIndex) {
 if (fromIndex < 0)
  throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
 if (toIndex > list.size())
  throw new IndexOutOfBoundsException("toIndex = " + toIndex);
 if (fromIndex > toIndex)
  throw new IllegalArgumentException("fromIndex(" + fromIndex +
      ") > toIndex(" + toIndex + ")");
 l = list;
 offset = fromIndex;
 size = toIndex - fromIndex;
 expectedModCount = l.modCount;
 }

從代碼中我們可以看出這個(gè)一個(gè)基本內(nèi)部類的實(shí)現(xiàn)，subList只是去List中的一段數(shù)據(jù)。但是關(guān)于subList我們要注意幾個(gè)事項(xiàng)。

第一：如果我們改變了List的數(shù)值，那么你獲取的subList中的值也隨之改變，原因如下

 public E get(int index) {
 rangeCheck(index);
 checkForComodification();
 return l.get(index+offset);
 }

因?yàn)楂@取的還是以前List中的數(shù)據(jù)。同樣如果修改subList獲取的數(shù)值，List同樣改變，

第二：如果改變了List結(jié)構(gòu)，可能導(dǎo)致subList的不可用，因?yàn)檫@些修改已然基于原來的list，他們共同用一個(gè)list數(shù)組。

public void add(int index, E element) {
 if (index<0 || index>size)
  throw new IndexOutOfBoundsException();
 checkForComodification();
 l.add(index+offset, element);
 expectedModCount = l.modCount;
 size++;
 modCount++;
 }

5：關(guān)于list刪除錯(cuò)誤分析

list在采用循環(huán)刪除的時(shí)候會(huì)報(bào)ConcurrentModificationException異常，那么我們來看看具體原因，先看一段代碼

List<String> list = new ArrayList<String>();
 list.add("a");
 list.add("b");
 list.add("c");
 list.add("d");
 list.add("e");
 for (String str:list){
  list.remove(str);
 }

由于foreach遍歷最終會(huì)for (Iterator it=iterator;iterators.hasNext();)模式那么所以獲取元素的時(shí)候必然會(huì)用到迭代器中的next方法，next方法我們前面說了會(huì)有if(modCount!= expectedModCount)throw new ConcurrentModificationException()驗(yàn)證。因?yàn)檎{(diào)用remove(T x)方法時(shí)候modCount會(huì)+1,所以2次比較就會(huì)出現(xiàn)不一致。

正確寫法如下

 Iterator iterator=list.iterator();
 while (iterator.hasNext()){
  iterator.next();
  iterator.remove();
 }

為啥迭代器中remove就可以呢，是由于在remove代碼中有expectedModCount = modCount這句代碼。

6：ArrayList是線程安全嗎

線程不安全就是指多個(gè)線程同時(shí)操作造成臟讀，錯(cuò)讀情況，很明顯ArrayList是非線程安全的，比如說ArrayList現(xiàn)在只有一個(gè)值后，如果A，B2個(gè)線程同時(shí)刪除這個(gè)值，A線程判斷得到size=1,而此時(shí)時(shí)間片段到，CPU調(diào)用B線程執(zhí)行發(fā)現(xiàn)size也是1，開始刪除操作，然后A繼續(xù)進(jìn)行發(fā)現(xiàn)ArrayList已經(jīng)空了就會(huì)報(bào)異常?；蛘咛砑拥鹊?。但是Vector是線程安全的，因?yàn)槔锩嫠蟹椒ǘ技尤肓藄ynchronized，這樣造成的結(jié)果就是所有線程執(zhí)行ArrayList方法都必須等待，直到獲取同步鎖才可以繼續(xù)進(jìn)行，這樣一來性能大大降低。

以上就是本文的全部?jī)?nèi)容，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時(shí)也希望多多支持創(chuàng)新互聯(lián)！

網(wǎng)站標(biāo)題：Java中ArrayList類的源碼解析
文章分享：http://muchs.cn/article18/ghjcgp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、、移動(dòng)網(wǎng)站建設(shè)、手機(jī)網(wǎng)站建設(shè)、響應(yīng)式網(wǎng)站、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

成都網(wǎng)站建設(shè)