这个系列的三将开启集合源码阅读，以及总结java集合api注意点和使用建议。好，废话不多说，开始吧。
本系列以前的文章：
(1) 深入Java基础（一）——基本数据类型及其包装类
(2)深入Java基础（二）——字符串家族
文章结构：（1）集合整体概述；（2）分析Collection继承树；（3）注意点（包括迭代器的使用细节）
一、集合整体概述
这里写图片描述
补充map的继承树，它依赖于collection接口
这里写图片描述
Collection是一个接口，是高度抽象出来的集合，它包含了集合的基本操作和属性。
可以看出 Collection包含了List、Set、Queue三大分支
（1）List：1.代表有序、重复的集合。2.像一个数组，可以记住每次添加元素的顺序（要以对象的形式来理解），且长度是可变的。3.访问的时候根据元素的索引值来访问。
（2）Set：1.代表无序、不可重复的集合。2.就像一个罐子，但元素单独存在。访问元素只能根据元素本身来访问。3.元素不可以重复
（3）Queue：1.代表队列集合。2.直接对应数据结构的队列。3.LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。
（4）Map：1.是一个映射接口，即key-value键值对。Map中的每一个元素包含“一个key”和“key对应的value”。2.AbstractMap是个抽象类，它实现了Map接口中的大部分API。而HashMap，TreeMap，WeakHashMap都是继承于AbstractMap。3. Hashtable虽然继承于Dictionary，但它实现了Map接口。
二、分析Collection继承树：
（1）先来大致看下标记是可遍历的接口：Iterable
Iterable此接口的目的：实现了这个接口的集合对象支持迭代，是可迭代的。而Iterator则是迭代器，它就是提供迭代机制的对象，具体如何迭代，都是Iterator接口规范的。Spliterator就是一个并行遍历的接口。
public interface Iterable<T> {
//这个目的是：返回传来的T类型的元素上的一个迭代器
Iterator<T> iterator();
//这个是Java8的新特性：Default方法是指，在接口内部包含了一些默认的方法实现（也就是接口中可以包含方法体，这打破了Java之前版本对接口的语法限制），从而使得接口在进行扩展的时候，不会破坏与接口相关的实现类代码
/**
翻译哦：
* 对这个Iterable的每一个元素执行给定的动作，直到所有元素都被处理或者动作抛出一个异常
* 为止。除非被实现类指定，动作将以迭代的顺序执行（如果一个迭代的顺序被指定）。被动作
* 抛出的异常将被传递给调用者
*/
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
/**
直译了，再往上的Spliterator接口也就是跟Iterator差不多，不过它是并行遍历的。
Spliterator： https://segmentfault.com/q/1010000007087438
* 创建一个被这个Iterable接口描述的元素上Spliterator。
*
* 默认实现从iterable的Iterator中创建一个早期绑定的spliterator。这个spliterator
* 继承iterable的iterator的fail-fast性质。
*
* 默认实现应该总是被重写。被默认实现返回的spliterator拥有不好分解能力，是不依据指定
* 大小定制的，而且不报告任何spliterator的性质。实现类差不多总是能提供更好的实现。
*/
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
//这个就是迭代器啦
public interface Iterator<E> {
boolean hasNext();//每次next之前，先调用此方法探测是否迭代到终点，判断是否要去下一个
E next(); //返回当前迭代元素 ，同时，迭代游标后移
//删除最近一次已近迭代出出去的那个元素。只有当next执行完后，才能调用remove函数。比如你要删除第一个元素，不能直接调用 remove()而要先next一下( );在没有先调用next 就调用remove方法是会抛出异常的。
default void remove() {
throw new UnsupportedOperationException("remove");
}
//也是1.8后的特性，支持lamdba表达式，主要是遍历游标后面的数据，按照所给的action去呈现，遍历。
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
（2）跟着继承树往下看就是Collection接口啦：
可以看出：一个高度抽象出来的集合，包含了集合的基本操作：添加、删除、清空、遍历、是否为空、获取大小等。Collection接口的所有子类（直接子类和间接子类）都必须实现2种构造函数：不带参数的构造函数和参数为Collection的构造函数。带参数的构造函数可以用来转换Collection的类型。
//这是接口，不是实现的地方，所以是一系列的规范
public interface Collection<E> extends Iterable<E> {
int size();//返回大小的方法
boolean isEmpty();//判空方法
boolean contains(Object o);//判是否存在方法
Iterator<E> iterator();//迭代器
Object[] toArray();//把集合转成数组
<T> T[] toArray(T[] a); //*返回包含此 collection 中所有元素的数组；返回数组的运行时类型与指定数组的运行时类型相同。
boolean add(E e);//加入元素，返回决定失败还是成功
boolean remove(Object o);//同样删除元素，返回决定失败还是成功
boolean containsAll(Collection<?> c);//同上，只是判别对象变了而已
boolean addAll(Collection<? extends E> c);//同上
boolean removeAll(Collection<?> c);//同上
//Java8搞的事情：删除所有该集合的元素，满足给定的预测。该方法将会批量删除符合filter条件的所有元素，该方法需要一个Predicate对象作为作为参数，Predicate也是函数式接口，因此可使用Lambda表达式作为参数。
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
//用于从列表中移除未包含在指定collection中的所有元素，返回值：如果List集合对象由于调用retainAll方法而发生更改，则返回 true。
boolean retainAll(Collection<?> c);
//全清咯
void clear();
//下面的两个方法都是object类过来的，从而要覆写的存在。
boolean equals(Object o);
int hashCode();
//在Iterable接口中有大致讲解
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
//也是Java8搞的事情：给予博客：http://www.cnblogs.com/guguli/p/4396093.html
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}
（3）还有一个抽象类呢：AbstractCollection
它实现了Collection中除了iterator()和size()之外的所有方法。AbstractCollection的主要作用是方便其他类实现Collection.，比如ArrayList、LinkedList等。它们想要实现Collection接口，通过集成AbstractCollection就已经实现大部分方法了，再实现一下iterator()和size()即可。
但是要注意一个东西，默认不支持添加单个元素，所以它的add()本身的实现是直接抛UnsupportedOperationException异常的。实际上add()是一种“可选操作”，目的是延迟到需要时再实现，也就是说子类想自己去添加单个的话需要自己去实现啦！！！
//讲些有趣的重要常用的咯。
public abstract class AbstractCollection<E> implements Collection<E> {
//上面说过，用collection接口都要两个构造器咯
protected AbstractCollection() {
}
//迭代的根据自己的子类的不同从而实现自己的迭代！！！
public abstract Iterator<E> iterator();
public abstract int size();
//判空
public boolean isEmpty() {
return size() == 0;
}
//判是否存在方法
public boolean contains(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext())//从这里可以看出，任何非空集合都包含null
if (it.next()==null)
return true;
} else {
while (it.hasNext())
if (o.equals(it.next()))
return true;
}
return false;
}
/*接口规定的，将集合转变成数组*/
public Object[] toArray() {
Object[] r = new Object[size()];//创建与集合大小相同的数组
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext())
return Arrays.copyOf(r, i);//第二个参数是待copy的长度，如果这个长度大于r，则保留r的长度
r[i] = it.next();
}
return it.hasNext() ? finishToArray(r, it) : r;
}
//同上，不过参数是泛型而已。引入泛型模板机制后的新调用方法，也就是明确了类型而转换。
public <T> T[] toArray(T[] a) {
// Estimate size of array; be prepared to see more or fewer elements
int size = size();
T[] r = a.length >= size ? a :
(T[])java.lang.reflect.Array
.newInstance(a.getClass().getComponentType(), size);
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) { // fewer elements than expected
if (a == r) {
r[i] = null; // null-terminate
} else if (a.length < i) {
return Arrays.copyOf(r, i);
} else {
System.arraycopy(r, 0, a, 0, i);
if (a.length > i) {
a[i] = null;
}
}
return a;
}
r[i] = (T)it.next();
}
// more elements than expected
return it.hasNext() ? finishToArray(r, it) : r;
}
//最大的数组分配容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//两个参数r和it分别是toArray方法中放置集合元素的对象数组和迭代器
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
int i = r.length;//初始数组大小
while (it.hasNext()) {//第一次进入该while循环，那么就会分配一个更大的数组（增加一半的大小，注意可能会溢出，这里处理了分配超大数组的情况）
int cap = r.length;
if (i == cap) {
int newCap = cap + (cap >> 1) + 1;//分配更大的数组
// overflow-conscious code
if (newCap - MAX_ARRAY_SIZE > 0)//一旦超过，还会继续分配大数组。最后只返回i个元素（即迭代器中元素个数）对应的数组
newCap = hugeCapacity(cap + 1);
r = Arrays.copyOf(r, newCap);//扩容机制：然后将原来数组r中的元素拷贝到新数组中，后续将元素放置在扩容数组中，一旦超过，还会继续分配大数组。
}
r[i++] = (T)it.next();
}
// trim if overallocated
return (i == r.length) ? r : Arrays.copyOf(r, i);
}
//分配大型数组时的异常处理
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError
("Required array size too large");
// MAX_ARRAY_SIZE的值是0x7ffffff7，如果需要分配的数组过大，可能导致内存溢出
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
//添加一个元素的add的默认实现总是抛出该异常。因为不支持添加一个元素，子类想实现就要自己去覆写
public boolean add(E e) {
throw new UnsupportedOperationException();
}
// 删除对象o ，使用迭代器去删除，也就是迭代过程中删除。问题根源文章：http://blog.csdn.net/qh_java/article/details/50154405 。一会还会详解这个问题。
public boolean remove(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext()) {
if (it.next()==null) {
it.remove();
return true;
}
}
} else {
while (it.hasNext()) {
if (o.equals(it.next())) {
it.remove();
return true;
}
}
}
return false;
}
// 判断是否包含集合c中所有元素
public boolean containsAll(Collection<?> c) {
for (Object e : c)
if (!contains(e))
return false;
return true;
}
//添加另一个集合中的所有元素addAll。！！！！这里是要求子类实现该类时如果需要调用addAll方法的话必须自己覆盖add操作。
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
//下面两个方法的时间复杂度都是O(this.size() * c.size())。
//删除集合c中所有元素（如果存在的话）
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
//取得两个List的交集的方法
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
Iterator<E> it = iterator();
while (it.hasNext()) {
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
//迭代清楚集合数据
public void clear() {
Iterator<E> it = iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
}
//将集合元素显示成[String]
public String toString() {
Iterator<E> it = iterator();
if (! it.hasNext())
return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = it.next();
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
}
}
三、我们来讲下集合的一些注意点：
（1）迭代器：
迭 代器是一种设计模式，它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。在Collection集合中都会实现Iterator，因此可以通过iterator()函数获得一个iterator对象，然后就可以利用提供的函数进行相应的输出操作。而ListIterator迭代器是一个另类迭代器，允许对容器中的元素进行双向遍历。
注意：使用集合子类的迭代器，我们是可以在遍历中进行删除操作的喔！！！！
在遍历的过程中，不允许对集合进行增删操作。如果想要对集合进行删除操作，也必须调用迭代器的remove（）方法！其实是那个集合子类重写过的remove方法的处理！！例子如下：
能边遍历边删除原因是：子类重写remove实现拷贝跟AbstractCollection中的remove是不一样的！
public class IteratorTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
List list=new ArrayList();//创建一个线性表
list.add("a");
list.add("#");
list.add("b");
list.add("#");
list.add("c");
list.add("#");
Iterator it=list.iterator();//返回线性表的迭代器
while(it.hasNext()) //遍历线性表 ，先检查是否还有元素可以迭代
{
String element=(String) it.next();//取出迭代的元素
if("#".equals(element))//如果元素=="#",则删除
{
it.remove();//true
//这个remove方法是ArrayList重写过的remove方法，是经过拷贝的一个处理。将在下一篇文章ArrayList源码解析中重点讲解
}
System.out.println(element);
}
System.out.println(list);
}
}
//输出是abc
Collection的remove导致的线程错误：也就是AbstractCollection中的remove
//将会出现Exception in thread "main" java.util.ConcurrentModificationException
public class IteratorTest4 {
public static void main(String args[]) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
//单纯的使用，真单纯。边遍历边删除，错死你！！
for (String s : list) {
if (s.equals("b")) {
list.remove(s);
}
}
}
}
原因就要对比源码去看了嘛。AbstractCollection中的remove
//单纯的边遍历边删除，它就搞死你咯，，像银行取钱，没有做处理。线程就会抢占。
public boolean remove(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext()) {
if (it.next()==null) {
it.remove();
return true;
}
}
} else {
while (it.hasNext()) {
if (o.equals(it.next())) {
it.remove();
return true;
}
}
}
return false;
}
