集合框架概览

Java集合，也叫做容器，主要由两大接口派生而来：

Collection：主要用于存放单一元素
- List：存储的元素有序、可重复
  - ArrayList：基于 Object[] 数组
  - Vector：基于 Object[] 数组
  - LinkedList：
    - JDK 1.6 之前为循环链表
    - JDK 1.7 之后为双向链表
- Set：存储的元素不可重复
  - HashSet：基于 HashMap
  - LinkedHashSet：基于 LinkedHashMap
  - TreeSet：红黑树实现
- Queue：按照特定的排队规则确定先后顺序，存储的元素是有序的、可重复的
  - PriorityQueue：基于 Object[] 数组，默认为小根堆
  - DelayQueue：基于 PriorityQueue
  - ArrayDeque：可扩容的动态双向数组
Map：主要用于存放键值对
- key 是无序的、不可重复的
- value 是无序的、可重复的
  - HashMap：
    - JDK 1.8 之前：由数组+链表构成，数组是 HashMap 的主体，链表用于解决哈希冲突（使用”拉链法”解决冲突）。
    - JDK 1.8 及其之后：由数组+链表+红黑树构成，主要变化在于解决哈希冲突的方式。如果当前数组的长度小于 64，会优先选择扩容数组；如果当前数组的长度大于 64，当链表的长度大于阈值 8 时，会将链表转换为红黑树，以减少搜索时间。
  - LinkedHashMap：
    - 在 HashMap 的基础上，增加了一条双向链表，使得键值对可以保持插入的顺序。
  - Hashtable：
    - 由数组+链表构成。
    - 相较于 HashMap：
      - API 很老旧，已经被废弃。
      - Hash 函数不同。
      - 计算索引时，HashMap 可以使用 (length - 1) & hashcode，而 Hashtable 只能使用 hashcode % length。
      - Hashtable 是线程安全的，其大部分方法是 synchronized 的。
      - Hashtable 不允许 null，而 HashMap 允许。
      - 扩容方面，HashMap 每次扩容会变为原来的 2 倍，且容量大小一定是 2 的幂次方；Hashtable 每次扩容则是扩容为 2 倍容量 + 1。
      - 在解决哈希冲突时，Hashtable 只能采取链地址法，而在 JDK 1.8 之后，HashMap 除了使用链地址法，还可以使用红黑树法。
  - TreeMap：
    - 基于红黑树实现。

ArrayList 源码分析

ArrayList 和 Vector 的区别？

ArrayList 线程不安全，Vector 线程安全，两者的底层都是 Object[]。

ArrayList 可以添加 null 值吗？

可以，但是最好不要，无意义且容易导致空指针异常。

ArrayList 和 LinkedList 的区别？

底层数据结构不同：ArrayList 是基于 Object[]，而 LinkedList 是基于双向链表。
两者都未做同步处理，都是线程不安全的。
ArrayList 支持快速随机访问，LinkedList 不支持快速随机访问。
插入和删除元素都受元素位置的影响：
- ArrayList 在尾部插入和删除的时间复杂度为 O(1)，在其他位置为 O(N)。
- LinkedList 在首部和尾部插入和删除的时间复杂度为 O(1)，在其他位置为 O(N)。
空间占用：
- ArrayList 的额外空间来自于结尾预留的空间。
- LinkedList 的额外空间来自于每个元素消耗的额外记录信息。

核心源码解读

