这块的话，主要集中在 hashmap，其他的问的少或者简单，之后 hashmap 问的比较深入，不过你把下面的问题掌握了，那就问题不大了。

需要掌握的知识概括：

HashMap

• 底层数据结构 + 为啥选择红黑树 + put/get 到大致执行逻辑
• 线程安全角度：为啥不安全，得举例子 + 如何让 hashmap 变安全 + 有哪些线程安全的集合
• Hashcode 取模 + 扩容原理 + 为啥扩容因子选择 0.75
• 一般就这几个，带着目的去看一些文章分析，之后自己看源码，就会容易很多了

ArrayList和LinkedList：这两个经常一起出现，主要掌握他们的底层数据结构以及应用场景。

系统资料推荐：集合问题的学习，主要基于面试题来，并且这里主要通过文章来学习，了解大概思想之后，然后自己进去 JDK 看源码。

1、HashMap 了解吗？平时在什么地方使用过它呢？（说明：发现没有，我喜欢问使用场景，希望大家也是能够思考使用场景的，因为掌握了这个，你说话更加有说服力）

2、HashMap 底层数据结构说一下？（指导：直接说最新的即可，不需要去对比以前的版本，因为面试官也听烦了，另外在说的时候，为了你语言的严谨，一定要强调下是哪个JDK版本的哈）

3、为什么用红黑树呢？用平衡二叉树不可以吗？或者你讲一讲他们各自的优缺点吗？

4、为什么选择 8 之后转为红黑树呢？另外链表转为红黑树之后，还会继续转为链表吗？

5、简单描述下 put 的流程？可以说一下JDK位了效率更快，在 put 的时候，做了哪些优化不？

6、多线程情况下，put 是线程安全的吗？可以简单举个例子，说一下哪里不安全吗？

7、如果我想要让 hashmap 变成线程安全的，你觉得可以怎么做？（有时候会扯到 concurrentHashMap，不过咱们这里先不追击这个）

8、头插法会导致死循环，那你觉得在以前的版本中，为啥会使用头插法呢？

9、那我们再说一说 HashMap 的扩容吧，什么时候会扩容呢？你觉得为啥负载因子为啥选择 0.75 呢？

10、频繁扩容会导致效率比较低下，那你觉得在平时，在实际的开发场景中，可以怎么优化来避免频繁扩容呢？

11、一个场景题：只存60个键值对，需要设置初始化容量吗？设置的话设置多少初始化容量比较好呢？🌟🌟

回答指导：上面这些问题，不应该需要记住！你需要理解，先理解大概=》看一下源码怎么做的，反正回答出上面这些问题，基本稳。以上问题，基本都是来自于实际被问过的问题，掌握上面这些，基本掌握 hashmap 95% 的考点。

【参考文章以及资料补充】：

23. HashMap 与 HashTable（超重点）

数据结构补充：

35. AVL树

36. 红黑树（简单了解）

参考回答：

1、HashMap 了解吗？平时在什么地方使用过它呢？（说明：发现没有，我喜欢问使用场景，希望大家也是能够思考使用场景的，因为掌握了这个，你说话更加有说服力）

HashMap 也就是哈希表，底层利用数组支持下标随机访问数据的特性，快速的对键值对进行增删改查操作。

2、HashMap 底层数据结构说一下？（指导：直接说最新的即可，不需要去对比以前的版本，因为面试官也听烦了，另外在说的时候，为了你语言的严谨，一定要强调下是哪个JDK版本的哈）

在最新的 JDK 1.8 中，HashMap 的底层数据结构为 “哈希表 + 链表 + 红黑树”。当哈希表中出现哈希冲突时，HashMap 采用 “链地址法” 来解决，也就是哈希表中的每个槽位，都会对应一个链表，所有哈希值相同的元素都会被放到同一个槽位对应的链表中。但随着链表长度的增加，元素的读取效率会下降，直到达到某个阈值时（目前JDK是8），HashMap 会将链表转化为红黑树，进一步提升性能。

