Java Map 原理、实现与使用场景分析

java map 详解：原理、实现与使用场景

一、介绍

map 是 java 集合框架（java.util）中键值对（key-value） 形式的集合接口，与 list/set 并列（继承自 collection 的父接口 iterable，但不直接继承 collection）。核心特征是：键（key）唯一且无序（部分实现有序），值（value）可重复，通过键快速查找值，是日常开发中存储关联数据的核心工具。

特性：

1. 键值对映射：每个 key 对应唯一的 value，key 不允许重复（若重复插入，新 value 会覆盖旧 value）；
2. key 不可变性：作为 key 的对象需重写 hashcode() 和 equals() 方法（保证哈希一致性），且建议使用不可变类型（如 string、integer），避免修改后哈希值变化导致无法查找；
3. 支持 null：不同实现类对 null 的支持不同（如 hashmap 允许 1 个 null key + 多个 null value，hashtable 不允许 null）；
4. 无序性（默认）：大部分 map 实现（如 hashmap）不保证键值对的存储 / 遍历顺序，有序实现需显式指定（如 treemap、linkedhashmap）。

二、map 接口核心方法

map 定义了键值对操作的核心方法，覆盖增删改查、遍历等场景：

三、map 主要实现类

java 提供了多款 map 实现类，适配不同的性能、有序性、并发场景，核心如下：

1. hashmap（最常用）

底层实现：jdk 8 前 = 数组（哈希桶）+ 链表；jdk 8 后 = 数组 + 链表 / 红黑树（链表长度 ≥8 转红黑树，≤6 转回链表）。

补充：

hashmap 的底层由「哈希桶数组」+「链表 / 红黑树」组成，核心设计目标是：通过哈希算法将 key 映射到数组下标，实现 o (1) 级别的快速存取；通过链表 / 红黑树解决「哈希冲突」（不同 key 哈希值相同的情况）。

• 哈希桶数组（table）：默认初始长度 16（2 的幂），每个下标对应一个「桶」，桶内存储链表或红黑树；
• 链表：当多个 key 哈希到同一桶时，先以链表形式存储；
• 红黑树：当链表长度 ≥8 且数组长度 ≥64 时，链表转为红黑树（查询性能从 o (n) 优化为 o (log n)）；当红黑树节点数 ≤6 时，转回链表（减少红黑树维护开销）。

红黑树：

红黑树是带红 / 黑颜色标记的自平衡二叉查找树，也是二叉树的一种，不过有5条规则对树的高度进行限制，增删改查的时间复杂度稳定在o(logn)

补充一下那5条规则：

（1）每个节点只能为黑色或者红色

（2）根节点必须为黑色

（3）所有“空叶子节点”都是黑色

（4）红色节点的父节点和子节点都必须为黑色（你也可以这样理解，不能连续俩红色节点）

（5）从任意节点到它自己所有叶子节点（在红黑树中这个叶子节点就是指的空叶子节点）的路径中，黑色节点的数量完全相同

规则是为了做什么？

保证树的结构不会退化成链表，同时保证增删查改始终是 o (log n)

（补：最长路径的长度 ≤ 2 × 最短路径的长度，两者的差值最大为 最短路径的长度）

什么是桶？

桶就是 hashmap 哈希桶数组里的一个存储单元，负责接收通过哈希计算分配过来的键值对节点，解决哈希冲突的链表 / 红黑树也都是在桶内部形成的。

简单举个例子：

把 hashmap 想象成一个 带编号的快递柜，这个快递柜的每个独立格子就是一个 桶。

1. 快递柜 = 哈希桶数组（table）快递柜有很多个格子，每个格子都有自己的编号（比如 0、1、2…15），对应 hashmap 数组的索引。
2. 桶 = 快递柜的单个格子每个格子（桶）的作用是存放 “属于自己” 的快递。在 hashmap 中，通过哈希计算，会把键值对节点分配到对应编号的桶里。
3. 哈希冲突 = 一个格子里放多个快递
   • 理想情况：一个快递（节点）对应一个格子（桶），取件时直接按编号找，速度飞快（对应 hashmap 的 o (1) 存取）。
   • 现实情况：可能出现多个快递被分配到同一个格子（不同 key 计算出相同的数组索引），这就是哈希冲突。这时，hashmap 会在这个桶里用链表把这些节点串起来；如果链表太长（≥8），就会变成红黑树，提升查询效率。

