有关ArrayList常用方法的源码解析

jdk1.7.0_79

  我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问题早已烂熟于心,前者基于数组实现,后者基于链表实现;前者随机方法速度快删除和插入指定位置速度慢,后者随机访问速度慢删除和插入指定位置速度快;两者都是线程不安全的;列表与数组之间的区别等等。

  列表与数组之间很大的一个区别就是:数组在其初始化就需要给它确定大小不能动态扩容,而列表则可以动态扩容。ArrayList是基于数组实现的,那么它是如何实现的动态扩容呢?   对于ArrayList的初始化有三种方式:   对于第一种默认的构造方法,ArrayList并没有初始化容量大小,而是将列表的元素数据引用指向了一个空数组。

private transient Object[] elementData;
private static final Object[] EMPTY_ELEMENTDATA = {};
//1.ArrayList默认构造方法
public ArrayList() {    
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

  与JDK1.6不同的是,JDK1.6即时是在调用默认的构造方法时,也会初始化容量大小,JDK1.7当然会带来一定的好处,如果初始化而不使用就白白浪费了存储空间,等到添加的时候再初始化容量大小即可。

//JDK1.6 ArrayList
public ArrayList() {
    this(10);
}    

  对于第二种构造方法,则直接创建一个指定大小的数组,将列表的元素数组引用指向它。

//2.ArrayList带有初始化大小的构造方法
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}

  第三种构造方法,能将一个集合作为参数传递,但集合中的元素必须继承自ArrayList中的元素。

//3.可将一个集合作为ArrayList的参数构造成ArrayList
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();    //将集合转换为数组
    size = elementData.length;    //集合中的元素大小
    // c.toArray might (incorrectly) not return Object[] (see 6260652) 这里是个bug,参考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

  上面提到了一个bug,也就是说将一个集合转换为数组的时候可能错误地不会返回Object[],举例说明。

 1 package com.algorithm.sort;
 2 
 3 import java.util.ArrayList;
 4 import java.util.Arrays;
 5 import java.util.List;
 6 
 7 /**
 8  * bug编号:6260652。toArray有可能不会返回Object[]
 9  * Created by yulinfeng on 2017/6/26.
10  */
11 public class Test {
12     public static void main(String[] args) {
13         correctly();
14         incorrectly();
15     }
16     
17     /**
18      * 返回Object[]
19      */
20     private static void correctly() {
21         List<String> list = new ArrayList<String>();
22         list.add("test");
23         System.out.println(list.getClass());
24         Object[] objArray = list.toArray();
25         System.out.println(objArray.getClass());
26     }
27     /**
28      * 不返回Object[]
29      */
30     private static void incorrectly() {
31         List<String> list = Arrays.asList("test");
32         System.out.println(list.getClass());
33         Object[] objArray = list.toArray();
34         System.out.println(objArray.getClass());
35     }
36 }

  运行结果:

  上面的这个例子就说明了toArray并不一定总是返回Object[],返回的Object[]时,Object元素就不能插入,故JDK在“6260652”中修复了这个bug。

  接下来看元素插入以及删除等其它方法。

//ArrayList#add
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  //确保容量是否充足
    elementData[size++] = e;    //将元素添加至数组
    return true;
}
//ArrayList#ensureCapacityInternal
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);     //如果此时还没有初始化列表容量大小,则对其初始化,默认容量为10
    }
    ensureExplicitCapacity(minCapacity); //检查容量是否充足
}
//ArrayList#ensureEcplicitCapacity
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;    //注意此变量
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);    //容量不够则进行扩容
}

  在ensureEcplicitCapacity方法中有一个modCount(modify count)变量进行了自增。

protected transient int modCount = 0;

  这个变量不仅在add方法中会自增,只要是在增加或者删除等对ArrayList结构产生了变化都会记录加1,这样做的原因和多线程下Iterator迭代器遍历有关。在AbstractList$Itr中也有一个变量与之对应。

//AbstractList$Itr
int expectedModCount = modCount;

  在AbstractList$Itr#next中调用了checkForComodification方法。