3、为什么用红黑树呢？用平衡二叉树不可以吗？或者你讲一讲他们各自的优缺点吗？

红黑树是弱平衡二叉树，整棵树可以有局部的不平衡。AVL 树是强平衡二叉树，它严格要求整棵树的平衡性。也就是说，虽然两者的插入，删除复杂度都为 O(logn)，实际中 AVL 树需要执行更多的旋转操作来保证强平衡性，效率要低于红黑树。但红黑树也有缺点，它需要额外的字段来记录每个节点的颜色，因此会占用更多的存储空间。

4、为什么选择 8 之后转为红黑树呢？另外链表转为红黑树之后，还会继续转为链表吗？（最好看过源码说明）

这个在源码的注释中有解释，大致意思为：如果元素的哈希值足够随机，理想情况下链表的长度对应的概率符合泊松分布，达到 8 的概率小于千万分之一。也就是说，一般情况下并不会发生链表到红黑树的转化，更多是一种防止自己选取的哈希算法不好的保底策略，在极端情况下仍会有较好的效率。

但是，当红黑树的节点小于 6 时，红黑树又会转回链表，原因是数据量很小的情况下，空间和时间上链表都要比红黑树优秀。至于为什么要把这个阈值定为 6，而不同样定为 8，主要是而为了防止元素数量在 8 附近导致两种数据结构的频繁转换。

5、简单描述下 put 的流程？可以说一下JDK位了效率更快，在 put 的时候，做了哪些优化不？

首先 put( ) 会计算出要插入 key 的哈希值，通过哈希值计算出其在数组中的索引位置，如果该位置上没有元素则直接插入，有元素则需要遍历这个位置上的所有元素。如果能找到与当前键相等的键值对，则将其更新为当前值并返回旧值，如果找不到与当前键相等的键值对，则需要执行真正的插入操作，将其插入到链表或者红黑树中，最后判断插入后是否需要扩容。

put( ) 的优化我印象深的是计算 key 哈希值的 hash( )，主要有两个优化的点：使用位运算代替取模运算和对 hashCode 进行搅动计算。具体来说，可以用x这个公式将取模转变为位运算来提升性能，但是同时也需要底层数组的长度是 2 的倍数，这个在 HashMap 的初始化和扩容方法中做了保证。

除此之外，为了进一步降低哈希冲突的概率，hash( ) 又通过多个与运算将哈希值的高位和低位进行搅动，尽可能的做到在不同 key 中哪怕有一个位的不同，都会对最终产生的哈希值造成影响。

6、多线程情况下，put 是线程安全的吗？可以简单举个例子，说一下哪里不安全吗？

不是，在 JDK 1.7 中多线程同时进行 put( ) 会出现数据覆盖问题，在需要扩容时也可能会出现链死循环问题。JDK 1.8 修复了链死循环，但数据覆盖问题依然存在。

JDK 1.7 的 HashMap 底层为数组 + 链表，扩容的 transfer( ) 会遍历原链表中的每个节点，采用头插法将其转移到新哈希表槽位的链表中，这个过程在多线程下会导致新链表中出现环路，并造成某些元素丢失。

JDK 1.8 采用的是尾插法，保证了元素在扩容前后的顺序一致，避免了死循环问题，但还会造成数据覆盖。比如两个线程同时执行 put( )，且两个线程都同时判断槽位为空，则后插入的数据会覆盖先插入的数据。

7、如果我想要让 hashmap 变成线程安全的，你觉得可以怎么做？（有时候会扯到 concurrentHashMap，不过咱们这里先不追击这个）

想要解决 HashMap 的线程不安全问题，首先我们不能修改源码，那就要么使用一些 “辅助” 操作，让它变得安全，要么就寻找替代品。首先说的 “辅助” 操作是指，使用 Collections 类的 synchronizedMap 方法包装一下，它返回由指定映射支持的同步映射，是线程安全的。换替代品的话，可以考虑 HashTable，HashTable 通过将整个表上锁来实现线程安全，某些情况下效率很低。还可以使用 ConcurrentHashMap，它使用分段锁或者 CAS 操作来保证线程安全。