核心特点：

• 存取效率高（平均 o (1) 时间复杂度），基于哈希表快速定位；
• 无序（存储顺序 ≠ 插入顺序）；
• 允许 1 个 null key、多个 null value；
• 非线程安全（多线程操作可能导致死循环、数据丢失）；
• 初始容量 16，负载因子 0.75（扩容阈值 = 容量 × 负载因子，默认 12），扩容时容量翻倍，且重新哈希。

机制详解：

哈希计算与索引定位：

hashmap 高效存取的核心是「将 key 映射到数组下标」，分为两步：

1.key 的哈希值计算

为了减少哈希冲突，hashmap 对 key 的 hashcode() 做了二次哈希（扰动函数）：

static final int hash(object key) {
    int h;
    // 核心逻辑：key.hashcode() ^ (h >>> 16)
    return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
}

• 作用：将 key 的哈希值高 16 位与低 16 位异或，混合高低位特征，减少哈希冲突（尤其数组长度较小时，仅低几位参与取模，混合后能利用高位信息）；
• null key 处理：hash 值固定为 0，因此 null key 始终映射到数组索引 0。

2.数组索引计算

通过哈希值计算数组下标，利用「位运算替代取模」提升性能（仅当数组长度为 2 的幂时生效）：

// i = 哈希值 & (数组长度 - 1)
int index = hash & (table.length - 1);

• 示例：数组长度 16（二进制 10000），table.length - 1 = 15（二进制 01111）；哈希值与 15 按位与，等价于 hash % 16，但位运算更快。
• 为什么数组长度是 2 的幂？
• → 保证hash & (length-1)等价于取模，且位运算效率远高于取模；
• → 扩容时，节点新索引要么不变，要么 = 原索引 + 原数组长度（简化扩容迁移逻辑）。

扩容机制：

条件：

• 首次 put 时，table 为 null，初始化数组（默认长度 16，threshold=16×0.75=12）；
• 后续 put 时，若 size > threshold，触发扩容；
• 链表长度≥8 但数组长度 < 64 时，优先扩容（而非树化）。

步骤：

// 1. 计算新容量：原容量翻倍（始终保持2的幂）
int newcap = oldcap << 1; // 如16→32，32→64...
// 2. 计算新扩容阈值：newthr = newcap × loadfactor
int newthr = oldthr << 1;
// 3. 创建新数组（长度newcap）
node<k,v>[] newtab = (node<k,v>[]) new node[newcap];
table = newtab;
// 4. 迁移原数组节点到新数组
for (int j = 0; j < oldcap; ++j) {
    node<k,v> e;
    if ((e = table[j]) != null) {
        table[j] = null; // 释放原数组引用（帮助gc）
        // 情况1：桶内仅一个节点，直接计算新索引并放入
        if (e.next == null)
            newtab[e.hash & (newcap - 1)] = e;
        // 情况2：桶内是红黑树，拆分红黑树并迁移
        else if (e instanceof treenode)
            ((treenode<k,v>)e).split(this, newtab, j, oldcap);
        // 情况3：桶内是链表，拆分链表（优化：无需重新哈希，仅判断高位）
        else {
            // 链表拆分规则：新索引 = 原索引 或 原索引 + oldcap
            node<k,v> lohead = null, lotail = null; // 原索引节点
            node<k,v> hihead = null, hitail = null; // 原索引+oldcap节点
            node<k,v> next;
            do {
                next = e.next;
                // 核心判断：哈希值的第n位（oldcap的二进制位）是否为0
                if ((e.hash & oldcap) == 0) {
                    // 第n位为0 → 新索引=原索引
                    if (lotail == null) lohead = e;
                    else lotail.next = e;
                    lotail = e;
                } else {
                    // 第n位为1 → 新索引=原索引+oldcap
                    if (hitail == null) hihead = e;
                    else hitail.next = e;
                    hitail = e;
                }
            } while ((e = next) != null);
            // 放入新数组
            if (lotail != null) {
                lotail.next = null;
                newtab[j] = lohead;
            }
            if (hitail != null) {
                hitail.next = null;
                newtab[j + oldcap] = hihead;
            }
        }
    }
}

