• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

ArrayList必知必会

技术杂谈 勤劳的小蚂蚁 4个月前 (12-28) 96次浏览 已收录 0个评论 扫描二维码

ArrayList一些说法

顾名思义,以数组实现。节约空间,但数组有容量限制。超出限制时会增加50%容量,用System.arraycopy()复制到新的数组。因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。 

按数组下标访问元素-get(i)、set(i, e) 的性能很高,这是数组的基本优势。 如果按下标插入元素、删除元素-add(i,e)、 remove(i)、remove(e),则要用System.arraycopy()来复制移动部分受影响的元素,性能就变差了。 越是前面的元素,修改时要移动的元素越多。直接在数组末尾加入元素-常用的add(e),删除最后一个元素则无影响。

我们先通过一段简单的代码来看下内存变化。

  1. List<String> list =newArrayList<>();

  2. list.add("语文: 99");

  3. list.add("数学: 98");

  4. list.add("英语: 100");

  5. list.remove(0);

内存变化图: 

 其中,add操作可以理解为直接将数组的内容置位,remove操作可以理解为删除index为0的节点,并将后面元素移到0处。 

ArrayList的类声明如下:

  1. publicclassArrayList<E>extendsAbstractList<E>

  2.        implementsList<E>,RandomAccess,Cloneable, java.io.Serializable

  3. {

  4.    //...

  5. }

实现了List接口,说明ArrayList是List的一个实现类,实现了RandomAccess(RandomAccess接口说明)说明ArrayList支持随机访问。

ArrayList初始化

ArrayList重载了多个构造方法,我们挑两个介绍一下。

  1. /**

  2.     * 默认初始化容量

  3.     */

  4.    privatestaticfinalint DEFAULT_CAPACITY =10;

  5.    /**

  6.     * ArrayList共享的空数组,这样节省内存

  7.     */

  8.    privatestaticfinalObject[] EMPTY_ELEMENTDATA ={};

  9.    /**

  10.     * 如果使用默认size时,共享的空数组

  11.     * 第一个元素增加时会重新初始化elementData

  12.     */

  13.    privatestaticfinalObject[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA ={};

  14.    /**

  15.     * 真正存储的数组

  16.     */

  17.    transientObject[] elementData;// non-private to simplify nested class access

  18.    /**

  19.     * List的元素数量

  20.     */

  21.    privateint size;

  22.     /**

  23.     * 带有初始化容量的构造方法

  24.     */

  25.    publicArrayList(int initialCapacity){

  26.        if(initialCapacity >0){

  27.            this.elementData =newObject[initialCapacity];

  28.        }elseif(initialCapacity ==0){

  29.            this.elementData = EMPTY_ELEMENTDATA;

  30.        }else{

  31.            thrownewIllegalArgumentException("Illegal Capacity: "+

  32.                                               initialCapacity);

  33.        }

  34.    }

  35.     /**

  36.     * 使用默认容量的构造方法,在放入第一个元素时进行初始化

  37.     */

  38.    publicArrayList(){

  39.        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

  40.    }

ArrayList的add方法

当然我们向ArrayList放入元素时,会使用add方法,这个方法会把元素放在队尾,源码如下:

  1. publicboolean add(E e){

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

  3.        elementData[size++]= e;

  4.        returntrue;

  5.    }

代码表面很简单,但是有一个稍微复杂的ensureCapacityInternal方法,可以看出ensureCapacityInternal方法才是add的核心,这段代码就是用来扩容的,代码如下:

  1. // 计算最小扩容的大小

  2.    privatestaticint calculateCapacity(Object[] elementData,int minCapacity){

  3.        //如果List初始化之后还未进行过插入操作,返回默认容量和扩容容量的最大的值

  4.        if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){

  5.            returnMath.max(DEFAULT_CAPACITY, minCapacity);

  6.        }

  7.        return minCapacity;

  8.    }

  9.    // 扩容操作入口

  10.    privatevoid ensureCapacityInternal(int minCapacity){

  11.        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

  12.    }

  13.    // 真正的扩容操作

  14.    privatevoid ensureExplicitCapacity(int minCapacity){

  15.        // 修改次数+1

  16.        modCount++;

  17.        // 如果扩容的容量大于已经存在的容量,则才进行扩容

  18.        if(minCapacity - elementData.length >0)

  19.            grow(minCapacity);

  20.    }

  21.    privatevoid grow(int minCapacity){

  22.        // overflow-conscious code

  23.        int oldCapacity = elementData.length;

  24.        // 扩展为原来的1.5倍

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

  26.        // 如果扩为1.5倍还不满足需求,直接扩为需求值

  27.        if(newCapacity - minCapacity <0)

  28.            newCapacity = minCapacity;

  29.        if(newCapacity - MAX_ARRAY_SIZE >0)

  30.            newCapacity = hugeCapacity(minCapacity);

  31.        // minCapacity is usually close to size, so this is a win:

  32.        elementData =Arrays.copyOf(elementData, newCapacity);

  33.    }

ArrayList的get和set方法

get和set操作比较简单了,就是对下标对应的元素进行set和get操作。

  1. public E get(int index){

  2.        rangeCheck(index);

  3.        return elementData(index);

  4.    }

  5.    public E set(int index, E element){

  6.        rangeCheck(index);

  7.        E oldValue = elementData(index);

  8.        elementData[index]= element;

  9.        return oldValue;

  10.    }

在这两个方法的最前面会校验一下传入的下标(index)是否合法,如果不再合法的范围内会抛出异常IndexOutOfBoundsException。

  1. privatevoid rangeCheck(int index){

  2.        if(index >= size)

  3.            thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));

  4.    }

remove方法

最后介绍一下remove方法:

  1. public E remove(int index){

  2.        //检测下标值(index)的合法性

  3.        rangeCheck(index);

  4.        modCount++;

  5.        E oldValue = elementData(index);

  6.        int numMoved = size - index -1;

  7.        //如果remove的不是最后一个元素,把后面的往前移动

  8.        if(numMoved >0)

  9.            System.arraycopy(elementData, index+1, elementData, index,

  10.                             numMoved);

  11.        //下标对应的值赋值为null,以便于GC可以回收这个对象占用的内存

  12.        elementData[--size]=null;// clear to let GC do its work

  13.        return oldValue;

  14.    }

ArrayList不是线程安全的

最后说明一下ArrayList不是线程安全的,如果要做到线程安全,需要我们自己对ArrayList进行加锁操作,或者使用锁或者使用synchronized,另外还可以用Collections提供的synchronizedList()进行操作,实际上synchronizedList()方法就是使用了synchronized进行并发控制的,只是对我们开发者来说使用起来更方便了。


丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:ArrayList必知必会
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00