集合Collection

常用集合类

• List

1. ArrayList
   list接口的可变数组实现，允许所有元素，包括null；
   非线程安全；
   底层使用的数据结构为数组；
   适合查改，弱于增删
2. LinkedList
   list接口中的链表列表实现，允许所有元素，包括null；
   实现Deque接口，提供先进先出的队列操作以及其他堆栈和双端队列操作；
   非线程安全；
   适合增删，弱于查改

• Map

1. HashMap
   基于哈希表的Map接口实现，并允许使用null值和null键；
   非线程安全；
   不保证映射的顺序，特别是它不保证该顺序恒久不变；

2. HashTable
   HashTable和HashMap采用相同的存储机制，二者的实现基本一致；
   不允许有null值得存在；
   HashTable是线程安全的，内部的方法基本都是synchoronized；
   迭代器具有强一致性；

3. TreeMap
   Map接口的树显示；红黑树
   不允许有null值的存在；
   非线程安全；
   键值有序；
   TreeMap的优势

   1. 空间利用率高
   HashMap的数组大小必须要2的n次方；
   TreeMap中树的每一个节点就代表了一个元素；
   2. 性能稳定
   Hash碰撞会导致HashMap查询开销提高
   HashMap扩容时会rehash，开销高
   TreeMap的操作均能在O(log n)内完成
   

4. LinkedHashMap
   Map接口的哈希表和链接链表实现，允许使用null值和null键；
   非线程安全；
   具有可预知的迭代顺序；
   Map的使用范围

   1. HashMap适用于一般的键值映射需求
   2. HashTable适用于有多线程并发的场合
   3. TreeMap适用于要按照键排序的迭代场合
   4. LinkedHashMap适用于特殊顺序的迭代场合（如LRU算法）
   

• Set

1. HashSet
   实现Set接口，由哈希表支持，允许使用null元素；
   非线程安全；
   不保证set的迭代顺序，特别是不保证该顺序恒久不变；

2. TreeSet

3. LinkedHashSet

   Set的特点

   1. HashSet通过HashMap实现
   2. TreeSet通过TreeMap实现
   3. LinkedHashSet通过LinkedHashMap实现
   4. Set类与Map类拥有近似的使用特性