专栏首页后端技术学习ArrayList源码学习

ArrayList源码学习

ArrayList是一种以数组实现的列表,而数组的优势在于有角标,因此查询的速度较快,是一种可以动态扩容的数组。我们着重了解添加、获取、替换、删除操作。

1.相关变量信息

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

//为空数组实例准备一个空数组{}
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认容量空元素数据,添加数组是会重新分配容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//元素数据,存放元素的数组,重要,操作数据用的都是它
transient Object[] elementData; // non-private to simplify nested class access
 
 //ArrayList大小
 private int size;

2.构造函数

//构造一个空的带特定初始化容量的list
public ArrayList(int initialCapacity) {
    //如果初始化容量>0,创建一个带特定容量的数组
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    //如果初始化容量为0,空元素数组
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //否者抛异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

//构造一个空列表同时带有初始化容量0,默认初始化容量
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//将传入集合的元素初始化到ArrayList中
public ArrayList(Collection<? extends E> c) {
    //集合转数组
    elementData = c.toArray();
    //如果长度不为0
    if ((size = elementData.length) != 0) {
        /**
         * 如果c.toArray()不是数组的话,
         * 采用arrays中的方法copyOf(U[] original, int newLength, Class<? extends T[]> newType)
         * 将其转成数组
         **/
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //否者size=0,将c.toArray()替换成空数组
        this.elementData = EMPTY_ELEMENTDATA;
     }
  }

3.方法

(1)元素添加操作

添加元素:我们可以思考,如果让你添加元素,你会考虑什么?第一考虑容量是否充足,第二是进行元素的添加。

public boolean add(E e) {
    //确保容量够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //进行元素添加
    elementData[size++] = e;
    return true;
}

 //进行容量确保是否够,不够则进行扩容
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

 //计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果数组为空,则直接返回默认容量
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //否者返回需要的容量
    return minCapacity;
}

//进行扩容操作
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

 //进行扩容操作
private void grow(int minCapacity) {
    //老的容量
    int oldCapacity = elementData.length;
    //新的容量=老容量+老的容量做位运算向右移一位,也即1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果新容量比需要的容量小,则将新容量变为需要容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果新容量比最大容量,则使用最大容量
    // MAX_VALUE=>@Native public static final int   MAX_VALUE = 0x7fffffff;  //2^31-1
    //private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; =>2^31-9
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //将数据转移到新的数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

添加元素到指定位置

//添加元素到指定位置
public void add(int index, E element) {
    //检查index索引是否越界
    rangeCheckForAdd(index);

    //看容量是否够,确保容量够用
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    /**
     * public static native void arraycopy(
     *          Object src,  int  srcPos,Object dest, int destPos,int length);
     * 进行数据拷贝,这样做的目的是为了将index的位置空出来,添加元素
     */
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //在index位置添加元素
    elementData[index] = element;
    //list长度+1
    size++;
}

进行addAll操作:

//将集合c中所有元素添加到当前ArrayList中
public boolean addAll(Collection<? extends E> c) {
    //将传入的集合转换为数组
    Object[] a = c.toArray();
    //获取集合转成数组之后的长度
    int numNew = a.length;
    //看容量是否够
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //将c中元素拷贝到arraylist中
    System.arraycopy(a, 0, elementData, size, numNew);
    //长度+添加元素长度
    size += numNew;
    return numNew != 0;
}

进行addAll操作添加元素到指定位置:

//将集合c中所有元素添加到当前ArrayList中
public boolean addAll(Collection<? extends E> c) {
    //将传入的集合转换为数组
    Object[] a = c.toArray();
    //获取集合转成数组之后的长度
    int numNew = a.length;
    //看容量是否够
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //将c中元素拷贝到arraylist中
    System.arraycopy(a, 0, elementData, size, numNew);
    //长度+添加元素长度
    size += numNew;
    return numNew != 0;
}

进行addAll操作添加元素到指定位置:

//将集合c中所有元素添加到当前ArrayList中
public boolean addAll(int index, Collection<? extends E> c) {
    //检查是否越界
    rangeCheckForAdd(index);
    //将传入的集合c转成数组
    Object[] a = c.toArray();
    //获取长度
    int numNew = a.length;
    //进行容量检查,如果容量不够,则进行扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //需要移动的元素个数
    int numMoved = size - index;
    //如果需要移动的个数大于0,则需要移动元素,并进行添加操作,size加上移动的数量
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    //将元素拷贝到index位置
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

默认的初始容量为10。是否需要扩容,会先计算容量。如果数组为空,则直接返回默认容量10。如果需要容量>数组长度,则进行扩容。如果需要容量比老容量要大,则需要进行扩容1.5倍,采用位运算实现,也就是15。如果新容量比最大容量大,则采用默认的最大容量,为2^31-9。最后将数据转移到新的数组中。而添加元素到指定位置,会先检查是否越界,接着会看容量是否够,不够,则进行扩容,接着进行数据拷贝,空出index位置,将元素放入到指定的index位置,同时size+1。

(2)get操作

获取指定位置的元素

public E get(int index) {
    //检查是否越界
    rangeCheck(index);
    //返回指定位置元素
    return elementData(index);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    //获取元素
    return (E) elementData[index];
}

(3)替换操作

//在特定位置替换你想要替换的元素
public E set(int index, E element) {
    //检查越界
    rangeCheck(index);
    //获取老的元素
    E oldValue = elementData(index);
    //将其替换成新的元素
    elementData[index] = element;
    //返回老的值
    return oldValue;
}

(4)删除操作

删除特定元素操作

//删除特定的元素
public E remove(int index) {
    //检查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;
}

删除第一次出现的元素

//删除指定的第一次出现的元素,如果没有出现,则不做修改
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;
}

 //删除元素
    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; // clear to let GC do its work
    }

