更多特训营笔记详见个人主页【面试鸭特训营】专栏

250120

1. 说说 Java 中 HashMap 的原理？

HashMap 的底层结构

• HashMap 底层由 node 数组、单链表、红黑树构成。
• 根据哈希函数计算得到哈希值，哈希值确定了元素保存在 node 数组中的具体下标。
• HashMap 的默认初始容量为 16，负载因子为 0.75。当存储的元素超过 16 × 0.75 = 12 个时，HashMap 会触发扩容操作，将容量 ×2 并重新分配元素位置。
• 扩容是比较耗时的操作，频繁扩容会影响性能。

哈希冲突

• 两个不同的元素，经过哈希函数计算之后，可能会得到相同的哈希值，映射到 node 数组的同一个下标，产生哈希冲突。
• 哈希冲突有多种解决方案，如链地址法，开放寻址法（线性探测、平方探测），再哈希法， HashMap 中采用的是链地址法。
• 在每个数组下标下挂一个单链表，单链表内保存的是【具有相同哈希值的不同元素】。
• 当单链表中保存的元素 >= 8 时，为提升查找效率，单链表转为红黑树。
  • 最坏情况下，单链表的查找时间复杂度是O(N)，红黑树的查找时间复杂度是O(logN)。
• 当红黑树中保存的元素 <= 6 时，为提升增删效率，红黑树转为单链表。
  • 红黑树在增删节点时，需要通过自旋和染色维持红黑树的平衡。

2. Java 中有哪些集合类？请简单介绍

3. Java 中 HashMap 的扩容机制是怎样的？

• 负载因子

  • 一个介于 0 到 1 的小数，当存储占比达到负载因子时，会通过扩容机制进行扩容。

• HashMap 的负载因子是 0.75 ，当 HashMap 已存储元素数量超过当前容量的 75% 时，就会进行扩容。

• 以初始容量 16 为例

  • 扩容阈值：16 × 0.75 = 12。
  • 前 12 个元素正常存储，当存入第 13 个元素时，HashMap 会进行扩容。
  • 每次扩容时
    • 1. 会将 HashMap 的容量扩大为当前容量的 2 倍。
    • 2. HashMap 需要重新计算所有元素的哈希值，并将它们重新分配到新的哈希桶中，这个过程称为rehashing。每个元素的存储位置会根据新容量的大小重新计算哈希值，并移动到新的数组中。

  • 由于每次扩容都需要重新遍历当前所有元素，重新计算元素的哈希值并移动到新的位置，所以扩容是一个很耗时的操作，频繁扩容会导致性能明显下降。
  • 优化方案：如果能预估到 HashMap 中大概会存储多少数据，可以在创建 HashMap 的时候就指定一个较大的初始容量，以减少扩容次数。
    • 例：对于存储 100 万个元素的 HashMap ，可以直接设置一个 1024 × 1024 的初始容量，避免多次扩容。