Java的集合类（容器）

四大集合接口

Java中的集合类主要由Collection和Map这两个接口派生而出，其中Collection接口又派生出三个子接口，分别是Set、List、Queue。所有的Java集合类，都是Set、List、Queue、Map这四个接口的实现类，这四个接口将集合分成了四大类：

• Set代表无序的，元素不可重复的集合
• List代表有序的，元素可以重复的集合
• Queue代表先进先出（FIFO）的队列
• Map代表具有映射关系（key-value）的集合

这些接口拥有众多的实现类，其中最常用的实现类有HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap等。

集合类的继承树

Collection体系继承树：

Map体系继承树：

线程安全和线程不安全

线程不安全的集合类：HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap
它们虽然线程不安全，但是性能很高。如果需要使用线程安全的集合类，则可以使用Collections工具类提供的synchronizedXxx()方法，将这些集合类包装成线程安全的集合类。

线程安全集合类：Vector、Hashtable
它们比较古老，而且性能很差。如果要使用线程安全的集合类，建议将线程不安全的集合类包装成线程安全集合类的方式，而不是直接使用这些古老的API。

从Java5开始，Java在java.util.concurrent包下提供了大量支持高效并发访问的集合类，它们既能包装良好的访问性能，有能包装线程安全。这些集合类可以分为两部分，它们的特征如下：

• 以Concurrent开头的集合类：
  以Concurrent开头的集合类代表了支持并发访问的集合，它们可以支持多个线程并发写入访问，这些写入线程的所有操作都是线程安全的，但读取操作不必锁定。以Concurrent开头的集合类采用了更复杂的算法来保证永远不会锁住整个集合，因此在并发写入时有较好的性能。
• 以CopyOnWrite开头的集合类：
  以CopyOnWrite开头的集合类采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时，线程将会直接读取集合本身，无须加锁与阻塞。当线程对此类集合执行写入操作时，集合会在底层复制一份新的数组，接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作，因此它是线程安全的。

1 Map集合

1.1 Map的常用实现类

1. HashMap
   应用场景：不需要排序、不要求线程安全（如果需要线程安全则用ConcurrentHashMap，它的性能好于Hashtable）
   特点：性能最好的Map

2. LinkedHashMap
   应用场景：需要按插入顺序排序、不要求线程安全

3. TreeMap
   应用场景：需要将key按自然顺序排列甚至是自定义顺序排列、线程不安全

4. ConcurrentHashMap
   应用场景：线程安全、不需要排序

• 补充：LinkedHashMap、TreeMap如果需要线程安全可用Collections工具类将两者包装成线程安全的Map。

1.2 Map的put过程

HashMap是最经典的Map实现，下面以它的视角描述put的过程：

1. 首次扩容：
   先判断数组是否为空，若数组为空则进行第一次扩容（resize）
2. 计算索引：
   通过hash算法，计算键值对在数组中的索引
3. 插入数据：
   如果当前位置元素为空，则直接插入数据
   如果当前位置元素非空，且key已存在，则直接覆盖其value
   如果当前位置元素非空，且key不存在，则将数据链到链表末端
   若链表长度达到8，则将链表转换成红黑树，并将数据插入树中
4. 再次扩容：
   如果数组中元素个数（size）超过threshold，则再次进行扩容操作。

1.3 HashMap的特点

1. HashMap是线程不安全的实现；
2. HashMap可以使用null作为key或value。

1.4 jdk7和jdk8中HashMap的区别

1. jdk7
   jdk7中的HashMap，是基于数组+链表来实现的，它的底层维护一个Entry数组。它会根据计算的hashCode将对应的KV键值对存储到该数组中，一旦发生hashCode冲突，那么就会将该KV键值对放到对应的已有元素的后面， 此时便形成了一个链表式的存储结构
   jdk7中HashMap的实现方案有一个明显的缺点，即当Hash冲突严重时，在桶上形成的链表会变得越来越长，这样在查询时的效率就会越来越低，其时间复杂度为O(N)。

