容器主要包括 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整理思路

1. HashSet的性能总是比TreeSet好(特别是最常用的添加、查询元素等操作)，因为TreeSet需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的Set时，才应该使用TreeSet，否则都应该使用HashSet
2. 对于普通的插入、删除操作，LinkedHashSet比HashSet要略慢一点，这是由维护链表所带来的开销造成的。不过，因为有了链表的存在，遍历LinkedHashSet会更快
3. EnumSet是所有Set实现类中性能最好的，但它只能保存同一个枚举类的枚举值作为集合元素
4. 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整理思路

1. HashMap和Hashtable的效率大致相同，因为它们的实现机制几乎完全一样。但HashMap通常比Hashtable要快一点，因为Hashtable需要额外的线程同步控制
2. TreeMap通常比HashMap、Hashtable要慢(尤其是在插入、删除key-value对时更慢)，因为TreeMap底层采用红黑树来管理key-value对
3. 使用TreeMap的一个好处就是： TreeMap中的key-value对总是处于有序状态，无须专门进行排序操作

如何记录每一个容器的结构和所属体系呢？

看名字！后缀名就是该集合所属的体系。前缀名就是该集合的数据结构。

看到array：就要想到数组，就要想到查询块，有下标。

看到link：就要想到链表，就要想到增删快，就要想到add，get，remove+first last的方法。

看到hash：就要想到哈希表，就要想到唯一性，就要想到元素需要覆盖hashCode方法和equals方法。

看到tree：就要想到二叉树，就要想到排序，就要想到两个接口Comparator，Comparable。

而且通常这些常用的集合容器都是不同步的。