面试题：Java中Map接口常用实现类在复杂业务逻辑应用上的区别

存储结构

HashMap：基于哈希表实现，使用数组加链表（JDK 1.8 后引入红黑树优化，链表长度超过 8 且数组长度大于 64 时转化为红黑树）来存储元素。它通过对 key 进行哈希运算来确定元素在数组中的位置。
TreeMap：基于红黑树实现，红黑树是一种自平衡的二叉查找树。TreeMap 中的元素按照 key 的自然顺序（或自定义比较器顺序）进行排序存储。
LinkedHashMap：继承自 HashMap，在 HashMap 的基础上维护了一个双向链表来记录插入顺序或访问顺序。

性能

HashMap：插入、查找操作平均时间复杂度为 O(1)，在哈希冲突较少的情况下性能最佳。但是在哈希冲突严重时，链表会变长，查找时间复杂度会退化为 O(n)（红黑树时为 O(log n)）。
TreeMap：插入、查找操作时间复杂度为 O(log n)，因为红黑树的自平衡特性保证了树的高度始终保持在对数级别。但是相比 HashMap，TreeMap 的插入和查找性能会稍慢，因为需要维护树的平衡。
LinkedHashMap：插入和查找操作性能与 HashMap 相近，因为其内部仍然基于哈希表实现。但是由于维护双向链表的额外开销，性能会略低于 HashMap。

元素顺序维护

HashMap：不保证元素的顺序，元素的顺序是由哈希值决定的，在不同的运行环境下顺序可能不同。
TreeMap：按照 key 的自然顺序（或自定义比较器顺序）进行排序。例如，如果 key 是 Integer 类型，那么会按照数字大小顺序存储；如果是自定义对象，需要实现 Comparable 接口或者提供一个 Comparator。
LinkedHashMap：可以按照插入顺序或者访问顺序维护元素顺序。当访问一个元素后，该元素会移动到链表末尾（如果是访问顺序）。

适用场景及举例

HashMap：适用于需要快速查找和插入的场景，对元素顺序没有要求。例如，缓存系统中，我们只关心根据 key 快速获取对应的 value，不关心元素的插入顺序或排序。

HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("one", 1);
hashMap.put("two", 2);
// 这里获取元素的顺序不确定
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}

TreeMap：适用于需要对元素按照 key 进行排序的场景。比如，统计单词出现的频率并按照单词字典序输出。

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("banana", 3);
treeMap.put("apple", 2);
treeMap.put("cherry", 1);
for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}
// 输出结果会按照单词字典序：apple : 2, banana : 3, cherry : 1

LinkedHashMap：适用于需要维护元素插入顺序或访问顺序的场景。例如，实现一个简单的 LRU（最近最少使用）缓存。

LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<String, Integer>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 3;
    }
};
linkedHashMap.put("one", 1);
linkedHashMap.put("two", 2);
linkedHashMap.put("three", 3);
linkedHashMap.get("two");
linkedHashMap.put("four", 4);
// 此时 "one" 会被移除，因为它是最久未使用的元素
for (Map.Entry<String, Integer> entry : linkedHashMap.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}

星途面试题库

面试题：Java中Map接口常用实现类在复杂业务逻辑应用上的区别

知识考点

面试题答案

存储结构

性能

元素顺序维护

适用场景及举例