使用示例：

map<string, integer> hashmap = new hashmap<>();
hashmap.put("java", 1);
hashmap.put("python", 2);
integer value = hashmap.get("java"); // 获取值：1
hashmap.put("java", 3); // 替换值，旧值 1 被覆盖

各操作逻辑：

1.存

先定位桶 → 无冲突则新增节点 → 有冲突则按链表 / 红黑树处理 → 替换重复 key 的 value → 检查扩容。

2.取

定位桶 → 桶头匹配直接返回 → 红黑树 / 链表遍历匹配 → 未找到返回 null。

3.删

定位待删除节点 → 按链表 / 红黑树规则删除 → 更新 size 和 modcount。

2. linkedhashmap

底层实现：hashmap + 双向链表（维护插入 / 访问顺序）。

补充：

linkedhashmap 完全复用 hashmap 的哈希桶数组、节点哈希 / 扩容 / 树化等逻辑，仅通过「双向链表」改造节点结构、新增头尾指针，实现有序性。

• 哈希桶层：和 hashmap 完全一致，负责通过哈希快速定位节点，解决哈希冲突（链表 / 红黑树）；
• 双向链表层：所有节点通过 before/after 指针串联，head 指向最早节点，tail 指向最新节点，专门维护遍历顺序；
• 节点复用：linkedhashmap 的 entry 继承 hashmap.node，因此哈希桶里的节点同时属于「哈希链表 / 红黑树」和「双向链表」，一个节点两个 “身份”。

什么是节点？

在 linkedhashmap（以及 hashmap）中，节点（node/entry） 是存储「键值对（key-value）」的最小单元 —— 就像快递包裹本身，而桶是放包裹的格子、双向链表是串包裹的绳子。

举个具体的例子：

比如你往 linkedhashmap 里存 put("手机", 1999)、put("耳机", 299)、put("充电器", 99)：

• 每个键值对对应一个「节点」：
  • 节点 1：key = 手机，value=1999；
  • 节点 2：key = 耳机，value=299；
  • 节点 3：key = 充电器，value=99。
• 这些节点会按哈希规则被分配到不同的桶（比如手机→3 号格、耳机→5 号格、充电器→3 号格）：
• 3 号桶里有两个节点（手机 + 充电器），用链表串起来；5 号桶只有耳机节点。
• 同时，这三个节点会被双向链表串成 head→手机→耳机→充电器→tail（插入顺序）；如果调用 get("手机")，节点 1 会被挪到尾部，链表变成 head→耳机→充电器→手机→tail（访问顺序）。

核心特点：

• 继承 hashmap 的所有特性，额外保证「有序性」；
• 有序模式：
  • 插入顺序（默认）：遍历顺序 = 插入顺序；
  • 访问顺序：调用 get()/put() 后，该键值对移至链表尾部（可实现 lru 缓存）；
• 非线程安全，性能略低于 hashmap（维护链表开销）。

使用示例（lru 缓存）：

// 初始容量16，负载因子0.75，访问顺序模式
map<string, integer> lrumap = new linkedhashmap<>(16, 0.75f, true);
lrumap.put("a", 1);
lrumap.put("b", 2);
lrumap.get("a"); // 访问后，"a" 移至尾部
// 遍历顺序：b → a（访问顺序）
for (map.entry<string, integer> entry : lrumap.entryset()) {
    system.out.println(entry.getkey());
}

3. treemap

底层实现：红黑树（自平衡的二叉查找树）。

核心特点：

• 有序：默认按 key 的自然顺序（如 integer 升序、string 字典序），或自定义 comparator 排序；
• 无 null key（会抛 nullpointerexception），允许 null value；
• 存取效率 o (log n)（红黑树查找 / 插入），低于 hashmap；
• 非线程安全；
• 适合需要排序的场景（如按 key 范围查询）。

