Java源码分析 – ArrayList动态数组列表源码分析
本文由发表于6年前 | Java基础 | 暂无评论 |  被围观 5,642 views+

所谓的ArrayList就是传说中的动态数组了,这个类提供了动态增减元素的功能。List 接口的大小可变数组的实现,而ArrayList则实现了这个接口。

接下来我们就找几个ArrayList中的方法的源代码进行分析。

查看ArrayList的构造函数:
public ArrayList() {
this(10);
}

这里继续调用:

public ArrayList(int initialCapacity) {
super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
this.elementData = new Object[initialCapacity];
}

这里的elementData为ArrayList中定义的一个数组:

private transient Object[] elementData;
可以发现:ArrayList本质上是一个Object类型的数组。
继续查看set(int, E)方法的源代码:
/**
 * Replaces the element at the specified position in this list with
 * the specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
RangeCheck(index);

E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}

这个函数中首先调用了RangeCheck():

private void RangeCheck(int index) {
if (index >= size)
	throw new IndexOutOfBoundsException(
	"Index: "+index+", Size: "+size);
}

此函数用于检查当前请求插入的位置是否越界了,如果越界则抛出异常;如果没越界则继续执行,给elementData数组赋值并返回插入位置原来的值。

这里使用了泛型,返回原来的值时先进行了转换。这是因为在JDK1.5之后引入了泛型,所以在使用泛型限定ArrayList中存放的对象具体类型。如果不使用泛型,则可以存放任何类型的对象。这里推荐使用泛型。使用了泛型之后,下面的代码将会提示错误:

ArrayList<Integer> list = new ArrayList<Integer>();
list.add(new Integer(1));
list.add("arthinking");
可以发现:使用泛型后的ArrayList只能存放同一类型的对象(也可以不适用泛型存放不同类型的对象)。
继续查看ArrayList的add(E)方法:
/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
ensureCapacity(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}

这里首先调用了ensureCapacity()函数:

public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
	Object oldData[] = elementData;
	int newCapacity = (oldCapacity * 3)/2 + 1;
    if (newCapacity < minCapacity)
	newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}
}

首先移动数组下标到需要插入的位置:modCount++;

然后判断插入位置的下标值是否越界了,如果越界则扩充数组size*3/2+1,然后使用copyOf(Object[] original, int newLength);把旧的数组复制到新的数组中。

接下来执行:elementData[size++] = e;把对象存入elementData[size],然后再执行size+1操作。

可以发现:ArrayList的容量是动态扩充的。当数组容量不足是,则使用(oldCapacity * 3)/2 + 1;规则扩充原来的数组为原来的1.5倍加1。
继续查看ArrayList的contains(Object):
/**
 * Returns <tt>true</tt> if this list contains the specified element.
 * More formally, returns <tt>true</tt> if and only if this list contains
 * at least one element <tt>e</tt> such that
 * <tt>(o==null ? e==null : o.equals(e))</tt>.
 *
 * @param o element whose presence in this list is to be tested
 * @return <tt>true</tt> if this list contains the specified element
 */
public boolean contains(Object o) {
return indexOf(o) >= 0;
}

这里简单的调用了indexOf(Object)函数:

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;
}

如果查找的是null时,如果elementData中含有null的话也会返回下标值。如果没有找到则返回-1。

可以得出:可以查找ArrayList是否包含null。如果没有查找到元素则返回-1。
继续查看ArrayList的remove(int):
/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
RangeCheck(index);

modCount++;
E oldValue = (E) elementData[index];

int numMoved = size - index - 1;
if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
		     numMoved);
elementData[--size] = null; // Let gc do its work

return oldValue;
}

首先仍然是调用RangeCheck(iint)方法判断需要删除的位置是否越界,如果越界则抛出异常。

接下来是先保存需要删除位置的值,然后计算删除元素后需要往前移动的元素个数:size - index – 1,然后调用void java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)方法把删除元素的后面的所有元素依次往前移动一个位置。

ArrayList的删除元素的时间开销是比较大的,每删除一个元素都要调整整个数组,总的时间复杂度为O(n)。

可以发现Arraylist的删除元素时间开销比较大。
继续查看ArrayList的addAll(Collection<? extends E>):
/**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order that they are returned by the
 * specified collection's Iterator.  The behavior of this operation is
 * undefined if the specified collection is modified while the operation
 * is in progress.  (This implies that the behavior of this call is
 * undefined if the specified collection is this list, and this
 * list is nonempty.)
 *
 * @param c collection containing elements to be added to this list
 * @return <tt>true</tt> if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
    public boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray();
        int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
	return numNew != 0;
    }

首先把需要附加的Collection转化为数组,然后调用ensureCapacity(int)动态扩充elementData数组。

最后通过void java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)方法把数组复制elementData数组的后面。更新size变量。返回值为是否插入了元素。

这里调用了.Arrays.copyOf(Object[] original, int newLength, Class<? extends Object[]> newType)和void java.lang.System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length),时间开销比较大。

可以发现ArrayList添加整个数组的时候时间开销比较大。
★ ArrayList本质上是一个Object类型的数组。
★ 使用泛型后的ArrayList只能存放同一类型的对象(也可以不适用泛型存放不同类型的对象)。
★ ArrayList在当遇到容量不足时动态扩充。
★ 可以查找ArrayList是否包含null。如果没有查找到元素则返回-1。
★ Arraylist的删除元素时间开销比较大。
★ ArrayList添加整个数组的时候时间开销比较大。
除了文章中有特别说明,均为IT宅原创文章,转载请以链接形式注明出处。
本文链接:http://www.itzhai.com/java-source-code-analysis-arraylist-list-of-source-code-analysis-dynamic-arrays.html
关键字: , ,
arthinking Java技术交流群:280755654,入门群:428693174 more
分享到:
 
2011 10/10
文章评论
    没有评论
给我留言

有人回复时邮件通知我
Java基础的相关文章
随机文章 本月热门 热评
1 C++语法笔记 – 流类库与IO 2011/9/3
2 ExtJS在树TreePanel之间拖放结点 2011/4/11
3 Semaphore的介绍和使用 2012/7/30
4 乐器销售管理系统 | Project 2011/11/15
5 jQuery中使用Ajax实现文本输入框的自动完成功能 2011/5/14
6 CompletionService的介绍和使用 2012/7/30
友情推荐 更多
破博客 文官洗碗安天下,武将打怪定乾坤。多么美好的年代,思之令人泪落。
Mr.5's Life 白天是一名程序员,晚上就是个有抱负的探索者
行知-追寻技术之美 关注大数据,分布式系统
我爱编程 编程成长轨迹
Cynthia's Blog 学习笔记 知识总结 思考感悟
 
猜您喜欢
欢迎关注我的公众号 IT宅
关于IT宅 文章归档

IT宅中的文章除了标题注明转载或有特别说明的文章,均为IT宅的技术知识总结,学习笔记或随笔。如果喜欢,请使用文章下面提供的分享组件。转载请注明出处并加入文章的原链接。 感谢大家的支持。

联系我们:admin@itzhai.com

Theme by arthinking. Copyright © 2011-2015 IT宅.com 保留所有权利.