深入理解ArrayList

2218
发表时间:2019-11-22 14:53

什么是ArrayList?

ArrayList的实现原理其实就是数组(动态数组),ArrayList的介绍及简单使用方法


动态数组与一般数组有什么区别?

与Java中的数组相比,ArrayList的容量能动态地增长


ArrayList效率怎么样?

ArrayList不是线程安全的,所以效率比较高 ,但是只能用于单线程的环境中,那多线程呢?别急,文末会讲到


ArrayList主要继承哪些类实现了哪些接口?

ArrayList主要继承了AbstractList类,实现了List、RandomAccess、Cloneable、Serializable接口


public class ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable


RandomAccess的意思是其拥有快速访问的能力,ArrayList可以以 O(1)[^1]的时间复杂度去根据下标访问元素。由于ArrayList底层机构是数组,所以它占据了一块连续的内存空间,其长度就是数组的大小,因此它也有数组的缺点,在空间效率不高,但是也有它的有点,就是查询速度快,时间效率较快


ArrayList的常量与变量有哪些?

// 序列ID

private static final long serialVersionUID = 8683452581122892189L;


// ArrayList默认的初始容量大小

private static final int DEFAULT_CAPACITY = 10;


// 空对象数组,用于空实例的共享空数组实例

private static final Object[] EMPTY_ELEMENTDATA = {};


// 空对象数组,如果使用默认的构造函数创建,则默认对象内容是该值

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


// 存放当前数据,不参与序列化

transient Object[] elementData; // non-private to simplify nested class access


// list大小

private int size;


当集合中的元素超出数组规定的长度时,数组就会进行扩容操作,扩容操作就是ArrayList存储操作缓慢的原因,尤其是当数据量较大的时候,每次扩容消耗的时间会越来越多


ArrayList的构造方法有哪些?

一、ArrayList(int initialCapacity)

所以当我们要使用ArrayList时,可以 new ArrayList(大小)构造方法来指定集合的大小,以减少扩容的次数,提高写入效率,该构造函数的源码如下:


// 自定义初始容量的构造方法

public ArrayList(int initialCapacity) {


    if (initialCapacity > 0) {

        this.elementData = new Object[initialCapacity];

    } else if (initialCapacity == 0) {

        this.elementData = EMPTY_ELEMENTDATA;

    } else {

        // 如果初始容量小于0,则会出现 IllegalArgumentException 异常

        throw new IllegalArgumentException("Illegal Capacity: "+

                                           initialCapacity);

    }

}


这个构造函数还是比较好理解的,因为涉及到的代码也不多,而且都是一些基础的代码,相信聪明的你肯定看得懂的


二、ArrayList()

这个就更简单了,只有两行代码


// 默认的构造方法,构造一个初始容量为10的空列表

