ArrayList概述

ArrayList是一個(gè)底層基于數(shù)組實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組。在數(shù)據(jù)大小未知的情況下，可以一直往其中添加元素，ArrayList通過動(dòng)態(tài)擴(kuò)容來保證容器的容量可以滿足元素的寫入。

ArrayList的實(shí)現(xiàn)

private transient Object[] elementData;
private int size;

ArrayList底層采用了一個(gè)Object[]數(shù)組來保存存入list的元素，用size來記錄list中存入元素的數(shù)量。其操作基本上是對(duì)數(shù)組elementData的操作。

主要操作

• 構(gòu)造方法
  1、無參構(gòu)造器。構(gòu)造一個(gè)空的集合，默認(rèn)初始容量大小10。
  2、指定capacity的構(gòu)造器。構(gòu)造一個(gè)空的集合，初始容量大小為傳入?yún)?shù)的大小。
  3、傳入一個(gè)已有的集合，構(gòu)造一個(gè)ArrayList。將傳入的集合轉(zhuǎn)換成數(shù)組，放到elementData中。
• add(element)
  1、判斷容量是否足夠并擴(kuò)容。如果底層數(shù)組elementData的length小于當(dāng)前size+1時(shí)，進(jìn)行擴(kuò)容，擴(kuò)容后的容量大約為之前的1.5倍。
  2、將元素加至elementData數(shù)組最后一個(gè)元素之后。
  3、size值加1

ArrayList擴(kuò)容圖解.png

步驟1和2分別通過Array.newInstance和System.arraycopy方法來實(shí)現(xiàn)。

• add(index, element)
  1、檢查index是否越界。
  2、判斷容量是否足夠并擴(kuò)容。 和上面一樣。
  3、index之前的元素不變，index之后的元素同時(shí)往后挪動(dòng)一個(gè)下標(biāo)。
  4、index位置的數(shù)據(jù)置為element。

  例如，add(4, 8) 的圖解：

  
  
  ArrayList add圖解.png

• set(index,element)
  1、檢查index是否越界。
  2、將下標(biāo)對(duì)應(yīng)的元素直接替換為傳入的新元素。elementData[index] = element

• remove(index)
  1、檢查set的下標(biāo)是否越界。
  2、index之前的元素不變，index之后的元素同時(shí)往前挪動(dòng)一個(gè)下標(biāo)。
  3、數(shù)組末尾size-1下標(biāo)位置置為null，同時(shí)size值減1。

  例如，remove(4) 圖解

ArrayList remove圖解.png

• get(index)
  直接返回elementData[index]

通過觀察，我們可以發(fā)現(xiàn)，ArrayList在get／set隨機(jī)讀取操作的時(shí)候，效率非常高，而在進(jìn)行add／remove等操作時(shí)，需要對(duì)數(shù)組中部分元素進(jìn)行移動(dòng)。查看源碼可以發(fā)現(xiàn)，元素前后移動(dòng)的過程中，主要使用了System.arraycopy進(jìn)行數(shù)組拷貝來實(shí)現(xiàn)。

在add中自動(dòng)擴(kuò)容的時(shí)候，需要用Array.newInstance創(chuàng)建一個(gè)容量更大的新數(shù)組，然后通過System.arraycopy進(jìn)行舊數(shù)組和新數(shù)組之間的數(shù)據(jù)copy。如果在預(yù)先能夠知道元素總數(shù)的情況下，可以直接構(gòu)造指定大小容量的集合?；蛘咴诖笈繑?shù)據(jù)添加之前，如果知道要添加的元素的總數(shù)，可以通過調(diào)用ensureCapacity方法一次性增加集合的容量，避免遞增式的擴(kuò)容帶來的程序消耗。

ArrayList多線程下的使用

ArrayList不是線程安全的，在多線程環(huán)境下遍歷，遇到并發(fā)修改時(shí)，會(huì)使用Fail-Fast機(jī)制，拋出ConcurrentModificationException。在多線程下可以考慮用Collections.synchronizedList(List list)函數(shù)返回一個(gè)線程安全的ArrayList類，也可以使用concurrent并發(fā)包下的CopyOnWriteArrayList類。

總結(jié)

1. ArrayList底層基于數(shù)組實(shí)現(xiàn)，用Object[]來存儲(chǔ)元素，用size來記錄元素個(gè)數(shù)。
2. ArrayList get／set直接對(duì)數(shù)組索引處進(jìn)行操作效率很高，add／remove需要對(duì)數(shù)組進(jìn)行元素進(jìn)行拷貝移動(dòng)。
3. ArrayList 在元素?cái)?shù)量可預(yù)知的情況下，可提前擴(kuò)容，減少遞增擴(kuò)容帶來的消耗。
4. ArrayList是非線程安全的，可以用Collections工具類返回同步的list，或者用并發(fā)包下的CopyOnWriteArrayList。