使用示例（自定义排序）：

// 按 key 降序排序
map<integer, string> treemap = new treemap<>((k1, k2) -> k2 - k1);
treemap.put(3, "c");
treemap.put(1, "a");
treemap.put(2, "b");
// 遍历顺序：3 → 2 → 1
for (integer key : treemap.keyset()) {
    system.out.println(key);
}

4. hashtable（古老的线程安全实现）

底层实现：数组 + 链表（jdk 8 未优化红黑树）。

补充：

hashtable 无红黑树优化（全程仅数组 + 链表），线程安全通过「方法级 synchronized」实现，是典型的 “简单粗暴” 的线程安全哈希表设计。

• 哈希桶数组：默认初始长度 11（非 2 的幂，区别于 hashmap），每个下标对应一个桶，桶内存储链表；
• 链表：所有哈希冲突的节点（key 哈希到同一桶）通过 next 指针串联，无红黑树优化，链表过长时查询性能退化至 o (n)；
• 线程安全：所有核心方法（put/get/remove）都加 synchronized 锁，锁粒度为整个 hashtable 对象。

核心特点：

• 线程安全（方法级 synchronized 锁），但锁粒度大，性能差；
• 不允许 null key/value（抛 nullpointerexception）；
• 初始容量 11，负载因子 0.75，扩容时容量 = 原容量 ×2 +1；
• 基本被 concurrenthashmap 替代，仅兼容旧代码时使用。

机制详解：

哈希计算与扩容：

key 的哈希计算（无扰动优化）

hashtable 的哈希计算逻辑简单，无 hashmap 的 “高低位异或” 扰动优化，且直接使用 key.hashcode()（不允许 null key）：

// 计算key的哈希值（简化版）
int hash = key.hashcode();
// 计算数组索引（取模，而非位运算）
int index = (hash & 0x7fffffff) % table.length;

扩容机制（区别于hashmap）：

hashtable 扩容触发后，新容量 = 原容量 × 2 + 1（而非 hashmap 的翻倍）

// 1. 计算新容量：原容量 ×2 +1（如 11→23，23→47...）
int newcapacity = table.length * 2 + 1;
// 2. 计算新扩容阈值：newthr = (int)(newcapacity × loadfactor)
int newthreshold = (int)(newcapacity * loadfactor);
// 3. 创建新数组（长度newcapacity）
entry<?,?>[] newtable = new entry<?,?>[newcapacity];
// 4. 迁移原数组节点到新数组（重新计算索引，拷贝链表）
for (int i = 0; i < table.length; i++) {
    entry<k,v> e = (entry<k,v>)table[i];
    if (e != null) {
        table[i] = null; // 释放原数组引用
        do {
            entry<k,v> next = e.next;
            // 重新计算新索引（取模）
            int index = (e.hash & 0x7fffffff) % newcapacity;
            e.next = (entry<k,v>)newtable[index];
            newtable[index] = e;
            e = next;
        } while (e != null);
    }
}
// 5. 替换数组和阈值
table = newtable;
threshold = newthreshold;

差异总结：

容量增长规则：2n+1（保证素数，理论减少哈希冲突，但无实际性能优势），hashmap 是 2n（2 的幂，位运算优化）；

索引重计算：每次扩容都需对所有节点重新取模，无 hashmap 的 “高位判断” 优化，扩容开销更大；

• 触发条件：count ≥ threshold（hashmap 是 size > threshold），更早触发扩容。

5. concurrenthashmap（并发安全）

底层实现：jdk 8 前 = 分段锁（segment 数组 + hashmap）；jdk 8 后 = 数组 + 链表 / 红黑树 + cas + synchronized（锁哈希桶，粒度更细）。

补充：

• 哈希桶层：与 hashmap 一致（数组长度为 2 的幂，链表≥8 转红黑树），但数组 / 节点关键字段（table/val/next）用 volatile 保证多线程可见性；
• 并发控制层：
  • 无竞争时：用 cas 操作新增节点（无锁）；
  • 有竞争时：对「单个哈希桶」加 synchronized 锁（仅锁住冲突的桶，其他桶可并行操作）；
  • 扩容时：用 forwardingnode 标记桶状态，多线程协同扩容（避免单线程扩容瓶颈）；
