526互联

20230308 java.util.ArrayList

发布时间 2023-06-19 14:10:40作者: 流星<。)#)))≦

简介

java.util.ArrayList

List 接口的可调整大小的数组实现。

源码中对数组的操作非常精彩，值得学习

数组一旦初始化长度就不可以发生改变

数组结构特点

  • 增删慢：每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。

  • 查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素。

继承关系

  • Serializable：序列化

  • Cloneable：克隆

    • 实现了 clone 方法 java.util.ArrayList#clone
    • 实现是 浅拷贝，如果元素是引用类型，拷贝的是引用

  • RandomAccess：随机访问，表明支持快速（通常为恒定时间）随机访问

  • AbstractList：List 接口的随机访问骨干实现

  • AbstractCollection：Collection 接口的骨架实现

RandomAccess

表明支持快速（通常为恒定时间）随机访问

Java 中的遍历会因为随机/顺序访问受到影响

// 创建List集合
List<String> list = new ArrayList<>();
// List<String> list = new LinkedList<>();

int size = 100000;


// 添加10W条数据
for (int i = 0; i < size; i++) {
    list.add(i + "a");
}


System.out.println("----通过索引(随机访问:)----");
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
    // 仅仅为了演示取出数据的时间,因此不对取出的数据进行打印
    list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("随机访问: " + (endTime - startTime));


System.out.println("----通过迭代器(顺序访问:)----");
startTime = System.currentTimeMillis();
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    // 仅仅为了演示取出数据的时间,因此不对取出的数据进行打印
    it.next();
}
endTime = System.currentTimeMillis();
System.out.println("顺序访问: " + (endTime - startTime));


System.out.println("----通过增强for循环(顺序访问:)----");
startTime = System.currentTimeMillis();
for (String s : list) {

}
endTime = System.currentTimeMillis();
System.out.println("顺序访问: " + (endTime - startTime));

增强for循环是顺序访问，反编译后可以看到class文件中使用的是迭代器

String var9;
for(Iterator var8 = list.iterator(); var8.hasNext(); var9 = (String)var8.next()) {
}

测试结论：

  • while和for在速度上有一些差异

  • LinkedList 在随机访问时，速度下降很明显，原因是每次获取都在链表上遍历

    • 参考 java.util.LinkedList#get

  • ArrayList 在顺序访问时，速度下降不明显

大数据量时的遍历方法应该判断是否实现了 RandomAccess 方法

public void forEach(List<?> list) {
    if (list instanceof RandomAccess) {
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    } else {
        for (Object o : list) {
            System.out.println(o);
        }
    }
}

方法清单

构造方法

  • ArrayList()

  • ArrayList(int initialCapacity)

    • 可以指定底层数组初始大小

  • ArrayList(Collection<? extends E> c)

public 方法

  • add、addAll

  • clear

  • clone、equals、toString

  • contains、containsAll

  • ensureCapacity

    • 确保最小容量，不够时会触发扩容

  • forEach

  • get

  • indexOf、lastIndexOf

  • isEmpty

  • iterator、listIterator

  • parallelStream、stream、spliterator

  • remove、removeAll、removeIf

    • removeIf 中对 BitSet 的用法非常有用

    • 几种remove的方法实现都不相同，且没有共同复用的方法，源码值得一读

  • replaceAll

    • 替换

  • retainAll

    • 保留入参集合中相同的元素

  • set

  • size

  • sort

  • subList

    • 子列表内数据和父列表是同一份

  • toArray

    • 参数为数组的重载方法比较特别，会根据传入的数组大小有不同表现

      • 如果入参是数组容量大于List，会将List内容拷贝到数组中，且数组的第size个元素被修改为null

      • 如果入参是数组容量小于List，会返回一个新的数组，内容、大小和List相同

  • trimToSize

    • 将底层数组的大小缩小为列表的当前大小（size）

源码分析

默认容量

  • 默认10

  • 构造器实现源码

  • EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA

    • DEFAULTCAPACITY_EMPTY_ELEMENTDATA 用于扩容前判断

  • 频繁扩容会导致性能下降，可以通过构造器提前设定好初始容量

扩容机制

  • 扩容方法 grow

  • 每次扩容原大小的1.5倍，需要创建新的数组

  • 扩容后不会缩容

  • 删除元素时可能会发生元素在数组上的拷贝，但不会创建新的数组

  • 扩容时，原数组元素个数小于10时，扩大到10，否则扩大到原大小的1.5倍

    • 如果从大小0开始扩容，底层数组大小应该是 0、10、15、22、33 ...

迭代器

  • java.util.ArrayList.Itr
  • 代码中的校验，如果不过会抛出并发修改异常 ConcurrentModificationException
  • 如果在遍历期间需要删除元素，调用迭代器的 remove 方法（不是List的）可以避免并发修改异常
  • 如果使用List.remove方法删除的是倒数第二个元素，不会抛出并发修改异常，但这只是代码实现上的巧合
ArrayList<String> list = ListUtil.toList("a", "b", "c", "d", "e");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String next = iterator.next();
    // 如果删除的是倒数第二个元素，巧合地，表现正常
    // 否则会抛出异常
    if (next.equals("d")) {
        list.remove(next);  // 错误做法
        // iterator.remove();  // 正确做法
    }
}
System.out.println(list);
}

并发修改异常

  • iterator 方法返回新建的 Itr 对象时，使用 modCount 初始化了成员变量 expectedModCount

  • hasNext 方法判断 cursor 和 size 的大小，正常情况下，随着 cursor 的递增，最终会与 size 相等，但是中间如果调用了 ArrayList 的 add 或 remove 方法，size 会被改变，导致 hasNext 判断错误

  • next 方法，刚进入方法内就会校验 modCount 和 expectedModCount 是否相等，如果不相等，会抛出异常，ArrayList 的 add 或 remove 方法会增加 modCount ，但是expectedModCount 的值没有改变，还是创建Itr 对象时的值，所以 next 校验不通过

  • 使用 Itr.remove 方法会设置 expectedModCount 和 cursor ，所以可以通过校验

和 LinkedList 对比

  • 本质区别：ArrayList 内部使用的动态数组来存储元素，LinkedList 内部使用的双向链表来存储元素

  • 通过索引随机访问元素，ArrayList 快于 LinkedList ，因为 LinkedList 需要遍历，而 ArrayList 根据下标计算无需遍历

  • 顺序遍历，ArrayList 因为是数组，所以也不慢

  • add 方法，如果是在最后添加，ArrayList 可能需要扩容，而 LinkedList 因为是双向链表，所以很简单；但是如果是在指定索引添加，LinkedList 需要遍历元素，会有时间消耗

  • remove 方法，与 add 方法同理

线程安全问题

  • ArrayList 不是线程安全的

  • 线程安全：

    • java.util.Vector

    • Collections.synchronizedList(list)

    • CopyOnWriteArrayList ：读写分离

参考资料