2023-09-10  阅读(4)
原文作者:keep_trying 原文地址: https://blog.csdn.net/yjp198713/article/details/78964783

一、ArrayList概述

ArrayList是实现List接口的动态数组,所谓动态就是它的大小是可变的。实现了所有可选列表操作,并允许包括 null 在内的所有元素。

每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。默认初始容量为10。随着ArrayList中元素的增加,它的容量也会不断的自动增长。在每次添加新的元素时,ArrayList都会检查是否需要进行扩容操作,扩容操作带来数据向新数组的重新拷贝,所以如果我们知道具体业务数据量,在构造ArrayList时可以给ArrayList指定一个初始容量,这样就会减少扩容时数据的拷贝问题。
注意,ArrayList实现不是线程安全的。如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。所以为了保证同步,最好的办法是在创建时完成,以防止意外对列表进行不同步的访问:

    List list = Collections.synchronizedList(new ArrayList(…));
复制代码

二、ArrayList源码分析

ArrayList我们使用的实在是太多了,非常熟悉,所以在这里将不介绍它的使用方法。ArrayList是实现List接口的,底层采用数组实现,所以它的操作基本上都是基于对数组的操作。

2.1、底层使用数组

    private transient Object[] elementData;
复制代码

transient??为java关键字,为变量修饰符,如果用transient声明一个实例变量,当对象存储时,它的值不需要维持。Java的serialization提供了一种持久化对象实例的机制。当持久化对象时,可能有一个特殊的对象数据成员,我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization,可以在这个域前加上关键字transient。当一个对象被序列化的时候,transient型变量的值不包括在序列化的表示中,然而非transient型的变量是被包括进去的。
这里Object[] elementData,就是我们的ArrayList容器,下面介绍的基本操作都是基于该elementData变量来进行操作的。

2.2、构造函数

ArrayList提供了三个构造函数:

  • ArrayList():默认构造函数,提供初始容量为10的空列表。
  • ArrayList(int initialCapacity):构造一个具有指定初始容量的空列表。
    ArrayList(Collection<’?’ extends E> c):构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
    /**
         * 构造一个初始容量为 10 的空列表
         */
        public ArrayList() {
            this(10);
        }
    
        /**
         * 构造一个具有指定初始容量的空列表。
         */
        public ArrayList(int initialCapacity) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "
                        + initialCapacity);
            this.elementData = new Object[initialCapacity];
        }
    
        /**
         *  构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
         */
        public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            size = elementData.length;
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        }
复制代码

2.3、新增

add(E e):将指定的元素添加到此列表的尾部。

    public boolean add(E e) {
        ensureCapacity(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
        }
复制代码

这里ensureCapacity()方法是对ArrayList集合进行扩容操作,elementData(size++) = e,将列表末尾元素指向e。
add(int index, E element):将指定的元素插入此列表中的指定位置。

    public void add(int index, E element) {
            //判断索引位置是否正确
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(
                "Index: "+index+", Size: "+size);
            //扩容检测
            ensureCapacity(size+1);  
            /*
             * 对源数组进行复制处理(位移),从index + 1到size-index。
             * 主要目的就是空出index位置供数据插入,
             * 即向右移动当前位于该位置的元素以及所有后续元素。 
             */
            System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
            //在指定位置赋值
            elementData[index] = element;
            size++;
            }
复制代码

在这个方法中最根本的方法就是System.arraycopy()方法,该方法的根本目的就是将index位置空出来以供新数据插入,这里需要进行数组数据的右移,这是非常麻烦和耗时的,所以如果指定的数据集合需要进行大量插入(中间插入)操作,推荐使用LinkedList。

2.4、删除

ArrayList提供了remove(int index)、remove(Object o)、removeRange(int fromIndex, int toIndex)、removeAll()四个方法进行元素的删除。
remove(int index):移除此列表中指定位置上的元素。

    public E remove(int index) {
            //位置验证
            RangeCheck(index);
    
            modCount++;
            //需要删除的元素
            E oldValue = (E) elementData[index];   
            //向左移的位数
            int numMoved = size - index - 1;
            //若需要移动,则想左移动numMoved位
            if (numMoved > 0)
                System.arraycopy(elementData, index + 1, elementData, index,
                        numMoved);
            //置空最后一个元素
            elementData[--size] = null; // Let gc do its work
    
            return oldValue;
        }
复制代码

remove(Object o):移除此列表中首次出现的指定元素(如果存在)。

    public boolean remove(Object o) {
            //因为ArrayList中允许存在null,所以需要进行null判断
            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()方法用于移除指定位置的元素。如下

    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; // Let gc do its work
        }
复制代码

2.5、查找

ArrayList提供了get(int index)用读取ArrayList中的元素。由于ArrayList是动态数组,所以我们完全可以根据下标来获取ArrayList中的元素,而且速度还比较快。

    public E get(int index) {
            RangeCheck(index);
            return (E) elementData[index];
    }
复制代码

2.6、扩容

在上面的新增方法的源码中我们发现每个方法中都存在这个方法:ensureCapacity(),该方法就是ArrayList的扩容方法。在前面就提过ArrayList每次新增元素时都会需要进行容量检测判断,若新增元素后元素的个数会超过ArrayList的容量,就会进行扩容操作来满足新增元素的需求。所以当我们清楚知道业务数据量或者需要插入大量元素前,我可以使用ensureCapacity来手动增加ArrayList实例的容量,以减少递增式再分配的数量。最终扩容的代码如下:

    private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            //先对容量扩大1.5倍,这里oldCapacity >> 1是二进制操作右移,相当于除以2 相当于1+1/2= 1.5
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
复制代码

在这里有一个疑问,为什么每次扩容处理会是1.5倍,而不是2.5、3、4倍呢?因为一次性扩容太大(例如2.5倍)可能会浪费更多的内存(1.5倍最多浪费33%,而2.5被最多会浪费60%,3.5倍则会浪费71%……)。但是一次性扩容太小,需要多次对数组重新分配内存,对性能消耗比较严重。所以1.5倍刚刚好,既能满足性能需求,也不会造成很大的内存消耗。


Java 面试宝典是大明哥全力打造的 Java 精品面试题,它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题,而是一套完整的 Java 知识体系,一套你 Java 知识点的扫盲贴。

它的内容包括:

  • 大厂真题:Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
  • 原创内容:Java 面试宝典内容全部都是大明哥原创,内容全面且通俗易懂,回答部分可以直接作为面试回答内容。
  • 持续更新:一次购买,永久有效。大明哥会持续更新 3+ 年,累计更新 1000+,宝典会不断迭代更新,保证最新、最全面。
  • 覆盖全面:本宝典累计更新 1000+,从 Java 入门到 Java 架构的高频面试题,实现 360° 全覆盖。
  • 不止面试:内容包含面试题解析、内容详解、知识扩展,它不仅仅只是一份面试题,更是一套完整的 Java 知识体系。
  • 宝典详情:https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
  • 宝典总览:https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
  • 宝典进展:https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw

目前 Java 面试宝典累计更新 400+ 道,总字数 42w+。大明哥还在持续更新中,下图是大明哥在 2024-12 月份的更新情况:

想了解详情的小伙伴,扫描下面二维码加大明哥微信【daming091】咨询

同时,大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ,回复【面试题】 即可免费领取。

阅读全文