Java Collections

总结下 Java 容器相关的知识。

常用的容器种类有 Set, Map 和 List，在项目中根据使用场景选取合适的容器。

Collection 无序，允许重复
- List 有序，允许重复
- Set 无序，不允许重复
- Quene
Map 无序，key 不允许重复

在 Java 中，Iterable，Collection，Set，List，Map 等都是 interface，
继承关系如下图。

List 容器

AbstractList

AbstractList 是继承了 List 接口的抽象类，实现了 List 一些通用的方法。对于需要随机访问数据的场景应优先选择实现它。

AbstractSequentialList

与 AbstractList 相似，只不过 AbstractSequentialList 更适用于实现连续访问数据的场景。

ArrayList

ArrayList 继承了 AbstractList，相对于数组来说，ArrayList 内部封装了一个 Object[],大体上操作没有太多区别，不同的是 ArrayList 可以动态的扩展大小，原理是当内部数组满了后新建一个当前 Object[] 大小 1.5 倍的数组，将原来内容拷贝到新的数组内。关于性能方面，因为 ArrayList 保存的是 Object 对象，在 get 时需要一次类型转换操作，如果数据量很大，性能上的差异会凸显出来。

// Positional Access Operations

@SuppressWarnings("unchecked")
E elementData(int index) {
  return (E) elementData[index];
}

/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
  rangeCheck(index);

  return elementData(index);
}

LinkedList

LinkedList 继承了 AbstractSequentialList ，内部数据储存部分使用的是链表。优点的话也就是链表这种数据结构的优点。

Map

AbstractMap

继承了 Map 接口，为实现 Map 提供大体框架。

HashMap

HashMap 内实现了 Map 所有的操作，接受 null 值作为 key 或 value，不保证元素顺序。HashMap 原理写不动了…

LinkedHashMap

LinkedHashMap 继承自 HashMap 并实现 Map 接口。与 HashMap 不同的是它维持一个所有元素的双向链表，所以它内部元素是有序的。

TreeMap

TreeMap 是一个基于红黑树的 NavigableMap 实现。会对插入的元素进行排序。

Set 容器

AbstractSet

提供实现 Set 接口的大体框架。它仅继承了 AbstractCollection ，实现 Set 接口。

HashSet

继承自 AbstractSet，并实现 Set 接口。内部实现使用一个 HashMap 储存，不保证元素顺序，允许元素值为 null。

LinkedHashSet

继承自 HashSet，翻开源文件代码却意外的少，原来它是调用了一个 HashSet 的构造函数。和 HashSet 相比较，LinkedHashSet 保证了元素插入的顺序；当一个元素 e 已经插入后再次调用s.add(e)，会在s.contains(e)判断时直接返回 true。

/**
  * Constructs a new, empty linked hash set. (This package private
  * constructor is only used by LinkedHashSet.) The backing
  * HashMap instance is a LinkedHashMap with the specified initial
  * capacity and the specified load factor.
  *
  * @param initialCapacity the initial capacity of the hash map
  * @param loadFactor the load factor of the hash map
  * @param dummy ignored (distinguishes this
  * constructor from other int, float constructor.)
  * @throws IllegalArgumentException if the initial capacity is less
  * than zero, or if the load factor is nonpositive
  */
  HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
  }

TreeSet

首先，TreeSet 继承自 AbstractSet ，并且实现了 NavigableSet 接口。主要提供时间复杂度为 log(n) 的插入，删除和查找操作，插入的元素默认由小到大排列。需要 key 实现 Comparable 接口，或者在构造函数提供一个 Comparator。

关于 Dictionary 和 Vector

Dictionary 和 Vector 都是早期Java提供的方法。

Vector也继承了AbstractList，和ArrayList的区别都有啥呢？

Vector 是线程安全的，不过这个我们 ArrayList 也可以通过Collections.synchronizedCollection(Collection<T> c)实现。
Vector 和 ArrayList 内部都靠数组驱动，当数组满了后，Vector 默认会新建一个当前 size 2 倍的数组，ArrayList 是 1.5 倍。(A Vector defaults to doubling the size of its array, while the ArrayList increases its array size by 50 percent.)

与 HashTable 对应的是 HashMap ，主要的差异有：

HashTable 方法是同步的。
HashTable 的 key 和 value 都不可以为 null。
继承不同
遍历方式的内部实现不同
Hash 值得使用不同，HashTable 直接使用对象的 hashCode ，HashMap 则重新计算。
内部数组的初始化和扩容方式

package io.github.tiiime;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Iterable iterable;
        Collection collection;

        Map map;

        AbstractCollection abstractCollection;
        Set set;
        List list;
        Queue queue;

        AbstractList abstractList;
        AbstractSequentialList abstractSequentialList;
        AbstractSet abstractSet;
        AbstractMap abstractMap;

        ArrayList arrayList;
        LinkedList linkedList;
        LinkedHashMap linkedHashMap;
        LinkedHashSet linkedHashSet;

        HashMap hashMap;
        HashSet hashSet;

        SortedMap sortedMap;
        SortedSet sortedSet;

        NavigableMap navigableMap;
        NavigableSet navigableSet;

        TreeMap treeMap;
        TreeSet treeSet;

        Dictionary dictionary;
        Hashtable hashtable;
        Vector vector;
    }
}