1：Collection 集合框架
2：并发集合框架
List,Set,Queue。
3：HashMap
3-1：HashMap 的数据结构
数组+链表，链表容量为 9 时转化为红黑树，扩容时小于等于 6 退化为链表。
3-2：链表插入法
3-2-1：头插法
1 | node.next = head; |
2-2-2：尾插法
1 | tail.next = node; |
3-2-3：扩容死循环问题
jdk1.8 以前链表扩容是加入到链表首，而 1.8 是加入到链表尾，已经不会出现这个问题。
3-3：红黑树的引入
3-3-1：HashMap 为什么要树化?
在最坏的情况下，查询效率从 O(1)变为线性的 O(n)，而红黑树就是为了解决这个问题。红黑树能保证最坏情况也有 O(logn)的时间复杂度。
3-3-2：HashMap 树化门槛及作用
链表长度大于 8 就会进行树化，是为了保证最坏情况的时间复杂度。
3-3-3：为什么不把链表全部换为红黑树
只有数据很多的情况下才需要红黑树，因为红黑树所消耗的资源和链表更大，而时间消耗也不会差太多。
3-3-4：为什么是使用红黑树而不是 AVL 树？
avl 树的自平衡占用资源太多，比红黑树更加严格。
3-3-5：为什么不用二叉查找树代替，而选择红黑树
二叉查找树也会存在最坏情况 O(n)的时间复杂度，所以在二叉查找树和 avl 树之间做一个平衡，选择了红黑树。
3-4：HashMap 为什么可以插入空值?
HashMap 中如果 key == null，那么 key 的 hash 为 0，而 Hashtable 中会直接抛出空指针异常。
3-5：JDK8 中 HashMap 的改变
扩容机制和红黑树。
3-6：put 操作
3-7：HashMap 的 get 操作
3-7-1：手写 get 方法
3-7-2：HashMap 的 get 和 put 操作的时间复杂度
最好为 O(1)，最坏为 O(n)。
3-8：HashMap 的 String 类型如何计算 hashcode 的
和其他对象，调用对象的 hashCode()和高位进行 &运算，结果就是 HashMap 中的 hash。
String 源码如下：
1 | public int hashCode() { |
如上，String 的 hash 计算方法为：
1 | s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] |
3-9：HashMap 容量
3-9-1：HashMap 中(tab.length - 1) & hash 作用
确定数组下标，其实就是对 hash 进行取余运算。
3-9-2：为什么默认初始化桶数组大小
避免容量太小频繁扩容。
3-9-3：HashMap 为什么是 2 的次幂
这是为了更方便的确定数组下标，因为 HashMap 是对 hash 进行位运算代替取余，而这一步的前提就是容量是 2 的幂。
3-9-4：什么时候扩容
当前元素数量大于（容量*影响因子）。
3-9-5：reHash（重散列）过程
如果是单节点，直接重新计算 hash，置于计算结果处，如果是链表或者红黑树，根据 hash & oldCap == 0 确定是原位置还是 j+oldCap位置，具体解释见->HashMap 扩容。红黑树重散列后会判断是否需要退化为链表，是否需要重新建立红黑树。
3-9-6：该容量如何变化
容量小于最大容量是，直接*2，如果大于最大容量，会将负载因子设为 Integer.MAX_VALUE，不再扩容。
3-9-7：这种变化会带来什么问题
jdk1.8 以前在并发情况下可能会出现链表循环。而 jdk1.8 已经不会了。
3-9-8：扩容的几个参数
oldCap,threshold,loadFactor。
3-9-9：HashMap 的 table 的容量如何确定
直接根据容量建立数组。
3-9-10：loadFactor 是什么
负载因子，是 HashMap 对内存和时间效率的一种权衡。它之所以是 0.75f，是因为它是内存和时间效率之间的一种经验值，更大虽然内存占用更少，但是 hash 冲突可能性增加，时间消耗更大；更小虽然 hash 冲突可能性减少，时间消耗更少，但是内存占用更多。
3-9-11：为什么在 JDK1.7 的时候是先进行扩容后进行插入，而在 JDK1.8 的时候则是先插入后进行扩容的呢
3-9-12：JDK1.8 链表转化为红黑树的阈值是 8,而不是 7 或者不是 20 呢
转化为红黑树的前提其实是 HashMap 数组长度大于等于 64 后才会转换，而理想情况下，在随机哈希码下，哈希表中节点的频率遵循泊松分布，而根据统计，忽略方差，列表长度为 K 的期望出现的次数是以下的结果，可以看到其实在为 8 的时候概率就已经很小了，再往后调整并没有很大意义。
1 | * 0: 0.60653066 |
3-9-13：插入一万个元素之后会不会扩容，扩容扩多少
其实时根据最大容量的设置来计算的，HashMap 默认最大容量为 1^30，如果容量大于这个值就不会扩容。
3-10：hash 函数
3-10-1：hash 的实现
如果 key 为 null，则 hash 值为 0，否则将 key 的 hash 和（hash>>>16)的结果进行 ^运算，避免低位相似高位不同的情况，通过这种散列运算使得 hash 分布更加均匀，再对 hash 取余的到下标。
3-10-2：为什么要用异或运算符？
如果使用 &或者 |运算，结果会更加偏向 0 或 1，而 ^能保证在 0 到 1 之间分布更加均匀。
3-10-3：哈希冲突的解决方法
- 开放定址法
如果 hash 冲突，以 hash 进行下一次运算，知道不冲突为止。 - 再 hash 法
通过不同函数构建不同 hash，选择一个不冲突的。 - 链地址法
将冲突的 hash 添加到链表中。 - 建立公共溢出区
分为基本表和溢出表，凡是和基础表冲突的都添加到溢出区中。
HashMap 使用的就是链地址法。
3-10-4：一致性 hash 和普通 hash 区别
普通 hash：每个 ip,或者 uri 进行 hash 计算得到一个数值，然后用这个数值除以整个节点数量取余。
普通 Hash 算法有一个明显的劣势：即当 node 数发生变化（增加、移除）后，数据项会被重新“打散”，导致大部分数据项不能落到原来的节点上，从而导致大量数据需要迁移。例如 HashMap 容量变化需要重 hash。
一致性 hash：先构造一个长度为 2^32 的整数环（这个环被称为一致性 Hash 环），根据节点名称的 Hash 值（其分布为[0, 2^32-1]）将服务器节点放置在这个 Hash 环上（例如下图的 a\b\c\d），然后根据数据的 Key 值计算得到其 Hash 值（其分布也为[0, 2^32-1]），接着在 Hash 环上顺时针查找距离这个 Key 值的 Hash 值最近的服务器节点，完成 Key 到服务器的映射查找。
这种算法解决了普通余数 Hash 算法伸缩性差的问题，可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。
当然，万事不可能十全十美，一致性 Hash 算法比普通的余数 Hash 算法更具有伸缩性，但是同时其算法实现也更为复杂。
3-10-5：扰动函数以及作用
扰动函数即 hash 的散列运算。通过这个方法减少 hash 冲突，避免低位相似高位不同的 hashcode 下标相同。
3-11：HashMap 线程问题
3-11-1：线程安全的 Map
Hashtable(每个方法都用 synchronized 修饰),ConcurrentHashMap(分段加锁)。
3-12：HashMap 引用
3-12-1：为什么 HashMap 中 String、Integer 包装类适合作为 key
因为 String、Integer 等包装类是 final 类型的，具有不可变性，而且已经重写了 equals() 和 hashCode() 方法。不可变性保证了计算 hashCode() 后键值的唯一性和缓存特性，不会出现放入和获取时哈希码不同的情况且读取哈希值的高效性，此外官方实现的 equals() 和 hashCode() 都是严格遵守相关规范的，不会出现错误。
3-12-2：如果想要一个 key 对应多个 Value 的话，怎么设计 Map
1 | Map<String,HashSet<String>> |
即 key 随意存放，value 用 set 来存放多个 value。
3-12-3：创建一个对象 HashMap<Integer,Integer> map=new HashMap<>先 put(10,1),然后 get(new Integer(10))结果是多少？
结果就是 1，因为 HashMap 内部的比较方法使用 ==和 equals()同时进行比较，只要有一个满足条件都可以。
3-12-4：使用 final static 修饰集合 HashMap 会产生什么影响
必须要显式初始化，而且 HashMap 不能修改引用。就和正常用 final 修饰对象相同。
3-12-5：JDK 的 HashMap 与 Redis 的 HashMap 的区别
JDK 使用数组+链表+红黑树解决，而 Redis 使用数组+链表。链表插入时，JDK 为了避免线程不安全的问题使用尾插法，而 Redis 使用头插法。
Redis 的 Hash 底层有两个哈希表，扩容时会通过渐进性复制逐渐将 ht[0]的值复制到 ht[1]中，再释放 ht[0]并将 ht[1]设为 ht[0]。
3-13：ConcurrentHashMap 数据结构
3-13-1：ConcurrentHashMap 的底层实现
其实 jdk1.8 中，HashMap 和 ConcurrentHashMap 底层数据结构是相似的。都是数组+链表+红黑树。
只是在一些关键操作利用 cas 和 synchronized 加锁，例如数组扩容，插入节点，平衡红黑树等等。在 Hashtable 中是直接对类加锁，而 ConcurrentHashMap 是锁数组中的头节点。同一个链表获取锁会竞争同一节点。同时，因为树平衡可能会切换根节点，所以单独列了一个 TreeBin 用于树的并发控制。
3-13-2：为什么 ConcurrentHashMap（Hashtable）为何不支持 null 键和 null 值
ConcurrentHashMap 不支持 null 键和 null 值是因为：无法分辨 get(key)返回的 null 是未找到还是 value 本来就是 null。即：
- 这个 key 从来没有在 map 中映射过，也就是不存在这个 key；
- 这个 key 是真实存在的，只是在设置 key 的 value 值的时候，设置为 null 了；
ConcurrentHashMap 和 Hashtable 都是支持并发的，这样会有一个问题，当你通过 get(k)获取对应的 value 时，如果获取到的是 null 时，你无法判断，它是 put（k,v）的时候 value 为 null，还是这个 key 从来没有做过映射。HashMap 是非并发的，可以通过 contains(key)来做这个判断。而支持并发的 Map 在调用 m.contains（key）和 m.get(key),m 可能已经不同了。
3-13-3：分段锁原理
ConcurrentHashMap 锁的是 node 节点，因为每一个对应位置的节点都竞争的是同一个锁，所以能保证线程安全，而在其他地方使用 cas 来保证数据的安全。
3-13-4：为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？
- 锁粒度降低了。
- 官方对 synchronized 进行了优化和升级，使得 synchronized 不那么“重”了。
- 在大数据量的操作下，对基于 API 的 ReentractLock 进行操作会有更大的内存开销。
3-13-5：HashMap 与 ConcurrentHashMap 中 put 的区别
其实区别不大，只是 ConcurrentHashMap 的初始化方法不同，而后如果正在扩容，会先帮助扩容再加锁添加节点。
3-13-6：手写 ConcurrentHashMap 的 get 操作
和 HashMap 的 get 操作没有区别，只是用 cas 来取值。同时 ConcurrentHashMap 的 Node 结构的 val 和 next 是用 volatile修饰的。
3-13-7：什么时候会发生扩容机制
3-13-8：HashMap 与 ConcurrentHashMap 中扩容的区别
3-13-9：为什么 ConcurrentHashMap 比 Hashtable 效率要高？
因为 ConcurrentHashMap 每次锁的是一个节点，粒度更小，而 Hashtable 是用 synchronized修饰方法，相等于锁了整个实例。
3-13-10：ConcurrentHashMap 的并发度是什么？
默认为 16，即 16 个线程同时操作，也可以通过构造方法自行设置，但是会自动扩容为 2 的幂。
4：TreeMap
4-1：TreeMap 数据结构
红黑树。
4-2：TreeMap 使用场景
在实际使用中，如果更新图时不需要保持图中元素的顺序，就使用 HashMap，如果需要保持图中元素的插入顺序或者访问顺序，就使用 LinkedHashMap，如果需要使图按照键值排序，就使用 TreeMap。
5：LinkedHashMap
5-1：LinkedHashMap 数据结构
HashMap 的基础上加上链表，维护插入顺序。
6：Hashtable
6-1：Hashtable 数据结构
数组+链表，使用 synchronized 修饰方法。
7：ArrayLlist
7-1：ArrayList 数据结构
ArrayList 底层其实就是数组，访问因为就是访问数组所以速度快，而扩容，删除则是将数组元素进行复制。
7-2：数组(Array)和列表(ArrayList)有什么区别？
- Array 可以容纳基本类型和对象，而 ArrayList 只能容纳对象。
- Array 是指定大小的，而 ArrayList 大小不是固定的。
- Array 没有提供 ArrayList 那么多功能，比如 addAll、removeAll 和 iterator 等。
7-3：ArrayList 扩容机制
一般情况下，每次扩容会增加原容量一般的大小。然后将原数组复制到新数组中。而如果没有设定初始容量，则会从 10 开始。
7-4：ArrayList 的 add 操作
先调用扩容方法，保证能容纳 size+1 个数组，如果是尾部加入，直接复制，如果是中间插入，就将插入位置开始的数组往后移。
7-5：ArrayList 初始大小以及扩容大小
设定了初始容量，就按照初始容量扩容，没有设定初始容量，默认为 10。每次扩容会增加原容量一半的值，即（oldCap>>1)。
7-6：那如何解决 ArrayList 线程不安全问题呢？
- 使用 Vector 类。
- 使用
Collections.synchronizedList方法。 - CopyOnWriteArrayList。
8：vector
8-1：vector 数据结构
数组。
8-2：扩容机制
9：LinkedList
9-1：LinkedList 数据结构
数组的基础上使用链表维护。
10：HashSet
10-1：HashSet 数据结构
其实就是 HashMap，将数组作为 HashMap 的 key 存储。
10-2：HashSet 的内存泄漏
因为 HashMap 使用数据的 hash 来定位，如果 set 中存放数据，重写 hashCode 方法后，属性变更导致 hash 也改变，使得后续修改无法作用在原对象上，但是 HashMap 中的引用依然存在，不会进行垃圾回收。
10-3：HashSet 如何保证线程安全
Collections.synchronizedSet。
11：TreeSet
11-1：TreeSet 数据结构
TreeMap。
12：LinkedHashSet
12-1：LinkedHashSet 数据结构
LinkedHashMap。
13：线程安全/非线程安全的集合
- Vector：就比 ArrayList 多了个同步化机制（线程安全），因为效率较低，现在已经不太建议使用。在 web 应用中，特别是前台页面，往往效率（页面响应速度）是优先考虑的。
- Stack：堆栈类，先进后出。
- Hashtable：就比 HashMap 多了个线程安全。
- Enumeration：枚举，相当于迭代器。
14：Java 基础-集合-集合大比较
14-1：set 和 list、map 的区别
- set 存放的不可重复的数据集。
- list 存放可重复数据。
- map 存放键值对，键不可重复，值可以。
14-2：ArrayList、LinkedList 区别和适用场景
最明显的区别是 ArrrayList 底层的数据结构是数组，支持随机访问，查询快，增删慢；线程不安全，效率高。
而 LinkedList 的底层数据结构是双向循环链表，不支持随机访问，查询慢，增删快；线程不安全，效率高。使用下标访问一个元素，ArrayList 的时间复杂度是 O (1)，而 LinkedList 是 O (n)。
14-3：HashMap、TreeMap、LinkedHashMap 区别和适用场景
在实际使用中，如果更新 map 时不需要保持 map 中元素的顺序，就使用 HashMap，如果需要保持 map 中元素的插入顺序或者访问顺序，就使用 LinkedHashMap，如果需要使 map 按照键值排序，就使用 TreeMap。
15：Collections
15-1：Collection 与 Collections 的区别
- Java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection 接口在 Java 类库中有很多具体的实现。Collection 接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有 List 与 Set。
- Collections 则是集合类的一个工具类 / 帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。
