面试题：Java中TreeMap与HashMap在原理上的差异

1. 数据结构

HashMap：基于哈希表实现，使用数组加链表（JDK 1.8 后引入红黑树优化，当链表长度大于 8 且数组长度大于 64 时转换为红黑树）来存储键值对。通过对键的哈希值进行计算来确定存储位置，以实现快速的查找和插入。
TreeMap：基于红黑树实现，红黑树是一种自平衡的二叉搜索树。每个节点包含键值对，通过比较键的大小来决定节点在树中的位置，保证树的左子节点小于根节点，右子节点大于根节点。

2. 排序方式

HashMap：不保证键值对的顺序，其顺序通常是根据哈希值来决定，在不同的插入顺序或不同的哈希算法下，顺序可能不同，并且在扩容等操作后顺序可能改变。
TreeMap：按键的自然顺序（如果键实现了 Comparable 接口）或者根据创建 TreeMap 时提供的 Comparator 进行排序。它始终保持键的有序性。

3. 性能特点

HashMap：在插入、查找和删除操作上平均时间复杂度为 O(1)，在理想情况下，哈希函数均匀分布，性能非常高效。但是在哈希冲突严重时，链表变长，时间复杂度可能退化为 O(n)，JDK 1.8 引入红黑树优化后，最坏情况下时间复杂度为 O(log n)。
TreeMap：插入、查找和删除操作的时间复杂度始终为 O(log n)，因为红黑树保证了树的平衡。但是相比 HashMap 的平均 O(1) 性能，TreeMap 的操作通常会慢一些。

4. 适用场景

HashMap：适用于需要快速插入、查找和删除操作，并且对键的顺序没有要求的场景。例如，缓存系统、统计数据频率等场景，只要快速获取数据而不关心顺序，HashMap 是很好的选择。
TreeMap：适用于需要按键有序遍历的场景，或者需要获取键的最值（如最大、最小值）等场景。例如，实现一个按时间顺序存储事件的系统，并且需要按时间顺序遍历事件；或者实现一个排行榜，需要根据分数对用户进行排序并快速获取最高分或最低分用户等场景。

举例

假设要实现一个程序，统计文本中每个单词出现的频率，并按单词的字典序输出。

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class WordFrequency {
    public static void main(String[] args) {
        String text = "apple banana apple cherry banana cherry";
        String[] words = text.split(" ");

        // 使用HashMap统计单词频率
        Map<String, Integer> hashMap = new HashMap<>();
        for (String word : words) {
            hashMap.put(word, hashMap.getOrDefault(word, 0) + 1);
        }

        // 使用TreeMap按字典序输出
        Map<String, Integer> treeMap = new TreeMap<>(hashMap);
        for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

在这个例子中，如果直接使用 HashMap 遍历输出，单词顺序是无序的。而使用 TreeMap 可以按单词的字典序输出，满足按序输出的需求，所以这种场景更适合使用 TreeMap。

面试题：Java中TreeMap与HashMap在原理上的差异

知识考点

面试题答案

1. 数据结构

2. 排序方式

3. 性能特点

4. 适用场景

举例