图解JDK 8 HashMap

HashMap-简介


HashMap 主要用来存放键值对,它基于哈希表的 Map 接口实现,是常用的 Java 集合之一,是非线程安全的。

HashMap 可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个

JDK1.8 之前 HashMap 由 数组+链表 组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于等于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。

HashMap 默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。并且, HashMap 总是使用 2 的幂作为哈希表的大小。


HashMap-数据结构

这是 HashMap 类中的一个成员变量,它是一个存储桶数组。table 数组用于存储键值对的实际数据。

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
}

这是 HashMap 内部定义的静态嵌套类 Node,它实现了 Map.Entry 接口。每个 Node 对象表示 HashMap 中的一个键值对,它包含键、值以及指向下一个节点的引用,从结构上来看,HashMap中链表结构与LinkedList相似。

测试示例

    public static void main(String[] args) {

        HashMap<String,Integer> hashMap = new HashMap<>();
        hashMap.put("KING",100);
    }

图解HashMap-put方法

根据key获取hash值

Hash是将Key转换为一个短的、定长的值去替代源Key作为索引,以更快的查询。

通过hash方法得到"KING"对应的hash值为2306996。

计算方式:

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
通过hash值得到对应的桶的Index

计算方式:

(n - 1) & hash

如此,当调用put方法将元素添加到HashMap时,“KING”、100便被放入到Index为4的Node中。

由于index为4的Node节点并无除"KING"其他元素,所以它的下一个节点信息为null。用同样的方法将"CLARK"

,90放入HashMap。

不同的Key得到的Index值相同的情况

接下来我们把Key:“BLAKE”,value:10放入该Map,得到key值的hash为63281940:

根据63281940计算Index结果为4:

由于"KING"对应的Node节点也为4,Key:"BLAKE"计算出的Index同样为4,不同的key通过哈希算法(n - 1) & hash计算出的索引位置相同时即为哈希冲突,HashMap在发生哈希冲突时,会将具有相同哈希码的键值对存储在同一个桶(bucket)中,通过链表或者在元素数量较多时转换为红黑树来处理冲突。如此,HashMap的结构将变为:


图解HashMap-get方法

HashMap的get方法用于获取指定键对应的值。

以获取"KING"的值为例:

Integer integer = hashMap.get("KING");

先计算出key的hash值,根据key值和key的hash值去获取Node信息。

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 && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 桶中可能存在不止一个节点
        if ((e = first.next) != null) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

先来明确一下各个变量的意义:

  • key:要查询的指定key
  • table:当前HashMap哈希表实际数据存储,用于存储节点的桶
  • first:要查询的指定key匹配到某个桶的第一个节点
  • e:临时节点,用于遍历桶中的节点链表或树结构。在这段代码中,e 用于遍历桶中的节点以查找匹配的键值对。
  • n:这是一个整数,表示哈希表的长度,即桶的数量。
  • k:这是一个键对象,表示 first 节点的键,即指定key计算后hash值对应桶的第一个节点的键。

链表

把上文源码链表部分翻译成一张图片:

图片局部放大:

当同一个Node<Key,Value>中存在多个元素时,开始根据key值和key的hash值在链表中匹配对应的value值。

红黑树

由于在链表中获取对应Value值的过程是通过for循环实现的,其时间复杂度为O(n),当链表过长时,查询时间变长,JDK使用红黑树解决了该问题,当链表长度大于8时,链表进行树化。

红黑树结构

如果存储桶中的元素是一个红黑树,则通过红黑树的查找算法,在红黑树中查找具有相同哈希码并且键相等的节点。

后续内容文章持续更新中…

近期发布。


关于我

👋🏻你好,我是Debug.c。微信公众号:种棵代码技术树 的维护者,一个跨专业自学Java,对技术保持热爱的bug猿,同样也是在某二线城市打拼四年余的Java Coder。

🏆在掘金、CSDN、公众号我将分享我最近学习的内容、踩过的坑以及自己对技术的理解。

📞如果您对我感兴趣,请联系我。

若有收获,就点个赞吧,喜欢原图请私信我。

