JAVA集合框架

JAVA 集合框架图（简单版）

集合框架

Collection 接口

Collection 是集合框架中最基本的接口（注意，是接口），它和 Map 接口并列为最顶级接口，集合框架中的其它集合都是从他们继承而来。
Collection 接口在集合框架中起的最重要的作用是提供了遍历每个元素的方法：iterator 方法，返回迭代子，程序员们可以根据这个迭代子来遍历所有元素。

1
2
3
4
Iterator it = collection.iterator();  
while(it.hasNext()) { 
　　    Object obj = it.next();  
}

List 接口

List 接口继承于 Collection 接口，和 Set 接口处于同一个级别。和 Set 接口相比，它有序、可以控制插入位置、允许重复、类似数组。
List 接口继承自 Collection，它比Collection多了一个 ListIterator迭代子，该迭代子使 List 可以插入/删除数据，双向遍历。

实现 List 接口的类有 ArrayList、LinkedList、Vector、Stack等。

ArrayList

ArrayList 实现了 List 接口，和古老的 Vector 相比，它放弃了同步的特性，以便追求更高的性能（Vector 在各个函数前都加上了 synchronized 关键字，导致性能下降的很厉害）。
ArrayList 的 get/set/size/isEmpty 等函数复杂度为常数级，而add 函数的复杂度则为 O(N)，因为插入后要移动元素。
和 LinkedList 相比，ArrayList 底层用数组来实现，默认容量为10，填满后扩容为原先的150%。

Vector

Vector 的出现早于 Collection 集合框架，它和 HashTable 是同一个时代的产物。
Vector 极度类似 ArrayList（甚至可以说 ArrayList 是去掉了 synchronized 关键字的Vector），也是基于数组。
Vector 支持着同步，当一个线程正在操作着 iterator 的同时，另一个线程修改了 Vector，如增加一个元素或修改一个元素，第一个线程再调用iterator 的方法就会抛异常ConcurrentModificationException。

LinkedList

LinkedList 基于链来实现，插入删除极快，遍历很慢，复杂度高达O(N)
LinkedList 也不支持同步。

Stack

Stack 和 Vector 是同一时代产物，继承自 Vector，支持同步，现已被抛弃（官方建议使用 Deque来实现栈）。

Set 接口

Set 接口同样继承自 Collection 接口，和 List 接口处于同一个级别。Set 中的元素无序、不重复，无法控制插入位置。（实际上，我们将 Set 看作一个黑盒，在 Set 中，元素就像是放入黑箱子，无人知晓它们的位置，元素之间都是独特单一的，我们也不知道元素被插到哪里去）。

实现 Set 接口的类有HashSet、TreeSet、SortedSet等。

HashSet

底层是个 HashMap，不支持同步，元素间无序，无法知晓插入位置，无重复。

TreeSet

TreeSet 底层是TreeMap（一般Set的底层都是Map），而TreeMap底层是一颗红黑树（红黑树的应用还挺多的，HashMap也用红黑树）。元素插入进去之后是有序，插入删除的 时间复杂度为O(LogN)。

Map 接口

Map 接口和 Collection 接口处于同一个级别，是（Key,Value）的集合，而 Collection 则是（Value）的集合。

实现了 Map 接口的有HashMap、TreeMap(SortedMap)、HashTable、WeakHashTable。

HashMap

HashMap 是典型的 key-value 型的数据集合，用哈希实现，get的速度高达 O(1)，以前get在最坏的情况下会是O(n)，现在当哈希码相同的同一条链上元素数目超过8时，该链会转为平衡树，所以最坏的情况下是O(logN)。
HashMap 底层是数组，扩容时直接扩为原先的200%。
和 HashTable 相比，HashMap 不支持同步，但性能高；HashMap 允许插入 null 的 key 或 null 的 value，而 HashTable 不允许；
计算数组下标时，HashMap 会做移位优化，以便将高位扩散到低位，而 HashTable 只会做单纯的模运算。
当冲突过多时，HashMap 会将冲突链转换为平衡树，进一步降低冲突的元素的寻找速度（ 从 O(N) 降为 O(LogN) ）。