面试题：Java中Map接口常用的实现类有哪些及其特点

Question

请列举出Java中Map接口常用的几个实现类，并简要描述每个实现类在存储结构、线程安全性、性能表现等方面的特点。

Answer 1

1. HashMap

   • 存储结构：基于哈希表实现，使用数组和链表（JDK 1.8 后引入红黑树优化链表过长问题）。数组的每个元素是一个链表头节点（桶），通过计算 key 的哈希值决定元素存放在哪个桶中。
   • 线程安全性：非线程安全，在多线程环境下使用可能出现数据不一致等问题。
   • 性能表现：在单线程环境下，插入、查找、删除操作平均时间复杂度为 O(1)，但在哈希冲突严重时，时间复杂度会退化为 O(n)。

2. TreeMap

   • 存储结构：基于红黑树实现，元素按照 key 的自然顺序或自定义顺序排序存储。
   • 线程安全性：非线程安全。
   • 性能表现：插入、查找、删除操作时间复杂度为 O(log n)，适用于需要有序遍历 key 的场景。

3. LinkedHashMap

   • 存储结构：继承自 HashMap，同时使用双向链表维护插入顺序或访问顺序。在存储结构上，除了哈希表结构，还额外维护了一个双向链表。
   • 线程安全性：非线程安全。
   • 性能表现：基本和 HashMap 类似，由于需要维护链表，在插入和删除操作上会略微多一些开销。在按插入顺序或访问顺序遍历元素时效率较高。

4. ConcurrentHashMap

   • 存储结构：在 JDK 1.7 中采用分段锁机制，由多个 Segment 组成，每个 Segment 类似一个小型的 HashMap；JDK 1.8 后采用 CAS 操作和 synchronized 关键字结合的方式，数组 + 链表/红黑树结构。
   • 线程安全性：线程安全，允许多个线程同时读，写操作通过锁分段或 CAS 等机制保证线程安全。
   • 性能表现：在多线程环境下，相比于 Hashtable 等线程安全的 Map，性能有显著提升。读操作基本无锁，写操作锁粒度更小，并发性能好。