深入Java集合系列之一:ArrayList

简介:

前言

ArrayList也叫数组列表,底层使用的数组实现的,严格来说是动态数组。为了简化,我将从以下几个方面对ArrayList进行分析

常用操作的源码分析
使用场景与小结

ArrayList工作原理

ArrayList工作原理其实很简单,底层是动态数组,每次创建一个ArrayList实例时会分配一个初始容量(如果指定了初始容量的话),以add方法为例,如果没有指定初始容量,当执行add方法,先判断当前数组是否为空,如果为空则给保存对象的数组分配一个最小容量,这里为10。当添加大容量元素额时候,会先增加数组的大小,以提高添加的效率。

把ArrayList理解为一个数组就好了

源码分析

由于ArrayList方法较多,对源码的分析不能一一到位,所以选取了我们平时最常用的add、get和remove方法来分析。

add方法

add方法重载了多个实现,包括add(E e)和add(int index,E e),由于没有指定插入的位置,每次插入操作会把元素放到数组的末尾,而这个过程只需要保证容量够用就行,先来看看add(E e)方法:

public boolean add(E e) {
    //保证数组的容量始终够用
    ensureCapacityInternal(size + 1);
    //size是elementData数组中元组的个数,初始为0
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    //如果数组没有元素,给数组一个默认大小,会选择实例化时的值与默认大小中较大值
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //保证容量够用
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    //modCount是数组发生size更改的次数
    modCount++;
    // 如果数组长度小于默认的容量10,则调用扩大数组大小的方法
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

下面看看add(int index,E e):

public void add(int index, E element) {
    //判断index的值是否合法,如果大于size或者小于0则将抛出异常
    rangeCheckForAdd(index);
    //保证容量够用,并修改modCount的值
    ensureCapacityInternal(size + 1); 
    //从第index位置开始,将元素往后移动一个位置
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //把要插入的元素e放在第index位置
    elementData[index] = element;
    //数组元素的个数增加1
    size++;
}

get方法

get方法最简单,首先判断该位置是否合法,如果合法则直接返回该位置的元素

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

remove方法

由于删除操作会改变size,所以每次删除都需要把元素向前移动一个位置,然后把原来最后一个位置的元素设置为null,一次删除操作完成。下面看看源码:

public E remove(int index) {
    //判断index是否合法
    rangeCheck(index);
    //remove操作会改变size,所以modCount加1
    modCount++;
    //保存待删除位置的元素
    E oldValue = elementData(index);
    //要移动的元素个数
    int numMoved = size - index - 1;
    //如果index不是最后一个元素,则从第index+1到最后一个位置,依次向前移动一个位置
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //元素的size减少1,并把原来末尾位置元素的值设置为null
    elementData[--size] = null; 
    //返回index位置的值
    return oldValue;
}

可以注意到源码调用了System.arraycopy方法,该方法是native的,即该代码是其他语言编写,但Java允许与其进行交互(详情请搜索JNI),那么该方法是如何让实现的呢?

//add方法的System.arraycopy()
//把从第i位置的元素开始到最后一个元素,都往后移动一个位置
for(int j = size - 1; j > i; j--){
    elements[j] = elements[j-1];
}
//把第i位置的值改为e
elements[i] = e;

//remove方法的System.arraycopy()方法
//把从第i位置到最后一个位置,都向前移动一个位置
for (int j = i; j < size - 1; j++) {
    elements[j] = elements[j + 1];
}
//把数组的元素个数减少1
elements[--size] = null;

ArrayList小结

ArrayList是基于数组实现的,是一个动态数组,其容量能够自动增长 ArrayList不是线程安全的,只能用在单线程环境下,多线程环境需要使用Collections同步方法。Collections.synchronizedList(List l)返回一个线程安全的ArrayList。如果是读写比例比较大的话,则可以考虑CopyOnwriteArrayList。

  1. 默认容量是10
  2. ArrayList每次增加元素的时候,都需要调用ensureCapacity方法来确保足够的容量。当容量不足的时候,就设置新的容量为旧的的容量的1.5倍加1,如果设置的容量仍然不够,那么直接设置为传入的参数,而后用Arrays.copyOf方法将元素拷贝到新的数组。建议:在能够实现确定元素数量的情况下使用ArrayList,否则使用LinkedList。
  3. Arrays.copy()方法在方法的内部又创建了一个长度等长的数组,调用System.arraycopy方法完成新数组元素的复制。该方法的实际上调用native方法中C的memmove函数,在复制大数组的时候强烈建议使用该方法进行数组的复制。效率高。
  4. ArrayList是基于数组实现的,支持随机访问,查找效率高,但是插入删除效率低。
  5. ArrayList一般应用于查询较多但插入以及删除较少情况,如果插入以及从删除较多则建议使用LinkedList.
目录
相关文章
|
9天前
|
存储 Java 容器
Java一分钟之-高级集合框架:LinkedList与TreeSet
【5月更文挑战第17天】这篇博客对比了Java集合框架中的LinkedList和TreeSet。LinkedList是双向链表,适合中间插入删除,但遍历效率低且占用空间大;TreeSet基于红黑树,保证元素有序且不重复,插入删除速度较LinkedList慢但查找快。选择时需根据操作需求和性能考虑。
17 2
|
5天前
|
存储 Java 容器
Java一分钟之-高级集合框架:LinkedList与TreeSet
【5月更文挑战第21天】本文对比了Java集合框架中的LinkedList和TreeSet。LinkedList是双向链表,实现List接口,适合中间插入删除,但遍历效率低;TreeSet基于红黑树,实现Set接口,保证元素有序且无重复,插入删除速度较LinkedList慢,但查找排序快。选择时应根据具体需求考虑操作频率和排序需求。
17 1
|
9天前
|
存储 Java 索引
Java ArrayList
5月更文挑战第11天
|
11天前
|
存储 安全 算法
【常见集合】Java 常见集合重点解析
【常见集合】Java 常见集合重点解析
25 0
|
1天前
|
存储 算法 Java
Java集合类深度解析与实践应用
Java集合类深度解析与实践应用
|
2天前
|
Java 程序员
JAVA集合框架详解与实战
这篇文档介绍了Java集合框架,包括Collection、List、Set和Queue接口及其常用实现类。List允许重复元素,如ArrayList和LinkedList;Set不允许重复,如HashSet和TreeSet;Queue支持队列操作,如LinkedList。文章通过代码示例展示了这些接口的使用方法,强调了集合框架在实际开发中的重要性及选择合适集合类型以优化代码的必要性。
|
2天前
|
存储 安全 Java
java面试基础 -- ArrayList 和 LinkedList有什么区别, ArrayList和Vector呢?
java面试基础 -- ArrayList 和 LinkedList有什么区别, ArrayList和Vector呢?
8 0
|
3天前
|
存储 Java
【JAVA学习之路 | 进阶篇】ArrayList,Vector,LinkedList内存解析
【JAVA学习之路 | 进阶篇】ArrayList,Vector,LinkedList内存解析
|
3天前
|
存储 Java
【JAVA学习之路 | 进阶篇】集合框架概述
【JAVA学习之路 | 进阶篇】集合框架概述
|
7天前
|
安全 Java 容器
Java一分钟之-并发编程:线程安全的集合类
【5月更文挑战第19天】Java提供线程安全集合类以解决并发环境中的数据一致性问题。例如,Vector是线程安全但效率低;可以使用Collections.synchronizedXxx将ArrayList或HashMap同步;ConcurrentHashMap是高效线程安全的映射;CopyOnWriteArrayList和CopyOnWriteArraySet适合读多写少场景;LinkedBlockingQueue是生产者-消费者模型中的线程安全队列。注意,过度同步可能影响性能,应尽量减少共享状态并利用并发工具类。
21 2