背景
最近也看了一篇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 构造方法有三个
- 默认的构造方法，创建了一个空的Object数组
- 指定容量的构造方法，是根据initialCapacity的值大小创建一个指定的Object数据
- 指定集合的构造方法，copy原来的集合创建新的集合
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);
}
首先创建一个长多未10的Object数组，接着就调用了ensureExplicitCapacity这个方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
modCount这个变量很关键，不管是对ArrayList执行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个字节的空间给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,先判断集合中是否有空元素，如果过有则执行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的源代码，我们可以自己思考一下如何去实现这个数据结构？
网友评论