删除包含和特定元素相同的所有元素,类似求差集

//删除包含c集合的元素
public boolean removeAll(Collection<?> c) {
    //进行非空校验
    Objects.requireNonNull(c);
    //不为空,执行批量删除操作
    return batchRemove(c, false);
}

//进行批量删除操作
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    //采用双指针 r是读指针,w是写指针
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            //如果集合c中包含元素,如果是true,则true==true则进行写入
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        //保留与AbstractCollection的行为兼容性,
        // 即使c.contains()抛出异常也是如此。
        if (r != size) {
            //如果c.contains()抛出了异常,则把未读的元素都拷贝到写指针之后
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            //将写指针之后的元素置置空,方便GC操作
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

删除包含c集合的元素:首先这里采用了双指针的方法。类似元素匹配。删除不包含c集合的所有元素,类似求交集

//移除不包含特定元素的所有的元素
public boolean retainAll(Collection<?> c) {
    //非空校验
    Objects.requireNonNull(c);
    //进行批量删除操作
    return batchRemove(c, true);
}

因此我们可以得到以下信息:

从操作上看,我们可以知道其实际上是在操作数组,而操作完之后将其采用arrayCopy的方式放入到arrayList中。同时我们可以知道其默认容量是10,如果不够的时候,会进行扩容,每次都是扩容成原来的1.5倍,采用位运算(右移动一位)进行扩容。

其进行添加元素的时候,会首先进行越界校验,如果没有越界才继续进行操作。接着查看容量是否够,不够的话,进行扩容操作,而扩容操作是在grow()方法中进行的。同时如果容量大于规定的最大容量2^31-9时,会默认为最大容量。

本文分享自微信公众号 - 后端技术学习(gh_9f5627e6cc61),作者:亚洲

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LinkedList源码学习

    LinkedList 继承 抽象SequentialList、实现list接口,双端队列Deque以及克隆,因此具备列表、队列、双端队列的特性,可克隆。

    路行的亚洲
  • ReentranLock源码学习

    首先回答一个问题?线程的三大特性?什么时候我们需要锁?java中已经提供了synchronized,为什么还要使用ReentrantLock?AQS原理。

    路行的亚洲
  • Kafka学习四

    在kafka启动时,首先执行的broker的操作,然后接着会执行生产者操作,接着将生产者的消息放入到存储中,此时生产者和broker会进行交互,而消费者发送消...

    路行的亚洲
  • 死磕 Java集合之ArrayList源码分析

    ArrayList是一种以数组实现的List,与数组相比,它具有动态扩展的能力,因此也可称之为动态数组。

    zhisheng
  • 死磕 Java集合之ArrayList源码分析

    ArrayList是一种以数组实现的List,与数组相比,它具有动态扩展的能力,因此也可称之为动态数组。

    彤哥
  • ArrayList 源码分析

    ArrayList 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,所...

    lwen
  • Java集合框架源码解析之ArrayList

    叶志陈
  • ArrayList源码解析(基于Java8)扩容删除

    JavaEdge
  • JDK8的ArrayList源码学习笔记

    itliusir
  • 控制器操作【3】

    五.请求类型 ThinkPHP 提供了一组常量来判断当前请求是否是 GET、POST 等。通过判断请求处理不同的业务逻辑。 常量 含义 IS_GET 判断是否 ...

    公众号php_pachong

扫码关注云+社区

领取腾讯云代金券