8、头插法会导致死循环，那你觉得在以前的版本中，为啥会使用头插法呢？

采用头插法的话，最新插入的数据就会在链表的最前边，根据程序的局部性原理，最近被访问的数据很可能不久之后会再次访问，那么此时可以在 O(1) 时间返回。

9、那我们再说一说 HashMap 的扩容吧，什么时候会扩容呢？你觉得为啥负载因子为啥选择 0.75 呢？

HashMap 需要扩容时，可以分为几种情况来考虑。

首先是在无参的构造函数中。在第一次进行 put 操作之前，HashMap 内部数组为 null，第一次 put 后才会开始第一次初始化扩容，默认为 16 。

其次是指定了初始容量的构造参数，也是在第一次 put 操作之后才开始初始化扩容，但此时的容量是第一个不小于指定容量的 2 的幂数，阈值为计算后容量乘负载因子。

其它情况就是，非首次 put，导致容量大于阈值，需要扩容。容量和阈值都变为原来的 2 倍，负载因子不变。

负载因子为 0,75 的原因，简单来说是 “哈希冲突” 和 “空间利用率“ 矛盾的一个折中。原因是，扩容因子是用来计算阈值的，阈值为底层 table 长度乘负载因子，当 HashMap 容量大于阈值时会触发扩容。所以如果负载因子过小，table 中还没填几个元素就要扩容，虽然哈希冲突概率很小，但空间浪费太多。相反，如果负载因子过大，空间利用率是高，但哈希冲突的概率也大大增加。那就取个折中吧，为 0.75。

10、频繁扩容会导致效率比较低下，那你觉得在平时，在实际的开发场景中，可以怎么优化来避免频繁扩容呢？

容易想到的就是，提前预估业务的存储量，设置一个较大的初始容量。这时不用考虑它是否是 2 的次幂，HashMap 自己会计算出第一个大于等于给定容量的 2 次幂来作为初始容量。除此之外，可以自定义负载因子的大小，对哈希函数优化等等。

11、一个场景题：只存60个键值对，需要设置初始化容量吗？设置的话设置多少初始化容量比较好呢？

HashMap 默认的初始容量大小为 16。如果不设置初始容量的话，根据规则 size > threshold 时会触发扩容，且 threshold = loadFactor *capacitry，最终 capacity 会经历 16 – 32 – 64 – 128 三次扩容操作。考虑到HashMap 自己会计算出第一个大于等于给定容量的 2 次幂来作为初始容量，所以随机选一个 65 – 128 之间的数作为初始容量即可。

1、请你说一说 ArrayList 和 LinkedList 区别？

2、如果我要删除第 k 个元素，也就是会执行 remove(k)，那么这个 remove 的操作，它们的时间复杂度各自是多少？

3、可以说一说它们的使用场景吗？或者说一说你平时在处理什么事情的时候，用过它们？

4、AarrayList 底层实现是数组，数组就会有容量限制，可以简单说一下 ArrayList 的扩容机制吗？（）

【参考文章以及资料补充】：

21. List | ArrayList | Vector

参考回答：

1、请你说一说 ArrayList 和 LinkedList 区别？

ArrayList 底层是用数组实现的，根据索引访问元素，使得查询的复杂度仅为 O(1)。但在插入和删除时有数组的复制和移动，复杂度为 O(n)；

LinkedList 底层使用双向链表实现的，由于每个节点都含有前驱和后继节点的引用，所以它插入删除时只需修改这些引用，效率要比 ArrayList 高 。但在查询元素时需要从头节点开始依次遍历整个链表，时间复杂度为 O(n)

2、如果我要删除第 k 个元素，也就是会执行 remove(k)，那么这个 remove 的操作，它们的时间复杂度各自是多少？

都是 O(n) 。

ArrayList 首先会以 O(1) 时间定位到第 k 个元素，然后将被这个元素分割的两部分复制拼接到一个新数组上，总体为 O(n) 。