初始容量大小为 10。
构造函数：
- 无参构造函数：默认创建的是一个空数组（JDK 6 及其之前创建的容量大小为 10 的数组），方便在添加第一个元素时确认容量。
- 带有初始容量的构造函数：创建一个等于初始容量的数组。
- 带有 Collection 的构造函数：通过迭代器访问 Collection 的顺序来初始化 elementData 数组。
扩容机制：
- 扩容发生在调用 add() 方法时。
- 在加入元素之前，首先会调用 ensureCapacityInternal(size + 1)：
  - size + 1 是要求的最小容量 minCapacity。
  - 该方法会先调用 calculateCapacity(elementData，minCapacity)：
    - 如果 elementData 是空数组，则返回 10。
    - 否则返回 minCapacity。
    - 本质上是计算当前 elementData 的最小容量 minCapacity。
  - 然后调用 ensureExplicitCapacity(minCapacity)：
    - modCount++。
    - 如果 minCapacity - elementData.length > 0，即空间不够，会调用 grow(minCapacity)。
  - grow(minCapacity)：
    - ArrayList 定义 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8。
    - oldCapacity = elementData.length。
    - newCapacity = oldCapacity + (oldCapacity >> 1)，即新的容量是旧容量的 1.5 倍左右。
    - 如果 newCapacity < minCapacity，则 newCapacity = minCapacity。
    - 如果新容量大于 MAX_ARRAY_SIZE，会使用 hugeCapacity 来比较 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity > MAX_ARRAY_SIZE，则容量为 Integer.MAX_VALUE，否则新容量为 MAX_ARRAY_SIZE。
  - 最后使用 Arrays.copy 拷贝旧数组到新数组，本质上是调用了 System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)。
- 在放入大量数据时，最好先调用 ensureCapacity(minCapacity)，这可以有效减少数组扩容的次数，加快运行速度。

HashMap 源码分析

在 JDK 1.8 之前，底层使用数组+链表，并使用拉链法解决哈希冲突。

在 JDK 1.8 及其之后，底层使用数组**+链表+红黑树解决哈希冲突**。

当链表长度大于阈值（默认为 8）时，会先调用 treeifyBin() 方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。当数组长度大于 64 时，会转换为红黑树，否则会执行 resize() 对数组进行扩容。

类的属性

默认的初始容量是 16。
最大容量是 1 << 30（2^30）。
默认的负载因子 loadFactor = 0.75：
- loadFactor 太大会导致查找元素的效率很低，太小会导致数组的利用率低，存放的数据会很分散。
threshold 门槛 = capacity * loadFactor，当数据量超过 threshold 时，就需要进行扩容。

构造方法

默认有 4 个构造方法：
- 无参构造。
- 包含另一个 Map 的构造函数。
- 指定容量大小的构造函数。
- 指定容量大小和负载因子的构造函数。
以上 4 个构造函数，都初始化了负载因子。由于 HashMap 中没有 capacity 字段，即使指定了初始化容量 initialCapacity，也只是通过 tableSizeFor 将其扩容到与 initialCapacity 最接近的 2 的幂次方大小，然后暂时赋值给 threshold，后续通过 resize() 方法将 threshold 赋值给 newCap 进行 table 的初始化。

put 方法

如果定位到的数组位置没有元素，直接插入。
如果有元素，就和要插入的 key 做比较，如果 key 相同，则直接覆盖；如果 key 不同，就判断 p 是否是一个树节点，如果是就加入树中，如果不是就加入链表尾部。
上述为 JDK 1.8 的处理方式。
如果是 JDK 1.7，在解决哈希冲突时，使用的是头插法：
- JDK 1.7 的头插法可能会导致死循环。
- 原理：多个线程同时对 HashMap 做扩容操作可能会导致一个线程以另一个线程扩容完的逆序链表进行顺序操作，导致循环链表的产生。
- 具体情况：两个线程同时对 HashMap 进行扩容，其中一个线程 A 在扩容过程中时间片耗尽，另一个线程 B 成功扩容。之后线程 A 重新获得时间片，按照原本的逻辑去扩容：
  - 假设一开始桶中元素是 3 -> 7 -> 5。
  - 扩容一次后第一个桶变为了 7 -> 3。
  - 此时线程 A 恢复，但线程 A 获取了 3 的下一个节点为 7。
    - 于是先处理 3 -> null。
    - 然后获取 7 的下一个节点，但 7 的下一个节点在 B 扩容的过程中变成了 3。
      - 7 -> 3
    - 此时再次处理 3，死循环出现：
      - 3 -> 7 -> 3
  - 出现的条件是链表在扩容时使用头插法会导致链表元素逆序。因此，改为尾插法解决了这个问题。

