概念

Java 的容器是前人为我们设计好的一套存储对象和数据的一套轮子，通过使用 Java 中写好的容器 API 我们可以很方便的存储、操作我们的数据。

容器的分类

容器主要包括 Collection 和 Map 两种：

Collection:

主要是单个元素的集合，由 List、Queue、Set 三个接口区分不同的集合特征，然后由下面的具体的类来实现对应的功能。

Map:

有一组键值对的存储形式来保存，可以用键对象来查找值。

关系图:

List

List 的特点就是所有的元素是可以重复的。

ArrayList

• 底层由 Object 数组实现。
• 默认长度为 10，每次扩容 1.5 倍，也可以自定义初始长度。
• 元素存放数据为遍历顺序。
• 访问与查找速度快，删除与插入速度慢。
• toArray：把 LinkedList 转化为 Array

LinkedList

• 底层由链表（双向链表）实现。
• 在列表中插入和删除速度快，但是查找需要遍历整个链表。
• 可以通过它实现队列和栈。
• 动态改变大小（链表特性）

Vector

• 底层由数组实现
• synchronized 进行同步，线程安全
• 插入、删除、访问速度慢

Queue

队列是一个满足“先进先出”的数据结构。
LinkedList 提供了方法支持队列操作，并且实现了 Queue 接口，所以 LinkedList 是队列的一种实现，可以通过 LinkedList 向上转型为 Queue

FIFO 队列

Queue q=new LinkedList();

优先队列

Queue q=new PriorityQueue();

默认升序，底层为堆，初始容量 11

Queue q=new PriorityQueue((e1,e2)->(e1.id-e2.id));

传入对象时需要指定比较器；

BlockingQueue

阻塞队列，在 java.util.concurrent 包下，在线程安全中介绍。

Set

不可重复

HashSet

• 基于哈希表实现，支持快速查找，但不支持有序性操作。
• 通过 HashMap 实现。
• HashSet添加的元素是存放在HashMap的key位置上，而value取了默认常量PRESENT

TreeSet

• 基于红黑树实现，支持有序性操作，查找效率 O(logN)。

• 通过 NavigableMap 实现

  private transient NavigableMap<E,Object> m;

• 数据类型为对象数据时须指定比较方法。

  public TreeSet(Comparator<? super E> comparator)

LinkedHashSet

具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。

Map

• Map 是使用键值对存储的一种结构，所以在处理列如单词统计等方面是杀手锏
• Map 的键值对都可以为 null
• Map 可以多维扩展。例如一个人拥有多个宠物，你可以这样定义：Map< Person, List< pet>>

TreeMap

基于红黑树实现。有序

HashMap

• 基于哈希表实现。
• 由数组和链表，红黑树共同完成：
• 键可以是 null，而且键值不可以重复，如果重复了以后就会对第一个进行键值进行覆盖。
• 初始容量为 16，最大容量 1073741824
• 默认负载因子 0.75,扩容 2 倍。
• 链表转红黑树的阈值 8，红黑树转链表的阈值 6

HashTable

• 和 HashMap 类似，但它是线程安全的
• 它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
• HashMap 的默认初始容量为 16，Hashtable 为 11。
• HashMap 的扩容为原来的 2 倍，Hashtable 的扩容为原来的 2 倍加 1。

LinkedHashMap

使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。

线程安全的容器

同步容器类（使用了 synchronized）

Vector、Stack、HashTable

缺点：

通过同步方法将访问操作串行化，导致并发环境下效率低下

复合操作（迭代、条件运算如没有则添加等）非线程安全，需要客户端代码来实现加锁。

并发容器：

1. CopyOnWriteArrayList

写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。

写操作需要加锁，防止并发写入时导致写入数据丢失。

写操作结束之后需要把原始数组指向新的复制数组。

内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。
所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景

2. CopyOnWriteArraySet

CopyOnWriteArraySet 基于 CopyOnWriteArrayList 实现，其唯一的不同是在 add 时调用的是 CopyOnWriteArrayList 的 addIfAbsent 方法，其遍历当前 Object 数组，如 Object 数组中已有了当前元素，则直接返回，如果没有则放入 Object 数组的尾部，并返回。

3. ConcurrentHashMap

采用了分段锁（Segment），每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度就是 Segment 的个数）。
默认的并发级别为 16，也就是说默认创建 16 个 Segment。

参考资料

Java 容器深入剖析