Collection

本篇文章记录学习java集合中Collection接口的内容。

$Collection$接口

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

• $jdk$​不提供此接口的任何直接实现，而是提供更具体的子接口(如$Set,List$​)实现。

• 在$java5$​之前，$java$​集合会丢失容器中所有对象的数据类型，把所有对象都当成$Object$​类型处理；从$jdk5.0$​增加了泛型之后，$java$​集合可以记住容器中对象的数据类型。

$Iterator$​迭代器接口

• $Iterator$对象称为迭代器(设计模式的一种)，主要用于遍历$Collection$集合中的元素。
• $Collection$接口继承了$java.lang.Iterator$接口，该接口有一个$iterator()$方法，那么所有实现了$Collection$接口的集合类都能调用$iterator()$方法，返回一个实现了$Iterator$接口的对象。
• $Iterator$​仅用于遍历集合，$Iterator$本身并不提供承装对象的能力。如果需要创建$Iterator$对象，则必须有一个被迭代的集合。
• 集合对象每次调用$iterator()$​方法都会得到一个全新的对象，默认指向集合第一个元素之前。

$List$接口

• $List$集合类中元素有序，且可重复，集合中每个元素都有其对应的顺序索引。
• List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号调用$get()$​方法取容器中的元素。
• $List$接口的常用实现类有$ArrayList、LinkedList$和$Vector$​.

$ArrayList$

$jdk7$​​​​

ArrayList list = new ArrayList();

在调用空参构造器时，创建了长度为$10$的$Object[]$数组$elementData$。当向$list$中增加元素达到$11$个时，数组容量不够，需要扩容，默认情况下，是扩容到原来的$1.5$倍，同时需要将原有数据中的数据复制到新的数组中。

$jdk8$​​​​

底层$Object[] elementData$​​​初始化空，当调用空参构造器时，并没有创建长度为$10$​数组。当第一次调用$add()$​时，才创建长度为$10$​的数组，并将数组添加到数组中。

这种创建对象的方式类似于单例的饿汉式，延迟了数组的创建，节省内存。

具体创建的方法为$grow()$，这也是扩容的方法。

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
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);
}

可以直接调用设置数组大小的构造器public ArrayList(int initialCapacity)

$ArrayList$是线程不安全的，效率较高

$LinkedList$

$LinkedList$底层使用双向链表实现，内部没有声明数组，而是定义了$Node$类型的$first$和$last$,用于记录首末元素。同时定义内部类$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;
    }
}

对于频繁的插入和删除元素操作，使用$LinkedList$效率比$ArrayList$高。

$Vector$

在$jdk7$​和$jdk8$​中创建$Vector$​对象，都创建了长度为$10$​​的数组。在扩容方面，默认扩容为原来数组长度的两倍。

大多数操作都和$ArrayList$​相同，区别在于$Vector$​​是线程安全的,它总是比$ArrayList$​慢，应避免使用。

$Stack$是$Vector$的子类。

$Set$接口

• $Set$接口$Collection$的子接口，没有提供额外的方法，不允许包含相同的元素。
• $Set$判断两个对象是否相同是根据$equals()$方法。

$HashSet$

$HashSet$​的内部采用了$HashMap$​作为数据存储，$HashSet$​其实就是在操作$HashMap$​的$key$​。

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 */
public HashSet() {
    map = new HashMap<>();
}

关于$hashMap$，可查看map

$LinkedHashSet$​

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

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

$TreeSet$

• 是$SortedSet$接口的实现类，可以确保集合元素处于排序状态。
• 底层使用红黑树结构存储数据。
• 两种排序方法：自然排序(集合元素需实现$Comparable$接口，重写$CompareTo()$方法)；定制排序(传入一个实现了$Comparator$接口重写$Compare()$方法的实例)

$Collections$工具类

• 是一个操作$Set、List、Map$等集合的工具类
• 提供了一系列静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法