• 节点特性：node 节点的 val/next 为 volatile，保证修改后其他线程能立即感知。

核心特点：

• 线程安全（高并发）：jdk 8 后锁粒度为「单个哈希桶」，并发性能远高于 hashtable；
• 支持 1 个 null key（jdk 8 后）、多个 null value；
• 存取效率接近 hashmap（并发场景下）；
• 迭代器是 “弱一致性”，不会抛 concurrentmodificationexception；
• 适合高并发读写的场景（如分布式缓存、业务核心数据存储）。

扩容机制（多线程协同）

当 size > 容量 × 负载因子（默认初始容量 16，负载因子 0.75，阈值 12），且当前数组（table）无其他扩容操作时触发。

concurrenthashmap 扩容由「触发线程 + 其他访问线程」协同完成，避免单线程扩容瓶颈：

1. 触发条件：size > sizectl（同 hashmap）；
2. 扩容流程：
   • 创建 nexttable（容量翻倍）；
   • 遍历 table 桶，将桶节点迁移到 nexttable；
   • 迁移时，将原桶头节点替换为 forwardingnode（标记扩容中）；
   • 其他线程访问该桶时，检测到 forwardingnode，会暂停当前操作，协助扩容；
3. 核心优势：多线程并行迁移不同桶，大幅提升扩容效率。

使用示例：

map<string, string> concurrentmap = new concurrenthashmap<>();
// 多线程安全写入
new thread(() -> concurrentmap.put("thread1", "data1")).start();
new thread(() -> concurrentmap.put("thread2", "data2")).start();
// 安全读取
system.out.println(concurrentmap.get("thread1"));

6. properties（配置文件专用）

底层实现：继承 hashtable，key/value 均为 string 类型。

补充：

properties 完全复用 hashtable 的哈希表核心逻辑（数组 + 链表、方法级 synchronized 锁、禁止 null 值），仅在其基础上增加「key/value 强制为 string 类型」和「配置文件读写」的扩展方法。

核心存储层：完全复用 hashtable 的 table 数组（初始容量 11，扩容规则 2n+1）、entry 链表节点，线程安全通过方法级 synchronized 实现；

扩展层：

• 类型约束：key/value 实际使用时强制为 string（虽底层仍存储 object，但 setproperty()/getproperty() 限定为 string）；
• 配置继承：通过 defaults 实现配置复用（当前配置无 key 时，从默认配置集查找）；
• io 能力：load()/store() 方法解析 / 生成 .properties 格式的配置文件（键值对以 key=value 换行存储）。

核心特点：

• 专为读取配置文件（.properties）设计，支持 load()/store() 方法读写文件；
• 线程安全（继承 hashtable 的 synchronized 方法）；
• 常用场景：读取系统配置、项目配置文件。

操作原理：

配置文件加载（load ()）

load() 是 properties 最核心的扩展方法，用于从 .properties 文件 / 输入流解析键值对：

// 示例：加载配置文件
properties props = new properties();
props.load(new fileinputstream("config.properties"));

解析：

1. 按行读取输入流，忽略注释行（以 #/! 开头）和空行；
2. 解析每行的 key=value 格式（支持 :/ 空格 作为分隔符），去除首尾空格；
3. 调用 put(key, value)（继承 hashtable）将键值对存入哈希表；
4. 全程加 synchronized 锁，保证线程安全。

配置获取（getproperty ()）

getproperty() 是 string 专属的获取方法，支持默认配置集查找：

string url = props.getproperty("db.url");
// 带默认值：若key不存在，返回默认值"jdbc:mysql://localhost"
string url = props.getproperty("db.url", "jdbc:mysql://localhost");

查找逻辑：

1. 调用 hashtable 的 get(key) 获取值，强转为 string；
2. 若值为 null 且 defaults 不为 null，递归从 defaults 中查找；
3. 若仍为 null，返回指定的默认值（或 null）。

