java集合概览

似乎我在 java 集合部分中的源码分析部分，了解的不够？但是时间不多了！需要加把劲了！

Java 集合概览

由两大接口派生而来：一个是 Collection 接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于 Collection 接口，下面又有三个主要的子接口：List、Set 、 Queue。

这里只列举了主要的继承派生关系，并没有列举所有关系。

集合框架底层数据结构总结

List

• ArrayList：Object[] 数组。详细可以查看：ArrayList 源码分析。
• Vector：Object[] 数组。
• LinkedList：双向链表 (JDK 1.6 之前为循环链表，JDK 1.7 取消了循环)。详细可以查看：LinkedList 源码分析。

Set

• HashSet (无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素。
• LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。
• TreeSet (有序，唯一): 红黑树 (自平衡的排序二叉树)。

Queue

• PriorityQueue: Object[] 数组来实现小顶堆。详细可以查看：PriorityQueue 源码分析。
• DelayQueue: PriorityQueue。详细可以查看：DelayQueue 源码分析。
• ArrayDeque: 可扩容动态双向数组。

Map

• HashMap：JDK 1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK 1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。详细可以查看：HashMap 源码分析。
• LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：LinkedHashMap 源码分析
• Hashtable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。
• TreeMap：红黑树（自平衡的排序二叉树）。

可能会被问到的重点问题！

加*的代表是重点！总的来说：ArrayList ，LinkedList， HashMap，ConcurrentHashMap 为重点！其他的了解即可。

ArrayList 底层的实现原理是什么

• ArrayList 底层是用动态的数组实现的
• ArrayList 初始容量为 0，当第一次添加数据的时候才会初始化容量为 10
• ArrayList 在进行扩容的时候是原来容量的 1.5 倍，每次扩容都需要拷贝数组
• ArrayList 在添加数据的时候
  • 确保数组已使用长度(size)加 1 之后足够存下下一个数据
  • 计算数组的容量，如果当前数组民使用长度+1 后的大于当前的数组长度，则调用 grow 方法扩容（原来的 1.5倍）
  • 确保新增的数据有地方存储之后，则将新元素添加到位于 size 的位置上。
  • 返回添加成功布尔值。

new ArrayList(10) list 扩容几次？0 次

如何实现数组和 List 之间的转换

• 数组转 List ，使用 JDK 中 java.util.Arrays 工具类的 asList 方法
• List 转数组，使用 List 的 toArray 方法。无参 toArray 方法返回 Object 数组，传入初始化长度的数组对象，返回该对象数组

面试官再问:

• 用 Arrays.asList 转 List 后，如果修改了数组内容，list 受影响吗? -> 受影响
• List 用 toArray 转数组后，如果修改了 List 内容，数组受影响吗? -> 不受影响
  答：
• Arrays.asList 转换 list 之后，如果修改了数组的内容，list 会受影响
  因为它的底层使用的 Arrays 类中的一个内部类 ArrayList 来构造的集
  合，在这个集合的构造器中，把我们传入的这个集合进行了包装而
  已，最终指向的都是同一个内存地址
• list 用了 toArray 转数组后，如果修改了 list 内容，数组不会影响，当
  调用了 toArray 以后，在底层是它是进行了数组的拷贝，跟原来的元
  素就没啥关系了，所以即使 list 修改了以后，数组也不受影响

ArrayList 和 LinkedList 的区别是什么?(*)

ArrayList 与 LinkedList 区别?

HashMap 的底层实现(*)

HashMap 的底层实现

JDK 1.7 和 1.8 的 HashMap 有什么区别？

HashMap 的 put 操作具体流程(*)

流程图：

(重)

1. 判断键值对数组 table 是否为空或为 null，否则执行 resize()进行扩容(初始化)
2. 根据键值 key 计算 hash 值得到数组索引
3. 如果 table[i]==null 条件成立，直接新建节点添加
4. 如果 table[i]!=null
   • 判断 table[i]的首个元素是否和 key 一样，如果相同直接覆盖 value
   • 判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对
   • 遍历 table[i]，链表的尾部插入数据，然后判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现 key 已经存在直接覆盖 value
5. 插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold (数组长度*0.75)，如果超过，进行扩容

HashMap 的扩容机制是什么？

流程图：

• 在添加元素或初始化的时候需要调用 resize 方法进行扩容，第一次添加数据初始化数组长度为 16，以后每次每次扩容都是达到了扩容阈值(数组长度*0.75)
• 每次扩容的时候，都是扩容之前容量的 2 倍(可以保证每次都是 2 的幂);
• 扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
  • 没有 hash 冲突的节点，则直接使用 e.hash &(newCap-1)计算新数组的索引位置
  • 如果是红黑树，走红黑树的添加
  • 如果是链表，则需要遍历链表，可能需要拆分链表，判断 (e.hash & oldCap) 是否为 0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

HashMap 的寻址算法？

HashMap JDK 1.7 在多线程下死循环问题

参考视频：

• 常见集合篇-17-HashMap在1.7情况下的多线程死循环问题_哔哩哔哩_bilibili
• JDK7的HashMap头插法循环的问题，这么难理解吗？_哔哩哔哩_bilibili
• 为什么 HashMap 会死循环？HashMap 死循环发生在 JDK 1.8 之前的版本中，它是指在并发环境下，因为多 - 掘金

在 jdk 1.7 的 hashmap 中在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环

比如说，现在有两个线程
线程一:读取到当前的 hashmap 数据，数据中一个链表，在准备扩容时，线程二介入
线程二:也读取 hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是 AB，扩容后
的顺序是 BA，线程二执行结束。

线程一:继续执行的时候就会出现死循环的问题。
线程一先将 A 移入新的链表，再将 B 插入到链头，由于另外一个线程的原因，B 的 next 指向了 A，所以 B->A->&,形成循环。
当然，JDK 8 将扩容算法做了调整，不再将元素加入链表头(而是保持与扩容前一样的顺序)，尾插法，就避免了 idk 7中
死循环的问题。