ArrayList相关

Arraylist与 LinkedList 异同点？ #

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： Arraylist 底层使用的是Object数组；LinkedList 底层使用的是双向循环链表数据结构；
插入和删除是否受元素位置的影响： ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而ArrayList 实现了RandmoAccess 接口，所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用： ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

ArrayList 与 Vector 区别？ #

Vector是线程安全的，ArrayList不是线程安全的。其中，Vector在关键性的方法前面都加了synchronized关键字，来保证线程的安全性。如果有多个线程会访问到集合，那最好是使用 Vector，因为不需要我们自己再去考虑和编写线程安全的代码。
ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍，这样ArrayList就有利于节约内存空间。

ArrayList 的扩容机制？ #

ArrayList的容量可以随着元素的增加而自动增加，因此不用担心ArrayList容量不足的问题。

基本概念 #

先来明确一下ArrayList源码中的一些概念。

// 默认的容量大小（常量）
private static final int DEFAULT_CAPACITY = 10;

// 定义的空数组（final修饰，大小固定为0）
private static final Object[] EMPTY_ELEMENTDATA = {};

// 定义的默认空容量的数组（final修饰，大小固定为0）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 定义的不可被序列化的数组，实际存储元素的数组
transient Object[] elementData; 

// 数组中元素的个数
private int size;

//数组元素个数的最大值
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList有三种构造方法:

无参的构造方法
根据传入的数值大小，创建指定长度的数组
通过传入Collection元素列表进行生成

无参构造方法 #

// 无参的构造方法
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/*
可以看出来，当我们直接创建ArrayList时，elementData被赋予了默认空容量的数组。注意，因为默认空容量数组是被final修饰的，此时ArrayList数组是空的、固定长度的，也就是说其容量此时是0，元素个数size为默认值0。
*/

创建指定长度的构造方法 #

// 传容量的构造方法
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);
    }
}
/*
当initialCapacity > 0时，会在堆上new一个大小为initialCapacity的数组，然后将其引用赋给elementData，此时ArrayList的容量为initialCapacity，元素个数size为默认值0。
当initialCapacity = 0时，elementData被赋予了默认空数组，因为其被final修饰了，所以此时ArrayList的容量为0，元素个数size为默认值0。
当initialCapacity < 0时，会抛出异常。
*/

通过传入Collection元素列表进行生成 #

// 传入Collection元素列表的构造方法
public ArrayList(Collection<? extends E> c) {
    // 将列表转化为对应的数组
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 此处见下面详细解析
        //如果存储的数组不是Object类型的，就要再次进行复制。
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 赋予空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
/*
传入Collection元素列表后，构造方法首先会将其转化为数组，将其索引赋给elementData。
如果此数组的长度为0，会重新赋予elementData为空数组，此时ArrayList的容量是0，元素个数size为0。
如果此数组的长度大于0，会更新size的大小为其长度，也就是元素的个数，然后执行里面的程序。大家对里面的代码可能不理解，让我们等会看下面解析。执行完后此时ArrayList的容量为传入序列的长度，也就是size的大小，同时元素个数也为size，也就是说，此时ArrayList是满的。
*/

可以通过下面的代码来理解 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class);

import java.util.Arrays;

public class Demo {
    public static void main(String[] args) {
        // 1.创建Student对象数组
        String[] students = new String[] {"小明", "小李", "小张"};
        // 2.将其赋值给Object对象数组
        Object[] objects = students;
        // 3.执行if语句前，打印数组的class
        System.out.println("执行前：" + objects.getClass());
        // 4.执行上面的代码
        if (objects.getClass() != Object[].class) {
            objects = Arrays.copyOf(objects, objects.length, Object[].class);
        }
        // 5.执行if语句后，打印数组的class
        System.out.println("执行后：" + objects.getClass());
    }
}

运行结果：

可以看到，对象数组也是有.class的，其中含有所存储元素的类型，而上面的那段代码的作用就是将原对象数组的数组类型转化为Object对象数组的数组类型，以便更好的存储。

扩容机制 #

JDK1.7之前ArrayList默认大小是10，JDK1.7之后是默认大小是0，JDK差异，每次约按1.5倍扩容。

public boolean add(E e) {
    //判断是否可以容纳e，若能，则直接添加在末尾；若不能，则进行扩容，然后再把e添加在末尾
    ensureCapacityInternal(size + 1);  
    //将e添加到数组末尾
    elementData[size++] = e;
    return true;
    }

// 每次在add()一个元素时，arraylist都需要对这个list的容量进行一个判断。通过ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储新元素的能力，经过处理之后将元素存储在数组elementData的尾部

private void ensureCapacityInternal(int minCapacity) {
    //minCapacity：列表目前至少需要size+1个元素
      ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //默认容量=10，minCapacity=size+1，可能大于/小于默认容量。
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
  private void ensureExplicitCapacity(int minCapacity) {
      // 存储了列表的修改次数
        modCount++;
        // 若ArrayList数组长度满足最低存储要求，则返回add直接添加元素；如果数组的存储能力>ArrayList已有的存储能力，这就表示ArrayList的存储能力不足，因此需要调用 grow();方法进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

//注意扩容的一些细节。。。
private void grow(int minCapacity) {
        // 获取elementData数组的内存空间长度
        int oldCapacity = elementData.length;
        // 扩容至原来的1.5倍，oldCapacity >> 1相当于 oldCapacity/2，但是运算速度更快。
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //校验容量是否够
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //若预设值大于默认的最大值，检查是否溢出
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 调用Arrays.copyOf方法将elementData数组指向新的内存空间
         //并将elementData的数据复制到新的内存空间
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

//如果容量大于 MAX_ARRAY_SIZE ，新的容量就用 Integer.MAX_VALUE
//不用再判断是否会大于 Integer.MAX_VALUE，因为 int 类型的最大值就是这么大
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

Array 和 ArrayList 有什么区别？什么时候该应该用 Array 而不用ArrayList 呢？ #

Array 可以包含基本类型和对象类型，ArrayList 只能包含对象类型。
Array 大小是固定的，ArrayList 的大小是动态变化的。
ArrayList 提供了更多的方法和特性，比如：addAll()，removeAll()，iterator() 等等。
数组转列表可以用 Arrays.asList(),列表转数组可以用 list.toArray()，