1、Java中有哪些集合

java.util包下面中最顶层的接口时是Collection接口，Collection下面又有三个接口分别是：

• Set：表示无序不可重复集合
• List：表示有序可以重复集合
• Queue：表示先入先出的队列

常见的实现类包含Set接口下有HashSet，TreeSet

List接口下面含有ArrayList，LinkedList，Stack等

Queue有PriorityQueue表示优先级队列，ArrayDeque，或者由链表实现的队列LinedList

Map表示（key-value）类型的集合，接口下有HashMap和TreeMap。

2、有哪些是线程安全的集合

在java.util包下面大多都是线程不安全的集合，也有少数线程安全的集合例如：Hashtable和Vector，但是这两个集合，都是一些古老的API，从名字就可以看出来，甚至Hashtable没有符合Java的命名规范。虽然线程安全，但是效率相较于其他常用的集合非常差。所以如果我们如果需要使用线程安全的集合可以使用Collections将HashMap包装成线程安全的Map。具体操作如下：

Map<String,String> unSafeMap = new HashMap<String,String>();
Map safeMap = Collections.synchronizedMap(unSafeMap);

或者可以使用java.util.concurrent包下对应的集合。

在jdk1.5之后Java引入了java.util.concurrent包里面实现了常用集合的线程安全的实现类：“

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

3、Map接口的实现类

map接口下有常见的四个实现类分别是：HashMap，TreeMap，ConcurrentHashMap，LinkedHashMap。

根据使用情况选择需要使用的map集合：

• 如果只是需要map集合不考虑排序和线程安全问题，HashMap是最佳选择，因为HashMap的效率最高，查询和插入删除的时间复杂度都是·O（1）.
• 如果考虑线程安全不考虑排序问题，那么可以使用ConcurrentHashMap，这个集合是通过CAS或分段锁这种机制保证的线程安全
• 如果需要排序而且只需要自然插入的排序，那么可以使用LinkedHashMap。
• 如果需要自定义排序规则那么使用TreeMap，TreeMap底层是通过红黑树实现的，支持排序。
• 如果需要排序和线程安全可以使用Collections工具类构造线程安全的集合。

4、TreeMap和HashMap的区别

1. HashMap是基于hash表和链表实现的（jdk1.8前），基于hash表+链表+红黑树实现的（1.8起）
2. HashMap的效率更高，因为是基于hash表实现，所以时间复杂度是O（1），TreeMap是基于红黑树实现的，查询效率是O(log2 N)
3. TreeMap是有序的集合，HashMap无序，由底层数据结构决定。
4. 都不是线程安全的

5、HashMap的机制

在jdk1.8之后，hashMap底层数据结构从hash表+链表变成了hash表+链表+红黑树。这是因为在hash冲突比较严重的情况下，防止hash表每个位置后面的链表过长导致查询效率变成O（n）,如果比较长的话，用红黑树来存储查询时间复杂度最大也是O（log2 N）。

1. HashMap初始容量是16，在插入时会检查容量，如果当前存储的节点数量大于负载因子（默认0.75）*最大容量（默认16）的时候，HashMap就会以2倍的容量进行扩容。
2. 为了解决hash冲突，hash表中的元素是通过单向链表的方式存储，在链表长度达到一个阈值之后（默认8），底层链表就会被构建成为一个红黑树来提高性能。当我们删除元素到链表长度为6的时候。红黑树会自动被转化为链表 提高性能。
3. 检查链表长度转换成红黑树之前，还会先检测当前数组数组是否到达一个阈值（64），如果没有到达这个容量，会放弃转换，先去扩充数组。

5.1、为什么要以两倍的大小进行扩容？

组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过hash转换坐标的方法计算后，恰好出现一个现象：最高位是0则坐标不变，最高位是1则坐标变为“10000+原坐标”，即“原长度+原坐标”。

5.2、为什么阈值是8和6而不是大于等于8和小于8？

因为可能有些HashMap在使用的过程中频繁添加删除元素，导致链表长度频繁的在7和8之间浮动，如果此时阈值是8的话，那么将会频繁的构造红黑树和链表。那么将浪费大量的系统资源，进行底层数据结构的转换。而进入红黑树是为了提高效率，此时反而达不到提高效率的效果，而会降低效率。

5.3、HashMap为什么使用红黑树而不是B树？

因为B/B+树都更适合存储数据数量比较大的情况。更适合在外存上使用，而我们引入红黑树是为了解决链表过长导致查询效率下降的问题，HashMap的一个数组空间中不可能会存储大量的元素。而元素量比较少的时候，使用B/B+树会导致数据都会挤在一个节点，此时效率和链表一样。