你对ArrayList了解多少?-白红宇

你对ArrayList了解多少?

阅读量：4005 次

发布时间：2019-05-24

本文共 8860 字，大约阅读时间需要 29 分钟。

1.前言

ArrayList 是我们常用的数据结构，但是你对ArrayList了解有多少了？不妨来考一考自己。

2.ArrayList每日一问（答案见末尾）

（1）jdk1.8ArrayList默认容量是多大？

（2）ArrayList 扩容多大？

（3）ArrayList 是线程安全的吗？为什么？

（4）ArrayList 中 elementData 为什么使用 transient 修饰？

（5）ArrayList list = new ArrayList(20); 中的list扩充几次？

如果你对以上的问题全部都能答对，嗯，确认过眼神，大佬喝茶~

如果没有答对，也不要灰心，我们来一起学一学ArrayList

3.ArrayList底层分析（基于jdk1.8）

面试造火箭，开发拧螺丝，实际我们大多数都是在CRUD，ArrayList也不例外，我们就从ArrayList的CRUD展开

3.1 ArrayList的成员变量

//默认的容量private static final int DEFAULT_CAPACITY = 10;//空数组实例private static final Object[] EMPTY_ELEMENTDATA = {
   };//默认大小的空数组实例，这里有的同学问了，和上面的那个有什么区别吗?//官方解释的是:与上面的实例分开，以至于我们知道何时会添加第一个元素private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
   };//Object数组，也就是ArrayList的底层transient Object[] elementData//大小private int size;

3.2 ArrayList的构造方法

无参的构造方法，这里我们看到无参的构造函数，也就是当我们不给ArrayList的大小时，ArrayList会是一个空数组

//这里我们看到初始了一个空数组    public ArrayList() {
           this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  }

带初始化容量的构造方法

//1.如果初始化的值大于0，直接new一个initialCapacity的Object数组    //2.如果等于0，会是一个上面成员变量中的第一种,EMPTY_ELEMENTDATA    //3.小于0，会跑出IllegalArgumentException异常    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);        }    }

Collection类型的构造器

//1.将Collection的集合转换成数组,ArrayList底层    //2.如果c.toArray()不是一个Object数组，使用Arrays.copyOf方法进行转换    //3.如果c.toArray()的长度等于0，使用自己的成员变量       public ArrayList(Collection
    c) {
           elementData = c.toArray();        if ((size = elementData.length) != 0) {
               if (elementData.getClass() != Object[].class)                elementData = Arrays.copyOf(elementData, size, Object[].class);        } else {
               this.elementData = EMPTY_ELEMENTDATA;        }    }

3.3 ArrayList add方法(分为两种)

直接添加

(1)判断是否个空数组，如果是空数组，就给默认值

(2)判断是否需要扩容

(3)正式扩容

(4)添加元素

//是否需要扩容    //添加元素    public boolean add(E e) {
           ensureCapacityInternal(size + 1);        elementData[size++] = e;        return true;    }             private void ensureCapacityInternal(int minCapacity) {
           ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));    }        //如果elementData，是个空数组的话，minCapacity也就是为1    //这里会取默认的大小：10，类似懒加载，默认是个空数组，当我们    //第一次添加时就会给个默认大小10,      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);    }        //真正的扩容代码    //旧数组容量+旧数组容量右移一位=1.5倍    // 检查新容量的大小是否小于最小需要容量，如果是的，新容量等于最小需要容量    //如果新容量大于MAX_ARRAY_SIZE，使用hugeCapacity比较二者    //使用Arrays.copyOf 进行拷贝        private void grow(int minCapacity) {
           // overflow-conscious code        int oldCapacity = elementData.length;        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);    }        //对minCapacity和MAX_ARRAY_SIZE进行比较    //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小    //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;        private static int hugeCapacity(int minCapacity) {
           if (minCapacity < 0) // overflow            throw new OutOfMemoryError();        return (minCapacity > MAX_ARRAY_SIZE) ?            Integer.MAX_VALUE :            MAX_ARRAY_SIZE;    }

