hashmap和treemap的区别

在Java面试中，HashMap和TreeMap是集合框架中常被问到的知识点，二者都实现了Map接口，但在底层结构、性能特性等方面有显著区别。以下是面试中常考的区别总结：

1. 底层数据结构

• HashMap：基于哈希表（数组+链表/红黑树）实现。 JDK 1.8后，当链表长度超过阈值（默认8）时，会转为红黑树以优化查询性能。
• TreeMap：基于红黑树（一种自平衡的二叉搜索树）实现。 红黑树的特性保证了键的有序性和高效的增删改查操作。

2. 有序性

• HashMap：无序。 存储顺序与插入顺序无关，且扩容时可能导致元素位置重排（JDK 1.8后优化了部分重排逻辑）。
• TreeMap：有序。 按键的自然顺序（Comparable）或自定义比较器（Comparator）排序，遍历时按排序后的顺序输出。

3. 键的要求

• HashMap： 键可以为null（仅允许一个null键），且键需正确实现hashCode()和equals()方法（否则可能导致数据异常，如元素无法查找）。
• TreeMap： 键不允许为null（会抛出NullPointerException），且键必须可比较：
  • 要么实现Comparable接口，
  • 要么在构造TreeMap时传入自定义Comparator。

4. 性能特性（时间复杂度）

• HashMap：哈希表的特性使其平均情况下增删查效率更高，但在哈希冲突严重时性能下降。
• TreeMap：红黑树的平衡性保证了稳定的O(log n)性能，但常数时间比HashMap略高。

5. 适用场景

• HashMap： 适用于插入、查询频繁，且不需要排序的场景（如缓存、快速查找）。 例如：存储用户ID与信息的映射，只需通过ID快速查询。
• TreeMap： 适用于需要按键排序的场景（如范围查询、排序遍历）。 例如：存储学生成绩并按分数排序，或需要查询“分数在90-100之间的学生”。

6. 其他区别

• 扩容机制： HashMap有扩容机制（默认容量16，负载因子0.75），当元素数量超过阈值时会扩容为原来的2倍； TreeMap无扩容概念，红黑树会自动平衡。
• 线程安全性： 二者均为非线程安全，多线程环境下需额外同步（如使用Collections.synchronizedMap()）或使用并发实现（如ConcurrentHashMap）。

面试题延伸

1. 为什么HashMap的键要重写hashCode()和equals()？
   • hashCode()决定元素在哈希表中的存储位置，equals()用于判断键是否相同。
   • 若不重写，可能导致相同逻辑的键被视为不同，或不同键被放入同一位置，引发性能问题。
2. TreeMap的排序是如何实现的？
   • 依赖Comparable的compareTo()方法或Comparator的compare()方法，红黑树会根据比较结果维护有序结构。
3. HashMap在JDK 1.8中为什么引入红黑树？
   • 解决哈希冲突时链表过长导致的查询效率下降问题（从O(n)优化为O(log n)）。
4. 如何选择HashMap和TreeMap？
   • 优先考虑HashMap（性能更优），除非明确需要排序功能才选择TreeMap。

总结：二者的核心区别在于有序性和底层结构，选择时需根据是否需要排序、操作频率（插入/查询）等场景决定。