当前位置:

首页 > 编程开发 > HashMap底层实现原理详解

HashMap底层实现原理详解

答案:HashMap底层基于数组+链表/红黑树,通过扰动函数减少哈希冲突,JDK8优化链表转红黑树,扩容时重新分配元素并优化索引计算,合理设置初始容量可提升性能。

本文目录

    答案:HashMap底层基于数组+链表/红黑树,通过扰动函数减少哈希冲突,JDK 8优化链表转红黑树,扩容时重新分配元素并优化索引计算,合理设置初始容量可提升性能。

    java后端开发中HashMap的底层实现原理是什么?

    HashMap 在 Java 后端开发中是最常用的集合类之一,理解其底层实现原理对性能调优和避免并发问题非常重要。

    数据结构:数组 + 链表/红黑树

    HashMap 的底层是基于哈希表实现的,使用一个Node 数组(即桶数组)来存储数据。每个数组元素是一个链表或红黑树的头节点。

    每一个键值对(key-value)都会通过 key 的 hashCode 计算出一个哈希值,再经过扰动处理和取模运算,确定该键值对应该存放到数组的哪个位置(也就是哪个“桶”里)。

    • 当多个 key 的哈希值落到同一个桶中时,就会发生哈希冲突。
    • 早期 JDK 使用链表解决冲突,JDK 8 开始引入优化:当链表长度超过 8 且数组长度大于等于 64 时,链表会转换为红黑树,以提升查找效率。
    • 当红黑树节点数小于 6 时,又会退化回链表。

    哈希计算与扰动函数

    为了减少哈希碰撞,HashMap 对 key 的 hashCode 进行了扰动处理。

    JDK 8 中的扰动函数是将高 16 位与低 16 位异或:

    hash = (key.hashCode()) ^ (key.hashCode() >>> 16)

    这样做可以让哈希值的高位也参与寻址运算,提高分散性,降低碰撞概率。

    扩容机制:resize()

    当元素数量超过阈值(threshold = capacity * loadFactor),HashMap 会进行扩容,默认加载因子是 0.75,初始容量是 16。

    • 扩容时容量变为原来的 2 倍。
    • 所有元素需要重新计算索引位置,放入新数组中。
    • JDK 8 利用扩容时容量为 2 的幂次的特性,通过位运算优化重哈希过程:元素要么留在原位置,要么移动到原索引 + 旧容量的位置。

    put 方法执行流程

    调用 put(key, value) 时的主要步骤如下:

    1. 计算 key 的 hash 值。
    2. 检查数组是否为空,为空则初始化。
    3. 根据 hash 找到对应的桶位置。
    4. 如果桶为空,直接插入新节点。
    5. 如果不为空,判断是否是相同 key,是则替换值。
    6. 否则遍历链表或红黑树插入新节点,并检查是否需要树化。
    7. 插入后判断是否需要扩容。

    基本上就这些。掌握 HashMap 的实现,能帮助你在实际开发中合理设置初始容量、避免频繁扩容、注意线程安全问题(比如用 ConcurrentHashMap 替代)。不复杂但容易忽略细节。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发
    相关文章 更多
    Nod 0.8.1怎样理解状态码、Ray ID与计划检查
    Nod 0.8.1怎样理解状态码、Ray ID与计划检查

    Nod 0.8.1补充连接服务状态与原因、Attio Cloudflare 403诊断,并让Gmail在连接服务429或503后延后计划轮询。

    Ducter 0.0.59如何理解同会话聊天、Git可选和附件变化
    Ducter 0.0.59如何理解同会话聊天、Git可选和附件变化

    Ducter 0.0.59扩展Telegram、Slack和Mac iMessage会话,区分项目目录来源、Git可选、等待状态与附件入口。

    llama.cpp b12435、b12436、b12438测试构建的三类兼容变化有什么区别?
    llama.cpp b12435、b12436、b12438测试构建的三类兼容变化有什么区别?

    llama.cpp b12435、b12436、b12438预发布构建,分别解释Vulkan并列选择确定性、32位编译与Jinja JSON键排序的适用范围。

    ScopeWeaver 0.9.2、0.9.3与0.9.4如何区分运行时、Zod和任务状态变化
    ScopeWeaver 0.9.2、0.9.3与0.9.4如何区分运行时、Zod和任务状态变化

    ScopeWeaver 0.9.2、0.9.3与0.9.4分别调整桥运行时、Zod依赖和同进程服务器重建后的暂停状态;区分版本对象与作者本地研究用途声明。

    AG2 1.3.2的输入Token为何变多,旧ACP版本还能用吗
    AG2 1.3.2的输入Token为何变多,旧ACP版本还能用吗

    AG2 1.3.2统一缓存Token统计并更新ACP1.x依赖;解释预算提前触达、报表口径与Python3.15构建限制。

    llama.cpp b12433怎样为AMD奇数列保留MUL_MAT_ID回退路径
    llama.cpp b12433怎样为AMD奇数列保留MUL_MAT_ID回退路径

    llama.cpp b12433避免AMD设备将奇数src0列送入需要偶数列的MMVF路径:满足偶数条件才保留MMVF,其他形状沿用既有回退。对应改动发生在MUL_MAT_ID处理和相关同步判断中,范围限定于代码说明中的类型与token条件。

    Ducter 0.0.58如何区分下一步消息、完成后消息与后台会话
    Ducter 0.0.58如何区分下一步消息、完成后消息与后台会话

    Ducter 0.0.58调整任务阅读、执行中消息和后台会话,区分下一步发送与做完再说,并说明tailnet HTTPS辅助的条件。

    Unlimited OCR 2在TextMind能否直接使用,账号权限与模型示例如何区分
    Unlimited OCR 2在TextMind能否直接使用,账号权限与模型示例如何区分

    Unlimited OCR 2官方确认百度智能云TextMind渠道;区分云端入口、账号权限配额与本地模型部署,避免混淆接口和计费条件。

    TensorFold 1.2.9的Ollama接口和服务配置文件怎么用
    TensorFold 1.2.9的Ollama接口和服务配置文件怎么用

    TensorFold 1.2.9的服务配置文件用于保存和复用启动参数,Ollama兼容API则在同一推理路径上提供聊天、生成和模型查询等接口。理解配置优先级及后端限制,比只看到“兼容”就直接迁移全部流量更有用。

    如何理解Univer 1.5.2的二次混淆移除与构建边界?
    如何理解Univer 1.5.2的二次混淆移除与构建边界?

    理解Univer 1.5.2的关键,是把额外混淆与构建压缩分开。本版删除二次混淆插件及相关配置,同时保留Pro模块的minify设置;它解释的是产物处理方式的变化,不代表增加了表格或公式能力。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。