2. jdk8
   jdk8中的HashMap，是基于数组+链表+红黑树来实现的，它的底层维护一个Node数组。当链表的存储的数据个数大于等于8的时候，不再采用链表存储，而采用了红黑树存储结构。这么做主要是在查询的时间复杂度上进行优化，链表为O(N)，而红黑树一直是O(logN)，可以大大的提高查找性能。

1.5 HashMap底层的实现原理

HashMap基于hash算法，通过put方法和get方法存储和获取对象。
存储对象时，我们将K/V传给put方法时，它调用K的hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Factor则resize为原来的2倍)。
获取对象时，我们将K传给get方法，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals方法确定键值对。
如果发生碰撞的时候，HashMap通过链表将产生碰撞冲突的元素组织起来。在Java8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

1.6 HashMap实现线程安全的方法

1. 直接使用Hashtable类（不推荐）
2. 直接使用ConcurrentHashMap
3. 使用Collections将HashMap包装成线程安全的Map

1.7 HashMap和HashTable的区别

1. Hashtable是一个线程安全的Map实现，但HashMap是线程不安全的实现，所以HashMap比Hashtable的性能高一点。
2. Hashtable不允许使用null作为key和value，如果试图把null值放进Hashtable中，将会引发空指针异常，但HashMap可以使用null作为key或value。

1.8 HashMap与ConcurrentHashMap的区别

HashMap是非线程安全的，这意味着不应该在多线程中对这些Map进行修改操作，否则会产生数据不一致的问题，甚至还会因为并发插入元素而导致链表成环，这样在查找时就会发生死循环，影响到整个应用程序。

Collections工具类可以将一个Map转换成线程安全的实现，其实也就是通过一个包装类，然后把所有功能都委托给传入的Map，而包装类是基于synchronized关键字来保证线程安全的（Hashtable也是基于synchronized关键字），底层使用的是互斥锁，性能与吞吐量比较低。

ConcurrentHashMap的实现细节远没有这么简单，因此性能也要高上许多。它没有使用一个全局锁来锁住自己，而是采用了减少锁粒度的方法，尽量减少因为竞争锁而导致的阻塞与冲突，而且ConcurrentHashMap的检索操作是不需要锁的。

1.9 ConcurrentHashMap是怎么实现的

1. jdk1.7

   在jdk1.7中，ConcurrentHashMap是由Segment数据结构和HashEntry数组结构构成，采取分段锁来保证安全性。Segment是ReentrantLock重入锁，在ConcurrentHashMap中扮演锁的角色，HashEntry则用于存储键值对数据。一个 ConcurrentHashMap里包含一个Segment数组，一个Segment里包含一个HashEntry 数组，Segment的结构和HashMap类似，是一个数组和链表结构。
   

2. jdk1.8

   jdk1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap，虽然在jdk1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本。
   

1.10 对LinkedHashMap的理解

LinkedHashMap使用双向链表来维护key-value对的顺序（其实只需要考虑key的顺序），该链表负责维护Map的迭代顺序，迭代顺序与key-value对的插入顺序保持一致。

LinkedHashMap可以避免对HashMap、Hashtable里的key-value对进行排序（只要插入key-value对时保持顺序即可），同时又可避免使用TreeMap所增加的成本。

LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能。但因为它以链表来维护内部顺序，所以在迭代访问Map里的全部元素时将有较好的性能。

1.11 LinkedHashMap的底层原理

LinkedHashMap继承于HashMap，它在HashMap的基础上，通过维护一条双向链表，解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题。在实现上，LinkedHashMap很多方法直接继承自HashMap，仅为维护双向链表重写了部分方法。

1.12 TreeMap的底层原理

TreeMap基于红黑树（Red-Black tree）实现。映射根据其键的自然顺序进行排序，或者根据创建映射时提供的Comparator进行排序，具体取决于使用的构造方法。TreeMap的基本操作containsKey、get、put、remove方法，它的时间复杂度是log(N)。