ConcurrentHashMap 源码分析

在 JDK 1.7 之前，ConcurrentHashMap 由多个 Segment 组成，每一个 Segment 是一个类似于 HashMap 的结构。每个 Segment 的内部可以进行扩容，但 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，因此 ConcurrentHashMap 默认最多支持 16 个并发。

ConcurrentHashMap 结构

ConcurrentHashMap 的初始化逻辑

必要参数检验。
检验并发级别 concurrentLevel 的大小，如果大于最大值，重置为最大值。无参构造默认是 16。
寻找并发级别 concurrentLevel 之上最近的 2 的幂次方值，作为初始化容量大小，默认是 16。
记录 segmentShift 偏移量，这个值为【容量 = 2 的 N 次方】中的 N，在后面 put 时计算位置时会用到。默认是 32 - sshift = 28。
记录 segmentMask，默认是 ssize - 1 = 15。
初始化 segment[0]，默认大小为 2，负载因子为 0.75，扩容阈值为 2 * 0.75 = 1.5，插入第二个值才会进行扩容。

put 流程

计算要 put 的 key 的位置，获取指定位置的 Segment。
如果指定位置的 Segment 为空，则初始化这个 Segment：
- 初始化 Segment 的流程：
  - 检查计算得到位置的 Segment 是否为 null。
  - 为 null 则继续初始化，使用 segment[0] 的容量和负载因子创建一个 HashEntry 数组。
  - 再次检查计算得到的 Segment 是否为 null。
  - 使用创建的 HashEntry 数组初始化这个 Segment。
  - 自旋判断得到的指定位置的 Segment 是否为 null，**使用 CAS 在这个位置赋值为 Segment**。
因为 Segment 继承了 ReentrantLock，所以 Segment 内部可以很方便地获取锁。
使用 tryLock() 获取锁，获取不到则使用 scanAndLockForPut 方法继续获取：
- scanAndLockForPut 的操作就是不断自旋 tryLock() 获取锁，当自旋次数超过指定次数时，使用 lock() 阻塞地获取锁。在自旋时顺便获取下 hash 位置的 HashEntry。
计算 put 的数据要放入的 index 位置，然后获取这个位置上的 HashEntry。
遍历 put 新元素：
- 如果这个位置上的 HashEntry 不存在：
  - 如果当前容量大于扩容阈值且小于最大容量，进行扩容。
  - 直接使用头插法插入。
- 如果这个位置上的 HashEntry 存在：
  - 判断链表当前元素 key 和 hash 值是否与 put 的 key 和 hash 值一致。一致则替换值。
  - 不一致则获取链表下一个节点，直到发现相同的元素进行替换，或者链表遍历完毕没有找到相同的元素：
    - 如果当前容量大于扩容阈值且小于最大容量，进行扩容。
    - 直接使用链表头插法插入。
如果待插入的位置之前已经有值存在，替换后返回旧值，否则返回 null。

扩容（rehash）

ConcurrentHashMap 的扩容只会扩容到原来的两倍。老数组的元素移动到新的数组时，位置要么不变，要么变为 index + oldSize，参数里的 node 会在扩容后使用链表头插法插入到指定位置。

Get 方法

计算得到 key 存放的位置。
遍历指定位置查找相同 key 的 value 值。

ConcurrentHashMap 1.8

ConcurrentHashMap 1.8 相较于 1.7 变化较大，不再是之前的 Segment 数组 + 链表，而是 Node 数组 + 链表 / 红黑树，当冲突链表达到一定长度时，链表会转换为红黑树。

初始化

