Java 集合可分为 Collection 和 Map 两种体系：

Collection 接口：定义了存取一组对象的方法的集合。
- List：元素有序、可重复的集合。
- Set：元素无序、不可重复的集合。

Map 接口：保存具有映射关系 key-value 对的集合。

Collection 接口

Collection 接口是 List、Set 和 Queue 接口的父接口，该接口里定义的方法既可用于操作 Set 集合，也可用于操作 List 和 Queue 集合。

JDK 不提供此接口的任何直接实现，而是提供更具体的子接口的实现。

子接口 - List

List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。

JDK API 中 List 接口的实现类常用的有：ArrayList、LinkedList 和 Vector。

实现类 - ArrayList

在 JDK 1.8 中，ArrayList 的空参数构造器采用了懒惰式的初始化方法，首先声明一个空的 Object 数组。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// ...

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
	throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
	}
}

在 add 时，再对底层数组进行初始化操作。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

其中 ensureCapacityInternal 方法保证了数组有足够的空间（扩容），以及初始化操作。

默认最小数组容量为 DEFAULT_CAPACITY（10）。
调用 ensureExplicitCapacity 方法，在必要时进行扩容。

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

在调用 grow 进行扩容时，默认扩容 1.5 倍，同时将原有数组中的元素复制到新的数组中。

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);
}

实现类 - LinkedList

LinkList 的底层为双向链表，类的内部定义了 Node 类型的 first 和 last，用于记录第一个和最后一个元素。

同时，定义内部类 Node，作为 LinkedList 中保存数据的基本结构。Node 除了保存数据，还定义了两个变量：

prev 变量记录前一个元素的位置。
next 变量记录下一个元素的位置。

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;
    }
}

ArrayList LinkedList Vector 的异同

相同点：

都是实现了 List 接口，存储的都是有序的、可重复的数据。

不同点：

ArrayList：
- 作为 List 接口的主要实现类。
- 执行效率高，线程不安全。
- 底层使用 Object[] 类型存储。
LinkedList：
- 对于频繁的插入、删除操作，效率比 ArrayList 高。
- 底层使用双向链表实现。
Vector：
- 作为 List 接口的古老实现类，在 JDK 1.0 就实现了。
- 效率低，但是线程安全。
- 底层使用 Object[] 类型存储。

子接口 - Set

Set 集合不允许包含相同的元素，判断两个对象是否相同不是使用 == 运算符：

HashSet 和 LinkedHashSet：先使用 hashcode 方法判断，若 hashcode 相同则使用 equals 方法。
TreeSet：
- 自然排序：使用 Comparable 接口的 compareTo 方法。
- 定制排序：使用 Comparator 接口的 compare 方法。

实现类 - HashSet

当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值，然后根据 hashCode 值，通过散列函数决定该对象在 HashSet 底层数组中的存储位置。

如果两个元素的 hashCode() 值相等，会再继续调用 equals 方法，如果 equals 方法结果为 true，添加失败；如果为 false，那么会保存该元素，但是该数组的位置已经有元素了，那么会通过拉链法（JDK 1.8 为尾插法）进行存储。

HashSet 的底层为数组（HashMap），初始长度为 16。当如果使用率超过 0.75，就会扩大容量为原来的 2 倍。

在 JDK 7 中，HashMap 采用数组 + 链表。

在 JDK 8 中，HashMap 采用数组 + 链表 + 红黑树。

实现类 - LinkedHashSet

LinkedHashSet 是 HashSet 的子类，LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。

LinkedHashSet 插入性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。

实现类 - TreeSet

TreeSet 的底层采用红黑树进行存储，特点是：有序、查询速度比 List 快。

在 TreeSet 中比较元素不再使用 hashcode 和 equals 比较：

自然排序：使用 Comparable 接口中的 compareTo 方法进行比较，返回零就认为是同一个元素。

定制排序：使用 Comparator 接口中的 compare 方法进行比较，返回零就认为是同一个元素。

HashSet LinkedHashSet TreeSet 对比

HashSet：
- 作为 Set 接口的主要实现类。
- 线程不安全。
- 可以存储 null 值。
LinkedHashSet：
- 作为 HashSet 的子类。
- 在遍历内部数据时，可以按照添加的顺序遍历。
TreeSet：
- 底层作为红黑树存储，可以按照添加的对象指定属性进行排序。

Iterator 迭代器接口

Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素。

Collection 接口继承了 java.lang.Iterable 接口，该接口有一个 iterator 方法，那么所有实现了 Collection 接口的集合类都有一个 iterator 方法，用以返回一个实现了 Iterator 接口的对象。

Iterator 仅用于遍历集合，Iterator 本身并不提供承装对象的能力。如果需要创建Iterator 对象，则必须有一个被迭代的集合。集合对象每次调用 iterator 方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。

Iterator 接口方法

Iterator 接口方法如下：

在调用 it.next() 方法之前必须要调用 it.hasNext() 进行检测。若不调用，且下一条记录无效，直接调用 it.next() 会抛出 NoSuchElementException 异常。

Dawn's Blogs

Java高级 (5) 集合之Collection