wallhaven-p9x8rm.jpg

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/543838.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Macbook M1 Pro使用brew安装Docker并安装Nacos【超详细图解】

目录 一、安装 Docker 二、修改 Docker 镜像地址 三、拉取镜像-举例 Nacos 1.拉取镜像 2.查看本地镜像 3.删除镜像 四、启动容器 1.启动 Nacos 容器&#xff1a; I.方式一【推荐】 II.方式二【懒人推荐】 2.访问 Nacos Web 控制台 3.进入容器和退出容器 五、配置…

labview中的同步定时结构

单帧定时循环定时比较精确&#xff0c;最常用的功能还是它的定时循环功能&#xff0c;定时循环允许不连接“循环条件”端子&#xff0c;可以连接定时循环“结构名称”端子&#xff0c;通过定时结构停止函数停止循环。 例子在附件中。

如何下载和安装Google Chrome扩展插件:一步步指南

Google Chrome 插件为我们提供了这样的便利&#xff0c;但有时找到一个有用的插件后&#xff0c;我们可能需要将其下载到本地以便离线使用或备份。 一、为什么可以从Google Chrome商店直接下载插件&#xff1f; Google Chrome 扩展插件主要通过Chrome Web Store分发&#xff…

凡泰极客亮相2024 亚马逊云科技出海全球化论坛,为企业数字化出海赋能

随着「不出海&#xff0c;即出局」登上热搜榜单&#xff0c;企业出海已成燎原之势&#xff0c;3月29日&#xff0c;2024 亚马逊云科技出海全球化论坛在深圳成功举办&#xff0c;凡泰极客创始人梁启鸿受邀出席&#xff0c;并以 「App 2.0&#xff1a;以SuperApp构建智能数字生态…

使用Python的Pillow库进行图像处理书法参赛作品

介绍&#xff1a; 在计算机视觉和图像处理领域&#xff0c;Python是一种强大而流行的编程语言。它提供了许多优秀的库和工具&#xff0c;使得图像处理任务变得轻松和高效。本文将介绍如何使用Python的wxPython和Pillow库来选择JPEG图像文件&#xff0c;并对选中的图像进行调整和…

Vol.45 这个壁纸网址,功能简单,每月37.7万访问量

哈咯&#xff0c;大家好&#xff0c;我是欧维&#xff0c;今天要给大家分享的网站是&#xff1a;极简壁纸&#xff0c;一个专门做电脑壁纸的网站&#xff1b; 它的网址是&#xff1a;极简壁纸_海量电脑桌面壁纸美图_4K超高清_最潮壁纸网站 网站的壁纸质量很高&#xff0c;页面…

c/c++普通for循环学习

学习一下 for 循环的几种不同方式&#xff0c;了解一下原理及差异 完整的测试代码参考 GitHub &#xff1a;for 循环测试代码 1 常用形态 对于 for 循环来说&#xff0c;最常用的形态如下 for (表达式1; 表达式2; 表达式3) {// code }流程图如下&#xff1a; 编写测试代码…

高清4路HDMI编码器JR-3214HD

产品简介&#xff1a; JR-3214HD四路高清HDMI编码器是专业的高清音视频编码产品&#xff0c;该产品具有支持4路高清HDMI音视频采集功能&#xff0c;4路3.5MM独立外接音频输入&#xff0c;编码输出双码流H.264格式&#xff0c;音频MP3/AAC格式。编码码率可调&#xff0c;画面质…

[Spring Cloud] (2)gateway全局异常捕捉统一返回值