ConcurrentHashMap 的初始化是通过自旋和 CAS 来完成的。变量 sizeCtl 的值决定了当前的初始化状态：
- -1：说明正在初始化，其他线程需要自旋等待。
- -N：说明 table 正在进行扩容，高 16 位表示扩容的标识戳，低 16 位减 1 表示正在扩容的线程数。
- 0：标识 table 的初始化大小，如果 table 没有初始化。
- >0：标识扩容的阈值，如果 table 已经初始化。

put 的过程：

根据 key 计算出 hashcode。
判断是否需要进行初始化。
为当前 key 定位出 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
如果当前位置的 hashcode == moved == -1 则需要进行扩容。
如果都不满足，则利用 synchronized 锁写入数据。
如果数量大于 TREEIFY_THRESHOLD 则执行树化方法，在 treeify 中会判断当前数组长度 >= 64 时，才会将链表转换为红黑树。

集合常见面试题

阻塞队列是如何实现的？

它是一个基于数组的有界阻塞队列，采用 ReentrantLock 锁来实现线程的互斥，而 ReentrantLock 底层采用的是 AQS 实现的队列同步。
**线程的阻塞调用 LockSupport.park，唤醒调用 LockSupport.unpark**。

ArrayList 是怎么序列化的？为什么用 transient 修饰数组？

ArrayList 通过两个方法，**readObject 和 writeObject 自定义序列化和反序列化逻辑**，实际使用两个流 ObjectOutPutStream 和 ObjectInputStream 来进行序列化和反序列化。
如果直接序列化 elementData 数组，可能会导致序列化一些无用的数据，比如 elementData 长度为 100，但实际上只用了 50。

快速失败和安全失败了解吗？

快速失败（fail-fast）：快速失败是 Java 集合的一种错误检测机制

在**用迭代器遍历一个集合对象时，如果线程 A 在遍历过程中，线程 B 对集合对象的内容进行了修改（增加、删除、修改），则会抛出 ConcurrentModificationException**。
原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。每当迭代器使用 hashNext()/next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedModCount 值，是的话就返回遍历；否则抛出异常，终止遍历。
注意：这里异常的抛出条件是检测到 modCount != expectedModCount 这个条件。如果集合发生变化时修改 modCount 值，刚好又设置为了 expectedModCount 值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的 bug。
场景：**java.util 包下的集合类都是快速失败的**，不能在多线程下发生并发修改（迭代过程中被修改），比如 ArrayList 类。

安全失败（fail-safe）

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
原理：**由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发 ConcurrentModificationException**。
缺点：基于拷贝内容的优点是避免了 ConcurrentModificationException，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
场景：**java.util.concurrent 包下的容器都是安全失败的，可以在多线程下并发使用，并发修改，比如 CopyOnWriteArrayList 类**。

有哪几种实现 ArrayList 线程安全的方法？

**使用 Vector 代替 ArrayList**（不推荐，Vector 是一个历史遗留类）。
使用 Collections.synchronizedList 包装 ArrayList，然后操作包装后的 list。
**使用 CopyOnWriteArrayList 代替 ArrayList**。
在使用 ArrayList 时，应用程序通过同步机制去控制 ArrayList 的读写。

CopyOnWriteArrayList 了解多少？

CopyOnWriteArrayList 采用了一种读写分离的并发策略。CopyOnWriteArrayList 容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

能说一下 HashMap 的底层数据结构吗？

