ArrayList 源码笔记

时间:2021-7-20 作者:qvyue

惯例先来个笑话。

ArrayList 源码笔记
哈哈哈
目录
数据结构基础
扩容
增删改查
面试知识

数据结构基础

数据存储只有两种形式,第一种数组,第二种链表,其他的树和图,堆栈,队列都是从这两个基础数据上衍生出来的,只是为了解决特定的问题进行的封装。

数组的特点

1,数组根据索引取查询数据,所以时间复杂度是O(1);
2,数组一创建就指定了大小,所以问题就来了,插入和从中间删除,剩余的数据保证数据的连续性,数组需要挪动,所以插入删除的时间复杂度是O(n);

链表的特点

1,链表查询数据,需要遍历整个链表,即便是做了优化,判断当前index,确定从前边遍历或者从后边遍历,时间复杂度仍是O(n)。
2,链表插入和删除的,首先需要找到当前插入的点,也需要遍历链表,然后把节点指针相连,所以时间复杂度也是O(n);但是为什么都说链表更适合插入和删除呢,因为链表查找的时间要比移动数据快很多。
简单解释下这里,时间复杂度概念

扩容

从名字上看就知道底层的实现是一个数组,如何做到动态的扩容呢?
首先看成员变量,

 /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    // Android-note: Also accessed from java.util.Collections
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

属性
DEFAULT_CAPACITY 默认容量
EMPTY_ELEMENTDATA 有参构造方法赋值给elementData
DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空构造函数赋值给elementData
elementData 数据保存的
size 当前arraylist的数据个数

构造方法三个。

    /**
     * 1
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * 2
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 3
     */
    public ArrayList(Collection extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

构造方法 核心就是给elementData 对象初始化赋值,然后做一些校验,如果有数据copy进去。
为什么上边是两个数组呢?EMPTY_ELEMENTDATA 和DEFAULTCAPACITY_EMPTY_ELEMENTDATA,为什么不用一个数组。

核心方法

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
//1
        }

        ensureExplicitCapacity(minCapacity);
    }


    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
//2
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
//3
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
//4
        if (newCapacity - minCapacity  0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
  //5 
     elementData = Arrays.copyOf(elementData, newCapacity);
    }

private static int hugeCapacity(int minCapacity) {
        if (minCapacity  MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

1,确定是无参构造函数创建的,默认扩容的值 最小是DEFAULT_CAPACITY =10;添加一个元素扩容一次,添加第二个发现还需要扩容,添加第三个还需要扩容,扩容比较消耗性能。很明显这是不合理的,一次性有个合理的默认值。
2,如果现在目标容量大于现在数组的长度,就调用grow方法扩容.
3,首先拿到数组长度 新的长度 = 原来长度的1.5倍,(为什么用左移,不写/2这种方式,因为二进制运算会比+ -*/速度快很多)
4,做两个校验,第一,如果扩容1.5倍还是不够目标容量,就直接扩容到目标容量minCapacity,如果目标容量大于最大于MAX_ARRAY_SIZE(Integer.MAX_VALUE – 8)需要做一个校验,最大值为Integer.MAX_VALUE
5,拷贝数组数据,进行扩容。

增删改查

添加

我们需要关注的点。
1,ensureCapacityInternal所有添加方法首先会调用扩容方法相关
2,System.arraycopy(); 可以看到这一句,大部分都需要copy 数据所以这也就是消耗性能的地方。

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
 public void add(int index, E element) {
        if (index > size || index  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;
    }
 public boolean addAll(int index, Collection extends E> c) {
        if (index > size || index  0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
删除

我们需要关注的点。
1,remove 的时候可以看到传入的对象可以为null,所以说明arraylist允许添加Null
2,System.arraycopy(); 可以看到这一句,大部分都需要copy 数据所以这也就是消耗性能的地方。

public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) 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 
修改

我们需要关注的点。
1,修改数据O(1)级别。

    public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

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

我们需要关注的点。
1,查询数据O(1)级别。

    public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }

面试知识

1、ArrayList的大小是如何自动增加的?你能分享一下你的代码吗?
答:1.8之后,默认构造函数,不会扩容数组,是一个空的数组,第一次添加元素时候,首先会ensureCapacityInternal 判断当前容量是否足够,不够就行扩容数组,最小一次扩容为10,正常情况下一次扩容当前数组长的1.5倍,如果一次性添加多个数组,则会直接扩容到原来length+新添加的length。最后调用naive进行数组数据copy。
2、什么情况下你会使用ArrayList?什么时候你会选择LinkedList?
答:如果需要频繁移除或者中间插入这种,arraylist都需要调用arraycopy比较消耗性能,这种时候需要考虑linkedlist,如果只是遍历就用arraylist 查询级别o(1);linkedlist查询虽然做了判断 如果当前index超过一半从后边倒序遍历,但是数据足够大还是o(n)级别。
3,如何复制某个ArrayList到另一个ArrayList中去?写出你的代码?深copy浅copy的问题
答:
1,使用clone()方法,比如ArrayList newArray = oldArray.clone();
2,使用ArrayList构造方法,比如:ArrayList myObject = new ArrayList(myTempObject);
3,使用Collection的copy方法。
注意1和2是浅拷贝(shallow copy)。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。