配置存储（store ()）

store() 用于将配置写入文件 / 输出流，生成标准 .properties 文件：

props.store(new fileoutputstream("config.properties"), "db config");

写入逻辑：

1. 先写入注释（可选）和当前时间戳；
2. 遍历哈希表的 entry 链表，按 key=value 格式逐行写入；
3. 全程加 synchronized 锁，保证写入过程不被打断。

基础操作（put/remove）

properties 未重写 hashtable 的 put()/remove() 方法，完全复用其逻辑：

• setproperty(key, value) 本质是调用 put(key, value)，仅限定参数为 string；
• 所有操作均加 synchronized 锁，线程安全但并发性能差（同 hashtable）。

使用示例：

properties props = new properties();
// 读取配置文件
props.load(new fileinputstream("config.properties"));
string url = props.getproperty("db.url"); // 获取配置值

四、map 常见使用场景

五、map 遍历方式（性能对比）

map 遍历的核心是操作 entryset()/keyset()/values()，推荐优先级：

entryset 遍历（最优）：直接获取键值对，无需二次查询，性能最高；

for (map.entry<string, integer> entry : map.entryset()) {
    string key = entry.getkey();
    integer value = entry.getvalue();
}

迭代器遍历（支持删除）：适合遍历中删除元素，避免 concurrentmodificationexception；

iterator<map.entry<string, integer>> it = map.entryset().iterator();
while (it.hasnext()) {
    map.entry<string, integer> entry = it.next();
    if (entry.getvalue() == 2) {
        it.remove(); // 安全删除
    }
}

keyset + get () 遍历（低效）：需二次哈希查询，性能最差，不推荐；

for (string key : map.keyset()) {
    integer value = map.get(key); // 额外哈希查询
}

lambda 遍历（简洁）：jdk 8+ 支持，代码简洁，性能接近 entryset；

map.foreach((key, value) -> system.out.println(key + ":" + value));

六、注意事项

1. key 的哈希与相等性：
   • 自定义对象作为 key 时，必须重写 hashcode() 和 equals()（保证相同对象哈希值相同，不同对象哈希值尽量不同）；
   • 避免使用可变对象作为 key（如 arraylist），修改后哈希值变化会导致无法查找。
2. hashmap 扩容优化：
   • 已知元素数量时，提前指定初始容量（如 new hashmap<>(100)），避免频繁扩容（扩容需重新哈希，开销大）；
   • 负载因子默认 0.75 是性能与内存的平衡，无需轻易修改。
3. 并发安全：
   • hashmap/linkedhashmap/treemap 非线程安全，多线程修改需手动加锁（如 collections.synchronizedmap()），或直接使用 concurrenthashmap；
   • concurrenthashmap 不支持 null key（jdk 7）/ 支持 1 个 null key（jdk 8+），需注意空值处理。
4. treemap 排序：
   • 自定义对象作为 key 时，需实现 comparable 接口，或创建 treemap 时指定 comparator，否则抛 classcastexception。

七、总结

map 是 java 中存储键值对的核心集合，核心实现类各有侧重：

• hashmap：性能均衡，适合绝大多数无排序、非并发场景；
• linkedhashmap：有序 + hashmap 特性，适合缓存场景；
• treemap：排序 + 范围查询，适合有序键值对场景；
• concurrenthashmap：高并发安全，适合核心业务的并发存储；
• properties：配置文件专用，简单易用。

七、总结

map 是 java 中存储键值对的核心集合，核心实现类各有侧重：

• hashmap：性能均衡，适合绝大多数无排序、非并发场景；
• linkedhashmap：有序 + hashmap 特性，适合缓存场景；
• treemap：排序 + 范围查询，适合有序键值对场景；
• concurrenthashmap：高并发安全，适合核心业务的并发存储；
• properties：配置文件专用，简单易用。

选择时需根据「有序性、并发要求、性能、业务场景」四大维度权衡，同时注意 key 的不可变性和遍历方式的性能优化。

附表：

到此这篇关于java map 原理、实现与使用场景分析的文章就介绍到这了,更多相关java map 使用内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！