Map

Java Map 接口及主要实现类详解

Map 是 Java 集合框架中用于存储键值对（key-value）的接口，与 Collection 接口并列，是日常开发中最常用的数据结构之一。Map 中的键（key）具有唯一性，值（value）可重复，键与值一一对应。本文将详细解析 Map 接口的主要实现类，包括 Hashtable、HashMap、TreeMap、LinkedHashMap 和 ConcurrentHashMap，分析它们的底层结构、核心特性及适用场景。

Map 接口概述

Map 接口定义了键值对集合的基本操作，如添加（put）、删除（remove）、查询（get）、遍历等。其核心方法包括：

• V put(K key, V value)：添加键值对，若键已存在则覆盖值并返回旧值。
• V get(Object key)：根据键获取值，若键不存在则返回 null。
• boolean containsKey(Object key)：判断是否包含指定键。
• Set<K> keySet()：返回所有键的集合（无序，除非实现类保证有序）。
• Collection<V> values()：返回所有值的集合。
• Set<Map.Entry<K,V>> entrySet()：返回键值对实体的集合，用于遍历。

主要实现类解析

Hashtable（线程安全的早期实现）

Hashtable 是 JDK 1.0 引入的最早的 Map 实现类，基于哈希表（数组 + 链表）实现，是线程安全的，但性能较低。

核心特性

• 线程安全：所有方法均用 synchronized 修饰，保证多线程安全，但并发效率低。

• 不允许 null：键（key）和值（value）均不能为 null，否则抛出 NullPointerException。

• 继承关系：继承自Dictionary类（已过时），实现Map接口。

  public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Serializable

底层结构

• 用Entry数组存储键值对，Entry是单向链表节点，包含hash、key、value、next（下一个节点）。

private transient Entry<?,?>[] table;
private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;
    // ... 构造器和方法
}

关键方法实现

• put 方法：先校验 value 不为 null，再计算 key 的哈希值，通过取模定位数组索引，若发生哈希冲突则链接到链表尾部。

  public synchronized V put(K key, V value) {
      if (value == null) throw new NullPointerException(); // 禁止 null 值
      int hash = key.hashCode(); // 直接使用 key 的 hashCode（key 不能为 null）
      int index = (hash & 0x7FFFFFFF) % table.length; // 计算索引（确保非负）
      // ... 检查键是否存在，存在则覆盖，否则新增 Entry
  }

• 扩容机制：初始容量为 11，加载因子 0.75。当元素数量超过 容量 * 加载因子 时，扩容为 旧容量 * 2 + 1（不保证为 2 的幂）。

适用场景

• 需线程安全但并发量低的场景（已被 ConcurrentHashMap 替代）。
• 不推荐在新代码中使用，仅用于兼容旧系统。

HashMap（最常用的非线程安全实现）

HashMap 是 JDK 1.2 引入的 Map 实现类，基于哈希表（数组 + 链表 / 红黑树）实现，非线程安全，但性能优异，是日常开发的首选。

核心特性

• 非线程安全：无同步机制，多线程并发修改可能导致数据不一致。

• 允许 null：键和值均可为 null（键最多一个 null，值可多个 null）。

• 无序性：存储顺序与插入顺序无关（由哈希值决定）。

• 继承关系：继承自AbstractMap，实现Map接口。

  public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

底层结构（JDK 8）

• 用Node数组（table）存储键值对，哈希冲突时先以链表存储，当链表长度超过阈值（默认 8）且数组容量 ≥ 64 时，链表转为红黑树（提高查询效率）。

  transient Node<K,V>[] table; // 哈希表数组
  static class Node<K,V> implements Map.Entry<K,V> {
      final int hash;
      final K key;
      V value;
      Node<K,V> next; // 链表节点的后继引用
      // ... 构造器和方法
  }

• 红黑树节点 TreeNode 继承自 Node，增加了树结构的引用（parent、left、right 等）。

关键方法实现

• 哈希值计算：对 key 的哈希值进行二次哈希（高位异或低位），减少哈希冲突。

  static final int hash(Object key) {
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //  null 键的哈希值为 0
  }

• put 方法：

  1. 若哈希表为空，先初始化（resize）。
  2. 根据哈希值计算索引，若索引位置为空，直接插入新节点。
  3. 若发生哈希冲突：
     • 若键相同，覆盖值。
     • 若为红黑树节点，插入树中。
     • 若为链表节点，遍历链表，若键存在则覆盖，否则新增节点；若链表长度达阈值，转为红黑树。
  4. 若元素数量超过阈值，触发扩容。

• 扩容机制：初始容量为 16（必须为 2 的幂），加载因子 0.75。扩容时容量翻倍（保证仍为 2 的幂），重新计算所有元素的索引并迁移。

适用场景

• 单线程环境或无需考虑线程安全的场景。
• 需高效增删改查（平均时间复杂度 O(1)）的场景。

TreeMap（有序的红黑树实现）

TreeMap 基于红黑树（一种自平衡二叉搜索树）实现，具有天然有序性，键的顺序由比较器决定。

核心特性