TreeMap包含几个重要的成员变量：root、size、comparator。其中root是红黑树的根节点。它是Entry类型，Entry是红黑树的节点，它包含了红黑树的6个基本组成：key、value、left、right、parent和color。Entry节点根据根据Key排序，包含的内容是value。Entry中key比较大小是根据比较器comparator来进行判断的。size是红黑树的节点个数。

1.13 Map和Set有什么区别

Set代表无序的，元素不可重复的集合；
Map代表具有映射关系（key-value）的集合，其所有的key是一个Set集合，即key无序且不能重复。

2 List集合

2.1 List和Set有什么区别

Set代表无序的，元素不可重复的集合；
List代表有序的，元素可以重复的集合。

2.2 ArrayList和LinkedList有什么区别

1. ArrayList的实现是基于数组，LinkedList的实现是基于双向链表；
2. 对于随机访问ArrayList要优于LinkedList，ArrayList可以根据下标以O(1)时间复杂度对元素进行随机访问，而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起，查找某个元素的时间复杂度是O(N)；
3. 对于插入和删除操作，LinkedList要优于ArrayList，因为当元素被添加到LinkedList任意位置的时候，不需要像ArrayList那样重新计算大小或者是更新索引；
4. LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

2.3 线程安全的List

Vector

Vector是比较古老的API，虽然保证了线程安全，但是由于效率低一般不建议使用。

Collections.SynchronizedList

SynchronizedList是Collections的内部类，Collections提供了synchronizedList方法，可以将一个线程不安全的List包装成线程安全的List，SynchronizedList。它比Vector有更好的扩展性和兼容性，但是它所有的方法都带有同步锁，也不是性能最优的List。

CopyOnWriteArrayList

CopyOnWriteArrayList是Java1.5在java.util.concurrent包下增加的类，它采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时，线程将会直接读取集合本身，无须加锁与阻塞。当线程对此类集合执行写入操作时，集合会在底层复制一份新的数组，接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作，因此它是线程安全的。在所有线程安全的List中，它是性能最优的方案。

2.4 ArrayList的数据结构

ArrayList的底层是用数组来实现的，默认第一次插入元素时创建大小为10的数组，超出限制时会增加50%的容量，并且数据以System.arraycopy()复制到新的数组，因此最好能给出数组大小的预估值。

按数组下标访问元素的性能很高，这是数组的基本优势。直接在数组末尾加入元素的性能也高，但如果按下标插入、删除元素，则要用System.arraycopy()来移动部分受影响的元素，性能就变差了，这是基本劣势。

2.5 CopyOnWriteArrayList的原理

CopyOnWriteArrayList是Java并发包里提供的并发类，简单来说它就是一个线程安全且读操作无锁的ArrayList。正如其名字一样，在写操作时会复制一份新的List，在新的List上完成写操作，然后再将原引用指向新的List。这样就保证了写操作的线程安全。

CopyOnWriteArrayList允许线程并发访问读操作，这个时候是没有加锁限制的，性能较高。而写操作的时候，则首先将容器复制一份，然后在新的副本上执行写操作，这个时候写操作是上锁的。结束之后再将原容器的引用指向新容器。注意，在上锁执行写操作的过程中，如果有需要读操作，会作用在原容器上。因此上锁的写操作不会影响到并发访问的读操作。

• 优点：读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。在遍历传统的List时，若中途有别的线程对其进行修改，则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想，遍历和修改操作分别作用在不同的List容器，所以在使用迭代器进行遍历时候，也就不会抛出ConcurrentModificationException异常了。
• 缺点：一是内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC。二是无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。

3 Set容器

3.1 HashSet的底层结构

HashSet是基于HashMap实现的，默认构造方法是构建一个初始容量为16，负载因子为0.75的HashMap。它封装了一个HashMap对象来存储所有的集合元素，所有放入 HashSet中的集合元素实际上由HashMap的key来保存，而HashMap的value则存储了一个PRESENT，它是一个静态的Object对象。

