java集合框架之Map系列

前言

  首先从最常用的HashMap开始。HashMap是基于哈希表实现的，使用数组和链表（或红黑树）的结构。在Java 8之后，当链表长度超过阈值时会转换为红黑树，以提高查询效率。哈希冲突通过链地址法解决。需要明确的是，HashMap允许null键和null值，是非线程安全的。
  LinkedHashMap，它继承自HashMap，但内部维护了一个双向链表来维护插入顺序或者访问顺序。这使得LinkedHashMap可以保持元素的顺序，比如用于实现LRU缓存。我需要确认其内部结构是否在HashMap的基础上增加了链表节点，以及如何维护这个链表。
  TreeMap，它基于红黑树实现，能够保持键的有序性。TreeMap的键必须实现Comparable接口，或者在构造时提供Comparator。红黑树的自平衡特性保证了基本操作的时间复杂度为O(log n)。本文详细说明红黑树的结构和调整过程，比如插入和删除时的旋转和颜色变换。

  Hashtable是早期的线程安全的Map实现，它通过synchronized方法实现同步，但性能较差。其结构与HashMap类似，也是基于哈希表，但不同的是它不允许null键和null值，并且是线程安全的。不过现在通常推荐使用ConcurrentHashMap代替Hashtable。
  ConcurrentHashMap是线程安全的，并且在Java 8之后采用了CAS和synchronized来保证并发安全，同时将数据结构改为与HashMap类似的数组+链表/红黑树，但每个桶（Node）在更新时使用同步块。需要了解其分段锁（Java 7）和CAS（Java 8）的演变，以及如何在高并发下提高吞吐量。
  EnumMap是专门为枚举类型设计的Map，使用枚举常量的自然顺序作为键，内部用数组存储，效率很高。需要说明其内部如何根据枚举的ordinal()值作为数组索引，以及如何保证类型安全。
  WeakHashMap基于哈希表，但键是弱引用，当键不再被外部引用时，条目会被自动移除。适用于需要缓存的场景，需要注意其垃圾回收机制对键的影响，以及如何通过引用队列来清理失效的条目。
  还有其他如IdentityHashMap，它使用==代替equals来比较键，适用于需要对象地址相等的情况。其内部实现通常是一个线性探测的哈希表，可能需要解释其哈希冲突解决方式的不同。
  本文会逐个Map实现类详细分析实现原理以及数据结构，并在最后总结对比它们的内部数据结构、哈希算法、冲突解决策略、线程安全机制、迭代顺序、允许的键值类型以及性能表现。并要指出各个实现类的适用场景，帮助理解为什么在特定情况下选择某种Map实现。
  注意，有些实现类可能在不同Java版本中有变化，例如HashMap在Java 8中的树化改进，ConcurrentHashMap在Java 8中放弃分段锁，采用更细粒度的锁机制。因此，需要确认所讨论的Java版本，这里假设是最新的Java版本。
  在细节上，比如初始容量、负载因子、扩容机制、迭代器的快速失败机制等。例如，HashMap的默认初始容量是16，负载因子0.75，当元素数量超过容量乘以负载因子时，会进行扩容，容量翻倍，并重新哈希所有元素。而ConcurrentHashMap在Java 8中可能使用不同的并发策略，如sizeCtl变量控制扩容。
  总结来说，我需要逐一分析每个Map实现类的数据结构、关键算法（如哈希函数、树操作）、线程安全处理、性能参数以及典型用例，确保全面而详细地解释它们的实现原理。
  Java集合框架中的Map接口有多种实现类，每种实现类在数据结构、线程安全、排序特性等方面各有不同。

1. HashMap

• 数据结构：数组 + 链表/红黑树（Java 8+）。

  • 数组（Node<K,V>[] table）作为哈希桶，每个桶可能为链表或红黑树。
  • 当链表长度超过8且数组长度≥64时，链表转换为红黑树；当红黑树节点数≤6时，退化为链表。

