AI 助理
备案控制台
开发者社区 云计算 文章 正文

HashMap 源码及原理解析

2025-11-17 70
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： HashMap是Java核心数据结构，基于哈希表实现键值对存储。JDK 1.8采用数组+链表/红黑树结构，通过哈希计算定位元素，链表过长时转为红黑树以提升性能。支持null键值，非线程安全。核心机制包括哈希扰动、扩容重哈希（2倍扩容）、负载因子（默认0.75）及树化阈值（8），确保高效存取与动态平衡。

@TOC

1. HashMap 概述

HashMap 是 Java 集合框架中最重要的数据结构之一，基于哈希表实现，提供了键值对的存储和检索功能。

1.1 核心特性

  • 键值对存储：存储 Key-Value 对
  • 允许 null：key 和 value 都允许为 null
  • 非线程安全：多线程环境下需要外部同步
  • 无序性：不保证元素的顺序
  • 时间复杂度：理想情况下 O(1) 的查询效率

2. 数据结构演变

2.1 数组 + 链表

JDK 1.7 及之前：

// JDK 1.7 的节点结构
static class Entry<K,V> implements Map.Entry<K,V> {
   
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
}

2.2 数组 + 链表/红黑树

JDK 1.8 及之后：

// JDK 1.8 的节点结构
static class Node<K,V> implements Map.Entry<K,V> {
   
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

// 红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
   
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;
}

3. 核心源码解析

3.1 关键常量

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

    // 默认初始容量 - 必须是 2 的幂
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 链表转红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;

    // 红黑树转链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;

    // 最小树化容量
    static final int MIN_TREEIFY_CAPACITY = 64;

    // 存储元素的数组
    transient Node<K,V>[] table;

    // 元素个数
    transient int size;

    // 修改次数
    transient int modCount;

    // 扩容阈值 (capacity * loadFactor)
    int threshold;

    // 负载因子
    final float loadFactor;
}

3.2 哈希计算

