共计 18567 个字符，预计需要花费 47 分钟才能阅读完成。
概述 Collection 接口是集合类的根接口，Java 中没有提供这个接口的直接的实现类。但是却让其被继承产生了两个接口，就是 Set 和 List。Set 中不能包含重复的元素。List 是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式。
1.Set（无序、不可重复）Set 集合类似于一个罐子，” 丢进 ”Set 集合里的多个对象之间没有明显的顺序。Set 继承自 Collection 接口，不能包含有重复元素。Set 判断两个对象相同不是使用 ”==” 运算符，而是根据 equals 方法。也就是说，我们在加入一个新元素的时候，如果这个新元素对象和 Set 中已有对象进行 equals 比较都返回 false，则 Set 就会接受这个新元素对象，否则拒绝。如果希望遍历 Set 集合中的元素只能调用其 iterator 方法，通过返回的 Iterator 对象来完成。1.1 HashSetHashSet 是底层通过 HashMap 实现, 为快速查找设计的 Set。存入 HashSet 的对象必须定 hashCode()，HashSet 使用 HASH 算法来存储集合中的元素，因此具有良好的存取和查找性能。当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode()方法来得到该对象的 hashCode 值，然后根据该 HashCode 值决定该对象在 HashSet 中的存储位置。值得注意的是，HashSet 集合判断两个元素相等的标准是两个对象通过 equals()方法比较相等，并且两个对象的 hashCode()方法的返回值相等 1.2 TreeSetTreeSet 是依靠 TreeMap 来实现的。TreeSet 集合底层数据结构是红黑树（自平衡二叉查找树）。TreeSet 的本质是一个”有序的，并且没有重复元素”的集合，而且支持自定义排序。2.List（有序、可重复）List 集合代表一个元素有序、可重复的集合，集合中每个元素都有其对应的顺序索引。List 集合允许加入重复元素，因为它可以通过索引来访问指定位置的集合元素。List 集合默认按元素的添加顺序设置元素的索引
2.1 LinkedList 概括的说，LinkedList 是线程不安全的，允许元素为 null 的双向链表。因其底层数据结构是链表，所以可想而知，它的增删只需要移动指针即可，故时间效率较高。不需要批量扩容，也不需要预留空间，所以空间效率比 ArrayList 高。缺点就是需要随机访问元素时，时间效率很低，虽然底层在根据下标查询 Node 的时候，会根据 index 判断目标 Node 在前半段还是后半段，然后决定是顺序还是逆序查询，以提升时间效率。不过随着 n 的增大，总体时间效率依然很低。构造方法
// 集合元素数量
transient int size = 0;
// 链表头节点
transient Node<E> first;
// 链表尾节点
transient Node<E> last;
// 啥都不干
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
对比 JDK1.6 构造方法
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
public LinkedList() {
header.next = header.previous = header;
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
可以看出在 1.7 之前 LinkedList 是双向循环链表，在这之后，因为不再使用 header 节点，所以默认构造方法什么也不做，first 和 last 会被默认初始化为 null。
节点 Node 结构
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;
}
}
增加 1 addAll
//addAll , 在尾部批量增加
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);// 以 size 为插入下标，插入集合 c 中所有元素
}
// 以 index 为插入下标，插入集合 c 中所有元素
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);// 检查越界 [0,size] 闭区间
Object[] a = c.toArray();// 拿到目标集合数组
int numNew = a.length;// 新增元素的数量
if (numNew == 0)// 如果新增元素数量为 0，则不增加，并返回 false
return false;
Node<E> pred, succ; //index 节点的前置节点，后置节点
if (index == size) {// 在链表尾部追加数据
succ = null; //size 节点（队尾）的后置节点一定是 null
pred = last;// 前置节点是队尾
} else {
succ = node(index);// 取出 index 节点，作为后置节点
pred = succ.prev; // 前置节点是，index 节点的前一个节点
}
for (Object o : a) {// 遍历要添加的节点。
@SuppressWarnings(“unchecked”) E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);// 以前置节点 和 元素值 e，构建 new 一个新节点，
if (pred == null) // 如果前置节点是空，说明是头结点
first = newNode;
else// 否则 前置节点的后置节点设置为新节点
pred.next = newNode;
pred = newNode;// 步进，当前的节点为前置节点了，为下次添加节点做准备
}
if (succ == null) {// 循环结束后，判断，如果后置节点是 null。说明此时是在队尾 append 的。
last = pred; // 则设置尾节点
} else {
pred.next = succ; // 否则是在队中插入的节点，更新前置节点 后置节点
succ.prev = pred; // 更新后置节点的前置节点
}
size += numNew; // 修改数量 size
modCount++; // 修改 modCount
return true;
}
// 根据 index 查询出 Node，
Node<E> node(int index) {
// assert isElementIndex(index);
// 通过下标获取某个 node 的时候，（增、查），会根据 index 处于前半段还是后半段 进行一个折半，以提升查询效率
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size – 1; i > index; i–)
x = x.prev;
return x;
}
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size; // 插入时的检查，下标可以是 size [0,size]
}
小结：
为什么添加新节点只是让前一个节点的 next 指向新节点？链表批量增加，是靠 for 循环遍历原数组，依次执行插入节点操作。通过下标获取某个 node 的时候，并不是只能从头到尾查询，因为同时存储了头节点和尾节点，会根据 index 处于前半段还是后半段进行一个折半查找，以提升查询效率 2 插入单个节点 add// 在尾部插入一个节点：add
public boolean add(E e) {
linkLast(e);
return true;
}
// 在指定下标，index 处，插入一个节点
public void add(int index, E element) {
checkPositionIndex(index);// 检查下标是否越界[0,size]
if (index == size)// 在尾节点后插入
linkLast(element);
else// 在中间插入
linkBefore(element, node(index));
}
// 生成新节点 并插入到 链表尾部，更新 last/first 节点。
void linkLast(E e) {
final Node<E> l = last; // 记录原尾部节点
final Node<E> newNode = new Node<>(l, e, null);// 以原尾部节点为新节点的前置节点
last = newNode;// 更新尾部节点
if (l == null)// 若原链表为空链表，需要额外更新头结点
first = newNode;
else// 否则更新原尾节点的后置节点为现在的尾节点（新节点）
l.next = newNode;
size++;// 修改 size
modCount++;// 修改 modCount
}
// 在 succ 节点前，插入一个新节点 e
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 保存后置节点的前置节点
final Node<E> pred = succ.prev;
// 以前置和后置节点和元素值 e 构建一个新节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 新节点 new 是原节点 succ 的前置节点
succ.prev = newNode;
if (pred == null)// 如果之前的前置节点是空，说明 succ 是原头结点。所以新节点是现在的头结点
first = newNode;
else// 否则构建前置节点的后置节点为 new
pred.next = newNode;
size++;// 修改数量
modCount++;// 修改 modCount
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
删除
// 删：remove 目标节点
public E remove(int index) {
checkElementIndex(index);// 检查是否越界 下标[0,size)
return unlink(node(index));// 从链表上删除某节点
}
// 删：remove 元素值
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
// 从链表上删除 x 节点
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item; // 当前节点的元素值
final Node<E> next = x.next; // 当前节点的后置节点
final Node<E> prev = x.prev;// 当前节点的前置节点
if (prev == null) {// 如果前置节点为空(说明当前节点原本是头结点)
first = next; // 则头结点等于后置节点
} else {
prev.next = next;
x.prev = null; // 将当前节点的 前置节点置空
}
if (next == null) {// 如果后置节点为空（说明当前节点原本是尾节点）
last = prev; // 则 尾节点为前置节点
} else {
next.prev = prev;
x.next = null;// 将当前节点的 后置节点置空
}
x.item = null; // 将当前元素值置空
size–; // 修改数量
modCount++; // 修改 modCount
return element; // 返回取出的元素值
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 下标[0,size)
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size–;
modCount++;
return element;
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size–;
modCount++;
return element;
}
修改
public E set(int index, E element) {
checkElementIndex(index); // 检查越界[0,size)
Node<E> x = node(index);// 取出对应的 Node
E oldVal = x.item;// 保存旧值 供返回
x.item = element;// 用新值覆盖旧值
return oldVal;// 返回旧值
}
改也是先根据 index 找到 Node，然后替换值，改不修改 modCount
查找
// 根据 index 查询节点
public E get(int index) {
checkElementIndex(index);// 判断是否越界 [0,size)
return node(index).item; // 调用 node()方法 取出 Node 节点，
}
// 根据节点对象，查询下标
public int indexOf(Object o) {
int index = 0;
if (o == null) {// 如果目标对象是 null
// 遍历链表
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {//// 遍历链表
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
从尾至头遍历链表，找到目标元素值为 o 的节点
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index–;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index–;
if (o.equals(x.item))
return index;
}
}
return -1;
}
toArray()
public Object[] toArray() {
//new 一个新数组 然后遍历链表，将每个元素存在数组里，返回
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
队列操作
// 返回头结点，但不删除
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
// 返回头结点，但不删除
public E element() {
return getFirst();
}
// 返回头结点并移除
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// 删除头结点并返回
public E remove() {
return removeFirst();
}
// 添加指定元素在集合末尾
public boolean offer(E e) {
return add(e);
}
双端队列操作
// 在集合头部插入元素
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
// 在集合尾部插入元素
public boolean offerLast(E e) {
addLast(e);
return true;
}
// 得到集合第一个元素
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
// 得到集合最后一个元素但不删除
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
// 得到并移除第一个元素
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// 得到并移除最后一个元素
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
// 在集合头部插入元素
public void push(E e) {
addFirst(e);
}
// 得到并删除第一个元素，如果为空抛出异常
public E pop() {
return removeFirst();
}
迭代器操作
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
从上面可以看到三者的关系是 iterator()——>listIterator(0)——>listIterator(int index)。最终都会调用 listIterator(int index)方法，其中参数表示迭代器开始的位置。ListIterator 是一个可以指定任意位置开始迭代，并且有两个遍历方法。下面直接看 ListItr 的实现：
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;// 保存当前 modCount，确保 fail-fast 机制
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);// 得到当前索引指向的 next 节点
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
// 获取下一个节点
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
// 获取前一个节点，将 next 节点向前移
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex–;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex – 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex–;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
}
在 ListIterator 的构造器中，得到了当前位置的节点，就是变量 next。next()方法返回当前节点的值并将 next 指向其后继节点，previous()方法返回当前节点的前一个节点的值并将 next 节点指向其前驱节点。由于 Node 是一个双端节点，所以这儿用了一个节点就可以实现从前向后迭代和从后向前迭代。另外在 ListIterator 初始时，exceptedModCount 保存了当前的 modCount，如果在迭代期间，有操作改变了链表的底层结构，那么再操作迭代器的方法时将会抛出 ConcurrentModificationException。
其他
public boolean contains(Object o) {
return indexOf(o) != -1;
}
// 返回一个浅拷贝 LinkedList 对象
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into “virgin” state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
private LinkedList<E> superClone() {
try {
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
public void clear() {
for (Node<E> x = first; x != null;) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
2.2 ArrayListArrayList 是一个动态数组，它是线程不安全的，允许元素为 null。因其底层数据结构是数组，所以可想而知，它是占据一块连续的内存空间（容量就是数组的 length），所以它也有数组的缺点，空间效率不高。由于数组的内存连续，可以根据下标以 O(1)的时间读写 (改查) 元素，因此时间效率很高。当集合中的元素超出这个容量，便会进行扩容操作。扩容操作也是 ArrayList 的一个性能消耗比较大的地方，所以若我们可以提前预知数据的规模，应该通过 public ArrayList(int initialCapacity) {}构造方法，指定集合的大小，去构建 ArrayList 实例，以减少扩容次数，提高效率。或者在需要扩容的时候，手动调用 public void ensureCapacity(int minCapacity) {}方法扩容。构造方法
// 默认构造函数里的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存储集合元素的底层实现：真正存放元素的数组
transient Object[] elementData;
// 当前元素数量
private int size;
// 默认构造方法
public ArrayList() {
// 默认构造方法只是简单的将 空数组赋值给了 elementData
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 带初始容量的构造方法
public ArrayList(int initialCapacity) {
// 如果初始容量大于 0，则新建一个长度为 initialCapacity 的 Object 数组.
// 注意这里并没有修改 size(对比第三个构造函数)
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {// 如果容量为 0，直接将 EMPTY_ELEMENTDATA 赋值给 elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {// 容量小于 0，直接抛出异常
throw new IllegalArgumentException(“Illegal Capacity: “+
initialCapacity);
}
}
// 利用别的集合类来构建 ArrayList 的构造函数
public ArrayList(Collection<? extends E> c) {
// 直接利用 Collection.toArray()方法得到一个对象数组，并赋值给 elementData
elementData = c.toArray();
// 因为 size 代表的是集合元素数量，所以通过别的集合来构造 ArrayList 时，要给 size 赋值
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)// 这里是当 c.toArray 出错，没有返回 Object[]时，利用 Arrays.copyOf 来复制集合 c 中的元素到 elementData 数组中
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 如果集合 c 元素数量为 0，则将空数组 EMPTY_ELEMENTDATA 赋值给 elementData
this.elementData = EMPTY_ELEMENTDATA;
}
}
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
常用 API1 增加每次 add 之前，都会判断 add 后的容量，是否需要扩容。
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;// 在数组末尾追加一个元素，并修改 size
return true;
}
private static final int DEFAULT_CAPACITY = 10;// 默认扩容容量 10
private void ensureCapacityInternal(int minCapacity) {
// 利用 == 可以判断数组是否是用默认构造函数初始化的
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity – elementData.length > 0)
grow(minCapacity);
}
// 需要扩容的话，默认扩容一半
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);// 默认扩容一半
if (newCapacity – minCapacity < 0)// 如果还不够，那么就用 能容纳的最小的数量。（add 后的容量）
newCapacity = minCapacity;
if (newCapacity – MAX_ARRAY_SIZE > 0) // 若 newCapacity 大于最大存储容量，则进行大容量分配
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);// 拷贝，扩容，构建一个新数组，
}
// 大容量分配，最大分配 Integer.MAX_VALUE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // 确认是否需要扩容
System.arraycopy(a, 0, elementData, size, numNew);// 复制数组完成复制
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);// 越界判断
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);// 确认是否需要扩容
int numMoved = size – index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);// 移动（复制)数组
System.arraycopy(a, 0, elementData, index, numNew);// 复制数组完成批量赋值
size += numNew;
return numNew != 0;
}
add、addAll 先判断是否越界，是否需要扩容，如果扩容，就复制数组，然后设置对应下标元素值。
值得注意的是：
如果需要扩容的话，默认扩容一半。如果扩容一半不够，就用目标的 size 作为扩容后的容量。在扩容成功后，会修改 modCount。扩容操作会导致数组复制，批量删除会导致找出两个集合的交集，以及数组复制操作，因此，增、删都相对低效。而 改、查都是很高效的操作。Vector 的内部也是数组做的，区别在于 Vector 在 API 上都加了 synchronized 所以它是线程安全的，以及 Vector 扩容时，是翻倍 size，而 ArrayList 是扩容 50%。2 删除
public E remove(int index) {
rangeCheck(index);// 判断是否越界
modCount++;// 修改 modeCount 因为结构改变了
E oldValue = elementData(index);// 读出要删除的值
int numMoved = size – index – 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);// 用复制 覆盖数组数据
elementData[–size] = null;// 置空原尾部数据 不再强引用
return oldValue;
}
// 根据下标从数组取值 并强转
E elementData(int index) {
return (E) elementData[index];
}
// 删除该元素在数组中第一次出现的位置上的数据。如果有该元素返回 true，如果 false。
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);// 根据 index 删除元素
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// 不会越界 不用判断，也不需要取出该元素。
private void fastRemove(int index) {
modCount++;// 修改 modCount
int numMoved = size – index – 1;// 计算要移动的元素数量
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);// 以复制覆盖元素 完成删除
elementData[–size] = null;// 置空 不再强引用
}
// 批量删除
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);// 判空
return batchRemove(c, false);
}
// 批量移动
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;//w 代表批量删除后 数组还剩多少元素
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement) // 如果 c 里不包含当前下标元素，
elementData[w++] = elementData[r];// 则保留
} finally {
if (r != size) {// 出现异常会导致 r !=size , 则将出现异常处后面的数据全部复制覆盖到数组里。
System.arraycopy(elementData, r,
elementData, w,
size – r);
w += size – r;// 修改 w 数量
}
if (w != size) {// 置空数组后面的元素
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size – w;// 修改 modCount
size = w;// 修改 size
modified = true;
}
}
return modified;
}
可以看出，当用来作为删除元素的集合里的元素多余被删除集合时，也没事，只会删除它们共同拥有的元素。
小结：删除操作一定会修改 modCount，且可能涉及到数组的复制，相对低效。
3 修改不会修改 modCount，相对增删是高效的操作。
public E set(int index, E element) {
rangeCheck(index);// 越界检查
E oldValue = elementData(index); // 取出元素
elementData[index] = element;// 覆盖元素
return oldValue;// 返回元素
}
4 查询不会修改 modCount，相对增删是高效的操作。
public E get(int index) {
rangeCheck(index);// 越界检查
return elementData(index); // 下标取数据
}
E elementData(int index) {
return (E) elementData[index];
}
5 清空 clear 会修改 modCount。
public void clear() {
modCount++;// 修改 modCount
for (int i = 0; i < size; i++) // 将所有元素置 null
elementData[i] = null;
size = 0; // 修改 size
}
6 包含 contain
// 普通的 for 循环寻找值，只不过会根据目标对象是否为 null 分别循环查找。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// 普通的 for 循环寻找值，只不过会根据目标对象是否为 null 分别循环查找。
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
7 迭代器 Iterator.
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // 要返回的下一个元素的索引, 默认是 0
int lastRet = -1; // 上一次返回的元素 (删除的标志位)
int expectedModCount = modCount; // 用于判断集合是否修改过结构的标志
public boolean hasNext() {
return cursor != size;// 游标是否移动至尾部
}
@SuppressWarnings(“unchecked”)
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)// 判断是否越界
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)// 再次判断是否越界，在 我们这里的操作时，有异步线程修改了 List
throw new ConcurrentModificationException();
cursor = i + 1;// 游标 +1
return (E) elementData[lastRet = i];// 返回元素，并设置上一次返回的元素的下标
}
public void remove() {//remove 掉 上一次 next 的元素
if (lastRet < 0)// 先判断是否 next 过
throw new IllegalStateException();
checkForComodification();// 判断是否修改过
try {
ArrayList.this.remove(lastRet);// 删除元素 remove 方法内会修改 modCount 所以后面要更新 Iterator 里的这个标志值
cursor = lastRet; // 要删除的游标
lastRet = -1; // 不能重复删除 所以修改删除的标志位
expectedModCount = modCount;// 更新 判断集合是否修改的标志，
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// 判断是否修改过了 List 的结构，如果有修改，抛出异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
总结 ArrayList 和 Vectorvector 是线程同步的，所以它也是线程安全的，而 arraylist 是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用 arraylist 效率比较高。如果集合中的元素的数目大于目前集合数组的长度时，vector 增长率为目前数组长度的 100%，而 arraylist 增长率为目前数组长度的 50%。如果在集合中使用数据量比较大的数据，用 vector 有一定的优势。如果查找一个指定位置的数据，vector 和 arraylist 使用的时间是相同的，如果频繁的访问数据，这个时候使用 vector 和 arraylist 都可以。而如果移动一个指定位置会导致后面的元素都发生移动，这个时候就应该考虑到使用 linklist, 因为它移动一个指定位置的数据时其它元素不移动。ArrayList 和 Vector 是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要涉及到数组元素移动等内存操作，所以索引数据快，插入数据慢，Vector 由于使用了 synchronized 方法（线程安全）所以性能上比 ArrayList 要差，LinkedList 使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快。ArrayList 和 LinkedListArrayList 是实现了基于动态数组的数据结构，LinkedList 基于链表的数据结构。对于随机访问 get 和 set，ArrayList 优于 LinkedList，因为 LinkedList 要移动指针。对于新增和删除操作 add 和 remove，LinedList 比较占优势，因为 ArrayList 要移动数据。这一点要看实际情况的。若只对单条数据插入或删除，ArrayList 的速度反而优于 LinkedList。但若是批量随机的插入删除数据，LinkedList 的速度大大优于 ArrayList. 因为 ArrayList 每插入一条数据，要移动插入点及之后的所有数据。