JDK 8 中 HashMap 的数据结构是数组+链表+红黑树。
HashMap 的核心是一个动态数组（Node[] table），用于存储键值对。这个数组的每个元素称为一个“桶”（Bucket），每个桶的索引是通过对键的哈希值进行哈希函数处理得到的。
当多个键经哈希处理后得到相同的索引时，会发生哈希冲突。HashMap 通过链表来解决哈希冲突——即将具有相同索引的键值对通过链表连接起来。
不过，链表过长时，查询效率会比较低，因此，当链表的长度超过 8 时（且数组的长度大于 64），链表就会转换为红黑树。红黑树的查询效率是 O(logn)，比链表的 O(n) 要快。数组的查询效率是 O(1)。
当向 HashMap 中添加一个键值对时，会使用哈希函数计算键的哈希码，确定其在数组中的位置。哈希函数的目标是尽量减少哈希冲突，保证元素能够均匀地分布在数组的每个位置上。
当向 HashMap 中添加元素时，如果该位置已有元素（发生哈希冲突），则新元素将被添加到链表的末尾或红黑树中。如果键已经存在，其对应的值将被新值覆盖。
当从 HashMap 中获取元素时，也会使用哈希函数计算键的位置，然后根据位置在数组、链表或者红黑树中查找元素。
HashMap 的初始容量是 16。随着元素的不断添加，HashMap 的容量（也就是数组大小）可能不足，于是就需要进行扩容。阈值是 capacity * loadFactor，capacity 为容量，loadFactor 为负载因子，默认为 0.75。
扩容后的数组大小是原来的 2 倍，然后把原来的元素重新计算哈希值，放到新的数组中。

你对红黑树了解多少？为什么不用二叉树/平衡树呢？

红黑树是一种自平衡的二叉查找树：
- 每个节点要么是红色，要么是黑色。
- 根节点永远是黑色。
- 所有的叶子节点都是黑色的（即 NULL 节点）。
- 红色节点的子节点一定是黑色的。
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
为什么不用二叉树？
- 二叉树是最基本的树结构，**每个节点最多有两个子节点，但二叉树容易出现极端情况，比如插入的数据是有序的，那么二叉树就会退化成链表，查询效率就会变成 O(n)**。
为什么不用平衡二叉树？
- 平衡二叉树比红黑树的要求更高，每个节点的左右子树的高度最多相差 1，这种高度的平衡保证了极佳的查找效率，但在进行插入和删除操作时，可能需要频繁地进行旋转来维持树的平衡，这在某些情况下可能导致更高的维护成本。
- 红黑树是一种折中的方案，它在保证了树平衡的同时，插入和删除操作的性能也得到了保证，查询效率是 O(logn)。
红黑树怎么保持平衡的？
- 旋转：旋转分为两种，左旋和右旋。
- 染色：根据红黑树的规则调整节点颜色。

HashMap 的 put 流程知道吗

HashMap put 流程

第一步：通过 hash 方法计算 key 的哈希值。
第二步：数组进行第一次扩容。
第三步：根据哈希值计算 key 在数组中的下标，如果对应下标正好没有存放数据，则直接插入。
如果对应下标已经有数据了，就需要判断是否为相同的 key，是则覆盖 value，否则需要判断是否为树节点，是则向树中插入节点，否则向链表中插入数据。
注意：在链表中插入节点时，如果链表长度大于等于 8，则需要把链表转换为红黑树。
所有元素处理完后，还需要判断是否超过阈值 threshold，超过则扩容。

只重写 equals 没重写 hashcode，map put 的时候会发生什么？

如果只重写 equals 方法，没有重写 hashcode 方法，那么会导致 equals 相等的两个对象，hashcode 不相等，这样的话，这两个对象会被放到不同的桶中，这样就会导致 get 时找不到对应的值。
默认的 hashcode 方法是通过对象的内存地址进行计算的，如果只重写了 equals 而没有重写 hashcode，在使用 map 时，会优先通过 hashcode 来判断是否为同一元素，这会导致 equals 相同的元素在 map 中存在多个。

HashMap 怎么查找元素的呢？

HashMap 查找流程

使用扰动函数，获取新的哈希值。
计算数组下标，获取节点。
当前节点和 key 匹配，直接返回。
否则，当前节点是否为树节点，查找红黑树。
否则，遍历链表查找。

HashMap 的 hash 函数是怎么设计的？

HashMap 的哈希函数是先拿到 key 的 hashcode，是一个 32 位的 int 类型的数值，然后让 hashcode 的高 16 位和低 16 位进行异或操作。
这么设计是为了降低哈希碰撞的概率。

为什么 hash 函数能降哈希碰撞？

