ArrayList和CopyOnWriteArrayList面试题总结与源码分析

须臾之余

发布于 2019-07-19 16:59:39

1.7K0

发布于 2019-07-19 16:59:39

面试题

（1）ArrayList和CopyOnWriteArrayList的增删改查实现原理？ （2）为什么说ArrayList查询快而增删慢？ （3）弱一致性的迭代器原理是怎么样的？ （4）CopyOnWriteArrayList为什么并发安全且性能比Vector好？

（1）ArrayList和CopyOnWriteArrayList的增删改查实现原理？

ArrayList类图

CopyOnWriteArrayList类图

1.List接口

首先我们来看List接口，如上因为ArrayList和CopyOnWriteArrayList都是实现了List接口，所有查看其相应的方法即可。

2.ArrayList的几个重点

1、底层是数组，初始化大小为10 2、插入时会判断数组容量是否足够，不够的化会进行扩容 3、所谓扩容就是新建一个数组，然后将老的数据里面的元素复制到新的数组里面 4、移除元素的时候也涉及到数组中元素的移动，删除指定index位置的元素，然后将index+1至数组最后一个元素往前移动一格

2.2增删改查

1.增

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!! //——进行数组扩容，不够就扩容
    elementData[size++] = e;
    return true;
}

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index); //——检查是否越界

    ensureCapacityInternal(size + 1);  // Increments modCount!! //——进行数组容量判断，不够就扩容
    System.arraycopy(elementData, index, elementData, index + 1, //——将index至数据最后一个元素整体往后移动一格，然后插入新的元素
                     size - index);
    elementData[index] = element;
    size++;
}

2.删

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    rangeCheck(index); //——判断是否越界

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0) //——若该元素不是最后一个元素的话，将index+1至数组最后一个元素整体向前移动一格
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If the list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * <tt>i</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns <tt>true</tt> if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return <tt>true</tt> if this list contained the specified element
 */
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 remove method that skips bounds checking and does not
 * return the value removed.
 */
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
}

3.改

public E set(int index, E e) {
    rangeCheck(index);
    checkForComodification();
    E oldValue = ArrayList.this.elementData(offset + index);
    ArrayList.this.elementData[offset + index] = e; //——将数组对应的index的元素进行替换
    return oldValue;
}

4.查

public E get(int index) {
    rangeCheck(index); //——进行数组越界判断
    checkForComodification();
    return ArrayList.this.elementData(offset + index); //——获取数组对应的index元素
}

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

总结

（2）为什么说ArrayList查询快而增删慢？

以上部分就是ArrayList的增删改查原理，以此就可以解决我们的第二个问题了。 ArrayList底层是数组，所以查询的时候直接根据索引可以很快地找到对应地元素，改也是如此，找到index对应元素进行替换。而增加和删除就涉及到数组元素地移动，所以会比较慢。

CopyOnWriteArrayList几个关键点

1、实现了List接口 2、内部持有一个ReentrantLock lock=new ReentrantLock() 3、底层是用volatile transient声明地数组 array 4、读写分离，写时复制出一个新地数组，完成插入、修改或者移除操作后将新数组赋值给array

增删改查

1.增

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock(); //——获得锁?
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1); //——复制一个新的数组
        newElements[len] = e; //——插入新的值
        setArray(newElements); //——将新的数组指向原来的引用
        return true;
    } finally {
        lock.unlock(); //——释放锁?
    }
}

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock(); //——获取锁?
    try {
        Object[] elements = getArray();
        int len = elements.length;
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            newElements = new Object[len + 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        newElements[index] = element;
        setArray(newElements);
    } finally {
        lock.unlock(); //——释放锁?
    }
}

如上代码可知：新数组的大小是原来数组大小增加1，所以CopyOnWriteArrayList是无界list。

2.删

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).  Returns the element that was removed from the list.
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    lock.lock(); //——获得锁?
    try {
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1)); //——如果删除的元素是最后一个，直接复制该元素前的所有元素到新的数组
        else {
            Object[] newElements = new Object[len - 1]; //——创建新的数组
            //——将index+1至最后一个元素像前移动一格
            System.arraycopy(elements, 0, newElements, 0, index); 
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {
        lock.unlock(); //——释放锁?
    }
}

3.改

