前言
ArrayList繼承了AbstractList類，實(shí)現(xiàn)了List接口,并且ArrayList底層是一個(gè)動(dòng)態(tài)擴(kuò)容的數(shù)組。ArrayList實(shí)現(xiàn)了RandomAccess接口，此接口是一個(gè)隨機(jī)訪問的標(biāo)記接口(不需要遍歷，直接通過下標(biāo)訪問數(shù)組元素的內(nèi)存地址)，此外還實(shí)現(xiàn)了Serializable接口支持序列化(就是將對(duì)象轉(zhuǎn)化為字符序的形式，這些字符序列包括了對(duì)象的字段和方法，序列化的對(duì)象可以被寫入數(shù)據(jù)庫，文件，也可以用于網(wǎng)絡(luò)傳輸)，同時(shí)ArrayList還支持拷貝實(shí)現(xiàn)了Cloneable接口
圖解展示ArrayList的實(shí)現(xiàn)和繼承關(guān)系:
ArrayList源碼 :
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
ArrayList類實(shí)現(xiàn)了RandomAccess接口，該接口是一個(gè)隨機(jī)訪問的標(biāo)記接口
//沒有任何的方法
public interface RandomAccess {
}
如何通過下標(biāo)直接訪問內(nèi)存地址呢，其實(shí)是做了下面這件事
這也就是為什么ArrayList查詢快的原因
E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
//這個(gè)方法是檢查下標(biāo)是否越界
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
ArrayLarrist類實(shí)現(xiàn)了Cloneable接口，說明該類支持拷貝，ArrayLarrist的內(nèi)部確實(shí)重寫了Object 的clone() 方法。
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
ArrayList動(dòng)態(tài)擴(kuò)容機(jī)制
ArrayList提供了三種初始化方法
public ArrayList()
public ArrayList(Collection<? extends E> c)
public ArrayList(int initialCapacity)
無參構(gòu)造方式
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
//elementData指向了一個(gè)空數(shù)組
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
源碼上面的注釋是說初始化了一個(gè)容量為10的數(shù)組，但是elementData指向了一個(gè)空數(shù)組
無參構(gòu)造還是不能說明問題繼續(xù)往下看
//默認(rèn)初始化容量為10
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//transient關(guān)鍵字作用：該字段不被序列化
transient Object[] elementData;
private int size;
有參構(gòu)造方式（1）
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[elementData ];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
initialCapacity形參表示一個(gè)初始化的容量可以理解為最初創(chuàng)建對(duì)象的時(shí)候給的一個(gè)容量
如果這個(gè)initialCapacity大于0，elementData 初始化的容量就是new Object[elementData ]
如果這個(gè)initialCapacity等于0，elementData就指向了一個(gè)空數(shù)組。
如果這個(gè)initialCapacity小于0, 拋出異常
這段代碼就會(huì)拋出以下異常
java.lang.IllegalArgumentException: Illegal Capacity: -10
List<Integer> list = new ArrayList<Integer>(-10);
try {
for (int i = 0; i < 10; i++) {
list.add(i);
}
for (Integer element : list) {
System.out.println(element);
}
}catch (Exception e){
e.printStackTrace();
}
有參構(gòu)造方式（2）
public ArrayList(Collection<? extends E> c) {
elementDatca = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
這個(gè)有參構(gòu)造是將一個(gè)集合作為ArrayList的元素 elementDatca就是c轉(zhuǎn)化的數(shù)組
Arrays.copyOf(elementData, size, Object[].class) 復(fù)制數(shù)組內(nèi)容給ArrayList類中字段elementData
賦值。
通過構(gòu)造方法的了解還是不能夠知道如何的動(dòng)態(tài)擴(kuò)容,那么重點(diǎn)來了
假設(shè)現(xiàn)在添加第十一個(gè)元素,下標(biāo)(索引)是10,也就是size是10執(zhí)行ensureCapacityInternal(size + 1)
add()方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
ensureCapacityInternal()方法是一個(gè)確保容量的方法,ensureCapacityInternal方法中calculateCapacity(elementData, minCapacity) 判斷elementData是否為空數(shù)組，如果是就使用Math.max(DEFAULT_CAPACITY, minCapacity);比較出來一個(gè)大的,此時(shí)應(yīng)該返回的是minCapacity
minCapacity的值是11,執(zhí)行方法ensureExplicitCapacity,判斷minCapacity是否超過當(dāng)前集合的容量elementData.length,如果超過就執(zhí)行g(shù)row(minCapacity),現(xiàn)在minCapacity是11,所以繼續(xù)執(zhí)行g(shù)row方法
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
執(zhí)行g(shù)row方法 將數(shù)組的長(zhǎng)度(這個(gè)長(zhǎng)度是默認(rèn)的10)賦值給了oldCapacity
執(zhí)行語句 int newCapacity = oldCapacity + (oldCapacity >> 1);這里涉及到了右移運(yùn)算符
右移運(yùn)算符:右側(cè)移除部分舍棄，左側(cè)補(bǔ)符號(hào)位(0表示整數(shù)1表示復(fù)數(shù)) 表示: 10>>1
0000 1010 —> 0000 0101 右移一位以后是十進(jìn)制5
所以是擴(kuò)大到原來的1.5倍,繼續(xù)判斷如果新容量沒有超過當(dāng)前的minCapacity
就將新的容量指向minCapacity,如果新容量超過最大容量就執(zhí)行 hugeCapacity(minCapacity);
以上判斷都不滿足就執(zhí)行Arrays.copyOf(elementData, newCapacity);將原有的數(shù)組復(fù)制到新分配的內(nèi)存地址上
//默認(rèn)的容量 如果超過這個(gè)容量就擴(kuò)容
private static final int DEFAULT_CAPACITY = 10;
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);
}
通過反射獲取容量的大小
public static Integer getCapacity(ArrayList list) {
Integer length = null;
Class clazz = list.getClass();
Field field;
try {
field = clazz.getDeclaredField("elementData");
field.setAccessible(true);
Object[] object = (Object[]) field.get(list);
length = object.length;
return length;
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return length;
}
驗(yàn)證數(shù)組動(dòng)態(tài)擴(kuò)容的過程:
- 不超過默認(rèn)容量
public class ArrayListTest {
public static void main(String[] args){
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 1; i < 5; i++) {
list.add(i);
}
Integer capacity = getCapacity(list);
System.out.println("集合容量:"+capacity);
int size = list.size();
System.out.println("集合大小:"+size);
//集合容量:10
//集合大小:4
}
}
- 超過默認(rèn)容量
ArrayList<Integer> list = new ArrayList<Integer>();
List<Integer> newList = new ArrayList<Integer>();
for (int i = 1; i < 15; i++) {
list.add(i);
}
Integer capacity = getCapacity(list);
System.out.println("集合容量:"+capacity);
int size = list.size();
System.out.println("集合大小:"+size);
//集合容量:15
//集合大小:14
- 如果先增加5個(gè)，然后在增加15個(gè),集合容量新容量等于最小容量
ArrayList<Integer> list = new ArrayList<Integer>();
ArrayList<Integer> newList = new ArrayList<Integer>();
for (int i = 1; i <= 5; i++) {
list.add(i);
}
for (int i = 0; i < 15; i++) {
newList.add(i);
}
list.addAll(newList);
//集合容量:20
//集合大小:20
- 如果添加20元素呢,根據(jù)前面的理解 當(dāng)添加了第11個(gè)元素的時(shí)候，通過oldCapacity + (oldCapacity >> 1)容量擴(kuò)容到了15,當(dāng)添加到16個(gè)元素的時(shí)候繼續(xù)擴(kuò)容此時(shí)新容量是22,所以集合容量是22,集合大小是20
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 1; i <= 20; i++) {
list.add(i);
}
//集合容量:22
//集合大小:20
結(jié)尾
本文到這里就結(jié)束了，感謝看到最后的朋友，都看到最后了，點(diǎn)個(gè)贊再走啊，如有不對(duì)之處還請(qǐng)多多指正。
