1、ArrayList

ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

（1）默认数组长度

    private static final int DEFAULT_CAPACITY = 10;

（2）数据存储结构

transient Object[] elementData; // non-private to simplify nested class access

数组一旦初始化，则不能修改数据的长度。

可调整大小的数组。

（3）支持随机访问

如何判断是否支持随机访问？

是随机访问快还是顺序访问快？

public interface RandomAccess {
}

随机访问和顺序访问测试：

public class ListRandom {
    public static void main(String[] args) {

        //-- 创建list
        ArrayList<String> list = new ArrayList<String>();
        for (int i = 0; i < 1000000; i++) {
            list.add("list"+i);
        }

        //-- 随机访问
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {
            String msg = list.get(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("随机访问时间："+(endTime-startTime));

        //-- 顺序访问
        startTime = System.currentTimeMillis();
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String msg = iterator.next();
        }
        endTime = System.currentTimeMillis();
        System.out.println("顺序访问时间："+(endTime-startTime));
    }
}

判单是否支持随机访问：

public class ListRandomChoice {

    public static void main(String[] args) {

        //-- 创建list
        ArrayList<String> list = new ArrayList<String>();
        for (int i = 0; i < 1000000; i++) {
            list.add("list"+i);
        }

        //-- 判断
        if(list instanceof RandomAccess) {
            //-- 随机访问
            for (int i = 0; i < list.size(); i++) {
                String msg = list.get(i);
            }
        }
        else {
            //-- 顺序访问
            Iterator<String> iterator = list.iterator();
            while (iterator.hasNext()) {
                String msg = iterator.next();
            }
        }
    }
}

（4）支持拷贝

深拷贝实现

public interface Cloneable {
}

（5）支持序列化

public interface Serializable {
}

（6）扩容机制

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

代码说明：

>>:右移，右移几位就相当于除以2的几次幂
<<:左移，左移几位就相当于乘以2的几次幂

扩容的核心算法：新容量是原容量的1.5倍

int newCapacity = oldCapacity + (oldCapacity >> 1);

（7）面试常见问题

• ArrayList是如何扩容的？
• ArrayList频繁扩容导致添加性能急剧下降，如何处理？
• ArrayList插入或者删除元素一定比LinkList慢吗？
• ArrayList是线程安全的么?
• 如何复制某个ArrayList到另一个ArrayList中去?
• 已知成员变量集合存储N多用户名称，在多线程的环境下，使用迭代器在读取集合数据的同时如何保证还可以正常的写入数据到集合?
• ArrayList和LinkList区别?