ArrayList详解

ArrayList摘要

ArrayList也应该是我们常用的容器之一了。它的主要结构就是数组,只不过它相较普通数组可以动态扩容,一般的放置单个元素的容器首选ArrayList。

ArrayList继承体系

ArrayList继承了AbstractList类,实现了List、RandomAccess、Cloneable、Serializable接口。RandomAccess是一个标记接口,里面没有任何东西,表明可以随机访问。继承体系图如下所示。

ArrayList数据结构

ArrayList就是一个数组列表,当我们装基本数据类型例如int、long等时,需要存储他们对应的包装类型。它的底层主要实现的是数组Object[] elementData。

与LinkedList类似,但与其相比,它的查找和访问元素速度非常快,新增和删除比较慢。主要是因为ArrayList按照数组形式存放数据,可以根据下标随机使用O(1)复杂度访问到数据,但新增和删除元素时可能需要移动大量的元素;而LinkedList是通过链表一个接着一个进行连接的,物理内存上无序,所以不能通过下标随机访问,只能挨个遍历,但新增和删除元素只需要变更链表指针即可,效率较高。下图依次是数组和链表的结构以及数组和链表增删元素的过程图(当然LinkedList是双向链表,原理都差不多,详细的操作流程请查看数据结构相关章节)。

由于内部的方法定义都没进行线程安全性保障(例如添加synchronized),所以ArrayList是线程不安全的类。但为何ArrayList还是大量的使用呢?因为我们一般使用ArrayList都是用于查询,若是频繁增删则可以使用LinkedList,若是线程安全可以使用Vector(不建议使用,Oracle已将其抛弃,替换使用的是CopyOnWriteArrayList),而开发中使用最多的还是ArrayList。

这里插入一块非常有趣的点,而且面试中或许也可能被问到,回答的不好的话面试官会认为你没有认真实践过。上面说了,ArrayList新增和删除可能会移动大量元素,效率可能较低,但也仅仅是可能,真实情况是什么样的呢?

当我们随机连续插入元素时,例如插入2000条,ArrayList快于LinkedList;而插入20W条时,ArrayList明显快于LinkedList。

按照指定位置插入时,若是位置靠前,LinkedList一般快于ArrayList,毕竟ArrayList需要挨个向后复制;而若是位置靠近中后,那ArrayList速度明显快于LinkedList。

当我们连续往后追加元素时,数据量小时ArrayList需要不断扩容,LinkedList只是每次需要new一个Node;数据量大时,ArrayList每次扩容的量很大,不需要经常扩容,但LinkedList每次添加都需要new一个Node;所以,基本上数据量小时,LinkedList可能也快不了多少,但数据量大时ArrayList明显加快。

连续删除时,若删除靠前,LinkedList明显快于ArrayList,毕竟ArrayList需要不断移动元素;而删除靠后,ArrayList快于LinkedList;删除位置随机,ArrayList也是快于LinkedList。

综上所述,并不是LinkedList插入删除就比ArrayList块,需要查看插入删除的位置以及数据量的大小。最重要的,需要我们进行实际的演练。

下面举个例子,插入100W条数据。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void addTest(List<String> list) {
        System.out.println(list.getClass().getName());
        long startTime = System.currentTimeMillis();
        System.out.println("开始时间:" + startTime);
        for (int i = 0; i < 1000000; i++) {
            list.add(String.valueOf(i));
        }
        long endTime = System.currentTimeMillis();
        System.out.println("结束时间:" + endTime);
        System.out.println("总耗时:" + (endTime - startTime));
    }

    public static void main(String[] args) {
        List<String> a = new ArrayList<>();
        List<String> b = new LinkedList<>();
        addTest(a);
        addTest(b);
//        java.util.ArrayList
//        开始时间:1603190400247
//        结束时间:1603190400438
//        总耗时:191
//        java.util.LinkedList
//        开始时间:1603190400439
//        结束时间:1603190402687
//        总耗时:2248
    }
}

ArrayList扩容机制

ArrayList虽然是数组实现的,但其可以动态扩容,因此,不需要管理ArrayList容量,但若定义数据量太大,超出内存限制会报内存溢出异常的。

ArrayList可以通过构造函数声明数据量大小。若使用的无参构造函数,底层Object[] elementData默认赋值为Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}空数组,只有真正实行add添加元素时,才分配默认容量为10。

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

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

那么,当ArrayList容量达到定义的上限时,怎么进行动态扩容呢?其实方式很简单,就是将数组容量扩展到原来的1.5倍。首先声明一个新数组,为旧数组容量的1.5倍,然后将旧数组的值挨个复制到新数组的前面,然后将ArrayList引用引向新数组。下图展示了过程。

如果构造方法中传递了参数值,初始值大小就是传入的值,若没有传入,默认初始值就是10。

private static final int DEFAULT_CAPACITY = 10;

JDK1.7前初始化时调用this(10)直接初始化容量为10,而1.7之后,默认使用了空数组,只有真正add后才初始化容量为10。

ArrayList重要部分源码分析

看一下add方法,这是ArrayList中使用最多的方法了,按照下标把元素添加到指定位置。

public void add(int index, E element) {
    rangeCheckForAdd(index); // 检查index是否越界

    ensureCapacityInternal(size + 1);  // 判断数组需不需要扩容
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index); // 取插入位置后的元素,往后依次复制
    elementData[index] = element; // 给数组元素下标为index的元素赋值
    size++;
}

ArrayList线程安全性

ArrayList是线程不安全的,内部的方法都没有类似加锁的机制。ArrayList也允许元素为null。如何实现ArrayList的线程安全性呢?主要有下列两种方式。

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

List<String> list2 = new CopyOnWriteArrayList<>();


end
  • 作者:JJ(联系作者)
  • 发表时间:2021-02-16 23:42
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 转载声明:如果是转载博主转载的文章,请附上原文链接
  • 公众号转载:请在文末添加作者公众号二维码(公众号二维码见右边,欢迎关注)
  • 评论