背景
最近也看了一篇ArrayList的文章壹店，講了一些ArrayList的源碼相關的知識骄瓣，一直也打算寫一篇ArrayList源碼的文件械馆，今天正好有時間嫉柴，搞起厌杜！
類圖結構
ArrayList.png
先看一下List接口定義
package java.util;
import java.util.function.UnaryOperator;
public interface List<E> extends Collection<E> {
int size();
boolean isEmpty();
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 addAll(int index, Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
void clear();
boolean equals(Object o);
int hashCode();
E get(int index);
E set(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);
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.ORDERED);
}
}
源碼分析
我們先有這樣一個概念，ArrayList的本身就是一個數組結構差凹，存儲的對象都是Object類型期奔，我們先看一下構造方法
構造方法
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private 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;
}
public ArrayList(Collection<? extends E> c) {
elementData = 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;
}
}
ArrayList 構造方法有三個
- 默認的構造方法侧馅，創(chuàng)建了一個空的Object數組
- 指定容量的構造方法危尿，是根據initialCapacity的值大小創(chuàng)建一個指定的Object數據
- 指定集合的構造方法，copy原來的集合創(chuàng)建新的集合
add方法馁痴，添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
通過add的源碼我們可以了解到谊娇，ensureCapacityInternal主要是計算數組長度是否已經滿了，滿了就需要對ArrayList的對象數組進行擴容罗晕， elementData[size++] = e; 這個比較好理解济欢，就是對這個數據進行賦值操作，關鍵的核心代碼還是ensureCapacityInternal這個方法小渊，當第一次給ArrayList添加元素的時候就會走過這個方法中
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
首先創(chuàng)建一個長多未10的Object數組法褥，接著就調用了ensureExplicitCapacity這個方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
modCount這個變量很關鍵，不管是對ArrayList執(zhí)行add酬屉、remove操作這個值都會增加半等，modCount這個變量主要的作用是在集合遍歷的時候來判斷集合中的數據有沒有修改揍愁，如果有修改了就跑出異常了ConcurrentModificationException,當minCapacity大于已經分配數據的大小時候就需要對原數組進行擴容，
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);
}
擴容的數組大小是多少了呢杀饵？新擴容的數組大小=原來的數組+原來的數組的/2莽囤，這個地方有注意事項，就是最大的數組長度=Integer.MAX_VALUE - 8切距，為什么是這樣呢朽缎？因為要保留8個字節(jié)的空間給JVM，否則可能出現Oom異常
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
一般情況下我們也不會關注這個谜悟，這個地方了解一下就OK了
remove 方法
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 remove method that skips bounds checking and does not
* return the value removed.
*/
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; // clear to let GC do its work
}
首先根據o是否為空來進行判斷话肖，如果o==null,先判斷集合中是否有空元素，如果過有則執(zhí)行fastRemove(index);
如果o不是空的赌躺，就遍歷集合對集合中的元素進行equals的判斷
fastRemove我們分析一下狼牺，建設ArrayList 中數據包含如何1、2礼患、3是钥、4
ArrayList remove.png
要想達到這樣的效果，我們看ArrayList源碼是怎么處理的
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; // clear to let GC do its work
}
numMoved=size(5)-2-1=2,numMoved計算出了修改后的數據的最后一位的位置缅叠，
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
arraycopy方法是從指定的索引位置拷貝數據到des對象中悄泥，desPos是目標對象的啟示位置，length是拷貝的數量
clear 方法
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
這個比較簡單肤粱，就是對數組中的元素賦予null
總結
1.難度并不是很復雜
2.通過源碼學習了一下ArrayList的實現弹囚，有很高的借鑒意義，比如對擴容的處理和和對異常情況擴容的處理
3.看了ArrayList的源代碼领曼，我們可以自己思考一下如何去實現這個數據結構鸥鹉？