文章目录 处理转发失败的情况全局参数同一返回格式操作消息对象AjaxResult返回值状态描述对象AjaxStatus返回值枚举接口层StatusCode 全局异常处理器自定义通用异常定一个自定义异常覆盖默认的异常处理自定义异常处理工具 在上一篇章时我们有了一个简单的gateway网关 [Spring C…

使用LangChain和GPT-4,创建Pandas DataFrame智能体

大家好&#xff0c;数据分析和数据处理是数据科学领域每天都在进行的基本任务。高效和快速的数据转换对于提取有意义的见解和基于数据做出明智决策至关重要。其中最受欢迎的工具之一是Python库Pandas&#xff0c;它提供了一个功能强大的DataFrame工具&#xff0c;使用灵活直观的…

【STL详解 —— stack和queue的介绍及使用】

STL详解 —— stack和queue的介绍及使用 stackstack的定义方式stack的使用 queuequeue的定义方式queue的使用 stack stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&#xff0c;其只能从容器的一端进行元素的插入与提取操作。 stack的定义方式 首…

list 简化版模拟实现

1ListNode template<class T>struct ListNode{public:ListNode(const T& x T()):_next(nullptr), _prev(nullptr), _data(x){}//private://共有可访问ListNode<T>* _next;ListNode<T>* _prev;T _data;}; 实现iterator对Node*的封装 实现运算符重载 vo…

深入理解DES算法:原理、实现与应用

title: 深入理解DES算法&#xff1a;原理、实现与应用 date: 2024/4/14 21:30:21 updated: 2024/4/14 21:30:21 tags: DES加密对称加密分组密码密钥管理S盒P盒安全性分析替代算法 DES算法简介 历史 DES&#xff08;Data Encryption Standard&#xff09;算法是由IBM研发&…

整数在内存中的存储和内存操作函数

目录 整数在内存中的存储1. 整数在内存中的存储2. 大小端字节序和字节序判断2.1 什么是大小端?2.2 为什么有大小端 3. 练习3.1 请简述大端字节序和小端字节序的概念&#xff0c;设计⼀个小程序来判断当前机器的字节序。&#xff08;10分&#xff09;-百度笔试题3.2 练习23.3 练…

科研学习|科研软件——如何使用SmartPLS软件进行结构方程建模

SmartPLS是一种用于结构方程建模&#xff08;SEM&#xff09;的软件&#xff0c;它可以用于定量研究&#xff0c;尤其是在商业和社会科学领域中&#xff0c;如市场研究、管理研究、心理学研究等。 一、准备数据 在使用SmartPLS之前&#xff0c;您需要准备一个符合要求的数据集。…

Vector - CAPL - XCP介绍_02

前面我们介绍了关于使用vector XCP License后&#xff0c;通过CAPL对XCP协议进行连接、断开和获取当前XCP连接状态的函数&#xff0c;本篇文章不做过多的其他赘述&#xff0c;我们继续介绍CAPL控制XCP相关的其他函数。 目录 xcpActivate 代码示例 xcpDeactivate xcpActiva…

【周总结】

周总结 完成工单脚本的编写以及解决操作问题 完成相关 jira 问题修改 学习了 sentinel 整合项目使用流控&#xff0c;熔断&#xff0c;热点等功能的使用 2024/4/14 晴 1. 这周只办两件事&#xff0c;吃&#xff01;喝&#xff01;&#xff01;&#xff01; 2.忙忙忙&am…

开源博客项目Blog .NET Core源码学习(15:App.Hosting项目结构分析-3)

本文学习并分析App.Hosting项目中前台页面的关于本站页面和点点滴滴页面。 关于本站页面 关于本站页面相对而言布局简单&#xff0c;与后台控制器类的交互也不算复杂。整个页面主要使用了layui中的面包屑导航、选项卡、模版、流加载等样式或模块。   面包屑导航。使用layui…

Web前端 Javascript笔记3

1、垃圾回收机制 内存中的生命周期 1、内存分配 2、内存使用&#xff08;读写&#xff09; 3、内存回收&#xff0c;使用完毕之后&#xff0c;垃圾回收器完成 内存泄漏&#xff1a;该回收的&#xff0c;由于某些未知因素&#xff0c;未释放&#xff0c;叫做内存泄漏 栈&#xf…

PostgreSQL入门到实战-第二十九弹

PostgreSQL入门到实战 PostgreSQL中数据分组操作(四)官网地址PostgreSQL概述PostgreSQL中CUBE命令理论PostgreSQL中CUBE命令实战更新计划 PostgreSQL中数据分组操作(四) 如何使用PostgreSQL CUBE生成多个分组集 官网地址 声明: 由于操作系统, 版本更新等原因, 文章所列内容不…