在 hash 函数中，先调用了 key.hashCode() 方法，这将会返回一个 int 类型的哈希值，比如字符串的 hashCode()。
int 的范围是 -2147483648~2147483647，加起来大概 40 亿上下的浮动。
通常我们会设置一个较小的数组长度，比如说 HashMap 的数组初始大小为 16，当发现容量不满足时再扩容，避免浪费。
当数组长度较小时，我们就需要设计一种巧妙的 hash 算法，来避免发生哈希冲突，尽可能地让元素均匀地分布在数组当中。
要达到这个目的，HashMap 在两方面下足了功夫：
- 第一：数组的长度必须是 2 的整数次幂，这样可以保证 hash & (n-1) 的结果能均匀地分布在数组中。
- 第二：hash & (n-1) 相当于 hash % n，n 为数组的长度。
  - 例如：数组长度为 16，hash 值为 20，那么 20 % 16 = 4，即 20 这个元素应该放在数组的第 4 个位置；hash 值为 23，那么 23 % 16 = 7，即 23 这个元素应该放在数组的第 7 个位置。
- 第三：& 操作的结果就是哈希值的高位全部归零，只保留 n 个低位，用来做数组下标访问。
- 那问题又来了，那么大一个哈希值，也只取最后 4 位，不就等于哈希值的高位都丢弃了吗？
- 这时候 hash 函数 (h = key.hashCode()) ^ (h >>> 16) 就派上用场了。
  - 将哈希值无符号右移 16 位，意味着原哈希值的高 16 位被移到了低 16 位的位置。这样，原始哈希值的高 16 位和低 16 位就可以参与到最终用于索引计算的低位中。

为什么 HashMap 的容量是 2 的倍数呢？

HashMap 的容量是 2 的倍数，或者说是 2 的整数次幂，是为了快速定位元素的下标。
HashMap 在定位元素位置时，先通过 hash(key) = (h = key.hashCode()) ^ (h >>> 16) 计算出哈希值，再通过 hash & (n-1) 来定位元素位置，n 为数组的大小，即 HashMap 的容量。
2 的整次幂（或者叫 2 的整数倍）刚好是偶数，偶数减 1 是奇数，奇数的二进制最后一位是 1，保证了 hash & (length-1) 的最后一位可能为 0，也可能为 1（取决于 hash 的值），即 & 运算后的结果可能为偶数，也可能为奇数，这样便可以保证哈希值的均匀分布。
当数组的长度是 2 的 n 次方时，hash & (length - 1) = hash % length。
当执行 hash & (length - 1) 时，实际上是保留 hash 二进制表示的最低 n 位，其他高位都被清零。
这时候，hash % length 和 hash & (length - 1) 的计算结果是一致的。

如果初始化 HashMap，传一个 17 容量，它会怎么处理？

HashMap 会将这个值转换为大于或等于 17 的最小的 2 的幂。这是因为 HashMap 的设计是基于哈希表的，而哈希表的大小最好是 2 的幂，这样可以优化哈希值的计算，并减少哈希冲突。
所以，如果你传入 17 作为初始容量，HashMap 实际上会被初始化为大小为 32 的哈希表。

解决哈希冲突有哪些方法呢？

再哈希法：
- 准备两套哈希算法，当发生哈希冲突时，使用另一种哈希算法，直到找到空槽为止。这对哈希算法的设计要求比较高。
开放地址法：
- 遇到哈希冲突时，寻找下一个空槽。有 3 种方法：
  - 线性探测：从冲突的位置开始，依次往后找，直到找到空槽。
  - 二次探测：从冲突的位置 x 开始，第一次增加 1^2 个位置，第二次增加 2^2 个位置直到找到空槽。
  - 双重哈希：和再哈希法类似，准备多个哈希函数，发生冲突时，使用另一哈希函数。
拉链法：
- 即链地址法，当发生哈希冲突时，使用链表将冲突的元素串起来。HashMap 采用的正是拉链法。

怎么判断 key 相等呢？