LinkedList 首先以 O(n) 时间定位到第 k 个元素，然后 O(1) 时间处理这个元素前后节点的引用，总体也为 O(n) 。

3、可以说一说它们的使用场景吗？或者说一说你平时在处理什么事情的时候，用过它们？

(待补充)

4、AarrayList 底层实现是数组，数组就会有容量限制，可以简单说一下 ArrayList 的扩容机制吗？

ArrayList 的默认容量为 10，当需要扩容时，会先申请一个容量为旧容量 1.5 倍的新数组，然后把旧数组复制到新数组中。值得注意的是，JDK 1.8 中 ArrayList 底层数组的最大容量为 Integer.MAX_VALUE – 8 ，目的是防止某些虚拟机会在数组中存一些额外的信息导致内存溢出。

1、counrrenthashmap 是如何实现线程安全的？可以简单说一下为了效率更快，比起 HashTable，counrrenthashmap 作了哪些优化吗？

2、平时我们会经常使用 HashMap，但是 counrrenthashmap 很少使用到，你可以简单说一下什么样的场景下使用 counrrenthashmap 吗？（指导：这个是个开放性问题，大家思考一下吧，千万不要只说 多线程 情况下使用 counrrenthashmap 哈，那样没有意义，因为有时候，线程的安全，可以由我们程序员来控制，不一定要使用 counrrenthashmap，所以需要大家思考一下）

【参考文章以及资料补充】：

ConcurrentHashMap

参考回答：

1、counrrenthashmap 是如何实现线程安全的？可以简单说一下为了效率更快，比起 HashTable，counrrenthashmap 作了哪些优化吗？

JDK 1.7 中 ConcurrentHashMap 使用了分段锁来实现线程安全。它的底层是一个 Segment 数组，每个 Segment 通过继承 ReetrantLock 来控制自己这部分的加锁。其中每个 Segment 就类似一个 HashTable，这样只要保证每个 Segment 是线程安全的，就能确保整个哈希表也是安全的了。

JDK 1.8 为了摆脱哈希表中 Segment 个数对并发度的限制，底层采用和 HashMap 类似的实现：数组 + 链表 + 红黑树，加锁用 CAS 和 synchronized 实现。具体来说，在进行 put 操作时，如果槽位为空，则使用 CAS 插入新节点。如果槽位不为空，则需要进一步判断其它线程是否在对其扩容，是则协助扩容，不是则使用 synchronized 锁住当前槽位，再进行插入节点操作。

2、平时我们会经常使用 HashMap，但是 counrrenthashmap 很少使用到，你可以简单说一下什么样的场景下使用 counrrenthashmap 吗？（指导：这个是个开放性问题，大家思考一下吧，千万不要只说 多线程 情况下使用 counrrenthashmap 哈，那样没有意义，因为有时候，线程的安全，可以由我们程序员来控制，不一定要使用 counrrenthashmap，所以需要大家思考一下）

比如在日志分析时，可以将日志分成多个数据块，同时开启多个线程进行对日志进行并发处理，最终将结果汇总到 ConcurrentHashMap 中；再比如一个并发执行的多任务列表，可以用 ConcurrentHashMap 来作为任务管理的数据结构。任务为 Key，任务的执行状态为 Value，多个线程可以同时查找和更新任务的状态，实现对多任务的控制。

【参考文章以及资料补充】：

无

参考回答：

两者都继承自 Collection，都是用来存储数据的集合。其中 List 接口会维护元素的插入顺序，并且允许根据索引进行数据查询和操作。而 Set 接口只强调元素的不可重复性，不保证元素的特定顺序，也不支持索引查询。

List 接口常见的实现类有 ArrayList，LinkedList 等，前者底层为数组，适合随机访问多的场景。后者底层为双向链表，适合插入删除操作多的场景。

Set 接口常见的实现类有 HashSet，TreeSet 等，前者底层为哈希表，提供快速的插入，删除和查找性能，但不保证元素的顺序。后者底层为红黑树，元素间可以使用自定义比较器进行排序。