1.Java中有哪些容器（集合类）？
Java中的集合类主要由Collection和Map这两个接口派生而出，其中Collection接口又派生出三个子接口，分别是Set、List、Queue。Java所有的集合类都是Set、List、Queue、Map这四个接口的实现类，这四个接口将集合分为了四大类：
（1）Set：代表无序的、元素不可重复的集合。
（2）List：代表有序的、元素可以重复的集合。
（3）Queue：代表先进先出（FIFO）的队列。
（4）Map：代表有映射关系（key-value）的集合。key不可重复，value可以。两个key可以引用相同的对象，但是key不能重复。
这些接口拥有众多的实现类，其中最常用的实现类有HashSet、TreeSet、ArrayList、LinkedList、ArrayQueue、HashMap、TreeMap。
Collection体系继承树：
Map体系的继承树：
2.Java中的容器，线程安全和线程不安全的分别有哪些？
java.util包下的集合类大部分都是线程不安全的，如常用的HashSet、TreeSet、LinkedList、ArrayList、ArrayQueue、HashMap、TreeMap等，这些都是线程不安全，但它们的优点是性能好。如果需要使用线程安全的集合类，可以使用Collections工具类提供的synchronizedXxx()方法，将这些集合类包装成线程安全的集合类。
java.util包下也有线程安全的集合类，如Vector、HashTable。这些集合类都是比较古老的API，虽然实现了线程安全，但是性能很差。
3.Map接口有哪些实现类？
Map接口有很多实现类，常用的有HashMap、TreeMap、LinkedHashMap、ConcurrentHashMap等。
（1）对于不需要排序的场景，推荐使用HashMap，因为它的性能最好；
（2）如果考虑线程安全，可以考虑ConcurrentHashMap，也可以将线程不安全实现类包装成线程安全实现类。
（3）对于需要排序的场景，如果是按插入顺序排序，则推荐使用LinkedHashMap；如果是需要将key按自然顺序排序甚至自定义排序，推荐使用TreeMap。
4.描述一下Map put的过程
HashMap是Map最经典的实现，下面以它来介绍put的过程，
（1）首次扩容
判断数组是否为空，若数组为空则进行首次扩容（resize）。
（2）计算索引
底层调用key的hascode方法，计算得到hash值。再利用哈希算法将hash值转化为数组索引下标。
（3）插入数据
若当前索引下标的位置为空，则直接插入数据；
若当前索引下标的位置不为空，将当前的key与单链表中的key进行equals对比：
若返回值均为false，则将当前节点添加到链表尾部；
若其中一个equals返回了true，则链表中对应这个节点的value会被当前节点的value覆盖（保证了不可重复性）。
若链表长度大于8，则将链表转换为红黑树，并将数据插入树中。
（4）再次扩容
若数组中的元素个数（size）超过临界点（threshold），则再次进行扩容操作。
5.如何得到一个线程安全的Map？
（1）使用Collections工具类，将线程不安全的Map包装成线程安全的Map；
（2）使用java.util.concurrent包下的Map，如ConcurrentHashMap；
不建议使用HashTable，虽然它是线程安全的，但其性能很差。
6.HashMap的特点
HashMap是线程不安全的实现；
HashMap可以使用null作为key或value，但只能有一个。
7.JDK7和JDK8的HashMap有什么区别？
JDK7的HashMap是基于数组+链表实现的，它的底层维护一个Entry数组。它会根据计算的hashCode将对应的键值对存储到数组中。一旦发生hashCode冲突，就会将当前键值对存储到对应的已有元素的后面，这样就形成了链表式的存储结构。但这样有一个缺点，当hash冲突严重时，链表会变得越来越长，导致查询效率变得更低，其时间复杂度为O(N)。
JDK8的HashMap是基于数组+链表+红黑树实现的，它的底层维护一个Node数组。当链表存储数据的个数大于等于8时，就不再采用链表，而是采用红黑树进行存储，这样主要对查询的时间复杂度进行了优化，其时间复杂度为O(nlogN)，大大提高了查找性能。
8.HashMap底层的实现原理
它基于hash算法，通过put和get方法存储和获取数据。
存储对象时，将键值对传给put方法时，他会调用key的hashCode方法计算hash值，从而确定数组下标位置，进一步存储，HashMap会根据当前数组的占用情况自动调整容量。
获取对象时，将key传给get方法，调用key的hasshCode方法计算hash值，从而确定数组下标位置，并进一步调用equals方法确定键值对。
在发生hash冲突的时候，HashMap通过链表将产生冲突的元素组织起来。在JDK8中，如果链表中的元素大于等于8个，则使用红黑树来代替链表，从而提高速度。
9.介绍一下HashMap的扩容机制
（1）数组的初始容量为16，扩充是以2的次方进行的。一是为了提高性能使用足够大的数组，二是为了能用位运算代替模运算；
（2）数组是否需要扩充，是通过负载因子进行判断的。如果当前元素个数为数组容量的0.75时，就会扩充数组。这个0.75就是默认的负载因子，可由构造器传入。
（3）为了解决碰撞，数组中的元素是单链表类型。当链表长度达到一个阈值时（7或8），会将链表转换为红黑树；当链表长度缩小到6时，又会将红黑树转换成单链表，从而提高性能。
（4）对于第3点补充说明，检查链表长度转换成红黑树之前，还会先检测当前数组容量是否到达一个阈值（64），如果没有到达这个容量，会放弃转换，先去扩充数组。所以上面也说了链表长度的阈值是7或8，因为会有一次放弃转换的操作。
10.HashMap中循环链表是如何产生的？
在多线程的条件下，当重新调整HashMap的大小时，就会存在条件竞争。假设两个线程都发现了HashMap需要调整大小，他们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的索引下标位置的时候，HashMap并不会把元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历。当条件竞争发生时，就会产生死循环。
11.HashMap为什么线程不安全？
多线程同时put时，如果同时调用了resize操作，可能会导致循环链表产生，进而使得后面get的时候，会死循环。
同10。
12.HashMap为什么使用红黑树，而不使用B树？
B树多用于外存上时，B树也被称为磁盘友好的数据结构。
HashMap本来是基于数组+链表实现的，由于链表的查询速度低，因此需要被查询速率较高的树结构来代替。
如果用B树的话，在数据量不够大的情况下，所有数据会挤在同一个节点上，这时查询效率就下降为链表了。
13.HashMap如何实现线程安全？
（1）直接使用HashTable类；不推荐使用，虽然其线程安全，但是性能很差；
（2）直接使用ConcurrentHashMap类；
（3）使用Collection工具类将HashMap包装成线程安全的Map类。
14.HashMap是如何解决哈希冲突的？
为了解决碰撞，数组中的元素是单向链表类型。当链表长度达到一个阈值时，将会使用红黑树来代替链表；而当链表的长度缩小到某个阈值时，又会将红黑树转换为链表。提高性能。
15.HashMap和HashTable的区别
（1）HashTable是线程安全的，HashMap是线程不安全的，所以HashMap比HashTable性能更高一点；
（2）HashTable不允许存储的key或value为null，当试图将null值存入HashTable，会发生空指针异常，而HashMap允许存储的key或value为空。
16.HashMap和ConcurrentHashMap的区别
（1）HashMap
HashMap是非线程安全的，这就意味着不应该在多线程中对Map进行修改操作，否则会产生数据不一致的问题，甚至会因为并发插入数据，导致链表成环，这样在查找数据时会陷入死循环，影响到整个应用程序；
Collections工具类可以将Map集合转换为线程安全的实现，其实就是通过包装类，然后把所有功能都委托给传入的Map，而包装类是基于synchronized关键字来保证线程安全的，底层使用的是互斥锁，性能和吞吐量比较低。
（2）ConcurrentHashMap
ConcurrentHashMap没有使用一个全局锁来锁住自己，而是采用了减少锁粒度的方法，尽量减少因为竞争锁而导致的阻塞与冲突，而且ConcurrentHashMap的检索操作是不需要锁的。
17.ConcurrentHashMap是怎么实现的 / 底层具体实现 /线程安全的具体实现方式
（1）JDK1.7中
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成，采用分段锁来保证安全性。Segment是重入锁，在ConcurrentHashMap中扮演锁的角色，HashEntry则用于存储键值对。一个ConcurrentHashMap里面包含一个Segment数组，一个Segment里面包含一个HashEntry数组。Segment和HashMap结构类似，都是一个数组和链表结构。
首先将数据分为⼀段⼀段的存储，然后给每⼀段数据配⼀把锁，当⼀个线程占用锁访问其中⼀个段数据时，其他段的数据也能被其他线程访问。
（2）JDK1.8中
JDK1.8的实现摒弃了Segment的概念，而是直接使用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来像是优化过且线程安全的HashMap。虽然在JDK1.8中还是能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本。
TreeBin是红黑二叉树节点，Node是链表节点。synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。
18.ConcurrentHashMap是怎么分段分组的？
19.对LinkedHashMap的理解
LinkedHashMap使用双向链表来维护键值对的顺序（其实只需要考虑键），该链表负责维护Map的迭代顺序，迭代顺序与键值对的插入顺序一致。
LinkedHashMap可以避免对HashMap、HashTable里的键值对进行排序，同时又可以避免使用TreeMap所增加的成本。
LinkedHashMap需要维护元素的插入顺序，因此其性能稍差于HashMap，但是它以链表维护内部顺序，因此在迭代访问Map里的所有元素时，有较好的性能。
20.介绍一下LinkedHashMap的底层实现原理
LinkedHashMap继承自HashMap，它在HashMap的基础上，通过维护一条双向链表，解决了HashMap不能随时保持插入顺序与遍历顺序一致的问题。
在实现上，LinkedHashMap很多方法直接继承自HashMap，仅为维护双向链表重写了部分方法。
21.介绍一下TreeMap的底层原理
TreeMap是基于红黑树实现的。映射是根据其键的自然顺序进行排序，或者是根据创建映射时传入的比较器Comparator进行排序，具体取决于使用的构造方法。TreeMap的基本方法有put、get、remove、containsKey等方法。
TreeMap有几个重要的成员变量：root、size、comparator。其中，root是红黑树的根节点，它是Entry类型，Entry是红黑树的节点，它由以下几部分组成：key、value、left、right、color、parent。Entry节点是根据key排序的，包含的内容是value。Entry中key排序的规则是由比较器comparator定义的。size是红黑树节点的个数。
22.Set和Map有什么区别？
（1）Set是无序的、元素不可重复的集合；
（2）Map是有映射关系（key-value）的集合，其中，所有的key是一个Set集合，即key是无序的、不可重复的。
23.List和Set有什么区别？
（1）List是有序的、元素可以重复的集合；
（2）Set是无序的、元素不可重复的集合。
24.ArrayList和LinkedList有什么区别？
（1）ArrayList是基于数组实现的，LinkedList是基于双向链表实现的；
（2）对于随机访问元素，ArrayList要优于LinkedList。ArrayList根据数组索引下标以O(1)的时间复杂度对元素进行访问；LinkedList中的每一个元素都依靠地址指针和它后一个元素连接在一起，查找某个元素时，其时间复杂度为O(N)；
（3）对于删除和插入操作，LinkedList要优于ArrayList。因为LinkedList删除或插入元素时，不需要像ArrayLIst那样重新计算大小或更新索引；
（4）LinkedList比ArrayList更占内存。LinkedList中的节点除了储存数据，还储存了两个引用，一个指向前一个节点，一个指向后一个节点。
25.有哪些线程安全的List？
（1）Vector
Vector是比较古老的API，虽然实现了线程安全，但是性能很差，一般不建议使用；
（2）Collection.SynchronizedList
SynchronizedList是Collections的内部类，Collections内部提供了synchronizedList方法，该方法可以将非线程安全的List包装成线程安全的List，即SynchronizedList。它比Vector更好的扩展性和兼容性，但是它的所有方法都带有同步锁，不是性能最优的List；
（3）CopyOnWriteArrayList
CopyOnWriteArrayList是Java1.5在java.util.concurrent包下增加的类，它采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时，会直接读取集合本身，无需加锁和阻塞。当执行写入操作时，集合会在底层复制一份新的数组，然后对新的数组进行写入操作，由于集合的写入操作都是对数组的副本执行的，因此它是线程安全的。在所有线程安全的List集合中，它是性能最优的。
26.介绍一下ArrayList的数据结构
ArrayList是基于数组实现的，默认第一次插入元素时创建大小为10的数组，超出限制时，扩充50%的容量，并且数据以System.arraycopy()复制到新的数组。
按数组索引来访问元素的性能很高，这是数组的基本优势。直接在数组末尾添加元素，性能也高。但是，按索引来增删元素时，则要用System.arraycopy()来移动部分受影响元素，因此性能就会变差。
27.谈一谈CopyOnWriteArrayList的原理
CopyOnWriteArrayList是Java并发包（java.util.concurrent包）里面提供的并发类，简单来说它是线程安全且读写无锁的ArrayList集合。在进行写操作时，它会复制一份新的List，并在新的List上完成写操作，最后将原引用指向新的List，这样就保证了写操作的线程安全。
CopyOnWriteArrayList允许线程并发访问读操作，这个时候是没有加锁限制的，性能较高。而在写操作的时候，会先将容器复制一份，并在新的副本上执行写操作，这个时候写操作是上锁的。结束写操作之后，会将原容器的引用指向新的容器。注意，在执行写操作的过程中，如果有需要读操作，会作用在原容器上，因此，上锁的写操作是不会影响到并发的读操作的。
优点：读性能很高，因为无需进行同步操作，比较适用于多读少写的并发场景。
缺点：占用内存多，每次写操作都需要复制一份新的List，数据量大时，内存压力较大。
28.HashSet和TreeSet的区别
两个都是线程不安全的，元素是无序的、不可重复的。区别有以下三点，
（1）HastSet中的元素可以为null，TreeSet中的元素不可以为null；
（2）HashSet底层是哈希表实现的，TreeSet底层是红黑树实现的；
（3）HashSet不能保证元素的排列顺序，TreeSet支持自然顺序排序和自定义排序两种方式。
29.说一说HashSet的底层结构
HashSet是基于HashMap实现的，默认构造函数是一个创建初始容量为16，负载因子为0.75的HashMap。它封装了一个HashMap对象来存储所有集合元素，所有放入HashSet的元素实际上是由HashMap的key保存，HashMap的value则存储了一个PRESENT，它是一个静态的Object对象。
