聊聊集合

Java的集合类很有必要主要是从Collection和Map接口衍生出来的，目前主要提供了List、Set和 Map这三大类的集合。

java.util.Collection [I]

+--java.util.List [I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vector [C]
+--java.util.Stack [C]

+--java.util.Set [I]
+--java.util.HashSet [C]
+--java.util.SortedSet [I]
+--java.util.TreeSet [C]

java.util.Map [I]
+--java.util.SortedMap [I]
+--java.util.TreeMap [C]
+--java.util.Hashtable [C]
+--java.util.HashMap [C]
+--java.util.LinkedHashMap [C]
+--java.util.WeakHashMap [C]

Collection接口主要有两种子类分别为List和Set，区别主要是List保存的对象可以重复，而Set不可以重复，而Map一般为key-value这样的对应关系，比如我们常用的HashMap。

下面简单的介绍一下List、Set和Map。

（1）List 主要有ArrayList、LinkedList、Vector和Stack

• LinkedList
  作为一种双向链表结构，对于元素的插入、删除效率比较高，只需要调整节点指向即可，但是对于随机查找而言性能主要看这个链表长度和运气了。 LinkedList也提供了ArrayList的get方法，但是要复杂的多，主要通过next或previous方法遍历得到。
• ArrayList
  实现了可变大小的数组，提供add和get方法，get相对于LinkedList比较高。每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并 没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
• Vector
  和ArrayList差不多，主要是内部实现了synchronized关键字，实现了线程安全访问但性能有些降低，同时对于元素的扩充在算法上和ArrayList稍有不同，通过构造的容量增量系数来决定。
• Stack
  作为栈的操作，继承于Vector，提供了push，pop和peek方法，peek是不弹出根据数据大小获取最后一个元素对象。

（2）Set 主要有HashSet 和 TreeSet

• HashSet
  此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证集合的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。
• TreeSet
  这个相对于HashSet而言主要是提供了排序支持，TreeSet是从TreeMap类实现，也是非线程安全的。

（3）Map 主要有 Hashtable、HashMap 、WeakHashMap和 TreeMap

• HashTable
  Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。Hashtable是同步的。
• HashMap
  HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap 的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。
• WeakHashMap
  WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。
• TreeMap
  相对于HashMap它的排序可以通过传入包含comparator的属性来控制