ArrayList 深入理解底层源码

Nissa ·

更新时间:2024-11-15

· 838 次阅读

ArrayList 集合源码解读介绍构造方法add方法remove方法总结介绍

ArrayList Jdk1.8采用的是数组的数据结构，是非线程安全的一个集合（多线程下数据不安全），本文章主要讲解ArrayList集合添加和集合扩容，其他方法都相对简单，读懂这个后相信你翻翻源码即可读懂其他方法原理，下面讲解源码的可能会有点枯燥，请着重去了解集合添加和扩容的一个流程

构造方法

在这里插入图片描述
我们来看源码迅速带过这三个构造方法,为了方便阅读，以下我们将当前集合数组统称为集合

无参构造方法，创建一个空集合


	//存放数据的Object数组
	transient Object[] elementData; // non-private to simplify nested class access
	//默认为空数组
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    public ArrayList() {
    	//将空数组赋值给当前集合
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

指定初始化大小构造方法


    private static final Object[] EMPTY_ELEMENTDATA = {};
	public ArrayList(int initialCapacity) {
		//如果指定数组大小大于0执行
        if (initialCapacity > 0) {
        	//new 一个对象数组赋值给当前ArrayList集合
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        	//等于零一样赋值为空集合
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        	//非法参数抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

集合参数的构造方法，作用是将集合参数转换为当前ArrayList集合的值

 public ArrayList(Collection c) {
 		//将Collection接口集合转换成数组 赋值给当前ArrayList集合
        elementData = c.toArray();
       //如果当前集合（Collection接口集合）中参数不为空
        if ((size = elementData.length) != 0) {
        	//如果集合数组类型不是Object类型 比如int[] 则执行
            if (elementData.getClass() != Object[].class)
            	//将当前集合转换成Object类型的数组返回给当前集合
            	//这里直接完成了集合大小的初始化
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 当前集合大小为空则赋值空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

add方法

集合初始化以及集合扩容都在add方法中完成！请认真阅读，我们首先看一下文档，发现有两个add重载方法，我们来一一解刨
在这里插入图片描述

add(E e)

	/**
     * Default initial capacity.
     * 集合默认初始化大小
     */
    private static final int DEFAULT_CAPACITY = 10;
	//未初始化 默认赋值为0
	//该变量是用来存储集合数据个数
	private int size;
	public boolean add(E e) {
		//调用ensureCapacityInternal方法 传入size+1
        ensureCapacityInternal(size + 1); 
        //扩容方法执行完后进行数据赋值 size++
        elementData[size++] = e;
        //添加成功
        return true;
    }
    // 该方法负责调用其他两个方法
     private void ensureCapacityInternal(int minCapacity) {
     	//首先调用calculateCapacity(elementData, minCapacity)方法
     	//elementData 当前集合 
     	//minCapacity add方法传过来的size大小
     	//接受到calculateCapacity方法返回的集合大小又调用ensureExplicitCapacity方法
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    //集合大小计算方法
	private static int calculateCapacity(Object[] elementData, int minCapacity) {
		//如果当前集合等于空集合
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        	// 比较DEFAULT_CAPACITY和minCapacity
        	// 返回最大值
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //不为空则返回当前集合大小
        return minCapacity;
    }
	private void ensureExplicitCapacity(int minCapacity) {
		//记录数据操作次数
        modCount++;
       //当集合满时（size+1>集合长度时）进行扩容
       //第一次集合大小初始化也会执行
        if (minCapacity - elementData.length > 0)
        	//扩容和集合大小初始化方法实现
            grow(minCapacity);
    }
	//扩容和集合大小初始化方法
	private void grow(int minCapacity) {
        // 当前数组长度赋值给oldCapacity
        int oldCapacity = elementData.length;
		//计算集合需要扩容的大小  集合原大小+原大小/2（奇数舍小数）
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //这句条件语句执行主要用于初始化场景
        //当前集合为空集合 还没初始化大小 newCapacity=0
        if (newCapacity - minCapacity  0)
            newCapacity = hugeCapacity(minCapacity);
         //扩容完成赋值给当前集合 Arrays.copyOf底层其实还是调用了System类的arraycopy方法
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

add(int index, E element)

	public void add(int index, E element) {
		//索引验证
        rangeCheckForAdd(index);
		//调用扩容机制 可以借鉴前面代码
        ensureCapacityInternal(size + 1);  
        //作用是为要插入的索引留出空位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
          //添加数据
        elementData[index] = element;
        //添加完成，数据个数++
        size++;
    }
	//索引验证方法
	private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

remove方法

讲完来重要的add方法还是有必要看一下remove方法，首先看文档，两个重载方法，一个传的是索引，一个传的是对象，那么我们一个一个来刚
在这里插入图片描述

remove(int index)

	public E remove(int index) {
		//索引验证
        rangeCheck(index);
		//数据操作记录
        modCount++;
        //存储要删除的值
        E oldValue = elementData(index);
		//集合大小减去待删除索引-1
        int numMoved = size - index - 1;
        //大于0表示在倒数一位数据前
        if (numMoved > 0)
        	//数组拷贝，在删除的索引接上后面的值（内存换时间，效率提升）
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
         //不满足上述条件表示要删除的是最后一位，这里直接赋值为null
        elementData[--size] = null; 
		//返回旧值
        return oldValue;
    }

remove(Object o)

// 我们可以看出集合根据数据删除 效率相对来说变差很多
 public boolean remove(Object o) {
 		//要删除数据为null
        if (o == null) {
        	//遍历整个数组
            for (int index = 0; index < size; index++)
            	//该索引值等于null 进行删除
                if (elementData[index] == null) {
                	//传入索引进行删除
                    fastRemove(index);
                    //返回true
                    return true;
                }
        } else {
            for (int index = 0; index  0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; 
    }

总结

ArrayList是一个非线程安全的一个数组集合，在多线程资源抢夺时必定会出现安全隐患,
ArrayList还可以存储null数据,
ArrayList采用数组的添加和扩容的机制，以及根据索引删除，都是内存换时间的方法，时间复杂度都控制在O(1),
ArrayList根据数据删除时间复杂度在O(n),效率相对索引删除相差太多
ArrayList当集合满时进行扩容扩容方式:原大小+原大小/2 (奇数舍小数）

本篇文章主要讲解这些核心知识点
但相信你看完这篇文章，其他的方法肯定是不在话下

作者：大山里的技术宅

arraylist 源码

1024 个赞