开发者

Java集合源码ArrayList的可视化操作过程示例详解

目录
  • 1. 底层数据结构
    • 1.1. ArrayList的特性
    • 1.2. 如何设计的数据结构
  • 2. 元素插入(增)
    • 2.1. 在数组末尾插入
    • 2.2. 指定索引下标插入
    • 2.3. ensureCapacityInternal 与 grow 扩容流程
    • 2.4. 扩容时才对modCount 自增合理吗?
    • 2.5. 允许null和可重复插入?
  • 3. 修改元素(改)
    • 4. 移除元素(删)
      • 4.1. 指定索引删除
      • 4.2. 按照对象值删除
    • 5. 获取和检索元素(查)
      • 5.1. 获取元素
      • 5.2. 检索元素
      • 1) 判断是否包含某个元素
      • 2) 返回元素首次出现的索引
      • 3) 返回元素最后一次出现的索引
    • 6. ArrayList 的迭代器(Iterator)
      • 6.1. 什么是迭代器?
      • 6.2. iterator迭代器
      • 1) Itr 内部类的核心源码(简化版):
      • 2) modCount 与并发修改检查(fail-fast)
      • 3) 示例代码
      • 6.3. ListIterator更强大的双向迭代器
      • 1) 增强版迭代器简述
      • 2) 示例代码
      • 6.4. 时间复杂度
      • 6.5. 注意事项
    • 7. 线程安全问题
      • 解决安全问题的一些方法
    • 8. 时间复杂度汇总
      • 9. 总结

        关于ArrayList的元素插入、检索、修改、删除、扩容等可视化操作过程

        还有关于ArrayList的迭代器、线程安全和时间复杂度

        1. 底层数据结构

        基于动态数组实现,内部维护一个Object[]数组。本质是数组数据结构,底层通过拷贝扩容使得数组具备了动态增大的特性。

        数组所具备的一些特性ArrayList也同样具备,比如、插入元素的有序性、访问元素的地址计算等。ArrayList与普通数组的本质区别就在于它的动态扩容特性。

        集合内可以保存什么类型元素?保存的是什么? 这点必须明确知道集合必须保存引用类型的元素,对于基本类型是无法保存的,比如、int、long类型,但可以保持对应的基本类型的封装类,比如,IntegerLong。集合内保存的是对象的引用,而非对象本身。

        1.1. ArrayList的特性

        有底层数据结构所决定的特性

        • 插入元素的有序性,而非排序,不会自动根据值排序;

        • 元素访问:通过数组“首地址+下标”来计算元素的存储地址,再通过元素地址直接访问,时间复杂度都是O(1);

        • 数组一但申请空间就确定不可变,所以ArrayList需要在添加元素操作时,实现自动扩容

        1.2. 如何设计的数据结构

        以下是ArrayList类结构与字段

        public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, Serializable {
            private static final long serialVersionUID = 8683452581122892189L;
            /** 默认初始容量 */ 
            private static final int DEFAULT_CAPACIandroidTY = 10;
            /** 空实例数组(无延迟扩容) */
            private static final Object[] EMPTY_ELEMENTDATA = {};
            /** 默认构造后首次扩容使用的空数组 */
            private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
            /** 阈值:最大数组大小 */
            private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
            /** 真正存储元素的数组;构造时或赋予 EMPTY_* 共享数组 */
            transient Object[] elementData;
            /** 当前元素个数 */
            private int size;
            /** 用于 Fail-Fast 的修改计数器 */
            protected transient int modCount;
            // …
        }

        真正存储元素的成员变量Object[] elementData和保存数组大小的size,其它字段多半服务于动态扩容

        Java集合源码ArrayList的可视化操作过程示例详解

        MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 为什么减8?因为数组头需要占用一些空间,8位刚好一个字节,故最小减8,使得ArrayList尽可能存储更多数据,但正常开发不可能保存这么大数据集合,Integer.MAX_VALUE可以保持十亿级了,你减个1024都没问题。

        modCount用于记录扩容次数,在迭代器中若存在并发修改,则快速失效抛出异常。

        我们从本质去学习技术:集合的作用是什么?

        集合的作用是将数据以特定结构存储在内存中,并且方便开发者进行操作

        • 存储:开辟内存空间,写入数据;在Java语言中无需开发者手动申请内存空间,只需要关注数据写入即可;

        • 操作:无非就是增删查改,只不过现在操作的是内存中的数据罢了。

        2. 元素插入(增)

        方法分类

        ArrayList 的 add 方法有两个重载版本,对应不同的用法:

        • add(E e) —— 在数组末尾插入

        • add(int index, E element) —— 在指定索引下标插入

        2.1. 在数组末尾插入

        使用方法 add(E e),以下是jdk8的源码

        public boolean add(E e) {
            ensureCapacityInternal(size + 1);
            elementData[size++] = e;
            return true;
        }

        插入数据的过程

        • 调用 ensureCapacityInternal 确保数组足够大;

        • 将元素写入 elementData[size]

        • size++ 并返回。

        可视化感受下:无参构造创建ArrayList集合,然后插入五个元素,首次add需要扩容数组为10(详细的扩容流程看后面章节),效果如图

        Java集合源码ArrayList的可视化操作过程示例详解

        2.2. 指定索引下标插入

        使用方法: add(int index, E element)

        public void add(int index, E element) {
            rangeCheckForAdd(index);
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }

        插入数据的过程

        • 检查是否越界;

        • 调用 ensureCapacityInternal 确保数组足够大;

        • 将坐标index后的元素都往后移动一位;

        • 将元素写入 elementData[size]

        • size++ 。

        演示在索引下标插入元素,效果如图:

        Java集合源码ArrayList的可视化操作过程示例详解

        2.3. ensureCapacityInternal 与 grow 扩容流程

        为了好查阅源码,简单调整了下,jdk源码基本如下

        private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                // 延迟初始化:第一次调用 ensureCapacity 时,将容量至少设置为 DEFAULT_CAPACITY(10)
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            ensureExplicitCapacity(minCapacity);
        }
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++; // 用于迭代时快速失败
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
        private void grow(int minCapacity) {
            // 旧容量
            int oldCapacity = elementData.length;
            // 新容量 = 旧容量 + 旧容量>>1 (1.5 倍扩容)
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            // 最大容量检查(防止溢出)
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
        • 延迟初始化:无参构造后 elementData 引用一个长度为 0 的共享常量数组。

        • modCount:每次结构修改(如扩容、增删)都会自增,配合迭代器检查并发修改。

        • 扩容策略oldCapacity + (oldCapacity >> 1),右移一位等于除于2,所以newCapacity为原来的1.5 倍,以权衡空间和拷贝成本。

        ArrayList如果不指定大小初始大小为0,首次add才进行首次扩容,扩容大小为10,这个默认的初始容量DEFAULT_CAPACITY在首层插入数据才会使用到。故此,在创建ArrayList时最好指定大小,最佳情况是创建时就知道集合的大小。

        详细可见构造方法源码

        public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                // 指定初始容量大于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;
        }

        扩容可视化过程:插入第11个元素的扩容过程

        Java集合源码ArrayList的可视化操作过程示例详解

        2.4. 扩容时才对modCount 自增合理吗?

        不合理。因为你插入新的数据没有扩容的情况下,集合申请的内存空间不变,但是集合保存元素的大小发生了变化,这和移除元素一样,集合也是发生了变化的,所以在后续的jdk版本中,add操作加入了modCount++;

        以下是jdk11的add源码:首行就对modCount做了自增

        public boolean add(E e) {
            modCount++;
            add(e, elementData, size);
            return true;
        }

        2.5. 允许null和可重复插入?

        ArrayList集合内保存的是对象的引用,在Java语言中,引用是可以指向null的,故ArrayList集合可以保存null。在元素插入时并没有对元素进行重复检查,故可以保存重复数据,包括重复的null。

        List 接口在 javadoc 里就明确说了:

        允许所有元素(包括 null),允许重复插入;

        如果你需要“元素唯一”或“禁止空值”,Java 提供了其他集合类型(如实现了 Set 接口的 HashSet/LinkedHashSet/TreeSet,或者在 Java 9+ 可以用 List.of(...) 构造的不可空、不可变的列表)

        实现简单高效ArrayList 底层用一块连续的 Object[] 数组存储元素:

        • 插入 null 只不过是往数组里赋一个 null,跟存任何其他对象没区别;

        • 重复插入只是把同一个引用赋给不同索引,也没有额外开销;

          如果强行在 add() 里做“非空检查”或“去重”,不仅会增加每次插入的开销,还会破坏它作为通用、轻量列表的设计初衷。

        3. 修改元素(改)

        根据指定索引进行覆盖E set(int index, E element)

        public E set(int index, E elem编程客栈ent) {
            rangeCheck(index);
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

        这个很简单,检查是否越界,暂存旧值,覆盖数组对应下标的值,返回旧值。

        修改索引元素可视化过程:

        Java集合源码ArrayList的可视化操作过程示例详解

        4. 移除元素(删)

        方法分类

        ArrayList 的 remove 方法有两个重载版本,对应不同的用法:

        • remove(int index) —— 按索引删除

        • remove(Object o) —— 按对象值删除

        4.1. 指定索引删除

        使用到的方法:remove(int index)

        public E remove(int index) {
            rangeCheck(index); // 检查索引是否合法
            modCount++;        // 修改次数+1,支持 fail-fast
            E oldValue = elementData(index); // 获取旧值
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index + 1, elementData, index, numMoved);
            elementData[--size] = null; // clear to let GC do its work
            return oldValue;
        }

        分析

        • 使用 System.arraycopy() 将后面所有元素向前移动一位;

        • 最坏情况是删除索引 0,移动 n-1 个元素;

        • 修改 size,清除最后一个元素引用。

        删除索引元素的可视化过程:

        Java集合源码ArrayList的可视化操作过程示例详解

        4.2. 按照对象值删除

        使用到的方法:remove(Object o)

        public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }

        配套的 fastRemove(int index) 实现如下:

        private void fastRemove(int index) {
            modCount++;
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index + 1, elementData, index, numMoved);
            elementData[--size] = null;
        }

        分析

        • 先线性查找目标元素,最多比较 n 次;

        • 然后移除元素,最多移动 n-1 个;

        • 所以总操作是一次“线性查找 + 线性移动”。

        避免在大列表中频繁删除中间元素(尤其在循环中删除),否则容易退化为 O(n²)。

        对比按照索引删除,多了一步元素查找对比,其它基本一致。

        按照对象值删除元素的可视化过程:

        Java集合源码ArrayList的可视化操作过程示例详解

        5. 获取和检索元素(查)

        5.1. 获取元素

        根据索引获取元素:get(int index)

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

        检查是否越界,然后根据下标索引获取元素。

        5.2. 检索元素

        在 ArrayList 中,检索某个元素(不是通过索引,而是查找某个值是否存在,或其位置)主要通过以下两个方法完成:

        1) 判断是否包含某个元素

        根据对象值判断集合中是否存在:contains(Object o)

        public boolean contains(Object o) {
            return indexOf(o) >= 0;
        }

        这个方法内部调用了 indexOf 方法。它返回一个布尔值,表示某个元素是否存在于列表中。

        2) 返回元素首次出现的索引

        根据对象值检索首次出现的位置:indexOf(Object o)

        跟按照对象值删除的检索过程一致,可查看上面的可视化过程动图。

        public int indexOf(Object o) {
            if (o == null) {
                for (int i = 0; i < size; i++http://www.devze.com)
                    if (elementData[i] == null)
                        return i;
            } else {
                for (int i = 0; i < size; i++)
                    if (o.equals(elementData[i]))
                        return i;
            }
            return -1;
        }

        如果查找的是 null,就用 == 比较;如果是非 null 对象,则用 equals() 方法逐个比较。从头遍历,找到第一个匹配项的索引。

        3) 返回元素最后一次出现的索引

        根据对象值检索最后出现的位置:lastIndexOf(Object o)

        public int lastIndexOf(Object o) {
            if (o == null) {
                for (int i = size - 1; i >= 0; i--)
                    if (elementData[i] == null)
                        return i;
            } else {
                for (int i = size - 1; i >= 0; i--)
                    if (o.equals(elementData[i]))
                        return i;
            }
            return -1;
        }

        与 indexOf 类似,但从尾部开始向前查找。

        6. ArrayList 的迭代器(Iterator)

        6.1. 什么是迭代器?

        迭代器(Iterator)是 Java 集合框架中用于遍历集合元素的工具。

        ArrayList 提供了两种主要的迭代方式:

        • Iterator<E>:基础的迭代器接口(只支持单向遍历)

        • ListIterator<E>:是 Iterator 的子接口,支持双向遍历、修改元素、获取索引等高级功能

        6.2. iterator迭代器

        源码(位于 ArrayList.java):

        public Iterator<E> iterator() {
            return new Itr();
        }

        这会返回一个内部类 Itr 的实例。

        1) Itr 内部类的核心源码(简化版):

        private class Itr implements Iterator<E> {
            int cursor = 0;       // 下一个要返回的元素索引
            int lastRet = -1;     // 上一个返回的元素索引,若没有则为 -1
            int expectedModCount = modCount;  // 用于检测并发修改
            public boolean hasNext() {
                return cursor != size;
            }
            public E next() {
                checkForComodification();
                int i = cursor;
                if (i >= size)
                    throw new NoSuchElementException();
                cursor = i + 1;
                return (E) elementData[lastRet = i];
            }
            public void remove() {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComandroidodification();
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            }
            final void checkForComodification() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }

        2) modCount 与并发修改检查(fail-fast)

        • modCount 是 ArrayList 中用于记录结构性修改(如添加、删除元素)次数的字段。

        • 迭代器创建时保存了当前的 modCount 到 expectedModCount

        • 如果在迭代期间集合发生结构性修改,modCount != expectedModCount,就会抛出 ConcurrentModificationException

        这就是所谓的 fail-fast机制

        3) 示例代码

        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String s = it.next();
            System.out.println(s);
        }

        6.3. ListIterator更强大的双向迭代器

        1) 增强版迭代器简述

        通过 list.listIterator() 或者listIterator(int index)来获取,本质都是返回new ListItr(index)对象。ListItrItr的子类)private class ListItr extends Itr implements ListIterator<E>,是增强版迭代器。

        ListIterator<String> it = list.listIterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
        while (it.hASPrevious()) {
            System.out.println(it.previous());
        }

        额外支持:

        • hasPrevious()previous()

        • add(E e)remove()set(E e)

        • nextIndex()previousIndex()

        2) 示例代码

        反序遍历案例

        import java.util.ArrayList;
        import java.util.List;
        import java.util.ListIterator;
        public class ListIteratorReverseDemo {
            public static void main(String[] args) {
                List<String> list = new ArrayList<>();
                list.add("Dog");
                list.add("Cat");
                list.add("Bird");
                list.add("Fish");
                System.out编程客栈.println("原始列表: " + list);
                ListIterator<String> iterator = list.listIterator(list.size()); // 从末尾开始
                while (iterator.hasPrevious()) {
                    String animal = iterator.previous();
                    // 替换元素
                    if (animal.equals("Cat")) {
                        iterator.set("Tiger"); // 将 Cat 替换为 Tiger
                    }
                    // 删除元素
                    if (animal.equals("Bird")) {
                        iterator.remove(); // 删除 Bird
                    }
                    // 在 Fish 前插入一个元素
                    if (animal.equals("Fish")) {
                        iterator.add("Whale"); // 插入 Whale(在 Fish 之前)
                    }
                }
                System.out.println("修改后的列表: " + list);
            }
        }

        6.4. 时间复杂度

        • 每个迭代器的 next()hasNext() 操作时间复杂度都是 O(1)

        • 但是若在 remove() 中触发 ArrayList 的 remove(index),那是 O(n),因为后面的元素要移动。

        6.5. 注意事项

        • 在使用 for-each 或 iterator 遍历时,不要直接修改原始集合(如调用 add()remove()),否则会抛出 ConcurrentModificationException

        • 如果需要在遍历中安全地修改集合,可以使用 ListIterator 的 remove() 或 add() 方法,它是支持修改的。

        7. 线程安全问题

        ArrayList是线程不安全的。

        举个例子

        List<Integer> list = new ArrayList<>();
        Runnable task = () -> {
            for (int i = 0; i < 1000; i++) {
                list.add(i);  // 非线程安全
            }
        };
        Thread t1 = new Thread(task);
        Thread t2 = new Thread(task);
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println("最终大小: " + list.size()); // 不一定是 2000

        不过只有 ArrayList 作为共享变量时,才需要考虑线程安全问题,当 ArrayList 集合作为方法内的局部变量时,无需考虑线程安全的问题。

        解决安全问题的一些方法

        类注释中推荐我们使用 Collections#synchronizedList 来保证线程安全,SynchronizedList 是通过在每个方法上面加上锁来实现,虽然实现了线程安全,但是性能大大降低。

        使用方式

        List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());
        // 遍历时手动加锁
        synchronized(syncList) {
            for (Integer i : syncList) {
                // 安全遍历
            }
        }

        也可以使用这个集合:CopyOnWriteArrayList(推荐用于读多写少)

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

        特性:

        • 所有写操作(add/remove/set)都会复制一份数组再修改;

        • 不会抛出 ConcurrentModificationException

        • 非常适合读多写少的场景。

        缺点:

        • 写操作开销大,性能比 ArrayList 差很多。

        8. 时间复杂度汇总

        操作时间复杂度备注
        插入元素O(1),扩容单次为 O(n)add(E)
        随机插入O(n),元素拷贝add(index,E)
        指定索引删除O(n),指定索引删除remove(index)
        指定对象值删除O(n),查找 + 移动remove(Object)
        指定索引修改O(1)set(index,E)
        获取元素O(1)get(index)
        检索元素都为O(n)indexOf(Object)lastIndexOf(Object)

        9. 总结

        在使用ArrayList集合时,需要关注以下特性:随机获取/修改快、插入/删除慢、扩容性能问题、并发线程安全问题。

        关于元素插入、检索、修改、删除、扩容过程等操作过程,完整的视频链接:https://www.bilibili.com/video/BV1KET2zGEm4/

        到此这篇关于Java集合源码--ArrayList的可视化操作过程的文章就介绍到这了,更多相关Java集合源码--ArrayList的可视化操作过程内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)!

        0

        上一篇:

        下一篇:

        精彩评论

        暂无评论...
        验证码 换一张
        取 消

        最新开发

        开发排行榜