面试题：Java中HashMap与TreeMap数据存储实现对性能的深层次影响

HashMap：基于哈希表实现，本质是数组加链表（JDK 1.8 后引入红黑树优化）。数组中的每个元素是一个链表的头节点，链表用来解决哈希冲突。当链表长度大于阈值（8）且数组长度大于 64 时，链表会转换为红黑树。
TreeMap：基于红黑树实现，红黑树是一种自平衡的二叉搜索树，每个节点包含键值对，通过比较键的大小来确定节点在树中的位置。

HashMap：使用哈希函数将键映射到数组的索引位置。哈希函数首先计算键的 hashCode()，然后对数组长度进行取模（实际采用位运算优化）。通过扰动函数（JDK 1.8 中）进一步混合哈希值，减少哈希冲突。
TreeMap：不依赖哈希算法，而是基于键的自然顺序或自定义比较器来确定元素在树中的位置。

红黑树特性：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶子节点（NIL 节点，空节点）是黑色。
- 如果一个节点是红色的，则它的两个子节点都是黑色。
- 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
HashMap 中红黑树应用：在 JDK 1.8 后，当链表长度过长时转换为红黑树，利用红黑树自平衡和有序特性，优化查找、插入和删除的时间复杂度。

插入操作：
- HashMap：理想情况下（无哈希冲突）时间复杂度为 O(1)，因为通过哈希函数直接定位到数组位置插入。但在最坏情况下（哈希冲突严重，链表很长），时间复杂度为 O(n)，n 为链表长度。JDK 1.8 引入红黑树优化后，当链表转换为红黑树，插入时间复杂度为 O(log n)。
- TreeMap：由于红黑树自平衡特性，插入操作时间复杂度始终为 O(log n)，n 为树中节点个数。插入后通过旋转和变色操作保持红黑树特性。
查找操作：
- HashMap：理想情况下时间复杂度为 O(1)，通过哈希函数定位数组位置直接获取值。最坏情况下（哈希冲突严重，链表很长），时间复杂度为 O(n)。转换为红黑树后，查找时间复杂度为 O(log n)。
- TreeMap：查找操作时间复杂度为 O(log n)，因为红黑树是二叉搜索树，通过比较键值大小在树中逐步查找。
删除操作：
- HashMap：理想情况下时间复杂度为 O(1)，定位到数组位置删除元素。最坏情况下（链表很长），时间复杂度为 O(n)。若删除红黑树节点，时间复杂度为 O(log n)，删除后需要调整红黑树保持平衡。
- TreeMap：删除操作时间复杂度为 O(log n)，同样需要调整红黑树保持平衡。

HashMap 性能优化：
- 初始容量设置：根据数据量预估合理设置初始容量，避免频繁扩容。扩容会导致重新计算哈希值和数据迁移，性能开销大。可以通过公式 capacity = (expectedSize / loadFactor) + 1 预估容量。
- 负载因子调整：默认负载因子为 0.75，可根据实际场景调整。如果对空间敏感，可适当降低负载因子减少哈希冲突，但会增加空间占用；如果对时间敏感，可适当提高负载因子节省空间，但可能增加哈希冲突导致性能下降。
- 选择合适的键：选择哈希分布均匀的键，减少哈希冲突。例如，重写 hashCode() 方法时保证不同键的哈希值尽量分散。
TreeMap 性能优化：
- 选择合适的比较器：如果使用自定义比较器，确保比较逻辑高效，避免复杂计算影响插入、查找和删除性能。
- 数据有序性利用：如果应用场景需要数据有序，TreeMap 天然有序的特性可以避免额外排序操作，提高性能。

HashMap：适用于需要快速查找和插入，对数据顺序无要求的场景。例如，缓存系统，因为可以快速根据键获取值；统计单词出现次数，利用哈希表快速插入和更新计数。
TreeMap：适用于需要按键排序的场景。例如，实现一个按时间顺序存储日志记录的系统，或者在统计数据时需要按数值大小排序展示等场景。

星途面试题库