面试——ArrayList

1. 底层研究

1. ArrayList

底层是数组

1. 无参构造

构造一个初始容量为10的空列表

当给空数组链表添加第一个数据的时候，数组链表才会初始化长度

2. 有初始化容量的构造

3. 扩容

2. LinkedList

底层是链表

2. 有用过ArrayList吗？它是做什么用的？

ArrayList就是数组列表，底层是数组
ArrayList在装载基本数据类型时，实际装载的是对应的包装类
与ArrayList类似的还有LinkedList，他们俩相比：

ArrayList：查找和访问元素的速度快，新增、删除的速度慢。线程不安全，使用频率高。查询时间复杂度O(1)
LinkedList：查找和访问元素的速度慢，新增、删除的速度快。查询时间复杂度O(n)

3. ArrayList线程不安全，为什么还要去用？

Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。

实际开发中有以下几种场景：

频繁增删：使用LinkedList，但是涉及到频繁增删的场景不多
追求线程安全：使用Vector
普通的用来查询：使用ArrayList，使用的场景最多

根据数据结构的特性，三者难以全包含，只能在相互之间做取舍

4. ArrayList底层是数组，那是怎么实现不断扩容的？

使用ArrayList空参的构造器创建集合时，数组并没有创建。当集合中添加第一个元素时，数组被创建，初始化容量为10
当数组长度+1>数组容量时，这时需要对数组进行扩容，扩容公式：新长度=原长度+原长度>>1，也就是扩容到了原来的1.5倍

 /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //新容量=旧容量+1/2旧容量
        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);
    }

5. ArrayList(int initialCapacity)会不会初始化数组大小？

会初始化大小，但如果通过ArrayList的size()方法进行判断时结果依然为0，因为只有在添加元素时才会对ArrayList的size属性+1

6. ArrayList1.7之前和1.7及以后的区别？

1.7之前ArrayList在初始化的时候直接调用this(10)，初始化容量为10的数组。
在1.7及以后，只有第一次执行add方法向集合添加元素时才会创建容量为10的数组。

7. 为什么ArrayList增删比较慢，增删是如何做的？

如果没有指定index，添加元素之间追加到数组最后，若容量不够，则需要扩容

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

若指定了index元素

从源码里看到，是将要添加的元素位置index之后的已有元素全部拷贝到添加到原数组index+1处，然后再把新的数据加入。

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

8. ArrayList插入和删除数据一定慢吗？

不一定，取决于删除的数据离数组末端有多远，如果离末端较近，则性能不一定差。

9. ArrayList如何删除数据？

ArrayList删除数据时同样使用拷贝数组的方式，将要删除的位置之后的所有元素拷到当前位置，最后再对最后一个位置的数据设置为null，交给gc来回收。这种删除，其实就是覆盖，如果数据量大，那么效率很低。

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
    }

10. ArrayList适合做队列吗？

队列需要遵循先进先出的原则
如果从ArrayList的数组头部入队列，数组尾部出队列，那么对于入队列时的操作，会涉及大数据量的数组拷贝，十分耗性能。
队头队尾反一反也是一样，因此ArrayList不适合做队列。

11. 数组适合做队列吗？

ArrayBlockingQueue环形队列就是用数组来实现的
ArrayBlockingQueue的存和取操作的索引是在当索引值等于容量值时，将索引值设置为0实现环形队列的效果，因此在这种情况下，数组适合做队列

 /**
     * Inserts element at current put position, advances, and signals.
     * Call only when holding lock.
     */
    private void enqueue(E x) {
        // assert lock.getHoldCount() == 1;
        // assert items[putIndex] == null;
        final Object[] items = this.items;
        items[putIndex] = x;
        if (++putIndex == items.length)
            putIndex = 0;
        count++;
        notEmpty.signal();
    }

    /**
     * Extracts element at current take position, advances, and signals.
     * Call only when holding lock.
     */
    private E dequeue() {
        // assert lock.getHoldCount() == 1;
        // assert items[takeIndex] != null;
        final Object[] items = this.items;
        @SuppressWarnings("unchecked")
        E x = (E) items[takeIndex];
        items[takeIndex] = null;
        if (++takeIndex == items.length)
            takeIndex = 0;
        count--;
        if (itrs != null)
            itrs.elementDequeued();
        notFull.signal();
        return x;
    }