1.List，Set，Map三者的区别？

• List是一个列表，用来存储有序的、可重复的元素
• Set是存储无序集合，一般用来判重
• Map用键值对(key-value)进行存储，key无序不可重复，value无序可以重复

2.List，Set，Queue，Map在Java中分别对应哪些实现类？底层的数据结构？

• List由ArrayList实现数组，LinkList实现链表
• Set由HashSet和LinkHashSet实现无序set， TreeSet红黑树实现有序set
• Queue由PriorityQueue实现小根堆
• Map由HashMap实现最常用的map，其余和set一样

List

3.ArrayList和Array、Vector的区别？

• 和Array相比：ArrayList更加灵活，可以动态地进行插入、删除、遍历等操作，Array只能通过下标访问
• 和Vector相比：两者都是List动态数组的实现类，ArrayList适合频繁的查找工作，相对线程不安全一点，但是更常用。

4.ArrayList与LinkedList区别?

• 底层数据结构：前者底层使用Object数组，后者底层使用 双向链表
• 插入和删除是否受元素位置影响：前者会受到影响，表头表尾插入O(1)，指定位置插入删除O(n)；后者因为采用链表存储，头尾插入或删除为O(1)，指定位置i插入删除也是O(n)
• 是否支持快速随机访问：前者可以通过序号快速进行随机访问
• 内存空间占用：前者肯定是会浪费一定的空间的，因为ArrayList每次会会在列表表尾预留一定的空间，然后当扩容到最大容量时，会有一个扩容操作，就是会创建一个新的更大的数组，将原来数组的元素复制到新数组中，新数组大小是原来的1.5倍左右
• ArrayList扩容机制步骤：计算新容量->创建新数组->复制元素->更新引用（将ArrayList引用指向新数组）

Queue

5.Queue与Deque的区别？

Queue是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循先进先出（FIFO）规则。Deque是双端队列，在队列的两端均可以插入或删除元素。

6.PriorityQueue有什么特点？

默认小根堆，其与Queue的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

HashMap

7.HashMap查询，删除的时间复杂度？

• 没有哈希冲突的情况下：查询和删除都是O(1)，可以直接在常数级别范围内实现
• 转链表的情况下：查询和删除操作的时间复杂度为 O(n)，其中 n 是链表中的元素数量。
• 转红黑树的情况下：查询和删除操作的时间复杂度为 O(logn)，其中 n 是红黑树中的元素数量

8.HashMap的底层实现？

• 数组和链表；红黑树
• 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
• 存储时，如果出现hash值相同的key，此时有两种情况。 a. 如果key相同，则覆盖原始值； b. 如果key不同（出现冲突），则将当前的key-value放入链表或红黑树中
• 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值
• 红黑树：当链表长度大于8然后数组长度大于64就转为红黑树

9.HashMap 的长度为什么是 2 的幂次方？

使用二进制来存储能提高运算效率

10.HashMap与HashSet、TreeMap、Hashtable的区别？

• 与HashSet：一个存储键值对，用put()添加，使用key计算hashcode；一个仅存储对象，用add()添加，使用成员对象计算hashcode
• 与TreeMap：比HashMap多了对集合元素根据key排序的能力以及集合内元素搜索的能力
• 与Hashtable：前者效率高，非线程安全；

ConcurrentHashMap

11.ConcurrentHashMap与Hashtable的区别？

• 底层数据结构：前者采用 分段的数组+链表 实现，后者和HashMap一样都是采用 数组+链表 的形式实现
• 实现线程安全的方式（重要）：
  – JDK1.7时候：ConcurrentHashMap对整个数组进行了分割（分段锁）操作，每一把锁只管对应一部分数据，在多线程访问的时候呢就不会出现锁竞争的问题，能够提高并发访问率
  – JDK1.8时候：直接用 Node 数组+链表+红黑树的数据结构来实现
  – Hashtable: 同一把锁 ，这样会导致效率低下，当其他线程同步访问的时候，可能会出现阻塞或轮询的状态。

12.ConcurrentHashMap 线程安全的具体实现方式/底层具体实现？（重要）

• JDK1.8之前：
• 首先将数据分为一段一段（这个“段”就是 Segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

• JDK1.8之后：
• ConcurrentHashMap 取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。
• 锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。