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了。