public ArrayList() {

    // elementData 初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}


三、ArrayList(Collection<? extends E> c)

// 构造一个包含指定元素的列表集合,按集合的返回顺序迭代器

// 传入参数为Collection对象

// c要将其元素放入此列表的集合

public ArrayList(Collection<? extends E> c) {

   

    // 调用toArray()方法将Collection对象转换为Object[]

    elementData = c.toArray();

   

    // 判断size的大小,如果size值为0,则会抛出NullPointerException异常

    // 如果size > 0 ,则执行以下代码

    if ((size = elementData.length) != 0) {

        // c.toArray might (incorrectly) not return Object[] (see 6260652)

        if (elementData.getClass() != Object[].class)

           

            // 执行Arrays.copyOf,把Collection对象的内容copy到elementData中

            elementData = Arrays.copyOf(elementData, size, Object[].class);

    } else {

        // replace with empty array.

        this.elementData = EMPTY_ELEMENTDATA;

    }

}


ArrayList的方法有哪些?

add()

单个add()

// 添加单个元素,添加元素之前会先检查容量,如果容量不足则调用grow方法

public boolean add(E e) {

    // 判断添加后的长度是否需要扩容

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

    // 然后在数组末尾添加当前元素,并且修改size的大小

    elementData[size++] = e;

    // 返回布尔值true

    return true;

}


add()方法中主要用到了一个新的方法——ensureCapacityInternal,来看下ensureCapacityInternal的源码:


// 判断是否需要扩容

private void ensureCapacityInternal(int minCapacity) {

    // 执行 calculateCapacity

    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}


而 ensureCapacityInternal 主要调用的是 ensureExplicitCapacity 方法和 calculateCapacity 方法,我们先看下calculateCapacity 方法


// 判断是否是第一次初始化数组

private static int calculateCapacity(Object[] elementData, int minCapacity) {

   

    // 判断当前数组是否等于空的数组

    // 注意:这里的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 并不是 EMPTY_ELEMENTDATA,不过并无太大差别,只是为了       区分何时需要扩容而已

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

       

        // 取其中最大的值作为判断本次是否需要扩容的依据,由于第一次数组是空的,所以默认要使数组扩容到10的长度

        return Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    return minCapacity;

}


点击ensureCapacityInternal中的ensureExplicitCapacity,可以看到来到了 ensureExplicitCapacity 方法,而 ensureExplicitCapacity 主要调用的就是上面所说的 grow 方法,源码如下:


// 判断扩容的方法

private void ensureExplicitCapacity(int minCapacity) {

   

    // 如果需要扩容modCount自增,这个参数是指当前列表的结构被修改的次数

    modCount++;


    // overflow-conscious code

    // 判断当前数据量是否大于数组的长度,如果是,进行扩容

    if (minCapacity - elementData.length > 0)

        // 执行扩容操作

        grow(minCapacity);

}


grow方法源码如下:


// grow扩容方法

private void grow(int minCapacity) {

    // overflow-conscious code

    // 记录扩容前的数组长度

    int oldCapacity = elementData.length;

   

    // 将原数组的长度扩大0.5倍作为扩容后数组的长度(如果扩容钱数组长度为10,那么经过扩容后的数组长度应该为15)

    // 这里涉及到异或运算,不懂的朋友可以看下这篇文章 https://blog.csdn.net/Woo_home/article/details/103146845

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

}


grow方法调用的hugeCapacity源码如下:


//如果新数组长度超过当前数组定义的最大长度时

private static int hugeCapacity(int minCapacity) {

   

    // 抛出OOM异常

    if (minCapacity < 0) // overflow

        throw new OutOfMemoryError();

   

    // 将扩容长度设置为Interger.MAX_VALUE,也就是int的最大长度

    return (minCapacity > MAX_ARRAY_SIZE) ?

        Integer.MAX_VALUE :

    MAX_ARRAY_SIZE;

}


指定add()

public void add(int index, E element) {

    //判断下标是否越界,如果是则抛出IndexOutOfBoundsException异常

    rangeCheckForAdd(index);

   

// 判断是否需要扩容,上面讲到过,这里不再解释

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

   

    // 拷贝数组,将下标后面的元素全部向后移动一位

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

                     size - index);

   

    // 将元素插入到当前下标的位置

    elementData[index] = element;

    size++;

}


rangeCheckForAdd方法


// 判断下标是否越界,如果是则抛出IndexOutOfBoundsException异常

private void rangeCheckForAdd(int index) {

    if (index > size || index < 0)

        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}


添加多个元素addAll()

// 添加多个元素

public boolean addAll(Collection<? extends E> c) {

    return addAll(this.size, c);

}


// 添加多个元素到指定下标

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

   

    // 判断下标是否越界,上面提到过

    rangeCheckForAdd(index);

   

    // 判断c的大小是否大于0

    int cSize = c.size();

   

    // 如果等于0 返回 false

    if (cSize==0)

        return false;


    checkForComodification();

   

    // 将元素插入到数组中

    parent.addAll(parentOffset + index, c);

   

    // 将修改次数赋值给 modCount

    this.modCount = parent.modCount;

   

    // size大小加一

    this.size += cSize;

    return true;

}


private void checkForComodification() {

    // 如果修改的次数不相等

    if (ArrayList.this.modCount != this.modCount)

        // 则抛出ConcurrentModificationException(并发修改)异常

        throw new ConcurrentModificationException();

}


总结:


在进行 add 操作时先判断下标是否越界,是否需要扩容,如果需要扩容,就复制数组,然后设置对应的下标元素值


扩容:默认扩容一半,如果扩容一半不够的话,就用目标的size作为扩容后的容量


get()

// 先判断下标索引

public E get(int index) {

    // 调用rangeCheck判断是否超出了Object数组长度

    rangeCheck(index);


    // 调用 elementData 方法

    return elementData(index);

}


private void rangeCheck(int index) {

    // 如果超出了Object数组的长度

    if (index >= size)

        // 则抛出 IndexOutOfBoundsException(数组下标越界)异常

        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}


// 通过下标索引找到对应的元素值,返回指定元素

E elementData(int index) {

    return (E) elementData[index];

}


set()

public E set(int index, E element) {

    // 调用rangeCheck判断是否超出范围,上面讲到过,不懂的同学往上翻翻

    rangeCheck(index);


    // 返回指定元素,上面也讲到过

    E oldValue = elementData(index);

    elementData[index] = element;

    return oldValue;

}


remove()

// 删除元素

public E remove(int index) {

    // 调用rangeCheck方法判断是否超出范围,上面讲到过

    rangeCheck(index);

   

    modCount++;

    // 位置访问操作

    E oldValue = elementData(index);


    // 计算移除元素后需要移动的元素个数

    int numMoved = size - index - 1;

    if (numMoved > 0)

        // 通过 System.arraycopy 方法将后面的元素往前移动一位

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

                         numMoved);

   

    // 最后一位赋值为null

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


    // 返回移除后元素的值

    return oldValue;

}