• 有序性：默认按键的自然顺序（Comparable）排序，或按构造器传入的 Comparator 排序。

• 非线程安全：无同步机制。

• 不允许 null 键：键必须实现 Comparable 或提供 Comparator，否则插入时抛出 ClassCastException；值可以为 null。

• 继承关系：继承自AbstractMap，实现NavigableMap接口（扩展了SortedMap，支持导航方法如ceilingKey、floorKey）。

  public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable

底层结构

• 红黑树的每个节点为 Entry，包含 key、value、左子树（left）、右子树（right）、父节点（parent）及颜色（color）。

• 键的比较逻辑：

  final int compare(Object k1, Object k2) {
      return comparator == null ? 
          ((Comparable<? super K>)k1).compareTo((K)k2) : // 自然排序
          comparator.compare((K)k1, (K)k2); // 自定义排序
  }

关键特性

• 查询效率：红黑树保证增删改查的时间复杂度为 O(log n)。
• 有序遍历：entrySet() 迭代器按键的顺序遍历，无需额外排序。

适用场景

• 需要按键排序的场景（如排行榜、范围查询）。
• 需使用导航方法（如获取小于等于某键的最大键）的场景。

LinkedHashMap（维护插入 / 访问顺序的 HashMap）

LinkedHashMap 是 HashMap 的子类，通过双向链表维护键值对的顺序，可保留插入顺序或访问顺序，兼具 HashMap 的高效性和有序性。

核心特性

• 有序性：默认按插入顺序遍历，若构造时指定 accessOrder = true，则按访问顺序（最近访问的元素在尾部）遍历。

• 继承关系：继承自HashMap，实现Map接口。

  public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

底层结构

• 在 HashMap 的Node基础上扩展为Entry，增加双向链表的引用（before前驱、after后继）：

  static class Entry<K,V> extends HashMap.Node<K,V> {
      Entry<K,V> before, after; // 双向链表的前驱和后继
      Entry(int hash, K key, V value, Node<K,V> next) {
          super(hash, key, value, next);
      }
  }

• 用 head（头节点）和 tail（尾节点）维护双向链表的顺序。

关键特性：LRU 缓存实现

LRU（Least Recently Used，最近最少使用）缓存策略会淘汰最久未使用的元素。LinkedHashMap 可通过重写 removeEldestEntry 方法实现 LRU 缓存：

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int MAX_SIZE;

    public LRUCache(int maxSize) {
        // 初始容量、加载因子、accessOrder = true（按访问顺序）
        super((int) Math.ceil(maxSize / 0.75) + 1, 0.75f, true);
        MAX_SIZE = maxSize;
    }

    // 当元素数量超过 MAX_SIZE 时，删除最久未使用的元素（头节点）
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > MAX_SIZE;
    }
}

适用场景

• 需要保留插入顺序的场景（如日志记录）。
• 实现 LRU 缓存（如热点数据缓存）。

ConcurrentHashMap（线程安全的高效实现）

ConcurrentHashMap 是 JUC（java.util.concurrent）包中的线程安全 Map 实现，专为高并发场景设计，性能优于 Hashtable。

核心特性（JDK 8）

• 线程安全：放弃 JDK 7 的 Segment 分段锁，采用 CAS + synchronized 实现细粒度同步（仅锁定哈希冲突的链表 / 红黑树头节点）。

• 高效并发：支持多线程同时读写，不同桶的操作互不阻塞。

• 不允许 null：键和值均不能为 null（避免与 get 方法返回 null 混淆）。

• 继承关系：实现ConcurrentMap接口（扩展Map，增加原子操作如putIfAbsent）。

  public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>, Serializable

底层结构与并发机制

• 底层结构与 HashMap 类似（数组 + 链表 / 红黑树），但节点为 Node（不可变，保证线程安全）。
• put 方法：
  1. 计算哈希值，定位桶位置。
  2. 若桶为空，用 CAS 原子操作插入新节点。
  3. 若桶正在扩容（hash == MOVED），协助扩容。
  4. 若桶非空，对桶的头节点加 synchronized 锁，执行插入 / 覆盖操作。

适用场景

• 高并发场景（如服务器缓存、多线程数据共享）。
• 需要线程安全且高性能的场景（替代 Hashtable）。

核心实现类对比

特性	HashMap	Hashtable	TreeMap	LinkedHashMap	ConcurrentHashMap
底层结构	数组 + 链表 / 红黑树	数组 + 链表	红黑树	数组 + 链表 / 红黑树 + 双向链表	数组 + 链表 / 红黑树
线程安全	否	是（synchronized）	否	否	是（CAS+synchronized）
有序性	无序	无序	按键排序	插入 / 访问顺序	无序
null 键值	允许（key 最多 1 个）	不允许	key 不允许	允许	不允许
平均时间复杂度	O(1)	O(1)	O(log n)	O(1)	O(1)
初始容量 / 扩容	16，翻倍	11，2n+1	无固定容量	同 HashMap	16，翻倍
适用场景	单线程高效存取	旧系统兼容	有序场景	顺序保留、LRU 缓存	高并发场景