//AbstractList$Itr#checkForComodification
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

  如果当前运行环境是单线程,不论对列表进行何种操作何时增加、修改、删除等,excpectedModCount总是会等于modCount,但是如果当前运行环境是多线程,很有可能一个线程在迭代遍历,而另一个线程在对其进行新增或者修改等,JDK则不允许这么做,此时则会抛出ConcurrentModificationException异常,这就是modCount变量在此起的作用。   回到ArrayList#add方法,当列表容量不足时,此时会调用grow方法进行扩容。

//ArrayList#grow
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);    //扩容策略为,每次新增容量的大小为旧容量的一半。也就是说如果默认容量为10,则第一次扩容大小为10 / 2 = 5,第二次扩容大小为15 / 2 = 7。
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;    //扩容策略扩得太小
    if (newCapacity - MAX_ARRAY_SIZE > 0)    //扩容策略扩得太大,大于最大数组大小时,最多等于Integer.MAX_VALUE
        newCapacity = hugeCapacity(minCapacity);
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

  ArrayList获取指定索引位置的元素get方法。

public E get(int index) {
    rangeCheck(index);    //检查索引是否越界
    return elementData(index);
}

  由于ArrayList是由基于数组实现,故此方法较为简单,判断是否越界,没有则根据数组下标来索引返回元素即可。remove方法删除指定位置的元素。  

//ArrayList#remove
public E remove(int index) {
    rangeCheck(index);    //检查索引是否越界
    modCount++;    //记录modCount,上面已提及
    E oldValue = elementData(index);    //取出指定索引元素
    int numMoved = size - index - 1;    //移动的元素个数
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //将最后一个数组元素置为null,方便GC

    return oldValue;
}

  代码比较简单,同样也体现了基于数组实习的ArrayList在删除指定元素时的效率问题。有关Arrays. copyOf和System.arraycopy方法可参考《System.arraycopy(src, srcPos, dest, destPos, length) 与 Arrays.copyOf(original, newLength)区别》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏积累沉淀

JDK源码分析-ArrayList分析

花了两个晚上的时间研究了一下ArrayList的源码, ArrayList 继承自AbstractList 并且实现了List, RandomAccess,...

1815
来自专栏书山有路勤为径

排序数组转换为二叉查找树

已知一个排序的数组,将该数组转换为一个高度平衡的二叉查找树。 平衡的定义: 二叉查找树中,任意节点的两颗子树高度差不超过1. LeetCode 108

903
来自专栏微信公众号:Java团长

Java集合源码剖析——ArrayList源码剖析

ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。

1122
来自专栏wannshan(javaer,RPC)

关于 java.util.ConcurrentModificationException jdk源码分析

先看怎么发生 List<Integer> list=new ArrayList<>(); for(int i=0;i<10;i++){ list.add...

2993
来自专栏IT可乐

JDK1.8源码(五)——java.util.ArrayList 类

  关于 JDK 的集合类的整体介绍可以看这张图,本篇博客我们不系统的介绍整个集合的构造,重点是介绍 ArrayList 类是如何实现的。 1、ArrayLis...

41711
来自专栏闻道于事

Java常用工具类之时间转换

import java.text.DecimalFormat; import java.text.ParseException; import java...

3406
来自专栏java系列博客

Iterator在ArrayList中的源码实现

1892
来自专栏用户画像

6.3.1 B树及其基本操作

B树,又称多路平衡查找树,B树中所有节点的孩子结点数的最大值成为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树:

931
来自专栏机器学习和数学

[算法与数据结构] 《算法导论》堆排序笔记

堆排序的实现是靠叫做“堆”的数据结构来实现的。所以学习堆排序,首先要了解什么是堆 堆 堆是一个数组,每个结点表示数组中的一个元素,堆可以看做是一个近似的完全二叉...

3139
来自专栏好好学java的技术栈

“365算法每日学计划”:06打卡-单向循环链表

单向循环链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。

701

扫码关注云+社区

领取腾讯云代金券