深入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.
目录
相关文章
|
10天前
|
算法 Java 数据处理
从HashSet到TreeSet,Java集合框架中的Set接口及其实现类以其“不重复性”要求,彻底改变了处理唯一性数据的方式。
从HashSet到TreeSet,Java集合框架中的Set接口及其实现类以其“不重复性”要求,彻底改变了处理唯一性数据的方式。HashSet基于哈希表实现,提供高效的元素操作;TreeSet则通过红黑树实现元素的自然排序,适合需要有序访问的场景。本文通过示例代码详细介绍了两者的特性和应用场景。
30 6
|
10天前
|
存储 Java
深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。
【10月更文挑战第16天】本文深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。HashSet基于哈希表实现,添加元素时根据哈希值分布,遍历时顺序不可预测;而TreeSet利用红黑树结构,按自然顺序或自定义顺序存储元素,确保遍历时有序输出。文章还提供了示例代码,帮助读者更好地理解这两种集合类型的使用场景和内部机制。
27 3
|
10天前
|
存储 Java 数据处理
Java Set接口凭借其独特的“不重复”特性,在集合框架中占据重要地位
【10月更文挑战第16天】Java Set接口凭借其独特的“不重复”特性,在集合框架中占据重要地位。本文通过快速去重和高效查找两个案例,展示了Set如何简化数据处理流程,提升代码效率。使用HashSet可轻松实现数据去重,而contains方法则提供了快速查找的功能,彰显了Set在处理大量数据时的优势。
20 2
|
12天前
|
存储 算法 Java
Java Set因其“无重复”特性在集合框架中独树一帜
【10月更文挑战第14天】Java Set因其“无重复”特性在集合框架中独树一帜。本文深入解析Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定的数据结构(哈希表、红黑树)确保元素唯一性,并提供最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的`hashCode()`与`equals()`方法。
23 3
|
7天前
|
安全 Java 程序员
深入Java集合框架:解密List的Fail-Fast与Fail-Safe机制
本文介绍了 Java 中 List 的遍历和删除操作,重点讨论了快速失败(fail-fast)和安全失败(fail-safe)机制。通过普通 for 循环、迭代器和 foreach 循环的对比,详细解释了各种方法的优缺点及适用场景,特别是在多线程环境下的表现。最后推荐了适合高并发场景的 fail-safe 容器,如 CopyOnWriteArrayList 和 ConcurrentHashMap。
34 5
|
8天前
|
安全 Java 程序员
Java集合之战:ArrayList vs LinkedList,谁才是你的最佳选择?
本文介绍了 Java 中常用的两个集合类 ArrayList 和 LinkedList,分析了它们的底层实现、特点及适用场景。ArrayList 基于数组,适合频繁查询;LinkedList 基于链表,适合频繁增删。文章还讨论了如何实现线程安全,推荐使用 CopyOnWriteArrayList 来提升性能。希望帮助读者选择合适的数据结构,写出更高效的代码。
28 3
|
10天前
|
存储 Java 数据处理
Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。
【10月更文挑战第16天】Java Set:无序之美,不重复之魅!Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。通过 hashCode() 和 equals() 方法实现唯一性,适用于需要唯一性约束的数据处理。示例代码展示了如何使用 HashSet 添加和遍历元素,体现了 Set 的高效性和简洁性。
19 4
|
12天前
|
存储 Java 数据处理
Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。
Java Set:无序之美,不重复之魅!Set 是 Java 集合框架中的一个接口,不包含重复元素且不保证元素顺序。它通过 hashCode() 和 equals() 方法确保元素唯一性,适用于需要唯一性约束的数据处理。示例代码展示了如何使用 HashSet 实现这一特性。
16 5
|
13天前
|
Java 开发者
在Java的集合世界里,Set以其独特的特性脱颖而出,它通过“哈希魔法”和“红黑树防御”两大绝技
【10月更文挑战第13天】在Java的集合世界里,Set以其独特的特性脱颖而出。它通过“哈希魔法”和“红黑树防御”两大绝技,有效抵御重复元素的侵扰,确保集合的纯洁性和有序性。无论是“人海战术”还是“偷梁换柱”,Set都能从容应对,成为开发者手中不可或缺的利器。
29 6
|
10天前
|
Java 开发者
在Java集合世界中,Set以其独特的特性脱颖而出,专门应对重复元素
在Java集合世界中,Set以其独特的特性脱颖而出,专门应对重复元素。通过哈希表和红黑树两种模式,Set能够高效地识别并拒绝重复元素的入侵,确保集合的纯净。无论是HashSet还是TreeSet,都能在不同的场景下发挥出色的表现,成为开发者手中的利器。
22 2