/**
 * Replaces the element at the specified position in this list with the
 * specified element.
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock(); //——获取独占锁?
    try {
        Object[] elements = getArray();
        E oldValue = get(elements, index);

        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len); //——创建一个新的数组
            newElements[index] = element; //——替换元素
            setArray(newElements); //——将新数组指向原来的引用
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock(); //——释放锁?
    }
}

4.查

private E get(Object[] a, int index) {
    return (E) a[index];
}

/**
 * {@inheritDoc}
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    return get(getArray(), index);
}

final Object[] getArray() {
    return array;
}

如上代码，当线程x调用get方法获取指定位置元素时，分两步走，首先获得array数组（步骤A），然后通过下标访问指定位置的元素（步骤B），整个过程没用加锁。由于步骤A和步骤B没用加锁，这就可能导致在线程X执行完步骤A后执行步骤B前，另外一个线程Y进行了remove操作，假设删除元素1，这时候线程开始执行步骤B，步骤B操作的数组是线程Y删除元素之前的数组，所以虽然线程Y已经删除了index元素，但是线程X的步骤B还是会返回index处的元素，这其实就是写时复制策略产生的弱一致性问题。

总结

从以上的增删改查中我们可以发现，增删改都需要获得锁，并且锁只有一把，而读操作不需要获得锁，支持并发读。 为什么增删改中都需要创建一个新的数组，操作完成之后再赋值给原来的引用？ 这是为了保证get的时候，都能获取到元素，如果在增删改的过程直接修改原来的数组，可能会造成执行读操作获取不到数据。

（3）弱一致性的迭代器原理是怎么样的？

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

public Spliterator<E> spliterator() {
    return Spliterators.spliterator
        (getArray(), Spliterator.IMMUTABLE | Spliterator.ORDERED);
}

static final class COWIterator<E> implements ListIterator<E> {
    /** Snapshot of the array */
    private final Object[] snapshot; //——array的快照版本
    /** Index of element to be returned by subsequent call to next.  */
    private int cursor; //——数组下标

    private COWIterator(Object[] elements, int initialCursor) { //——构造函数
        cursor = initialCursor;
        snapshot = elements;
    }

    public boolean hasNext() { //——是否遍历结束
        return cursor < snapshot.length;
    }

    public boolean hasPrevious() {
        return cursor > 0;
    }

    @SuppressWarnings("unchecked")
    public E next() { //——获取元素
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }

如上代码中，再调用iterator()方法获取迭代器时实际上会返回一个COWIterator对象，COWIterator对象的snapshot变量保存了当前list的内容，cursor是遍历list数组元素的下标为什么说snapshot是list的快照呢？如果在该线程使用返回的迭代器遍历元素的过程中，其它线程没用对list 进行增删改，那么snapshot本身就是list的array，因为他们是引用关系。但是如果在遍历期间其它线程对该list进行增删改，那么snapshot就是快照了，因为增删改后list里面的数组被新数组替换了，这时候老数组被snapshot引用。这也说明获取迭代器元素时，其它线程对list进行增删改不可见，因为他们操作的是两个不同的数组，这就是弱一致性。

下面通过一个例子来演示多线程下迭代器的弱一致性的效果

public class copyList {
    private static volatile CopyOnWriteArrayList<String>arrayList=new CopyOnWriteArrayList<>();

    public static void main(String[] args) throws InterruptedException {
        arrayList.add("hello");
        arrayList.add("alibaba");
        arrayList.add("to");
        arrayList.add("hangzhou");

        Thread thread = new Thread(() -> {
            arrayList.set(1, "baba"); //——修改元素
            arrayList.remove(1); //——删除元素
            arrayList.remove(2);
        });
        Iterator<String> iterator = arrayList.iterator(); //——保证在修改线程启动前获取迭代器
        thread.start(); //——启动线程
        thread.join(); //——等待子线程执行完毕
        while (iterator.hasNext()){ //——迭代元素
            System.out.println(iterator.next());
        }
    }
}

输出结果

hello alibaba to hangzhou
如上代码中，main函数首先初始化了arrayList，然后再启动线程前获取到了arrayList迭代器。子线程thread启动后首先修改了arrayList的第一个元素的值，然后删除了arrayList对应下标的元素。主线程在子线程执行完毕后使用获取的迭代器遍历数组元素，从结果可知，子线程的操作一个都没有生效，这就是迭代器的弱一致性的体现。需要注意的是，获取迭代器的操作需要在子线程操作之前进行。

（4）CopyOnWriteArrayList为什么并发安全且性能比Vector好？

我们知道Vector是增删改查方法都加了synchronized，保证同步，但是每个方法执行的时候都要去获取锁，性能就会大大降低，而CopyOnWriteArrayList只是在增删改上加ReentrantLock独占锁，但是读操作不加锁，支持并发读，CopyOnWriteArrayList支持读多写少的情况。

参考书籍

Java并发编程之美

参考链接

https://www.jianshu.com/p/c046b7f31228

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

java

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

java

登录后参与评论

0 条评论

热度

ArrayList和CopyOnWriteArrayList面试题总结与源码分析

ArrayList和CopyOnWriteArrayList面试题总结与源码分析

面试题

（1）ArrayList和CopyOnWriteArrayList的增删改查实现原理？

（2）为什么说ArrayList查询快而增删慢？

（3）弱一致性的迭代器原理是怎么样的？

（4）CopyOnWriteArrayList为什么并发安全且性能比Vector好？

参考书籍

参考链接

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