前言

在这个寒风咧咧的互联网寒冬岁月，好不容捞到了一个面试机会的我格外珍惜这个机会，

我今天一定要好好的面试，拿到offer，干掉面试官，朝着美好的未来加油。

当我还沉浸在自己的瞎想中的时候，这个时候面试官进来了。
一个婀娜多姿，戴着眼镜的小姐姐，拿着一个精致的mac，径直走过来坐在我的面前。这就是今天面试官小姐姐吗？今天不要太容易？

你就是今天来面试的同学吗？ 小姐姐的话语打断了我的思绪，让我回到了现实。

正文

面试官：

ArrayList用过吗？ 

我：

用过，
ArrayList 最大的特点就是：有序、可重复、线程不安全。
  
主要用来装载数据，查询效率高，增删效率低，线程不安全。使用频率很高。
	
默认大小：10；扩容机制：1.5倍。
		
	比如我们现在有一个长度为10的数组，现在我们要新增一个元素，发现已经满了，那ArrayList会怎么做呢？第一步他会重新定义一个长度为10+10/2的数组也就是新增一个长度为15的数组。然后把原数组的数据，原封不动的复制到新数组中，这个时候再把指向原数的地址换到新数组，ArrayList就这样完成了一次扩容
	扩容的时候，老版本的jdk和8以后的版本是有区别的，8之后的效率更高了，采用了位运算，右移一位，其实就是除以2这个操作。

面试官：

Arraylist为什么线程不安全？

我：

ArrayList进行添加元素的操作的时候是分两个步骤进行的。多线程，高并发情况下，没有任何同步机制。

面试官：

为什么线程不安全还要用它？？

我：

因为我们正常使用的场景中，都是用来查询，不会涉及太频繁的增删，如果涉及频繁的增删，可以使用LinkedList，如果你需要线程安全就使用Vector，Collections.synchronizedList(new ArrayList<>())，CopyOnWriteArrayList实际开发过程中还是ArrayList使用最多的。
不存在一个集合工具是查询效率又高，增删效率也高的，还线程安全的，因为他们底层用的数据结构是不同的，数据结构的特性就是优劣共存的，想找个平衡点很难，牺牲了性能，那就安全，牺牲了安全那就快速。

面试官：

ArrayList的默认数组大小为什么是10？又为什么是1.5倍扩容呢

我：

ArrayList的默认数组大小为什么是10？
	据说是因为sun的程序员对一系列广泛使用的程序代码进行了调研，结果就是10这个长度的数组是最常用的最有效率的。也有说就是随便起的一个数字

为什么是1.5倍扩容？
	扩容的目的需要综合考虑这两种情况：1. 扩容容量不能太小，防止频繁扩容，频繁申请内存空间 + 数组频繁复制，2. 扩容容量不能太大，需要充分利用空间，避免浪费过多空间；如果采用扩容固定容量，很难决定到底取多少值合适，取任何具体值都不太合适，因为所需数据量往往由数组的客户端在具体应用场景决定。
依赖于当前已经使用的量 * 系数， 比较符合实际应用场景。
	比如，我现在已经用到一个数组100的容量，接下来很可能会有这个数量级的数据需要插入。为什么是1.5，而不是1.2，1.25，1.8或者1.75？因为1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数。

面试官

前面你提到了arrayList的增删效率低，这是为什么呢

我：

add( )
● 对于增加，因为数组在内存中是连续存储的，要想在某个节点之前增加，且保持增加后数组的线性与完整性，必须要把此节点往后的元素依次后移。要是操作的是一个几百几千几万大小的List新增，那就需要后面所有的元素都复制，然后如果再涉及到扩容啥的就更慢了。
delete( )
● 对于删除，和增加是一样的原理

面试官

初始化 ArrayList 会不会初始化数组大小？

我：

不会初始化数组大小！
	使用ArrayList（int initialCapacity）的时候，只是指定了缓冲区数组的大小， 跟数组的大小size并没有什么关系。所以出现了初始化之后，打印数组的size仍然为0的结果。
	看源码里elementData的注释，elementData作为存储ArrayList元素的数组缓冲区，ArrayList的容量是这个数组缓冲区的长度。注意，这里提到的是容量capacity，而size则是：the size of the ArrayList (the number of elements it contains).数组中包含元素的个数。

面试官

ArrayList的遍历和LinkedList遍历性能比较哪个更好呢