// 删除对象

public boolean remove(Object o) {

    // 如果对象为null

    if (o == null) {

        // 遍历整个list去匹配移除的值

        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;

}


fastRemove源码如下:


/**

  * 私有删除方法,跳过边界检查并且不返回删除的值。

  */

private void fastRemove(int index) {

    modCount++;

    // 位置访问操作

    int numMoved = size - index - 1;

    if (numMoved > 0)

        // 通过 System.arraycopy 方法将后面的元素往前移动一位

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

                         numMoved);

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

}


Iterator

// ArrayList中的迭代器

public Iterator<E> iterator() {

    // 主要返回一个Itr类

    return new Itr();

}


Itr类源码如下:


private class Itr implements Iterator<E> {

    int cursor;       // 下一个要返回的元素的索引

    int lastRet = -1; // 返回的最后一个元素的索引; -1(如果没有)

    int expectedModCount = modCount;


    Itr() {}


    // 判断是否还有下一个元素

    public boolean hasNext() {

        // 通过判断以下一个下标是否为数组大小,返回布尔值

        return cursor != size;

    }


    @SuppressWarnings("unchecked")

    // 获取下一个元素

    public E next() {

        // 调用checkForComodification方法检查修改的次数是否一致

        checkForComodification();

       

        // 定义下一个元素的下标

        int i = cursor;

       

        // 判断下标,如果下标大于ArrayList包含的元素个数

        if (i >= size)

            // 抛出 NoSuchElementException (没有这样的元素异常)异常

            throw new NoSuchElementException();

       

        // 定义elementData 为ArrayList的数组

        Object[] elementData = ArrayList.this.elementData;

       

        // 再次判断下标,如果此次判断不一致则说明数组被修改过

        if (i >= elementData.length)

            // 抛出 ConcurrentModificationException (并发修改)异常

            throw new ConcurrentModificationException();

       

        // 定义下一个元素的下标

        cursor = i + 1;

       

        // 将lastRet定义为下一个元素的下标(返回的最后一个元素的下标),然后返回下标对应的值

        return (E) elementData[lastRet = i];

    }


    // 移除当前元素

    public void remove() {

        // 如果没有元素

        if (lastRet < 0)

            // 则抛出 IllegalStateException 异常

            throw new IllegalStateException();

        // 又来了,调用 checkForComodification,上面讲到过,用于判断修改次数是否一致

        checkForComodification();


        try {

            // 调用ArrayList的remove方法

            //如果在遍历外remove会导致Itr中的expectedModCount没有修改则抛出异常

            ArrayList.this.remove(lastRet);

           

            // 定义下一个元素的下标为当前下标

            cursor = lastRet;

           

            // 定义上个遍历下标为-1

            lastRet = -1;

            expectedModCount = modCount;

        } catch (IndexOutOfBoundsException ex) {

            throw new ConcurrentModificationException();

        }

    }

}


final void checkForComodification() {

    // 判断当前Itr修改次数和ArrayList是否一致

    if (modCount != expectedModCount)

        // 不一致则抛出ConcurrentModificationException(并发修改异常)异常

        throw new ConcurrentModificationException();

}


ArrayList是线程安全的吗?

不,ArrayList不是线程安全的,而且ArrayList允许元素为null


ArrayList如何实现线程安全?

上上面说过ArrayList不是线程安全的,所以效率较高,但是只能适用于单线程,那么多线程怎么办呢?, 多线程可以使用**Collections.synchronizedList(List list) **函数返回一个线程安全的 ArrayList 集合,或者使用 concurrent 并发包下的CopyOnWriteArrayList,如下:


//使用Collections.synchronizedList(List list)方法实现线程安全

List<?> list = Collections.synchronizedList(new ArrayList<>());

————————————————

版权声明:本文为CSDN博主「Woo_home」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。

原文链接:https://blog.csdn.net/Woo_home/article/details/103177912


文章分类: 技术论坛Java
热门文章

这篇文章很长,但绝对是精华,相信我,读完以后,你会知道学历不好的解决方案,记得帮我点赞哦。先说结论,无论赞不赞同,...

Java最常用的工具类,这些就够了

1、搜索引擎1.1、秘迹搜索一款无敌有良心、无敌安全的搜索引擎,不会收集私人信息,保护私隐,没有Cookie,并且...

就在昨天,一位叫小菜的读者微信我说了上面这段话。我当时看到这条微信的第一感觉是:小菜你也太菜了吧,这都不知道为啥啊...

包含的模块:本文分为十九个模块,分别是: Java 基础、容器、多线程、反射、对象拷贝、Java Web 、异常、...

官方公众号
打造IT教学生态圈,服务好每一位IT学员
官方微博
关于沃沃
与沃合作
核心课程
14天免费学习申请
UI设计表单
姓名
QQ号
手机号
提交