指定位置添加，就好比我们插队一样，需要在中间挪出一个位置才能进去,上面如果理解了，这里就比较好理解，就多了一个判断,判断有没有超过最大值，然后调用System.arraycopy进行拷贝

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));    }

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UOEAi0zc-1597248035484)(http://52jdk.com/ArrayListAdd.png)]

3.4 get方法(两行代码)

第一步判断下表是否越界，第二步直接通过数组下表获取元素

public E get(int index) {
           rangeCheck(index);        return elementData(index);    }              E elementData(int index) {
           return (E) elementData[index];    }

3.5 remove方法(两种方法)

按照下标remove
(1) 判断下标是否越界，如果越界就会直接抛出异常

(2) 在数组中查询该元素

(3)计算需要移动的数目

(4)如果numMoved大于0,说明要删除的元素后面的都需要左移，如果是最后一个元素，则不需要移动

(5)使原数组大小减一，并赋值为空，有利于GC

(6)返回旧的元素

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;    }        //src:源数组       //srcPos:从源数组的srcPos位置处开始移动    //dest:目标数组    //desPos:源数组的srcPos位置处开始移动的元素，这些元素从目标数组的desPos处开始填充    //length:移动源数组的长度    public static native void arraycopy(Object src,  int  srcPos,                                    Object dest, int destPos,                                    int length);

按照元素值来删除，这里也比较好理解，就是先遍历，获取元素的下标，然后利用上面的删除代码进行删除

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    }

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TTmIOap9-1597248035486)(http://52jdk.com/ArrayList%20remove.png)]

3.6 ensureCapacity 方法

这个方法可以在 add 大量元素之前用 ensureCapacity 方法，以减少增量从新分配的次数

public void ensureCapacity(int minCapacity) {
               int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)                // any size if not default element table                ? 0                // larger than default for default empty table. It's already                // supposed to be at default size.                : DEFAULT_CAPACITY;                if (minCapacity > minExpand) {
                   ensureExplicitCapacity(minCapacity);            }        }         private void ensureExplicitCapacity(int minCapacity) {
           modCount++;        // overflow-conscious code        if (minCapacity - elementData.length > 0)            grow(minCapacity);    }

3.7 writeObject和readObject

ArrayList 为什么要定义这两个读写流的方法呢，这就要回到我们第四个问题了，
ArrayList 中 elementData 为什么使用 transient 修饰？

由于 ArrayList 是基于动态数组实现的，所以并不是所有的空间都被使用。因此使用了 transient 修饰，可以防止被自动序列化。

因此 ArrayList 自定义了序列化与反序列化，具体可以看 writeObject 和 readObject 两个方法。

需要注意的一点是，当对象中自定义了 writeObject 和 readObject 方法时，JVM 会调用这两个自定义方法来实现序列化与反序列化。

writeObject 官方解释（意思是：通过流来序列化ArrayList）

/**

* Save the state of the ArrayList instance to a stream (that

* is, serialize it).

* @serialData The length of the array backing the ArrayList

* instance is emitted (int), followed by all of its elements

* (each an Object) in the proper order.

readObject 官方解释 (意思是：通过流来反序列化ArrayList)

/**

* Reconstitute the ArrayList instance from a stream (that is,

* deserialize it).

4.答案

jdk1.8如果不给初始值容量的话，是默认给了一个空数组，也就是0，当在第一次添加时，会重新比较大小，给10的容量

ArrayList 扩容1.5倍，记住右移一位：newCapacity = oldCapacity + (oldCapacity >> 1)

ArrayList不是线程安全的，当我们add添加或者删除时，elementData[size++] = e; elementData[–size] = e; 这两个操作，并不是原子操作，都是分为两步操作

3.7咋们已经分析到了

默认ArrayList的长度是10个，所以如果你要往list里添加20个元素肯定要扩充一次（newCapacity 扩充为原来的1.5倍，但和输入的minCapacity相比发现小于minCapacity，于是 newCapacity = minCapacity，所以只扩容一次，具体见扩容里的grow方法），但是这里显示指明了需要多少空间，所以就一次性为你分配这么多空间，也就是不需要扩充了！