我：

ArrayList的遍历性能优于LInkedList。原因有两点：
1、数组在物理内存上是连续存储的，支持“随机访问”，就是你访问一个a[3]的元素与访问一个a[10000]，使用数组下标访问时，这两个元素的时间消耗是一样的。但是对于链表就不是了，链表也没有下标的概念，只能通过头节点指针，从每一个节点，依次往下找。数组和链表时间复杂度分别是O(1)与O(n)，方式一种是“随机访问”，一种是“顺序访问”。
2、在操作系统内存管理方面也有不同。因为数组与链表的物理存储结构不同，在内存预读方面，内存管理会将连续的存储空间提前读入缓存，所以数组往往会被都读入到缓存中，这样进一步提高了访问的效率。

面试官

LinkedList和ArrayList在尾部插入数据效率 哪个高些？

我：

LinkedList每次增加的时候，会new 一个Node对象来存新增加的元素，所以当数据量小的时候，new 这个对象的时间并不明显，而ArrayList是需要多次扩容的，所以LinkedList的效率就会比较高，当数据量很大的时候，new对象的总体时间时间可能会大于扩容的时间，那么就会出现ArrayList 的效率比Linkedlist高了。

面试官

ArrayList用来做队列合适吗？

我：

不适合，队列一般是FIFO（先入先出）的，如果用ArrayList做队列，就需要在数组尾部追加数据，数组头部删除数组，反过来也可以。但是无论如何总会有一个操作会涉及到数组的数据搬迁，这个是比较耗费性能的。

面试官

那数组适合用来做队列吗？

我：

ArrayList固然不适合做队列，但是数组是非常合适的。比如ArrayBlockingQueue内部实现就是一个环形队列，它是一个定长队列，内部是用一个定长数组来实现的。另外著名的Disruptor开源Library也是用环形数组来实现的超高性能队列，具体原理不做解释，比较复杂。简单点说就是使用两个偏移量来标记数组的读位置和写位置，如果超过长度就折回到数组开头，前提是它们是定长数组。

面试官

ArrayList和Vector的区别

我：

	这两个类都实现了List接口（List接口继承了Collection接口），他们都是有序集合，即存储在这两个集合中的元素的位置都是有顺序的，相当于一种动态的数组，我们以后可以按位置索引号取出某个元素，并且其中的数据是允许重复的，这是与HashSet之类的集合的最大不同处，HashSet之类的集合不可以按索引号去检索其中的元素，也不允许有重复的元素。
ArrayList与Vector的区别主要包括两个方面：.
（1）同步性：Vector是线程安全的 方法上加了synchronized，也就是说是它的方法之间是线程同步的，而ArrayList是线程序不安全的。
（2）数据增长：ArrayList与Vector都有一个初始的容量大小，当存储进它们里面的元素的个数超过了容量时，就需要增加ArrayList与Vector的存储空间，每次要增加存储空间时，Vector默认增长为原来两倍，而ArrayList的增长策略在文档中没有明确规定（从源代码看到的是增长为原来的1.5倍）

面试官

在 foreach 循环里可否进行元素的 remove/add 操作？为什么？

我：

我们使用的增强for循环，其实是Java提供的语法糖，其实现原理是借助Iterator进行元素的遍历。但是如果在遍历过程中，不通过Iterator，而是通过集合类自身的方法对集合进行添加/删除操作。那么在Iterator进行下一次的遍历时，经检测发现有一次集合的修改操作并未通过自身进行，那么可能是发生了并发被其他线程执行的，这时候就会抛出异常，来提示用户可能发生了并发修改，这就是所谓的fail-fast机制。

一番拉扯之后，面试官小姐姐露出了一丝丝微笑，说道：
	前面你也说了ArrayList是线程不安全的，那我项目中要怎么用呢？ 怎么获得一个线程安全的集合呢？ 

copyOnWriteArrayList... 未完待续

附录：扩容源码分析

//添加元素
public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //判断是否第一次添加元素，是则取10与size+1间最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

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

        //如果最小需要空间比elementData的内存空间要大，扩容
        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;
        //若预设值大于默认的最大值检查是否溢出 
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //调用Arrays.copyOf方法将elementData数组指向新的长度为扩容后长度的内存空间
        elementData = Arrays.copyOf(elementData, newCapacity);
    }    

//检查溢出
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }