课程咨询 :186 8716 1620      qq:2066486918

昆明Java培训 > 达内新闻 > java程序-剖析ArrayList
  • java程序-剖析ArrayList

    发布:昆明Java培训      来源:达内新闻      时间:2016-09-22

  • 昆明Java培训机构的老师今天给大家探讨Java中的容器类,所谓容器,顾名思义就是容纳其他数据的,计算机课程中有一门课叫数据结构,可以粗略对应于Java中的容器类,我们不会介绍所有数据结构的内容,但会介绍Java中的主要 现,并分析其基本原理和主要实现代码。

    前几节在介绍泛型的时候,昆明Java培训机构的老师自己实现了一个简单的动态数组容器类DynaArray,本节,昆明Java培训机构的老师介绍Java中真正的动态数组容器类ArrayList。

    我们先来看它的基本用法。

    基本用法

    新建ArrayList

    ArrayList是一个泛型容器,新建ArrayList需要实例化泛型参数,比如:

    ArrayList<Integer> intList = new ArrayList<Integer>();

    ArrayList<String> strList = new ArrayList<String>();

    添加元素

    add方法添加元素到末尾

    ArrayList<Integer> intList = new ArrayList<Integer>();

    intList.add(123);

    intList.add(456);

    ArrayList<String> strList = new ArrayList<String>();

    strList.add("老马");

    strList.add("编程");

    长度方法

    判断是否为空

    public boolean isEmpty()

    获取长度

    public int size()

    访问指定位置的元素

    public E get(int index)

    如:

    ArrayList<String> strList = new ArrayList<String>();

    strList.add("老马");

    strList.add("编程");

    for(int i=0; i<strList.size(); i++){

    System.out.println(strList.get(i));

    }

    查找元素

    public int indexOf(Object o)

    如果找到,返回索引位置,否则返回-1。

    从后往前找

    public int lastIndexOf(Object o)

    是否包含指定元素

    public boolean contains(Object o)

    相同的依据是equals方法返回true。如果传入的元素为null,则找null的元素。

    删除元素

    删除指定位置的元素

    public E remove(int index)

    返回值为被删对象。

    删除指定对象

    public boolean remove(Object o)

    与indexOf一样,比较的依据的是equals方法,如果o为null,则删除值为null的元素。另外,remove只删除第一个相同的对象,也就是说,即使ArrayList中有多个与o相同的元素,也只会删除第一个。返回值为boolean类型,表示是否删除了元 。

    删除所有元素

    public void clear()

    插入元素

    在指定位置插入元素

    public void add(int index, E element)

    index为0表示插入最前面,index为ArrayList的长度表示插到最后面。

    修改元素

    修改指定位置的元素内容

    public E set(int index, E element)

    基本原理

    内部组成

    可以看出,ArrayList的基本用法是比较简单的,它的基本原理也是比较简单的,原理与昆明Java培训机构的老师在前面几节介绍的DynaArray类似,内部有一个数组elementData,一般会有一些预留的空间,有一个整数size记录实际的元素个 ,如下所示:

    private transient Object[] elementData;

    private int size;

    我们暂时可以忽略transient这个关键字。各种public方法内部操作的基本都是这个数组和这个整数,elementData会随着实际元素个数的增多而重新分配,而size则始终记录实际的元素个数。

    Add方法

    虽然基本思路是简单的,但内部代码有一些比较晦涩,我们来看下add方法的代码:

    public boolean add(E e) {

    ensureCapacityInternal(size + 1); // Increments modCount!!

    elementData[size++] = e;

    return true;

    }

    它首先调用ensureCapacityInternal确保数组容量是够的,ensureCapacityInternal的代码是:

    private void ensureCapacityInternal(int minCapacity) {

    if (elementData == EMPTY_ELEMENTDATA) {

    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    ensureExplicitCapacity(minCapacity);

    }

    它先判断数组是不是空的,如果是空的,则首次至少要分配的大小为DEFAULT_CAPACITY,DEFAULT_CAPACITY的值为10,接下来调用ensureExplicitCapacity,代码为:

    private void ensureExplicitCapacity(int minCapacity) {

    modCount++;

    // overflow-conscious code

    if (minCapacity - elementData.length > 0)

    grow(minCapacity);

    }

    modCount++是什么意思呢?modCount表示内部的修改次数,modCount++当然就是增加修改次数,为什么要记录修改次数呢?我们待会解释。

    如果需要的长度大于当前数组的长度,则调用grow方法。这段代码前面有个注释:overflow-conscious code,翻译一下,大意就是代码考虑了溢出这种情况,溢出是什么意思呢?我们解释下,假设a,b都是int,下面两行代码是不一样的:

    1 if(a>b)

    2 if(a-b>0)

    为什么呢?考虑a=Integer.MAX_VALUE, b=Integer.MIN_VALUE:

    a>b为true

    但由于溢出,a-b的结果为-1

    反之,再考虑a=Integer.MIN_VALUE, b=Integer.MAX_VALUE:

    a>b为false

    但由于溢出,a-b的结果为1。

    不过,在a, b都为正数且数值没有那么大的情况下,一般也没有溢出问题,为便于理解,在后续的分析中,我们将忽略溢出问题。

    接下来,看grow方法:

    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, ewCapacity);

    }

    排除边缘情况,长度增长的主要代码为:

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    右移一位相当于除2,所以,newCapacity相当于oldCapacity的1.5倍。

    Remove方法

    我们再来看Remove方法的代码:

    public E remove(int index) {

    rangeCheck(index);

    modCount++;

    E oldValue = elementData(index);

    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

    return oldValue;

    }

    它也增加了modCount,然后计算要移动的元素个数,从index往后的元素都往前移动一位,实际调用System.arraycopy方法移动元素。elementData[--size] = null;这行代码将size减一,同时将最后一个位置设为null,设为null后就不再引用原来对象, 如果原来对象也不再被其他对象引用,就可以被垃圾回收。

    基本原理小结

    其他方法大多是比较简单的,我们就不赘述了。总体而言,内部操作要考虑各种情况,代码有一些晦涩复杂,但接口一般都是简单直接的,这就是使用容器类的好处了,这也是计算机程序中的基本思维方式,封装复杂操作,提 简单接口。

    迭代

    foreach用法

    理解了ArrayList的基本用法和原理,接下来,我们来看一个常见的操作-迭代,比如说,循环打印ArrayList中的每个元素,ArrayList支持foreach语法,比如:

    ArrayList<Integer> intList = new ArrayList<Integer>();

    intList.add(123);

    intList.add(456);

    intList.add(789);

    for(Integer a : intList){

    System.out.println(a);

    }

    当然,这种循环也可以使用如下代码实现:

    for(int i=0; i<intList.size(); i++){

    System.out.println(intList.get(i));

    }

    不过,foreach看上去更为简洁,而且,它适用于各种容器,更为通用。

    这种foreach语法背后是怎么实现的呢?其实,编译器会将它转换为类似如下代码:

    Iterator<Integer> it = intList.iterator();

    while(it.hasNext()){

    System.out.println(it.next());

    }

    接来下,我们解释一下其中的代码。

    迭代器接口

    ArrayList实现了Iterable接口,Iterable表示可迭代,它的定义为:

    public interface Iterable<T> {

    Iterator<T> iterator();

    }

    定义很简单,就是要求实现iterator方法。iterator方法的声明为:

    public Iterator<E> iterator()

    它返回一个实现了Iterator接口的对象,Iterator接口的定义为:

    public interface Iterator<E> {

    boolean hasNext();

    E next();

    void remove();

    }

    hasNext()判断是否还有元素未访问,next()返回下一个元素,remove()删除最后返回的元素,只读访问的基本模式就类似于:

    Iterator<Integer> it = intList.iterator();

    while(it.hasNext()){

    System.out.println(it.next());

    }

    我们待会再看迭代中间要删除元素的情况。

    只要对象实现了Iterable接口,就可以使用foreach语法,编译器会转换为调用Iterable和Iterator接口的方法。

    初次见到Iterable和Iterator,可能会比较容易混淆,我们再澄清一下:

    Iterable表示对象可以被迭代,它有一个方法iterator(),返回Iterator对象,实际通过Iterator接口的方法进行遍历。

    如果对象实现了Iterable,就可以使用foreach语法。

    类可以不实现Iterable,也可以创建Iterator对象。

    ListIterator

    除了iterator(),ArrayList还提供了两个返回Iterator接口的方法:

    public ListIterator<E> listIterator()

    public ListIterator<E> listIterator(int index)

    ListIterator扩展了Iterator接口,增加了一些方法,向前遍历、添加元素、修改元素、返回索引位置等,添加的方法有:

    public interface ListIterator<E> extends Iterator<E> {

    boolean hasPrevious();

    E previous();

    int nextIndex();

    int previousIndex();

    void set(E e);

    void add(E e);

    }

    listIterator()方法返回的迭代器从0开始,而listIterator(int index)方法返回的迭代器从指定位置index开始,比如,从末尾往前遍历,代码为:

    public void reverseTraverse(List<Integer> list){

    ListIterator<Integer> it = list.listIterator(list.size());

    while(it.hasPrevious()){

    System.out.println(it.previous());

    }

    }

    迭代的陷阱

    关于迭代器,有一种常见的误用,就是在迭代的中间调用容器的删除方法,比如要删除一个整数ArrayList中所有小于100的数,直觉上,代码可以这么写:

    public void remove(ArrayList<Integer> list){

    for(Integer a : list){

    if(a<=100){

    list.remove(a);

    }

    }

    }

    但,运行时会抛出异常:

    java.util.ConcurrentModificationException

    发生了并发修改异常,为什么呢?迭代器内部会维护一些索引位置相关的数据,要求在迭代过程中,容器不能发生结构性变化,否则这些索引位置就失效了。所谓结构性变化就是添加、插入和删除元素,只是修改元素内容不算 构性变化。

    如何避免异常呢?可以使用迭代器的remove方法,如下所示:

    public static void remove(ArrayList<Integer> list){

    Iterator<Integer> it = list.iterator();

    while(it.hasNext()){

    if(it.next()<=100){

    it.remove();

    }

    }

    }

    迭代器如何知道发生了结构性变化,并抛出异常?它自己的remove方法为何又可以使用呢?我们需要看下迭代器的工作原理。

    迭代器实现的原理

    我们来看下ArrayList中iterator方法的实现,代码为:

    public Iterator<E> iterator() {

    return new Itr();

    }

    新建了一个Itr对象,Itr是一个成员内部类,实现了Iterator接口,声明为:

    private class Itr implements Iterator<E>

    它有三个实例成员变量,为:

    int cursor;      // index of next element to return

    int lastRet = -1; // index of last element returned; -1 if no such

    int expectedModCount = modCount;

    cursor表示下一个要返回的元素位置,lastRet表示最后一个返回的索引位置,expectedModCount表示期望的修改次数,初始化为外部类当前的修改次数modCount,回顾一下,成员内部类可以直接访问外部类的实例变量。

    每次发生结构性变化的时候modCount都会增加,而每次迭代器操作的时候都会检查expectedModCount是否与modCount相同,这样就能检测出结构性变化。

    我们来具体看下,它是如何实现Iterator接口中的每个方法的,先看hasNext(),代码为:

    public boolean hasNext() {

    return cursor != size;

    }

    cursor与size比较,比较直接,看next()方法:

    public E next() {

    checkForComodification();

    int i = cursor;

    if (i >= size)

    throw new NoSuchElementException();

    Object[] elementData = ArrayList.this.elementData;

    if (i >= elementData.length)

    throw new ConcurrentModificationException();

    cursor = i + 1;

    return (E) elementData[lastRet = i];

    }

    首先调用了checkForComodification,它的代码为:

    final void checkForComodification() {

    if (modCount != expectedModCount)

    throw new ConcurrentModificationException();

    }

    所以,next()前面部分主要就是在检查是否发生了结构性变化,如果没有变化,就更新cursor和lastRet的值,以保持其语义,然后返回对应的元素。

    remove的代码为:

    public void remove() {

    if (lastRet < 0)

    throw new IllegalStateException();

    checkForComodification();

    try {

    ArrayList.this.remove(lastRet);

    cursor = lastRet;

    lastRet = -1;

    expectedModCount = modCount;

    } catch (IndexOutOfBoundsException ex) {

    throw new ConcurrentModificationException();

    }

    }

    它调用了ArrayList的remove方法,但同时更新了cursor, lastRet和expectedModCount的值,所以它可以正确删除。

    不过,需要注意的是,调用remove方法前必须先调用next,比如,通过迭代器删除所有元素,直觉上,可以这么写:

    public static void removeAll(ArrayList<Integer> list){

    Iterator<Integer> it = list.iterator();

    while(it.hasNext()){

    it.remove();   

    }

    }

    实际运行,会抛出异常:

    java.lang.IllegalStateException

    正确写法是:

    public static void removeAll(ArrayList<Integer> list){

    Iterator<Integer> it = list.iterator();

    while(it.hasNext()){

    it.next();

    it.remove();

    }

    }

    当然,如果只是要删除所有元素,ArrayList有现成的方法clear()。

    listIterator()的实现使用了另一个内部类ListItr,它继承自Itr,基本思路类似,我们就不赘述了。

    迭代器的好处

    为什么要通过迭代器这种方式访问元素呢?直接使用size()/get(index)语法不也可以吗?在一些场景下,确实没有什么差别,两者都可以。不过,foreach语法更为简洁一些,更重要的是,迭代器语法更为通用,它适用于各种容器类。

    此外,迭代器表示的是一种关注点分离的思想,将数据的实际组织方式与数据的迭代遍历相分离,是一种常见的设计模式。需要访问容器元素的代码只需要一个Iterator接口的引用,不需要关注数据的实际组织方式,可以使用一致 和统一的方式进行访问。

    而提供Iterator接口的代码了解数据的组织方式,可以提供高效的实现。在ArrayList中, size/get(index)语法与迭代器性能是差不多的,但在后续介绍的其他容器中,则不一定,比如LinkedList,迭代器性能就要高很多。

    从封装的思路上讲,迭代器封装了各种数据组织方式的迭代操作,提供了简单和一致的接口。

    ArrayList实现的接口

    Java的各种容器类有一些共性的操作,这些共性以接口的方式体现,我们刚刚介绍的Iterable接口就是,此外,ArrayList还实现了三个主要的接口Collection, List和RandomAccess,我们逐个来看下。

    Collection

    Collection表示一个数据集合,数据间没有位置或顺序的概念,接口定义为:

    public interface Collection<E> extends Iterable<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 removeAll(Collection<?> c);

    boolean retainAll(Collection<?> c);

    void clear();

    boolean equals(Object o);

    int hashCode();

    }

    这些方法中,除了两个toArray方法和几个xxxAll()方法外,其他昆明Java培训机构的老师已经介绍过了。

    这几个xxxAll()方法的含义基本也是可以顾名思义的,addAll添加,removeAll删除,containsAll检查是否包含了参数容器中的所有元素,只有全包含才返回true,retainAll只保留参数容器中的元素,其他元素会进行删除。

    有一个抽象类AbstractCollection对这几个方法都提供了默认实现,实现的方式就是利用迭代器方法逐个操作,比如说,我们看removeAll方法,代码为:

    public boolean removeAll(Collection<?> c) {

    boolean modified = false;

    Iterator<?> it = iterator();

    while (it.hasNext()) {

    if (c.contains(it.next())) {

    it.remove();

    modified = true;

    }

    }

    return modified;

    }

    代码比较简单,就不解释了。ArrayList继承了AbstractList,而AbstractList又继承了AbstractCollection,ArrayList对其中一些方法进行了重写,以提供更为高效的实现,具体我们就不介绍了。

    关于toArray方法,我们待会再介绍。

    List

    List表示有顺序或位置的数据集合,它扩展了Collection,增加的主要方法有:

    boolean addAll(int index, Collection<? extends E> c);

    E get(int index);

    E set(int index, E element);

    void add(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);

    这些方法都与位置有关,容易理解,就不介绍了。

    RandomAccess

    RandomAccess的定义为:

    public interface RandomAccess {

    }

    没有定义任何代码。这有什么用呢?这种没有任何代码的接口在Java中被称之为标记接口,用于声明类的一种属性。

    这里,实现了RandomAccess接口的类表示可以随机访问,可随机访问就是具备类似数组那样的特性,数据在内存是连续存放的,根据索引值就可以直接定位到具体的元素,访问效率很高。下节昆明Java培训机构的老师会介绍LinkedList, 它就不能随机访问。

    有没有声明RandomAccess有什么关系呢?主要用于一些通用的算法代码中,它可以根据这个声明而选择效率更高的实现。比如说,Collections类中有一个方法binarySearch,在List中进行二分查找,它的实现代码就根据list是否实现了RandomAcce ss而采用不同的实现机制,如下所示:

    public static <T>

    int binarySearch(List<? extends Comparable<? super T>> list, T key) {

    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)

    return Collections.indexedBinarySearch(list, key);

    else

    return Collections.iteratorBinarySearch(list, key);

    }

    ArrayList的其他方法

    构造方法

    ArrayList还有两个构造方法

    public ArrayList(int initialCapacity)

    public ArrayList(Collection<? extends E> c)

    第一个方法以指定的大小initialCapacity初始化内部的数组大小,代码为:

    this.elementData = new Object[initialCapacity];

    在事先知道元素长度的情况下,或者,预先知道长度上限的情况下,使用这个构造方法可以避免重新分配和拷贝数组。

    第二个构造方法以一个已有的Collection构建,数据会新拷贝一份。

    与数组的相互转换

    ArrayList中有两个方法可以返回数组

    public Object[] toArray()

    public <T> T[] toArray(T[] a)

    第一个方法返回是Object数组,代码为:

    public Object[] toArray() {

    return Arrays.copyOf(elementData, size);

    }

    第二个方法返回对应类型的数组,如果参数数组长度足以容纳所有元素,就使用该数组,否则就新建一个数组,比如:

    ArrayList<Integer> intList = new ArrayList<Integer>();

    intList.add(123);

    intList.add(456);

    intList.add(789);

    Integer[] arrA = ew Integer[3];

    intList.toArray(arrA);

    Integer[] arrB = intList.toArray(new Integer[0]);

    System.out.println(Arrays.equals(arrA, arrB));

    输出为true,表示两种方式都是可以的。

    Arrays中有一个静态方法asList可以返回对应的List,如下所示:

    Integer[] a = {1,2,3};

    List<Integer> list = Arrays.asList(a);

    需要注意的是,这个方法返回的List,它的实现类并不是本节介绍的ArrayList,而是Arrays类的一个内部类,在这个内部类的实现中,内部用的的数组就是传入的数组,没有拷贝,也不会动态改变大小,所以对数组的修改也会反映到L ist中,对List调用add/remove方法会抛出异常。

    要使用ArrayList完整的方法,应该新建一个ArrayList,如下所示:

    List<Integer> list = new ArrayList<Integer>(Arrays.asList(a));

    容量大小控制

    ArrayList还提供了两个public方法,可以控制内部使用的数组大小,一个是:

    public void ensureCapacity(int minCapacity)

    它可以确保数组的大小至少为minCapacity,如果不够,会进行扩展。如果已经预知ArrayList需要比较大的容量,调用这个方法可以减少ArrayList内部分配和扩展的次数。

    另一个方法是:

    public void trimToSize()

    它会重新分配一个数组,大小刚好为实际内容的长度。调用这个方法可以节省数组占用的空间。

    ArrayList特点分析

    后续我们会介绍各种容器类和数据组织方式,之所以有各种不同的方式,是因为不同方式有不同特点,而不同特点有不同适用场合。考虑特点时,性能是其中一个很重要的部分,但性能不是一个简单的高低之分,对于一种数据 构,有的操作性能高,有的操作性能可能就比较低。

    作为程序员,就是要理解每种数据结构的特点,根据场合的不同,选择不同的数据结构。

    对于ArrayList,它的特点是:内部采用动态数组实现,这决定了:

    可以随机访问,按照索引位置进行访问效率很高,用算法描述中的术语,效率是O(1),简单说就是可以一步到位。

    除非数组已排序,否则按照内容查找元素效率比较低,具体是O(N),N为数组内容长度,也就是说,性能与数组长度成正比。

    添加元素的效率还可以,重新分配和拷贝数组的开销被平摊了,具体来说,添加N个元素的效率为O(N)。

    插入和删除元素的效率比较低,因为需要移动元素,具体为O(N)。

    小结

    本文昆明Java培训机构的老师详细介绍了ArrayList,ArrayList是日常开发中最常用的类之一。我们介绍了ArrayList的用法、基本实现原理、迭代器及其实现、Collection/List/RandomAccess接口、ArrayList与数组的相互转换,最后昆明Java培训机构 老师分析了ArrayList的特点。

    推荐文章

上一篇:昆明java培训:spring与hibernate整合事务管理的理解

下一篇:昆明达内java培训:java线程公平锁

最新开班日期  |  更多

Java--零基础全日制班

Java--零基础全日制班

开班日期:11/30

Java--零基础业余班

Java--零基础业余班

开班日期:11/30

Java--周末提升班

Java--周末提升班

开班日期:11/30

Java--零基础周末班

Java--零基础周末班

开班日期:11/30

  • 网址:http://km .java.tedu.cn      地址:昆明市官渡区春城路62号证券大厦附楼6楼
  • 课程培训电话:186 8716 1620      qq:2066486918    全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56