面试题
（1）ArrayList和CopyOnWriteArrayList的增删改查实现原理？
ArrayList类图
CopyOnWriteArrayList类图
1.List接口
首先我们来看List接口，如上因为ArrayList和CopyOnWriteArrayList都是实现了List接口，所有查看其相应的方法即可。
2.ArrayList的几个重点
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 ? get(i)==null : 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查询快而增删慢？
CopyOnWriteArrayList几个关键点
增删改查
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(); //——释放锁🔒
}
}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;
}总结
（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++];
}下面通过一个例子来演示多线程下迭代器的弱一致性的效果
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());
}
}
}输出结果
（4）CopyOnWriteArrayList为什么并发安全且性能比Vector好？
参考书籍
Java并发编程之美