• 哈希函数：

  static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
  

  • 通过异或高位与低位减少哈希冲突。

• 冲突解决：链地址法（拉链法）。

• 扩容机制：

  • 默认初始容量16，负载因子0.75。
  • 当元素数量超过capacity * loadFactor时，容量翻倍并重新哈希。

• 线程安全：非线程安全，需外部同步。

• 允许键值：允许null键和null值。

2. LinkedHashMap

• 数据结构：继承自HashMap，维护双向链表记录插入顺序或访问顺序。

  • 每个节点（Entry<K,V>）新增before和after指针，形成链表。

• 顺序特性：

  • 插入顺序（默认）：按元素插入顺序迭代。
  • 访问顺序（accessOrder=true）：每次访问（get/put）将节点移到链表末尾，用于实现LRU缓存。

• 线程安全：非线程安全。

• 示例LRU实现：

  public class LRUCache<K,V> extends LinkedHashMap<K,V> {private final int maxCapacity;protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return size() > maxCapacity;}
  }
  

3. TreeMap

• 数据结构：基于红黑树（自平衡二叉搜索树）。

• 红黑树特性：

  • 节点为红或黑，根和叶子（NIL）为黑。
  • 红节点的子节点必为黑。
  • 任一节点到叶子路径的黑节点数相同。
    排序机制：
  • 键必须实现Comparable接口，或构造时提供Comparator。
  • 支持自然排序和定制排序。

• 操作复杂度：O(log n)（插入、删除、查找）。

• 线程安全：非线程安全。

4. Hashtable

• 数据结构：数组 + 链表（类似Java 8前的HashMap）。
• 线程安全：通过synchronized方法实现，性能较低。
• 哈希函数：直接使用key.hashCode()。
• 键值限制：不允许null键或值。
• 扩容机制：初始容量11，负载因子0.75，扩容为2n + 1。

5.ConcurrentHashMap

• 数据结构（Java 8+）：数组 + 链表/红黑树，类似HashMap。
• 线程安全：
  • 分段锁（Java 7）：将数据分为多个段（Segment），每段独立加锁。
  • CAS + synchronized（Java 8+）：桶（Node）头节点无竞争时使用CAS，有竞争时synchronized锁住头节点。
• 并发控制：
  • sizeCtl变量控制初始化与扩容。
  • 多线程协助扩容（transfer方法）。
• 性能：高并发下吞吐量优于Hashtable和synchronizedMap。

6. WeakHashMap

• 数据结构：数组 + 链表，键为弱引用（WeakReference）。
• 垃圾回收：当键不再被强引用时，条目自动被移除。
• 实现原理：
  • 键的弱引用被垃圾回收后，条目加入引用队列（ReferenceQueue）。
  • 在get/put/resize时清理失效条目。
• 适用场景：缓存临时数据，防止内存泄漏。

7. EnumMap

• 数据结构：基于枚举常量的序数（ordinal()）作为索引的数组。
  • 内部数组长度等于枚举类型的常量数量。
• 特性：
  • 键必须为同一枚举类型。
  • 迭代顺序为枚举常量声明顺序。
  • 性能高，无哈希冲突。
  • 线程安全：非线程安全。

8. IdentityHashMap

• 数据结构：线性探测哈希表（开放地址法）。
• 键比较：使用==（对象地址）代替equals()。
• 适用场景：需要区分对象地址的场景（如序列化框架）。

对比总结

选择建议

• 快速查找：HashMap（无需排序）。
• 保持插入/访问顺序：LinkedHashMap。
• 键排序需求：TreeMap。
• 高并发场景：ConcurrentHashMap。
• 缓存临时数据：WeakHashMap。
• 枚举键：EnumMap。
• 对象地址比较：IdentityHashMap。
    通过理解各Map实现类的内部机制，可针对具体场景选择最合适的实现，优化性能和功能需求。