文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

详解 HashMap 的底层实现原理

2024-11-30 11:31

关注

作为一名程序员,你可能经常使用 HashMap 这个重要的数据结构,但你对它的底层实现原理可能不够了解。本文将通过图文结合的方式,为你详细解析 HashMap 的底层实现原理,并回答一些常见问题,让你能够更好地理解和应用 HashMap。

1. HashMap 概述

HashMap 是 Java 集合框架中最常用的映射表实现,它提供了键值对的存储和检索功能。底层基于数组和链表(或红黑树)实现,通过哈希算法将键映射到数组的索引位置,以实现快速的插入和查找操作。下面我们来看一下 HashMap 的底层代码流程图:

2. HashMap 的主要方法分析

2.1 put方法

put方法用于将键值对插入到 HashMap 中。让我们看一下put方法的源代码:

首先通过has(key)方法计算键的哈希码,并调用putVal()方法进行插入操作。下面putVal()方法的源代码:

putVal()方法的核心是通过哈希码定位桶,然后在桶中进行插入操作。如果桶为空,则直接在桶中插入新节点。如果桶不为空,则遍历链表或红黑树,查找键是否已存在。如果键已存在,则替换对应的值;如果键不存在,则将新节点插入到链表的末尾,并根据链表长度是否达到阈值来决定是否将链表转化为红黑树。最后,更新修改次数和元素数量,并进行必要的操作。

2.2 resize方法

resize方法用于动态扩容 HashMap。当元素数量超过阈值时,HashMap 会自动触发扩容操作。下面是resize方法的源代码:

resize方法的主要功能是创建一个新的数组,并将所有键值对重新计算哈希码和索引位置,然后将它们分配到新的桶中。扩容后的容量是原来的两倍,并根据负载因子重新计算阈值。在转移键值对时,会根据哈希码的高位来确定是保留在原来的位置还是移动到新的位置。如果链表长度超过阈值,则会将链表转化为红黑树以提高查找效率。

2.3 get方法

当我们需要根据键来获取值时,可以使用 HashMap 的get(key)方法。下面讲解下 HashMap 的get方法的原理。

首先,我们传入要查找的键key,然后通过hash(key)方法计算键的哈希码。哈希码被用来确定键在 HashMap 中的桶(bucket)位置。根据哈希码,我们可以确定键在数组中的索引位置。

接下来,我们在确定的索引位置找到对应的桶。如果桶为空,即没有键值对存在,那么返回 null,表示没有找到对应的值。

如果桶不为空,那么可能存在多个键值对,这时我们需要遍历链表或红黑树来找到具有相同键的节点。在遍历过程中,我们会使用键的 equals() 方法来比较传入的键和当前节点的键是否相等。如果找到了相等的键,那么返回对应节点的值。

如果遍历完整个链表或红黑树仍然没有找到相等的键,那么返回 null,表示没有找到对应的值。

整个get()方法的原理就是根据键的哈希码确定索引位置,然后在对应的桶中遍历链表或红黑树,通过 equals() 方法比较键的相等性来找到对应的值。

以下是get方法的伪代码示例:

通过分析上述代码,我们可以看到get方法的实现流程:首先计算键的哈希码,然后根据哈希码找到对应的桶,最后在桶中遍历链表或红黑树,查找具有相同键的节点,如果找到则返回对应的值,否则返回 null。

3. 常见问题分析

3.1为什么哈希码很重要?

哈希码在 HashMap 中扮演着重要的角色。它通过哈希函数将键转换为一个唯一的整数,决定了键值对在数组中的存储位置。如果两个键的哈希码不同,它们会被分配到不同的桶中,提高了查找效率。如果哈希码相同,就会发生哈希冲突,需要进一步处理。

3.2如何处理哈希冲突?

当两个不同的键具有相同的哈希码时,HashMap 会使用链表或红黑树来解决哈希冲突。链表是 JDK 8 之前的解决方案,而红黑树是 JDK 8 之后的优化。HashMap 在桶中通过链表或红黑树结构存储冲突的键值对,以便在查找时能快速定位到正确的键值对。

3.3为什么需要动态扩容?

动态扩容是为了避免哈希冲突过多,提高 HashMap 的性能。当键值对的数量接近数组容量的阈值时,HashMap 会自动触发扩容操作。它创建一个更大的数组,并重新计算每个键的哈希码和索引位置,然后将键值对重新插入到新数组中。这样可以减少桶的数量,降低哈希冲突的概率,提高存储和检索的效率。

3.4如何保证键的唯一性?

HashMap 通过哈希码和链表/红黑树结构来保证键的唯一性。当存储键值对时,如果发现相同的键已经存在于桶中,HashMap 会检查键的 equals() 方法来确定是否是同一个键。如果 equals() 方法返回 true,新的键值对会替换旧的键值对;如果 equals() 方法返回 false,新的键值对会被添加到桶中。这样就确保了 HashMap 中的键是唯一的。

3.5HashMap 和线程安全有关吗?

HashMap 在默认情况下是非线程安全的。多个线程同时对 HashMap 进行插入、删除或查找操作可能会导致不一致的结果。如果在并发环境下使用 HashMap,应考虑使用线程安全的 ConcurrentHashMap 或使用适当的同步机制来保护 HashMap 的访问。

3.6如何选择适当的初始容量和负载因子?

HashMap 的初始容量和负载因子会影响其性能和空间利用率。初始容量是指 HashMap 初始化时的桶数量,默认为 16。负载因子是指 HashMap 在扩容之前允许的平均桶占用比例,默认为 0.75。

选择适当的初始容量和负载因子取决于你的应用需求。如果预计存储的键值对数量较多,可以选择一个较大的初始容量,以减少动态扩容的频率。负载因子较小可以减少哈希冲突的概率,但会增加空间占用。综合考虑,通常可以使用 HashMap 的默认值,并根据实际情况进行调整。

HashMap 是一个强大而灵活的数据结构,合理使用它可以提高程序的性能和效率。通过深入了解 HashMap 的底层实现原理,你可以更好地理解其工作方式,并在实际开发中做出更明智的设计和优化决策。

结论

通过以上的源代码分析和常见问题的解答,相信你已经对 HashMap 的底层实现原理有了更深入的理解。HashMap 的底层使用数组和链表(或红黑树)实现,通过哈希算法将键映射到数组的索引位置,以实现快速的插入和查找操作。动态扩容过程会创建一个更大的数组,并重新分配键值对到新的桶中,以提高性能。同时,我们还回答了一些常见问题,希望能帮助你更好地理解和应用 HashMap。

作者介绍

波哥,在互联网行业从业10余年,先后担任项目总监及架构师。目前专攻技术,喜欢研究技术原理。技术全面,主攻Java,精通JVM底层机制及Spring全家桶底层框架原理,熟练掌握当前主流的中间件、服务网格等技术原理。

来源:51CTO内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