HashMap 判断两个 key 是否相等，依赖于 key 的 equals() 方法和 hashCode() 方法，以及 == 运算符：
- hashCode()：首先，使用 key 的 hashCode() 方法计算 key 的哈希码。由于不同的 key 可能有相同的哈希码，hashCode() 只是第一步筛选。
- equals()：当两个 key 的哈希码相同时，HashMap 还会调用 key 的 equals() 方法进行精确比较。只有当 equals() 方法返回 true 时，两个 key 才被认为是完全相同的。
- 当然，如果两个 key 的引用指向同一个对象，那么它们的 hashCode() 和 equals() 方法都会返回 true，因此在 equals 判断之前会优先使用 == 运算符判断一次。

为什么 HashMap 链表转红黑树的阈值为 8 呢？

阈值为什么要选 8 呢？和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为 8 的情况，发生概率仅为 0.00000006。
红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树，牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。
至于红黑树转回链表的阈值为什么是 6，而不是 8？是因为如果这个阈值也设置成 8，假如发生碰撞，节点增减刚好在 8 附近，会发生链表和红黑树的不断转换，导致资源浪费。

扩容在什么时候呢？为什么扩容因子是 0.75？

HashMap 会在存储的键值对数量超过阈值（即 capacity * loadFactor）时进行扩容。
简单来说，这是对空间成本和时间成本平衡的考虑。
HashMap 的散列构造方式是 Hash % n，负载因子决定元素个数达到多少时扩容。假如我们设的比较大，元素比较多，空位比较少的时候才扩容，那么发生哈希冲突的概率就增加了，查找的时间成本就增加了。我们设的比较小的话，元素比较少，空位比较多的时候就扩容了，发生哈希碰撞的概率就降低了，查找时间成本降低，但是就需要更多的空间去存储元素，空间成本就增加了。

那扩容机制了解吗？

扩容时，HashMap 会创建一个新的数组，其容量是原数组容量的两倍。
然后将键值对放到新计算出的索引位置上。一部分索引不变，另一部分索引为“原索引 + 旧容量”。
实际上就相当于用键的哈希值和数组大小取模，也就是 hashCode % table.length。
在 JDK 8 的新 hash 算法下，数组扩容后的索引位置，要么就是原来的索引位置，要么就是“原索引 + 原来的容量”，遵循一定的规律：
- 具体来说，就是判断原哈希值的高位中新增的那一位是否为 1。如果是，该元素会被移动到原位置加上旧容量的位置；如果不是，则保持在原位置。
- 只需要通过位运算，获取计算出的哈希值的下一位的值（从右往左），判断是否为 1。
- 尽管有几十万条数据，每个数据项的位置决定仅需要一次简单的位运算。位运算的计算速度非常快，因此，尽管扩容操作涉及遍历整个哈希表并对每个节点进行操作，但这部分操作的计算成本是相对较低的。

JDK 1.8 对 HashMap 主要做了哪些优化呢？为什么？

数组 + 链表改成了数组 + 链表或红黑树。
链表的插入方式从头插法改成了尾插法：
- 因为 JDK 1.7 的头插法扩容时，头插法会使链表发生反转，在多线程环境下会产生环。
扩容时，JDK 1.7 需要对原数组中的元素重新 hash 定位到新数组的位置；JDK 1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。
在插入时，JDK 1.7 先判断是否需要扩容再插入；JDK 1.8 先进行插入，插入完成再判断是否需要扩容。
JDK 1.7 做了四次移位和四次异或，JDK 1.8 只做了一次。

HashMap 是线程安全的吗？多线程下会有什么问题？

多线程下扩容会死循环。JDK 1.7 中的 HashMap 使用的是头插法插入元素，在多线程环境下扩容时可能导致出现环形链表，造成死循环。
线程的 put 可能会导致元素的丢失。因为计算出来的位置可能会被其他线程的 put 覆盖，本来哈希冲突是应该用链表的，但多线程时由于没有加锁，相同位置的元素可能就被干掉了。
**put 和 get 并发时，可能导致 get 返回 null**。线程 1 执行 put 时，由于元素个数超出阈值而导致出现扩容，线程 2 此时执行 get，就可能出现这个问题。

