• 《JavaSE-第十六章》之ArrayList源码与扩容机制

    前言

    在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!”

    博客主页：KC老衲爱尼姑的博客主页

    博主的github，平常所写代码皆在于此

    刷题求职神器

    共勉：talk is cheap, show me the code

    作者是爪哇岛的新手，水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

    文章目录

    ArrayList

    ArrayList概述

    ArrayList底层是一个Object数组,而数组在内存是连续的空间,所以使用ArrayList存储的元素与添加时的顺序是一致的,每一个ArrayList都有一个容量大小,当添加的元素数量大于该数组的容量时,ArrayList会自动扩容。

    ArrayList具体框架图

    在这里插入图片描述

    ArrayList继承于AbstractList,实现了RandomAccess，Cloneable,Serializable这些接口。

    • 实现RandomAccess接口,意味着ArrayList支持随机方法,即可以像数组一样通过下标快速的访问某一元素。
    • 实现了Cloneable接口,意味着可以被克隆
    • 实现Serializable,意味着可以被序列化

    属性

    /**
     * 序列化ID
     */
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 默认初始化的容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于空实例的共享空数组实例。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 共享空数组实例用于默认大小的空实例。我们将它与EMPTY_ELEMENTDATA区分开来，以了解添加第一个元素时要膨胀多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     *保存ArrayList元素的数组
     */
    transient Object[] elementData; 

    /**
     * 
     *
     * ArrayList中元素的个数
     */
    private int size;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    通过查看源码可知,ArrayList有2个Object数组,那么这2两数组有啥区别呢?这个问题得继续往下看。

    构造方法

    无参构造方法
        /**
     * 默认无参构造函数
     *DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0,也就是说明初始其实是空数组,当添加第一个元素的时候数组容量才变成10,当容量超过10时,会扩大1.5倍
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    ​ 当创建使用无参构造方法创建一个ArrayList对象时, elementData引用所指向的数组是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

    带初始容量的构造方法
        /**
     * 带初始容量参数的构造函数（使用者可以在创建ArrayList对象时自己指定集合的初始大小）
     */
    public ArrayList(int initialCapacity) {
        //初始的大小大于0则分配一个该大小的数组
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //初始的大小为0,分配一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //小于0抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    当创建使用带初始容量参构造方法创建一个ArrayList对象时,如果初始的容量initialCapacity大于0则分配一个相应大小的数组，如果初始的容量initialCapacity等于0则

    elementData引用指向EMPTY_ELEMENTDATA,如果小于0则抛出异常。

    带集合参数的构造方法
    /**
     * 利用其他 Collection 构建 ArrayList
     */
    public ArrayList(Collection<? extends E> c) {
        //将集合转换成数组
        elementData = c.toArray();
        //如果elementData数组的长度不为0
        if ((size = elementData.length) != 0) {
            //如果elementData是不是Object类型
            if (elementData.getClass() != Object[].class)
                //将原来不是Object类型的数组赋值给新的Object数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            //如果elementData数组的长度为0,直接给个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    上述代码,首先将传入的集合转换成数组并赋值给 elementData,再将elementData的长度赋值为size，然后判断是否为0,如果不为0,则判断 elementData 的 class 类型是否为 Object[]，不是的话则做一次转换。如果为0则将EMPTY_ELEMENTDAT赋值给elementData。

    扩容机制

    通过上述无参构造方法创建的ArrayList对象,该数组分配的是一个空数组,所以容量大小为0,当添加元素或者数组满了的时候会触发扩容机制。接下来就先看看add()方法。

        public boolean add(E e) {
        ensureCapacityInternal(size + 1); //添加第一个元素时size为0
        elementData[size++] = e;
        return true;
    }

    • 1
    • 2
    • 3
    • 4
    • 5

    向ArrayList添加一个元素

    package com.kc.demo;

import java.util.ArrayList;

public class Demo2 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("叶秋涵");
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    根据add方法在添加元素之前,会对容量进行判断已经满了,如果满了自然要扩容,下面就来看看ensureCapacityInternal()方法。

       private void ensureCapacityInternal(int minCapacity) {//添加第一个元素时minCapacity为1
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    • 1
    • 2
    • 3

    ensureCapacityInternal方法参数minCapacit的含义为所需最小的容量,ensureCapacityInternal的方法体中又调用了calculateCapacity()方法。

      private static int calculateCapacity(Object[] elementData, int minCapacity) {//minCapacity为1
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY为10
        }
        return minCapacity;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    ensureExplicitCapacity()方法会判断当前数组的引用是否为空数组,如果是就返回DEFAULT_CAPACITY(默认容量为10)以及minCapacity的最大值。否则返回minCapacity。

    然后ensureExplicitCapacity()方法根据返回的最小容量与数组长度进行扩容

        private void ensureExplicitCapacity(int minCapacity) {//minCapacity为10
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)//10>0
            grow(minCapacity);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    如果最小的容量大于数组长度时就需要调用grow()方法进行扩容

    private void grow(int minCapacity) {//minCapacity 为10
        // overflow-conscious code
        int oldCapacity = elementData.length;//0
        int newCapacity = oldCapacity + (oldCapacity >> 1);//原数组的1.5倍-->0
        if (newCapacity - minCapacity < 0)//0<10
            newCapacity = minCapacity;// newCapacity = 10
        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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    grow()方法会先计算出原数组大小的1.5倍,如果扩容后的长度比最小容量小,则newCapacity为最小容量,如果newCapacity比整数的最大值还要大,就会调用hugeCapacity()方法进行调整。

        private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    hugeCapacity()方法会对minCapacity进行判断,如果它小于0则抛出异常。最终的newCapacity取决于minCapacity和MAX_ARRAY_SIZE,如果前者大于后者则返回

    Integer.MAX_VALUE,否则返回ArrayList定义的数组最大的容量。

    ArrayList有2个Object数组的区别?

    看完构造方法、添加方法、扩容方法之后，new ArrayList(),elementData赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA,new ArrayList(0),会将 EMPTY_ELEMENTDATA赋值给elementData,当EMPTY_ELEMENTDATA扩容时,传入的参数是多少就是多少,而DEFAULTCAPACITY_EMPTY_ELEMENTDATA初次扩容之后的容量为10。

    常用方法

    在指定位置插入元素
        /**
     * 先将原来该位置的元素以及后面的元素整体往后移动,再把这个位置的元素插入
     */
    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++;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    将指定集合元素追加到ArrayList末尾
        /**
     *将指定集合元素追加到ArrayList末尾
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    删除 index 位置元素
       /**
     * 删除指定位置的元素,返回值为已删除的元素
     *
     */
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    删除遇到的第一个元素
        /**
     *删除从某个元素,删除成功返回true,否则返回false。
     */
    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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    获取下标 index 位置元素
      public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    将下标 index 位置元素设置为 element
        public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    清空
     public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    判断元素是否在ArrayList中
        /**
     * 判断集合是否包含指定的元素,有则返回true
     */
    public boolean contains(Object o) {
        //调用indexOf()方法进行寻找,该方法会从集合头一直到尾去寻找指定的元素,找到就返回首次出现的索引,没有找到就返回-1
        return indexOf(o) >= 0;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    返回第一个元素所在下标
        /**
     * 从列表头到开始寻找指定的元素,找到了就返回首次出现该元素的索引,没有则返回-1
     */
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    返回最后一个元素的下标
        /**
     * 从列表尾到头开始寻找指定的元素,找到了就返回首次出现该元素的索引,没有则返回-1
     */
    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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    总结

    • ArrayList底层的数据结构是数组
    • ArrayList可以自动扩容，不传初始容量或者初始容量是0，都会初始化一个空数组，但是如果添加元素，会自动进行扩容。
    • ArrayList是线程不安全的,在单线程可以使用,多线程环境下可以使用CopyOnWriteArrayList

    结

    各位看官如果觉得文章写得不错，点赞评论关注走一波！谢谢啦！

    在这里插入图片描述

  • 相关阅读:
    10.5作业
    C++项目实战-mysql数据库安装及配置
    线程创建方式
    ABP - 缓存模块(2)
    问题：关于醋酸钠的结构，下列说法错误的是（） #媒体#媒体
    python 动态加载C# 动态库的一些问题
    MySQL表查询--多表笛卡尔积和子连接
    Winform圆角用户控件的软件实现
    HTML+CSS+JS网页设计期末课程大作业 DW个人博客网站制作 web前端开发技术 web课程设计 网页规划与设计
    软考 系统架构设计师系列知识点之数字孪生体（4）
  • 原文地址：https://blog.csdn.net/qq_60308100/article/details/127574067