static final int hash(Object key) {
   
    int h;
    // key 为 null 时哈希值为 0，否则计算哈希值
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 计算数组下标
final int indexFor(int hash, int length) {
   
    // 等价于 hash % length，但效率更高
    return hash & (length - 1);
}

3.3 put 方法实现

public V put(K key, V value) {
   
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
   
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 1. 如果 table 为空，进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 2. 计算索引位置，如果该位置为空，直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
   
        Node<K,V> e; K k;

        // 3. 如果第一个节点就是目标节点
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

        // 4. 如果是树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

        // 5. 链表遍历
        else {
   
            for (int binCount = 0; ; ++binCount) {
   
                if ((e = p.next) == null) {
   
                    p.next = newNode(hash, key, value, null);
                    // 链表长度达到阈值，转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        // 6. 存在相同的 key，更新 value
        if (e != null) {
   
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    ++modCount;
    // 7. 检查是否需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

3.4 扩容机制 (resize)

final Node<K,V>[] resize() {
   
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;

    // 计算新容量和新阈值
    if (oldCap > 0) {
   
        if (oldCap >= MAXIMUM_CAPACITY) {
   
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 双倍阈值
    }
    else if (oldThr > 0) // 初始容量设置为阈值
        newCap = oldThr;
    else {
                  // 零初始阈值表示使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    if (newThr == 0) {
   
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }

    threshold = newThr;

    // 创建新数组并重新哈希
    @SuppressWarnings({
   "rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

    if (oldTab != null) {
   
        for (int j = 0; j < oldCap; ++j) {
   
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
   
                oldTab[j] = null;
                if (e.next == null)  // 单个节点
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)  // 红黑树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
     // 链表
                    // 低位链表和高位链表
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;

                    do {
   
                        next = e.next;
                        // 判断节点在新数组中的位置
                        if ((e.hash & oldCap) == 0) {
   
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
   
                            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;
                    }
                }
            }
        }
    }
    return newTab;
}

3.5 get 方法实现

public V get(Object key) {
   
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
   
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
   

        // 检查第一个节点
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;

        if ((e = first.next) != null) {
   
            // 如果是树节点
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);

            // 遍历链表
            do {
   
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

4. 核心原理详解

4.1 哈希冲突解决

链地址法

// 当发生哈希冲突时，将新节点添加到链表末尾
if ((e = p.next) == null) {
   
    p.next = newNode(hash, key, value, null);
}

红黑树优化

当链表长度超过 TREEIFY_THRESHOLD(8) 且数组长度达到 MIN_TREEIFY_CAPACITY(64) 时，链表转换为红黑树：

final void treeifyBin(Node<K,V>[] tab, int hash) {
   
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // 先尝试扩容
    else if ((e = tab[index = (n - 1) & hash]) != null) {
   
        // 转换为红黑树
        TreeNode<K,V> hd = null, tl = null;
        do {
   
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
   
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

4.2 扩容机制原理

扩容时机

  • 元素数量超过阈值 (capacity × loadFactor)
  • 链表长度超过阈值但数组长度小于 MIN_TREEIFY_CAPACITY

高效重新哈希

JDK 1.8 优化：节点在新数组中的位置要么保持不变，要么是原位置 + 原容量

// 判断节点位置变化的巧妙方法
if ((e.hash & oldCap) == 0) {
   
    // 位置不变（低位链表）
} else {
   
    // 位置 = 原位置 + 原容量（高位链表）
}

4.3 负载因子作用

负载因子 = 元素数量 / 数组长度

  • 默认值 0.75：时间和空间的平衡点
  • 较小值：减少哈希冲突，但浪费空间
  • 较大值：节省空间，但增加哈希冲突

5. 性能分析

5.1 时间复杂度

操作 平均情况 最坏情况
插入 O(1) O(log n)
删除 O(1) O(log n)
查找 O(1) O(log n)

5.2 空间复杂度

  • O(n)：存储 n 个元素

6. 使用注意事项

6.1 正确实现 hashCode() 和 equals()

class KeyClass {
   
    private final String id;

    @Override
    public int hashCode() {
   
        return Objects.hash(id);
    }

    @Override
    public boolean equals(Object obj) {
   
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        KeyClass key = (KeyClass) obj;
        return Objects.equals(id, key.id);
    }
}

6.2 线程安全问题

// 解决方案 1：使用 ConcurrentHashMap
Map<String, String> concurrentMap = new ConcurrentHashMap<>();

// 解决方案 2：使用 Collections.synchronizedMap
Map<String, String> syncMap = Collections.synchronizedMap(new HashMap<>());

// 解决方案 3：使用同步块
synchronized (map) {
   
    // 操作 map
}

7. 总结

HashMap 的核心设计思想：

  1. 数组 + 链表/红黑树的复合结构平衡了空间和时间效率
  2. 动态扩容机制保证哈希表的负载均衡
  3. 红黑树优化解决了极端情况下的性能退化问题
  4. 位运算优化提升了计算效率

理解 HashMap 的源码和原理对于编写高性能的 Java 程序至关重要

文章标签：
Java
存储
安全
负载均衡
木易士心
目录
相关文章
木易士心
|
21天前
|
安全 算法 Java
Android APK签名机制的工作原理、结构差异、安全局限与优势
本文深入解析Android APK的v1与v2签名机制，涵盖工作原理、结构差异、安全局限及最佳实践。详述身份认证、完整性保护等核心目标，对比各版本优劣，并提供签名生成、验证流程与生产环境建议，助力开发者构建安全可信的应用。
木易士心
344 1
Calvad0s
|
21天前
|
架构师 IDE Java
【Java架构师】Maven中lombok那点事
SpringBoot项目中Lombok需在maven-compiler-plugin中配置`annotationProcessorPaths`，确保编译期生成getter/setter等方法；而`excludes`则在打包时排除Lombok依赖，减小体积，因运行时已无需该库。
Calvad0s
98 0
木易士心
|
20天前
|
前端开发 Java 测试技术
MVC、MVP 与 MVVM：Android 架构演进之路
本文深度剖析Android架构演进史：从MVC、MVP到MVVM，再到2025年主流的MVI与分层架构。结合Jetpack、Compose与Kotlin协程，揭示架构本质是对复杂性的管理，展现从“上帝类”到响应式、声明式开发的工程进化之路。
木易士心
131 0
木易士心
|
21天前
|
XML Android开发 数据格式
Android setContentView源码与原理分析
`setContentView` 是 Activity 显示界面的核心方法，其本质是将布局嵌入由 `PhoneWindow` 管理的 `DecorView` 中。系统首先创建包含状态栏、标题栏等的窗口模板（如 `screen_simple.xml`），再通过 `LayoutInflater` 将开发者指定的布局加载到 ID 为 `android.R.id.content` 的 `mContentParent` 容器内，最终在 `Activity` 恢复时由 `WindowManager` 将 `DecorView` 添加至窗口，触发测量与绘制流程，完成界面显示。
木易士心
178 73
木易士心
|
26天前
|
数据采集 缓存 数据可视化
Android 无侵入式数据采集：从手动埋点到字节码插桩的演进之路
本文深入探讨Android无侵入式埋点技术，通过AOP与字节码插桩（如ASM）实现数据采集自动化，彻底解耦业务代码与埋点逻辑。涵盖页面浏览、点击事件自动追踪及注解驱动的半自动化方案，提升数据质量与研发效率，助力团队迈向高效、稳定的智能化埋点体系。（238字）
木易士心
433 158
灵杰开发者
|
1月前
|
人工智能 并行计算 算法
为什么 OpenSearch 向量检索能提速 13 倍？
本文介绍在最新的 OpenSearch 实践中，引入 GPU 并行计算能力 与 NN-Descent 索引构建算法，成功将亿级数据规模下的向量索引构建速度提升至原来的 13 倍。
灵杰开发者
586 24
为什么 OpenSearch 向量检索能提速 13 倍？
木易士心
|
21天前
|
JavaScript 前端开发 安全
TypeScript 与 ArkTS 全面对比：鸿蒙生态下的语言演进
本文深入对比TypeScript与华为鸿蒙原生语言ArkTS，从类型系统、UI开发、性能优化到生态定位，全面解析二者差异。ArkTS基于TS演进，面向操作系统层级重构，具备强类型安全、声明式UI、AOT编译与分布式能力，助力“一次开发，多端部署”。结合10亿鸿蒙设备爆发趋势，为开发者提供技术选型指南与平滑迁移路径，是进军全场景智慧生态的关键钥匙。（238字）
木易士心
148 1
木易士心
|
19天前
|
Dart 开发工具 Android开发
Flutter PC 应用开发指南：从环境搭建到实战避坑
本文系统介绍如何在 Windows 平台使用 Flutter 开发 PC 应用，涵盖环境搭建、项目创建、插件兼容性、原生功能调用、签名发布、常见问题解决及性能优化等全流程，助你高效构建跨平台桌面应用，少走弯路。
木易士心
373 5
计算机程序设计Y2013070224
|
19天前
|
Java 关系型数据库 MySQL
基于springboot的电脑商城系统
本研究聚焦3C数码电商系统的技术升级，针对传统架构性能瓶颈与用户体验不足问题，基于SpringBoot微服务框架构建高并发、易扩展的新型电商平台，结合MySQL、B/S架构与Java技术，提升系统稳定性与智能化水平。
计算机程序设计Y2013070224
119 1