Java Map1
Java Map1
29. 讲一下 HashMap 的工作原理？
回答：
HashMap 基于哈希表实现，通过键的 hashCode 值定位元素在数组中的位置，处理哈希冲突时使用链表或红黑树结构来提升性能。
分析：
HashMap 是 Java 中最常用的 Map 实现，其核心思想是"通过哈希函数将 key 映射为数组下标，再通过数组存取 value"。当调用 put(key, value) 时，HashMap 首先会调用 hash() 方法对 key 进行扰动计算，生成较为均匀的哈希值，然后通过取模操作映射到数组的某个位置。如果当前位置为空，直接插入；否则判断该位置是否存在相同 key（通过 equals 判断）。若存在则覆盖，否则形成链表或树结构。自 JDK 1.8 起，当链表长度超过 8 且桶数组长度大于 64 时，链表结构将自动转换为红黑树，以提升查询效率。在读取操作中，如 get(key)，HashMap 会根据 hash 定位数组，再遍历链表或红黑树查找目标 key，查找到后返回对应 value。这种设计结合了数组的快速访问与链表/树结构的冲突解决能力，实现了空间与效率的平衡。
30. HashMap 的 key 可以为 null 吗？
回答：
可以，HashMap 允许最多一个 key 为 null 的键值对存在，JDK 对此做了特殊处理。
分析：
在 HashMap 中，key 为 null 是一个被显式支持的特性。内部在调用 put(null, value) 时，会直接将 key 为 null 的键值对存入数组的第一个位置（即下标 0 处）。这是通过在 hash() 方法中对 null 做特殊处理实现的：若 key 为 null，哈希值直接为 0，绕过了 hashCode 的调用。虽然 HashMap 支持一个 null key，但由于 key 的唯一性原则，再次插入 null 会覆盖已有值。value 值方面，HashMap 支持任意多个 null value。这个特性在某些场景下非常有用，例如初始化缓存、延迟加载等。但需要注意，其他一些 Map 实现如 Hashtable、ConcurrentHashMap 出于线程安全考虑并不允许 key 为 null。
31. Java 8 对 HashMap 做了哪些优化？
回答：
Java 8 在 HashMap 上引入了链表转红黑树的机制、优化了扩容策略和插入逻辑，提升了高并发下的性能表现和可预测性。
分析：
在 Java 7 中，HashMap 采用数组 + 链表的结构来处理哈希冲突，但在极端情况下可能退化为链表，导致查询效率从 O(1) 降为 O(n)。为解决这一问题，Java 8 对 HashMap 做出以下优化：首先，引入"数组 + 链表/红黑树"的混合结构，当同一哈希桶中的元素超过 8 个时，链表会自动转换为红黑树，提升查询效率为 O(log n)。其次，链表插入方式由原来的头插法改为尾插法，避免在扩容时因链表反转带来的死循环问题。再次，在扩容时，1.7 重新计算所有元素位置，而 1.8 采用位运算判断元素是否保留原位置或移动到新数组索引 + 旧容量位置，简化了迁移过程。最后，在插入顺序上，1.8 先插入再判断是否需要扩容，而 1.7 是先判断再插入。这些改进不仅优化了性能，也增强了容器行为的一致性和稳定性，体现了对实际应用场景的深入考量。
32. 讲一下 HashMap 的 put 流程？
回答：
HashMap 的 put 操作主要包括：计算 hash 值、定位数组索引、处理哈希冲突（链表/红黑树）、必要时扩容等步骤。
分析：
当调用 put(key, value) 时，HashMap 首先会判断 table 是否为空，若为空则执行初始化（resize）。然后通过扰动函数计算 key 的 hash 值，再用 hash & (length - 1) 得到数组下标 i。如果该位置为空，则直接插入新节点。若该位置已有元素，会判断首节点的 key 是否与当前 key 相同，相同则替换 value；否则根据节点类型（链表或红黑树）采取不同策略。链表中遍历查找相同 key，否则追加新节点；若形成的链表长度超过 8 且 table 长度超过 64，会转为红黑树。最后插入成功后，会判断 size 是否超过阈值，超出则触发扩容操作。整个流程体现了 HashMap 在空间利用与访问效率之间的平衡控制。
33. HashMap 的长度为什么是 2 的幂次方？
回答：
这是为了优化哈希取模操作，将原本较慢的 % 运算替换为更快的按位与 & 运算。
分析：
在 HashMap 中，将 hash 值映射为数组索引时，使用 hash & (table.length - 1) 而非传统的 hash % length。这要求数组长度必须为 2 的幂次方，因为只有这样才能确保每一位都参与哈希映射，分布更加均匀，避免哈希冲突集中。同时，& 操作比 % 运算速度快，能提升整体性能。若数组长度不是 2 的幂次，则位与运算不能正确替代取模操作，导致分布不均甚至数组越界，因此 JDK 内部强制将容量调整为 2 的幂。
34. HashMap 默认负载因子为什么是 0.75？
回答：
0.75 是在时间效率和空间利用之间的折中选择，既保证查找性能，又避免频繁扩容。
分析：
负载因子（loadFactor）是衡量 HashMap 空间使用效率的关键参数。其定义是：实际存储元素数 ÷ 数组容量。值越大，数组使用越充分，但冲突概率上升，链表/树结构加长，降低查询效率。反之，负载因子越小，查找快但浪费空间。JDK 选择 0.75 这一经验值，是经过大量性能测试得出的权衡结果——在实际业务中能达到较好的查找效率，又不会因频繁扩容而增加性能开销。若有特殊场景，可通过构造函数手动设置更适配的负载因子。
35. HashMap 的默认初始容量为什么是 16？
回答：
16 是一个性能与内存之间的经验折中，既能避免初始就扩容，也不会浪费过多空间。
分析：
HashMap 的默认容量为 16（2^4），这一数值不是随意选择的，而是根据实际应用中的负载均衡与性能表现做出的折中。容量过小（如 4 或 8）在面对较多元素时容易频繁扩容，影响性能；过大则会导致内存浪费。16 是一个恰当的起点：结合默认负载因子 0.75，首次扩容会在存入 12 个元素后触发，既保障性能，又利于控制空间开销。此外，16 是 2 的幂次，便于 hash 计算。JDK 虽未在文档中显式说明原因，但这是一种基于历史实践的合理经验值。
36. Java 8 中链表转红黑树和红黑树转链表为什么是 8 和 6？
回答：
链表长度超过 8 才转红黑树，是为了平衡空间和时间效率；当元素减少到 6 以下再还原为链表，是为了避免频繁结构切换。
分析：
Java 8 为提升 HashMap 在高冲突场景下的查找效率，引入了链表转红黑树的机制。当某个桶中的链表节点数超过 8 且数组长度超过 64 时，链表将转为红黑树。这一阈值并非随意设定，而是基于泊松分布等实证数据得出的结论：哈希碰撞超过 8 次的概率非常小，若真的发生了，说明哈希算法或 key 分布存在问题，此时使用红黑树可显著提升查找性能。而红黑树转链表的阈值设为 6，是为了避免在节点数反复波动于 7 附近时发生结构震荡（频繁切换树与链表），通过设置 hysteresis 范围减少资源浪费。
37. 了解的哈希冲突解决方法有哪些？
回答：
常见的冲突解决策略包括：链表法、开放地址法、再哈希法和扩容机制等。
分析：
哈希冲突是哈希结构中不可避免的问题，不同实现有不同的应对策略。Java 中主要使用的是链地址法（即链表或红黑树挂载在数组桶上），简单直观且支持扩展。开放地址法（如线性探测、二次探测、双重散列）通过在数组中寻找下一个可用位置解决冲突，适用于不允许使用链表的场景。再哈希法通过更换哈希函数在冲突时重新计算索引，增加分布均匀性。此外，扩容机制是从宏观上降低冲突密度，即增大数组容量、重新分布元素。不同策略在性能、内存占用与实现复杂度上各有优劣，实际应用需根据需求选择。
38. Java 8 为什么使用红黑树而不是 AVL 树？
回答：
红黑树结构更宽松，插入和删除操作比 AVL 树更高效，是时间复杂度与操作性能的折中。
分析：
AVL 树在插入/删除操作后保持严格的高度平衡，虽然查找效率略高于红黑树，但为了保持这种平衡，其插入删除时需频繁做旋转，代价较大。而红黑树在保持大致平衡的基础上，通过颜色标记限制最长路径，结构调整相对简单，插入删除开销小。在 HashMap 的应用场景中，更多关注的是插入性能与平均查找效率的平衡，极端场景也较少，因此红黑树是更合适的选择。JDK 也广泛采用红黑树作为 TreeMap、TreeSet、ConcurrentSkipListMap 等结构的底层实现。
39. 为什么 HashMap 要将 hashCode 右移 16 位再异或？
回答：
这是为了混合高低位信息，增强哈希值的随机性，使其分布更均匀，降低哈希冲突概率。
分析：
HashMap 使用的 hash(key) 方法不仅调用了对象的 hashCode()，还进行了额外扰动处理：(h = key.hashCode()) ^ (h >>> 16)。目的是将高位信息混入低位，提高低位的随机性。因为在计算数组索引时，只有低位有效（通过 & 运算），若高位信息未参与，会造成高位变动无法影响定位，增加碰撞概率。通过右移 16 位并异或的方式，高低位融合后生成的哈希值分布更均匀，有效避免热点集中，大幅提升哈希桶的利用率。
40. HashMap 什么时候会触发扩容？
回答：
当元素数量超过容量与负载因子的乘积时会扩容，默认触发条件为 size > 16 × 0.75，即 12 个元素。
分析：
HashMap 扩容是为了解决容量不足引起的哈希冲突。其扩容触发主要有两个条件：一是整体元素数量超过 threshold = capacity × loadFactor（默认为 16×0.75=12）；二是在 Java 8 中，如果单个桶内链表长度达到 8 且当前数组长度小于 64，也会触发扩容而非转红黑树。扩容时，HashMap 会将原数组中的元素重新计算 hash 后搬迁到新数组，元素位置可能保留原地或移动到下标 + oldCap 的位置。扩容代价较大，因此应尽量通过构造函数提前指定合适初始容量，减少 resize 次数，提升性能。