List体系
ArrayList和LinkedList有什么区别？
ArrayList的底层结构是数组， LinkedList的底层结构是双向链表。
ArrayList是怎么扩容的？
当数组长度不够时进行扩容，每次加一半的空间。
private void grow(int minCapacity) {
// overflow-conscious code
// 数组长度
int oldCapacity = elementData.length;
// 容量大小 = 原数组长度 + 原数组长度的0.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新容量发现比需要的容量还小，则以需要的容量为准
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量发现比最大容量还大，则使用最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 拷贝出来原有的数据
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList插入、删除、查询元素的时间复杂度各是多少？
- ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；
- ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；
- ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)；
- ArrayList从尾部删除元素极快，时间复杂度为O(1)；
- ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)；
怎么求两个集合的并集、交集、差集？
- ArrayList支持求并集，调用addAll(Collection<? extends E> c)方法即可；
- ArrayList支持求交集，调用retainAll(Collection<? extends E> c)方法即可；
- ArrayList支持求单向差集，调用removeAll(Collection<? extends E> c)方法即可；
ArrayList是怎么实现序列化和反序列化的？
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// 防止序列化期间有修改
int expectedModCount = modCount;
// 写出非transient非static属性（会写出size属性）
s.defaultWriteObject();
// 写出元素个数
s.writeInt(size);
// 依次写出元素
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
// 如果有修改，抛出异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// 声明为空数组
elementData = EMPTY_ELEMENTDATA;
// 读入非transient非static属性（会读取size属性）
s.defaultReadObject();
// 读入元素个数，没什么用，只是因为写出的时候写了size属性，读的时候也要按顺序来读
s.readInt();
if (size > 0) {
// 计算容量
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
// 检查是否需要扩容
ensureCapacityInternal(size);
Object[] a = elementData;
// 依次读取元素到数组中
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
查看writeObject()方法可知，先调用s.defaultWriteObject()方法，再把size写入到流中，再把元素一个一个的写入到流中。
一般地，只要实现了Serializable接口即可自动序列化，writeObject()和readObject()是为了自己控制序列化的方式，这两个方法必须声明为private，在java.io.ObjectStreamClass#getPrivateMethod()方法中通过反射获取到writeObject()这个方法。
在ArrayList的writeObject()方法中先调用了s.defaultWriteObject()方法，这个方法是写入非static非transient的属性，在ArrayList中也就是size属性。同样地，在readObject()方法中先调用了s.defaultReadObject()方法解析出了size属性。
elementData定义为transient的优势，自己根据size序列化真实的元素，而不是根据数组的长度序列化元素，减少了空间占用。
集合的方法toArray()有什么问题？
返回的有可能不是Object[]类型。
public class ArrayTest {
public static void main(String[] args) {
Father[] fathers = new Son[]{};
// 打印结果为class [Lcom.coolcoding.code.Son;
System.out.println(fathers.getClass());
List<String> strList = new MyList();
// 打印结果为class [Ljava.lang.String;
System.out.println(strList.toArray().getClass());
}
}
class Father {}
class Son extends Father {}
class MyList extends ArrayList<String> {
/**
* 子类重写父类的方法，返回值可以不一样
* 但这里只能用数组类型，换成Object就不行
* 应该算是java本身的bug
*/
@Override
public String[] toArray() {
// 为了方便举例直接写死
return new String[]{"1", "2", "3"};
}
}
什么是fail-fast？
fail-fast机制是java集合中的一种错误机制。
当使用迭代器迭代时，如果发现集合有修改，则快速失败做出响应，抛出ConcurrentModificationException异常。
这种修改有可能是其它线程的修改，也有可能是当前线程自己的修改导致的，比如迭代的过程中直接调用remove()删除元素等。
另外，并不是java中所有的集合都有fail-fast的机制。比如，像最终一致性的ConcurrentHashMap、CopyOnWriterArrayList等都是没有fast-fail的。
fail-fast是怎么实现的？
像ArrayList、HashMap中都有一个属性叫 modCount，每次对集合的修改这个值都会加1，在遍历前记录这个值到 expectedModCount中，遍历中检查两者是否一致，如果出现不一致就说明有修改，则抛出ConcurrentModificationException异常。
LinkedList是单链表还是双链表实现的？
双向链表
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList除了作为List还有什么用处？
双端队列、栈
LinkedList插入、删除、查询元素的时间复杂度各是多少？
- LinkedList在队列首尾添加、删除元素非常高效，时间复杂度为O(1)；
- LinkedList在中间添加、删除元素比较低效，时间复杂度为O(n)；
- LinkedList获取第几个元素，依次遍历，复杂度O(n)
什么是随机访问？
java集合类中元素的访问分为随机访问和顺序访问。随机访问一般是通过index下标访问，行为类似数组的访问。而顺序访问类似于链表的访问，通常为迭代器遍历。以List接口及其实例为例。ArrayList是典型的随机访问型，而LinkedList则是顺序访问型。List接口既定义了下标访问方法又定义了迭代器方法。所以其实例既可使用下标随机访问也可以使用迭代器进行遍历。但这两种方式的性能差异很明显。
哪些集合支持随机访问？他们都有哪些共性？
ArrayList、HashMap、TreeMap和HashTable类提供对元素的随机访问。
CopyOnWriteArrayList是怎么保证并发安全的？
ReentrantLock, 以及 private transient volatile Object[] array 修饰元素。
CopyOnWriteArrayList的实现采用了什么思想？
写入时复制（CopyOnWrite，简称COW）思想是计算机程序设计领域中的一种优化策略。其核心思想是，如果有多个调用者（Callers）同时要求相同的资源（如内存或者是磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者视图修改资源内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的（transparently）。此做法主要的优点是如果调用者没有修改资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。
CopyOnWriteArrayList是不是强一致性的？
不是，CopyOnWriteArrayList只保证最终一致性，不保证实时一致性,因为读写是在两个容器进行的，只有当写操作执行完毕引入指向新容器后，读才能感知到容器的变化。
CopyOnWriteArrayList适用于什么样的场景？
适用于读多写少的场景
CopyOnWriteArrayList插入、删除、查询元素的时间复杂度各是多少？
CopyOnWriteArrayList的写操作都要先拷贝一份新数组，在新数组中做修改，修改完了再用新数组替换老数组，所以空间复杂度是O(n)，性能比较低下；
CopyOnWriteArrayList的读操作支持随机访问，时间复杂度为O(1)；
删除也是空间复杂度是O(n)
CopyOnWriteArrayList为什么没有size属性？
因为每次修改都是拷贝一份正好可以存储目标个数元素的数组，所以不需要size属性了，数组的长度就是集合的大小，而不像ArrayList数组的长度实际是要大于集合的大小的。
比如，add(E e)操作，先拷贝一份n+1个元素的数组，再把新元素放到新数组的最后一位，这时新数组的长度为len+1了，也就是集合的size了。