有什么办法能解决 HashMap 线程不安全的问题呢？

最常用的是**ConcurrentHashMap 和 Collections.synchronizedMap(Map) 包装器**。
HashTable 是直接在方法上加 synchronized 关键字，比较粗暴。
Collections.synchronizedMap 返回的是 Collections 工具类的内部类。
ConcurrentHashMap 在 JDK 7 中使用分段锁，在 JDK 8 中使用了 CAS（Compare-And-Swap）+ synchronized 关键字，性能得到进一步提升。

HashMap 内部节点是有序的吗？

HashMap 是无序的，根据 hash 值随机插入。如果想使用有序的 Map，可以使用 LinkedHashMap 或者 TreeMap。

讲讲 LinkedHashMap 怎么实现有序的？

LinkedHashMap 维护了一个双向链表，有头尾节点。同时 LinkedHashMap 节点 Entry 内部除了继承 HashMap 的 Node 属性，还有 before 和 after 用于标识前置节点和后置节点。

讲讲 TreeMap 怎么实现有序的？

TreeMap 通过 key 的比较器来决定元素的顺序，如果没有指定比较器，那么 key 必须实现 Comparable 接口。
TreeMap 的底层是红黑树，红黑树是一种自平衡的二叉查找树，每个节点都大于其左子树中的任何节点，小于其右子树中的任何节点。
查找时通过从根节点开始，利用二叉查找树的性质，逐步向左或者右子树递归查找，直到找到目标元素。

TreeMap 和 HashMap 的区别

HashMap 是基于数组+链表+红黑树实现的，put 元素时会先计算 key 的哈希值，然后通过哈希值计算出数组的索引，再将元素插入到数组中。如果发生哈希冲突，会使用链表来解决，如果链表长度大于 8，则会转换为红黑树。
get 元素时同样会先计算 key 的哈希值，然后通过哈希值计算出数组的索引，如果遇到链表或者红黑树，会通过 key 的 equals 方法来判断是否是要找的元素。
TreeMap 是基于红黑树实现的，put 元素时会先判断根节点是否为空，如果为空，则直接插入到根节点；如果不为空，则通过 key 的比较器来判断元素应该插入到左子树还是右子树。
get 元素时会通过 key 的比较器来判断元素的位置，然后递归查找。
由于 HashMap 是基于哈希表实现的，所以在没有发生哈希冲突的情况下，HashMap 的查找效率是 O(1)。适用于查找操作较频繁的场景。
而 TreeMap 是基于红黑树实现的，所以 TreeMap 的查找效率是 O(logn)。并且保证了元素的顺序，因此适用于需要大量范围查找或者有序遍历的场景。

讲讲 HashSet 的底层实现？

HashSet 其实是由 HashMap 实现的，只不过值由一个固定的 Object 对象填充，而键用于操作。
HashSet 主要用于去重，比如需要统计一篇文章中有多少个不重复的单词，就可以使用 HashSet 来实现。
HashSet 会自动去重，因为它是用 HashMap 实现的，HashMap 的键是唯一的（哈希值），相同键的值会覆盖掉原来的值，因此当第二次 set.add("key") 时会覆盖第一次的 set.add("key")。

HashSet 和 ArrayList 的区别

ArrayList 是基于动态数组实现的，HashSet 是基于 HashMap 实现的。
ArrayList 允许重复元素和 null 值，可以有多个相同的元素；HashSet 保证每个元素唯一，不允许重复元素，基于元素的 hashCode 和 equals 方法来确定元素的唯一性。
ArrayList 保持元素的插入顺序，可以通过索引访问元素；HashSet 不保证元素的顺序不保证元素的顺序，元素的存储顺序依赖于哈希算法，并且可能随着元素的添加或删除而改变。·