容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。
Collection (图片来源网络，侵删)
Collection
List：有先后顺序，数值不唯一
ArrayList
- 基于数组实现List接口。
- 由于基于数组实现，连续内存，所以擅长于顺序访问和随机下标访问，速度最快，时间复杂度是O(1)。
- 用会自动扩增容量的Array（[]，最高效，但是容量固定但不可动态改变）。
- 数组扩容是对ArrayList效率影响比较大的一个因素。每当执行Add、AddRange、Insert、InsertRange等添加元素的方法，都会检查内部数组的容量是否不够了，如果不够，它就会以当前容量的两倍来重新构建一个数组，将旧元素Copy到新数组中，然后丢弃旧数组，在这个临界点的扩容操作，应该来说是比较影响效率的。
- 按内容查找逐个遍历，速度较慢，时间复杂度是，时间复杂度是O(N)。
- 增、删操作导致元素大量移动，非常耗时，时间复杂度是O(N)。
LinkedList
- 基于头尾相连的双向链表实现，只能顺序或逆序访问，但是可以快速地在链表中间插入和删除元素，时间复杂度是O(1)。
- 随机访问速度较慢，时间复杂度是O(N)。
- 用作栈、队列和双向队列。
Set：无先后顺序，数值唯一
HashSet
- 底层使用HashTable实现。
- 添加快、内容查询快、删除快，都是O(1)。
- 无先后顺序，无大小顺序，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
LinkedHashSet
- 具备HashSet优点，但是添加、删除会比HashSet慢一点
- 内部使用双向链表维护元素的插入先后顺序。
TreeSet
- 红黑树（有序的自平衡二叉树）
- 有大小顺序
- 查询内容O(logN)比List的O(N)快，比HashSet的O(1)慢
EnumSet
- 以位向量的形式存储，对象占用内存很小，而且运行效率很好。尤其是进行批量操作（如调用containsAll()和retainAll()方法）时，如果其参数也是EnumSet集合，则该批量操作的执行速度也非常快。
Set整理思路
- HashSet的性能总是比TreeSet好(特别是最常用的添加、查询元素等操作)，因为TreeSet需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的Set时，才应该使用TreeSet，否则都应该使用HashSet
- 对于普通的插入、删除操作，LinkedHashSet比HashSet要略慢一点，这是由维护链表所带来的开销造成的。不过，因为有了链表的存在，遍历LinkedHashSet会更快
- EnumSet是所有Set实现类中性能最好的，但它只能保存同一个枚举类的枚举值作为集合元素
- HashSet、TreeSet、EnumSet都是"线程不安全"的，通常可以通过Collections工具类的synchronizedSortedSet方法来"包装"该Set集合。
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
Queue
LinkedList
- 实现双向列表队列
PriorityQueue
- 基于堆结构实现，实现了优先级队列
- 队首元素优先级最高
- 默认按照元素比较多顺序排序，此时要实现comparable接口
- 也可以传入Compartor自定义排序对象，此时不实现comparable接口
- 可以实现
Map
HashTable
- 与HashMap类似，但是是线程安全的
- 现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
LinkedHashTable
- 使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。
HashMap
- 基于哈希表实现
TreeMap
- 基于红黑树实现（有序的自平衡二叉树）
Map整理思路
- HashMap和Hashtable的效率大致相同，因为它们的实现机制几乎完全一样。但HashMap通常比Hashtable要快一点，因为Hashtable需要额外的线程同步控制
- TreeMap通常比HashMap、Hashtable要慢(尤其是在插入、删除key-value对时更慢)，因为TreeMap底层采用红黑树来管理key-value对
- 使用TreeMap的一个好处就是： TreeMap中的key-value对总是处于有序状态，无须专门进行排序操作
如何记录每一个容器的结构和所属体系呢？
看名字！后缀名就是该集合所属的体系。前缀名就是该集合的数据结构。
看到array：就要想到数组，就要想到查询块，有下标。
看到link：就要想到链表，就要想到增删快，就要想到add，get，remove+first last的方法。
看到hash：就要想到哈希表，就要想到唯一性，就要想到元素需要覆盖hashCode方法和equals方法。
看到tree：就要想到二叉树，就要想到排序，就要想到两个接口Comparator，Comparable。
而且通常这些常用的集合容器都是不同步的。
