李哥技术

V1

2022/02/26阅读:34主题:橙心

用动画的方式带你阅读Java源码ArrayList

大家好,我是老黑[1]

今天我们来研究研究ArrayList的源码,废话不多说。

先抛砖引玉:

  • 你是否知道ArrayList的存储原理?
  • 你是否知道ArrayList的扩容原理?
  • 你知道ArrayList什么时候扩容吗?
  • 你知道ArrayList是线程安全的吗?
  • 你知道ArrayList与LinkedList的区别吗?

(答案与ArrayList生命周期动画放在文末~)

再预览一下本文大纲:

ArrayList概述

ArrayList是Java语言中最常见的集合工具类之一,它继承AbstractList,实现了List(列表)、RandomAccess(顺序访问)、Cloneable(可克隆)、Serializable(可序列化)接口。

从它的继承与实现来看,ArrayList是一个可克隆,可序列化,可顺序访问的列表。

ArrayList的存储原理

在ArrayList中,内部拥有4个属性:

ArrayList继承关系与属性
ArrayList继承关系与属性

从上图发现,ArrayList的实现原理内部其实是一个对象数组:Object[],然后还有一个属性size用来表示链表的实际长度。

源码分析

add(E object)

add(E object)
add(E object)

add(int index, E object)

add(int index, E object)
add(int index, E object)

请问:这个方法是线程安全的吗?

我们再看一个动画演示:

所以,add(int index, E object)不是线程安全的。

remove(int index)

remove(int index)
remove(int index)

remove(Object o)

remove(Object o)
remove(Object o)

set(int index, E object)

set(int index, E object)
set(int index, E object)

修改与删除不同,修改没有类似CAS(比较并且交换)的API。

在这里多提一嘴,我们要知道,一个列表存放的到底是什么?

没错,存放的是对象的地址,而不是真正的对象,下面再来看一下动画演示如何修改的:

查询比较简单,直接根据下标获取数据即可。

get(int index)
get(int index)

迭代器

ArrayList.Itr迭代器

ArrayList的内部类Itr迭代器
ArrayList的内部类Itr迭代器

迭代器的这些方法其实都是我们经常会使用到的,hasNextnextremove等等。

Itr的next方法
Itr的next方法
Itr的remove方法
Itr的remove方法

小结:

  1. 使用迭代器后,在迭代器外部最好是不要操作列表,否则在后续使用这个迭代器时很有可能将抛出异常;
  2. 使用next之前一般都会使用hasNext进行判断;
  3. 使用remove之前必须使用next方法;
  4. 使用remove方法后迭代器内部的expectedModCount会同步更新,所以在迭代器内部remove是允许的;
  5. remove方法不允许连续使用两次,因为在第一次使用后lastRet就会置为-1,下次remove时判断lastRet<0则抛出IllegalStateException。

ArrayList.ListItr迭代器

ListItr是继承了Itr的,所以Itr的所有功能在ListItr都有。

ListItr与Itr的区别是:Itr只能从前往后迭代,并且是不允许查找上一个数据;而ListItr则允许从前往后和从后往前两种迭代方向,同时也允许查找上一个数据,并且也允许从中间某一个位置开始遍历。

遍历方式

准备

List<Object> list = new ArrayList();
list.add("1");
list.add(2);
list.add("3");
list.add(4);

for循环

for (int i = 0; i < list.size(); i++) {
    Object obj = list.get(i);
    System.out.println(obj);
 
    // remove
    // 不推荐,原因:内部会进行数组块移动,性能低
    // list.remove(obj);
}

增强for循环:foreach

// foreach遍历的本质是迭代器遍历
for (Object obj : list) {
    System.out.println(obj);
 
    // remove
    // 反对,原因:如果在里面remove元素的话,会抛ConcurrentModificationException异常
    // list.remove(obj);
}

老黑在这里额外提一嘴,foreach遍历的本质是迭代器遍历,所以,在迭代器遍历的时候,使用list.remove方法,会修改list内部的modCount,而迭代器内部的expectedModCount并没有改变,所以在下一次迭代的时候,迭代器内部检查将会抛出ConcurrentModificationException异常。

迭代器遍历(推荐)

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    Object obj = iterator.next();
    System.out.println(obj);
 
    // remove
    // 推荐,不管是遍历还是remove都推荐
    iterator.remove();
}

lambda表达式遍历

list.forEach(item -> {
    System.out.println(item);
 
    // 遍历的话,推荐
    // remove的话,不推荐,remove会抛
    // ConcurrentModificationException异常
});

Stream遍历

list.stream().forEach(item -> {
    System.out.println(item);
 
    // 遍历的话,推荐
    // remove的话,不管是串行流还是并行流都不推荐,remove会抛ConcurrentModificationException异常。
});

对于Stream,后面我们单独出一篇文章来了解它的原理。

List的生命周期

今天我们讲解暂且告一段落了,感谢大家的阅读。

下一篇我们就来研究LinkedList的原理实现。

周末肝文不易,求赏个在看

参考资料

[1]

老黑: https://www.yuque.com/javahome/java/guide

分类:

后端

标签:

Java

作者介绍

李哥技术
V1