前言
本文快速回顾了Java中容器的知识点,用作面试复习,事半功倍。
上篇:主要为容器概览,容器中用到的设计模式,List源码
中篇:Map源码
下篇:Set源码,容器总结
容器主要包括 Collection 和 Map 两种,Collection 又包含了 List、Set 以及 Queue。
数组和集合的区别:
https://blog.csdn.net/Kato_op/article/details/80356618
Fail-fast 机制是 java 集合(Collection)中的一种错误机制。 当多个线程对同一个集合的内容进行操作时,就可能会产生 fail-fast 事件。
注意,如果集合发生变化时修改modCount值, 刚好有设置为了expectedmodCount值, 则异常不会抛出.(比如删除了数据,再添加一条数据)
所以,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。
迭代器的快速失败行为应该仅用于检测程序错误, 而不是用他来同步。
java.util包下的集合类都是Fail-Fast机制的,不能在多线程下发生并发修改(迭代过程中被修改).
采用安全失败(Fail-Safe)机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先copy原有集合内容,在拷贝的集合上进行遍历。
原理:
由于迭代时是对原集合的拷贝的值进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会出发ConcurrentModificationException
缺点:
迭代器并不能访问到修改后的内容(简单来说就是, 迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的)
使用场景:
java.util.concurrent包下的容器都是Fail-Safe的,可以在多线程下并发使用,并发修改
Collection 实现了 Iterable 接口,其中的 iterator() 方法能够产生一个 Iterator 对象,通过这个对象就可以迭代遍历 Collection 中的元素。
从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象。
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String item : list) {
System.out.println(item);
}
适配器模式解释:https://www.jianshu.com/p/93821721bf08
java.util.Arrays#asList() 可以把数组类型转换为 List 类型。
@SafeVarargs
public static <T> List<T> asList(T... a)
如果要将数组类型转换为 List 类型,应该注意的是 asList() 的参数为泛型的变长参数,因此不能使用基本类型数组作为参数,只能使用相应的包装类型数组。
Integer[] arr = {1, 2, 3};
List list = Arrays.asList(arr);
也可以使用以下方式生成 List。
List list = Arrays.asList(1,2,3);
实现了 RandomAccess 接口,因此支持随机访问。这是理所当然的,因为 ArrayList 是基于数组实现的。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
如果不够时,需要使用 grow() 方法进行扩容,新容量的大小为 oldCapacity+(oldCapacity>>1)
,也就是旧容量的 1.5 倍。
扩容操作需要调用 Arrays.copyOf()
把原数组整个复制到新数组中
因此最好在创建 ArrayList 对象时就指定大概的容量大小,减少扩容操作的次数。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}
add(E e)
首先去检查一下数组的容量是否足够
扩容到原来的1.5倍,第一次扩容后,如果容量还是小于minCapacity,就将容量扩充为minCapacity。
add(int index, E element)
步骤:
步骤:
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上,复制的代价很高。
看到arraycopy(),我们可以发现:该方法是由C/C++来编写的
modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作,或者是调整内部数组的大小,仅仅只是设置元素的值不算结构发生变化。
在进行序列化或者迭代等操作时,需要比较操作前后 modCount 是否改变,如果改变了需要抛出 ConcurrentModificationException。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
ArrayList 提供了三种方式的构造器:
补充:transient讲解
http://www.importnew.com/21517.html
你只需要实现Serilizable接口,将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目的地中。
ArrayList 基于数组实现,并且具有动态扩容特性,因此保存元素的数组不一定都会被使用,那么就没必要全部进行序列化。
保存元素的数组 elementData 使用 transient 修饰,该关键字声明数组默认不会被序列化。
transient Object[] elementData; // non-private to simplify nested class access
ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法,原理类似。
ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);
可以使用 Collections.synchronizedList();
得到一个线程安全的 ArrayList。
List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);
也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。
List<String> list = new CopyOnWriteArrayList<>();
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();
}
}
final void setArray(Object[] a) {
array = a;
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
}
CopyOnWriteArrayList 在写操作的同时允许读操作,大大提高了读操作的性能,因此很适合读多写少的应用场景。
所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。
基于双向链表实现,内部使用 Node 来存储链表节点信息。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
每个链表存储了 Head 和 Tail 指针:
transient Node<E> first;
transient Node<E> last;
set方法和get方法其实差不多,根据下标来判断是从头遍历还是从尾遍历
LinkedList实现了Deque接口,因此,我们可以操作LinkedList像操作队列和栈一样
LinkedList的方法比ArrayList的方法多太多了,这里我就不一一说明了。具体可参考:
本人目前为后台开发工程师,主要关注Python爬虫,后台开发等相关技术。
原创博客主要内容:
同步更新以下几大博客:
http://blog.csdn.net/qqxx6661
拥有专栏:Leetcode题解(Java/Python)、Python爬虫开发
https://www.zhihu.com/people/yang-zhen-dong-1/
拥有专栏:码农面试助攻手册
https://juejin.im/user/5b48015ce51d45191462ba55
https://www.jianshu.com/u/b5f225ca2376