本節(jié)主要分析JDK提供的ArrayList的源碼，以及與自己手寫的ArrayList進行對比。

ArrayList源碼分析

構(gòu)造方法

private static final int DEFAULT_CAPACITY = 10;private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData; // non-private to simplify nested class accessprivate int size;public ArrayList(int initialCapacity) { // 指定容量初始化if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);} }public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 默認初始化為空數(shù)組 }public ArrayList(Collection<? extends E> c) { // 通過集合構(gòu)造ArrayListelementData = 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;} }

JDK的ArrayList構(gòu)造時默認初始化為空數(shù)組，而我手寫的ArrayList默認初始化數(shù)組長度為DEFAULT_CAPACITY。

add()

public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!elementData[size++] = e;return true; }// 擴容 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); // 添加第一個元素時會將數(shù)組初始化為10}return minCapacity; }private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0) // 元素個數(shù)大于數(shù)組長度時觸發(fā)擴容grow(minCapacity); }private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍擴容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); // 將舊數(shù)組元素復(fù)制到新數(shù)組中 }public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size + 1); // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index); // 將index及后面的元素后移一位elementData[index] = element;size++; }

• 當添加第一個元素時會將數(shù)組容量初始化為10

• 當元素個數(shù)大于數(shù)組長度時觸發(fā)擴容，擴容后數(shù)組的長度為原來數(shù)組長度的1.5倍

• JDK的ArrayList使用的是Arrays.copyOf來移動或拷貝數(shù)組，效率更高

indexOf()

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()中根據(jù)對象是否為空來進行遍歷，而我手寫的ArrayList是使用的Objects.equals()方法。

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; // clear to let GC do its workreturn oldValue; }

remove()需要將index后的元素前移一位。

手寫ArrayList

ArrayList底層是一個動態(tài)數(shù)組。

構(gòu)造方法

public static final int DEFAULT_CAPACITY = 10;private int size;private E[] elements;public ArrayList() {this(DEFAULT_CAPACITY); }public ArrayList(int capacity) {capacity = Math.max(capacity, DEFAULT_CAPACITY); // 讓容量必須>=DEFAULT_CAPACITY，減少擴容次數(shù)elements = (E[]) new Object[capacity]; }

默認構(gòu)造方法會初始化數(shù)組的大小為10，也可以指定數(shù)組初始化的大小。

size() && isEmpty() && clear()

public int size() {return size; }public boolean isEmpty() {return 0 == size; }public void clear() {// 僅需要清除到size位置，后面沒有元素，而不是elements.lengthfor (int i = 0; i < size; i++) {elements[i] = null;}size = 0; }

clear()方法要將數(shù)組的所有元素賦值為null，這樣數(shù)組中的對象就會被垃圾回收器回收，釋放內(nèi)存，這里也可以考慮縮容。

add()

public void add(E e) {add(size, e); }public void add(int index, E e) {rangeCheckForAdd(index);ensureCapacity(size + 1);// 索引從index至size-1的元素后移一位for (int i = size - 1; i >= index; i--) {elements[i + 1] = elements[i];}elements[index] = e;size++; }// 添加的時候允許添加至size位置 private void rangeCheckForAdd(int index) {// 0<=index<=sizeif (index > size || index < 0) {throw new IndexOutOfBoundsException();} }// 擴容 private void ensureCapacity(int n) {int oldCapacity = elements.length;if (n > oldCapacity) { // 元素個數(shù)大于數(shù)組int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍擴容E[] newElements = (E[]) new Object[newCapacity];for (int i = 0; i < size; i++) {newElements[i] = elements[i]; // 將舊數(shù)組的元素逐一拷貝至新數(shù)組}elements = newElements;} }

add(E e)在數(shù)組最后添加元素，時間復(fù)雜度為O(1)。add(int index, E e)在數(shù)組指定索引位置添加元素，因為需要將指定索引位置及后面的元素后移一位，時間復(fù)雜度為O(n)。

set()

public void set(int index, E e) {rangeCheck(index);elements[index] = e; }private void rangeCheck(int index) {// 0<=index<sizeif (index >= size || index < 0) {throw new IndexOutOfBoundsException();} }

set()通過數(shù)組下標隨機訪問元素，時間復(fù)雜度為O(1)。

get()

public E get(int index) {rangeCheck(index);return elements[index]; }

get()通過數(shù)組下標隨機訪問元素，時間復(fù)雜度為O(1)。

indexOf() && lastIndexOf()

public int indexOf(E e) {for (int i = 0; i < size; i++) {if (Objects.equals(e, elements[i])) { // Objects.equals處理了空和值相等的情況return i;}}return ELEMENT_NOT_FOUND; }public int lastIndexOf(E e) {for (int i = size - 1; i >= 0; i++) {if (Objects.equals(e, elements[i])) {return i;}}return ELEMENT_NOT_FOUND; }

indexOf()是從索引0開始往后查找指定元素，一旦找到立刻返回對應(yīng)的索引，時間復(fù)雜度為O(n)。lastIndexOf()是從數(shù)組最后開始往前查找指定元素，一旦找到立刻返回對應(yīng)的索引，時間復(fù)雜度為O(n)。

contains()

public boolean contains(E e) {return ELEMENT_NOT_FOUND != indexOf(e); }

contains()判斷是否包含指定元素，時間復(fù)雜度為O(n)。

remove()

public E remove(int index) {rangeCheck(index);E oldValue = elements[index];// 索引從index+1至size-1的元素前移一位for (int i = index + 1; i < size; i++) {elements[i - 1] = elements[i];}elements[--size] = null;return oldValue; }public boolean remove(E e) {int index = indexOf(e);if (index == ELEMENT_NOT_FOUND) {return false;}remove(index);return true; }

remove(int index)刪除指定索引的元素，需要將索引后的元素往前移動一位，時間復(fù)雜度為O(n)。remove(E e)刪除指定元素，需要先查找指定元素的索引，然后再將索引后的元素往前移動一位，時間復(fù)雜度為O(n)。

總結(jié)

• ArrayList適合在數(shù)組最后添加元素，以及根據(jù)索引隨機訪問元素，如果要頻繁的刪除元素就不適合了。

• 如果在創(chuàng)建ArrayList時知道存儲的元素個數(shù)，就可以指定創(chuàng)建ArrayList的容量，這樣就能減少擴容。

總結(jié)

以上是生活随笔為你收集整理的ArrayList源码分析与手写的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。