概述
ArrayList是一个可以自动扩容的List接口实现,由命名可以看出是由数组实现。本文尝试编写一个简单的ArrayList实现,通过对比来理解JDK中的ArrayList是如何实现的。本次主要实现ArrayList的常用方法,完成简单的CRUD和迭代器。
动手实现
成员变量和构造方法
首先看一下类声明,为了更方便实现列表的相关方法,以及面向接口编程,这里声明实现List
接口,类命名为SimpleArrayList
public class SimpleArrayList<E> implements List<E> {}
然后再看一下成员变量,这里设计两个成员变量,第一个变量是实际存储数据的数组,第二个变量是数据的大小
private Object[] data;
private int size;
然后在构造方法中初始化数组
public SimpleArrayList() {
data = new Object[10];
}
CRUD的实现
首先看一下add
方法实现
@Override
public boolean add(E e) {
//判断数组还有没有空间存放新的元素
if( (size + 1) > data.length){
Object[] newData = new Object[data.length + 10];
System.arraycopy(data, 0, newData, 0, data.length);
data = newData;
}
data[size++] = e;
return true;
}
方法先判断数组中还有没有足够空间存放新元素。如果没有足够空间,就创建一个新数组,长度在原来的基础上增加10,再把原来数组的内容拷贝到新数组里,最后把新数组赋值给实际存储数据的成员变量data,这样就完成了扩容。最后再把add的元素放在最后一位,这样add
方法就完成了。
然后再看一下get
方法的实现
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("索引越界");
}
return (E) data[index];
}
get
方法的实现比较简单,首先检查一下传入索引的合法性,然后再返回数组中对应索引的元素。
下面是set
方法实现
@SuppressWarnings("unchecked")
@Override
public E set(int index, E element) {
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("索引越界");
}
E e = (E) data[index];
data[index] = element;
return e;
}
set
方法首先检查一下传入索引的合法性。通过查看List
接口的set
方法上的return
注释,知道set
方法返回的是旧元素,所以这里需要先声明旧元素的变量,再把新元素赋值,最后返回旧元素。
下面是remove
方法,传入Object的版本
@Override
public boolean remove(Object o) {
for (int i = 0; i < size; i++) {
if ( o==null ? get(i)==null : o.equals(get(i)) ){
if( i != (size-1))
System.arraycopy(data, i + 1, data, i, size - (i + 1) );
data[size--] = null;
return true;
}
}
return false;
}
方法传入的是一个object参数,所以要遍历所有元素,然后找到第一个对应的元素,再把后面的元素往前移动,覆盖被删除的元素。当被删除的元素是数组中最后一个时,就不再需要移动数组,所以在移动之前加一个判断。
迭代器
迭代器的实现类如下
private class SimapleIterator implements Iterator<E>{
private int currentIndex = 0;
@Override
public boolean hasNext() {
return currentIndex < size;
}
@SuppressWarnings("unchecked")
@Override
public E next() {
return (E) data[currentIndex++];
}
}
这是一个比较简单又能完成任务的实现。初始索引currentIndex是0,调用hasNext
方法时,如果currentIndex小于size,表示还有下一个元素,如果currentIndex等于size,就表示已经没有下一个元素了。next
方法在取出currentIndex下的元素之后,再自增移动currentIndex。
测试
目前主要的CRUD方法和迭代器都已经实现,现在可以测试一下这些方法能不能正常使用。测试方法如下
@Test
public void testSimpleArrayList(){
for (int i = 0; i < 100; i++) {
list.add(i);
}
list.add(null);
System.out.println("size=" + list.size());
System.out.println(list.remove(Integer.valueOf(0)));
System.out.println(list.remove(null));
System.out.println(list.remove(Integer.valueOf(100)));
System.out.println("size=" + list.size());
int count = 0;
for (int i = 0; i < list.size(); i++) {
count += list.get(i);
}
System.out.println("count = " + count);
int count2 = 0;
for (Integer i : list) {
count2 += i;
}
System.out.println("count2 = " + count2);
System.out.println("get(0)=" + list.get(0));
list.set(0, 1000);
System.out.println("get(0)=" + list.get(0));
}
输出
size=101
true
true
false
size=99
count = 4950
count2 = 4950
get(0)=1
get(0)=1000
可以看到输出正常,表示这个简单的实现的基本功能都已经完成了。下面再来看看JDK中是如何实现的。
jdk8的ArrayList实现
现在来看看jdk8的是如何实现ArrayList的,下面源码基于jdk1.8.0_121。
成员变量和构造方法
先来看一下主要的成员变量
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
这里主要看一下elementData
变量,这个变量是实际存储数据的数组,但是又声明为transient
,这表示ArrayList没法序列化吗?其实并不是,因为ArrayList实现了自己的readObject
和writeObject
方法来用于序列化。
下面再来看一下构造方法
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) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
public ArrayList(int initialCapacity)
:这个构造方法主要用于初始化数组的大小,当创建时就能知道有多少元素时,用这个构造方法能让时间和空间都达到最好的效果。比如,如果在创建时就知道会有1000个元素,用这个构造方法能避免在调用add
方法时频繁地复制数组。
public ArrayList()
:这是默认构造方法,初始化时会构造一个默认的空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
,被所有ArrayList共用。
public ArrayList(Collection<? extends E> c)
:这个构造方法接收一个集合作为基础元素返回一个新的ArrayList。
CRUD实现
首先看一下add
方法,主要看一下ArrayList是如何扩容的,扩容的主要方法是private void grow(int minCapacity)
public boolean add(E e) {
ensureCapacityInternal(size + 1);
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++;//数组修改标记
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//计算扩容长度
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新计算出的数组长度,小于需求的数组长度,就丢弃计算出的结果,把需求的数组长度赋值给newCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//考虑新计算出的数组长度过大的情况
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
//这里主要考虑int值溢出的情况,当需求的数组长度超过int的最大值时,就会发生溢出,此时主动抛出异常
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
在add
方法实现的流程上SimpleArrayList与ArrayList差别不是很大,都是先判断数组大小,再把新元素赋值,不过ArrayList考虑得更多:
-
第一个是多考虑了数组结构修改的情况,
modCount++
在这里表示数组结构发生了变化。对于在使用迭代器之类的情况时,如果数组结构发生变化,会导致结果不正确,所以通过这个值来监控数组结构的变化,并在发生变化的时候抛出ConcurrentModificationException
。 -
第二个是更仔细地考虑了扩容的长度,包括数组长度过长,就主动抛出异常等,详细可以查看上面的
private void grow(int minCapacity)
和private static int hugeCapacity(int minCapacity)
方法上的注释。
ArrayList扩容长度的计算方法是int newCapacity = oldCapacity + (oldCapacity >> 1);
,表示新的长度是在旧的长度基础之上,增加旧长度的50%(oldCapacity >> 1
在oldCapacity为正整数的情况下,等于oldCapacity / 2
)。
那么为什么JDK设计扩容长度是在原基础上增加50%呢?其实这是基于普遍性能上的考虑,在原基础上增加50%的长度,在一定程度上能保证add
方法执行为常数时间(在扩容期间会有一定的性能损失)。
在早期的Java版本中,扩容长度的计算方式是
int newCapacity = (oldCapacity * 3)/2 + 1;
现在再来看一下get
方法的实现
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
在get
方法实现的流程上,SimpleArrayList与ArrayList类似,先检查边界,再从数组中取出元素。
现在到set
方法的实现
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
set
方法相对也比较简单,SimpleArrayList实现类似。
再来看看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 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
}
在remove
方法上,ArrayList先判断了null
,然后再进行循环判断,最后再进行移动覆盖删除。同时也考虑到了数组结构修改的情况,修改modCount
变量来标记。
ArrayList中迭代器的hasNext
和next
使用modCount
来判断数组结构是否发生修改,SimpleArrayList只是简单的实现数据的获取。
总结
本文通过对比来加深对ArrayList常用方法的理解。
最后基于本文,总结了以下几个点:
- ArrayList内部使用Object数组来存储元素
- 当数组需要扩容时,每次增加原来长度的50%
- 当元素被删除时,删除元素后面的数组会往前移动(当被删除的元素在最后一个时除外),所以在很多情况下,想通过每次删除单个元素来提高遍历ArrayList的性能是不靠谱的(见过一些人尝试这样做),通常更可能损失性能
- 当使用
public boolean remove(Object o)
方法删除元素时,只会删除第一个找到的对应元素
评论
发表评论