3.2 TreeSet和HashSet的区别

HashSet、TreeSet中的元素都是不能重复的，并且它们都是线程不安全的，二者的区别是：

1. HashSet中的元素可以是null，但TreeSet中的元素不能是null；
2. HashSet不能保证元素的排列顺序，而TreeSet支持自然排序、定制排序两种排序的方式；
3. HashSet底层是采用哈希表实现的，而TreeSet底层是采用红黑树实现的。

4 Queue容器

4.1 BlockingQueue中的方法

为了应对不同的业务场景，BlockingQueue 提供了4 组不同的方法用于插入、移除以及对队列中的元素进行检查。如果请求的操作不能得到立即执行的话，每组方法的表现是不同的。这些方法如下：

	抛异常	特定值	阻塞	超时
插入	add(e)	offer(e)	put(e)	offer(e, time, unit)
移植	remove()	poll()	take()	poll(time, unit)
检查	element()	peek()

四组不同的行为方式含义如下：

• 抛异常：如果操作无法立即执行，则抛一个异常；
• 特定值：如果操作无法立即执行，则返回一个特定的值(一般是 true / false)。
• 阻塞：如果操作无法立即执行，则该方法调用将会发生阻塞，直到能够执行；
• 超时：如果操作无法立即执行，则该方法调用将会发生阻塞，直到能够执行。但等待时间不会超过给定值，并返回一个特定值以告知该操作是否成功(典型的是true / false)。

4.2 BlockingQueue的实现

BlockingQueue是一个接口，它的实现类有ArrayBlockingQueue、DelayQueue、LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue等。它们的区别主要体现在存储结构上或对元素操作上的不同，但是对于put与take操作的原理是类似的。下面以ArrayBlockingQueue为例，来说明BlockingQueue的实现原理。

首先看一下ArrayBlockingQueue的构造方法，它初始化了put和take方法中用到的关键成员变量，这两个变量的类型分别是ReentrantLock和Condition。ReentrantLock是AbstractQueuedSynchronizer（AQS）的子类，它的newCondition方法返回的Condition实例，是定义在AQS类内部的ConditionObject类，该类可以直接调用AQS相关的方法。

/** ArrayBlockingQueue的构造器 **/
public ArrayBlockingQueue(int capacity, boolean fair) {
	if (capacity <= 0)
		throw new IllegalArgumentException();
	this.items = new Object[capacity];
	lock = new ReentrantLock(fair);
	notEmpty = lock.newCondition();
	notFull = lock.newCondition();
}

put方法会在队列末尾添加元素，如果队列已经满了，无法添加元素的话，就一直阻塞等待到可以加入为止。方法的源码如下所示。我们会发现put方法使用了wait/notify的机制。与一般生产者-消费者的实现方式不同，同步队列使用ReentrantLock和Condition相结合的机制，即先获得锁，再等待，而不是synchronized和wait的机制。

/** put方法源码：注释是我根据自己的理解加的，如有错误欢迎指正 **/
public void put(E e) throws InterruptedException {
	checkNotNull(e);  // 检查插入的元素是否为空
	final ReentrantLock lock = this.lock;  // 获取锁
	lock.lockInterruptibly();  // 上锁
	try {
		while (count == items.length)  // 队列满
			notFull.await();  // 等待
		enqueue(e);  // 入队
	} finally {
		lock.unlock();  // 释放锁
	}
}

再来看一下消费者调用的take方法，take方法在队列为空时会被阻塞，一直到阻塞队列加入了新的元素。

/** take方法源码：注释是我根据自己的理解加的，如有错误欢迎指正 **/
public E take() throws InterruptedException {
	final ReentrantLock lock = this.lock;  // 获取锁
	lock.lockInterruptibly();  // 上锁
	try {
		while (count == 0)  // 队列为空时
			notEmpty.await();  // 等待
		return dequeue();  // 出队
	} finally {
		lock.unlock();  // 释放锁
	}
}