HashMap源码解析
目录
一:put方法流程
二:get方法
三:扩容机制
一: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;//判断数组是否未初始化if ((tab = table) == null || (n = tab.length) == 0)//如果未初始化,调用resize方法 进行初始化n = (tab = resize()).length;//通过 & 运算求出该数据(key)的数组下标并判断该下标位置是否有数据if ((p = tab[i = (n - 1) & hash]) == null)//如果没有,直接将数据放在该下标位置tab[i] = newNode(hash, key, value, null);//该数组下标有数据的情况else {Node<K,V> e; K k;//判断该位置数据的key和新来的数据是否一样if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//如果一样,证明为修改操作,该节点的数据赋值给e,后边会用到e = p;//判断是不是红黑树else if (p instanceof TreeNode)//如果是红黑树的话,进行红黑树的操作e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//新数据和当前数组既不相同,也不是红黑树节点,证明是链表else {//遍历链表for (int binCount = 0; ; ++binCount) {//判断next节点,如果为空的话,证明遍历到链表尾部了if ((e = p.next) == null) {//把新值放入链表尾部p.next = newNode(hash, key, value, null);//因为新插入了一条数据,所以判断链表长度是不是大于等于8if (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;}}//判断e是否为空(e值为修改操作存放原数据的变量)if (e != null) { // existing mapping for key//不为空的话证明是修改操作,取出老值V oldValue = e.value;//一定会执行 onlyIfAbsent传进来的是falseif (!onlyIfAbsent || oldValue == null)//将新值赋值当前节点e.value = value;afterNodeAccess(e);//返回老值return oldValue;}}//计数器,计算当前节点的修改次数++modCount;//当前数组中的数据数量如果大于扩容阈值if (++size > threshold)//进行扩容操作resize();//空方法afterNodeInsertion(evict);//添加操作时 返回空值return null;
}
二:get方法
public V get(Object key) {Node<K,V> e;//hash(key),获取key的hash值//调用getNode方法,见下面方法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;//找到key对应的桶下标,赋值给first节点if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//判断hash值和key是否相等,如果是,则直接返回,桶中只有一个数据(大部分的情况)if (first.hash == hash && // always check first node((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;
}
三:扩容机制
//扩容、初始化数组
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;//如果当前数组为null的时候,把oldCap老数组容量设置为0int oldCap = (oldTab == null) ? 0 : oldTab.length;//老的扩容阈值int oldThr = threshold;int newCap, newThr = 0;//判断数组容量是否大于0,大于0说明数组已经初始化if (oldCap > 0) {//判断当前数组长度是否大于最大数组长度if (oldCap >= MAXIMUM_CAPACITY) {//如果是,将扩容阈值直接设置为int类型的最大数值并直接返回threshold = Integer.MAX_VALUE;return oldTab;}//如果在最大长度范围内,则需要扩容 OldCap << 1等价于oldCap*2//运算过后判断是不是最大值并且oldCap需要大于16else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold 等价于oldThr*2}//如果oldCap<0,但是已经初始化了,像把元素删除完之后的情况,那么它的临界值肯定还存在, 如果是首次初始化,它的临界值则为0else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//数组未初始化的情况,将阈值和扩容因子都设置为默认值else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//初始化容量小于16的时候,扩容阈值是没有赋值的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;//判断当前下标为j的数组如果不为空的话赋值个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 {//比如老数组容量是16,那下标就为0-15//扩容操作*2,容量就变为32,下标为0-31//低位:0-15,高位16-31//定义了四个变量// 低位头 低位尾Node<K,V> loHead = null, loTail = null;// 高位头 高位尾Node<K,V> hiHead = null, hiTail = null;//下个节点Node<K,V> next;//循环遍历do {//取出next节点next = e.next;//通过 与操作 计算得出结果为0if ((e.hash & oldCap) == 0) {//如果低位尾为null,证明当前数组位置为空,没有任何数据if (loTail == null)//将e值放入低位头loHead = e;//低位尾不为null,证明已经有数据了else//将数据放入next节点loTail.next = e;//记录低位尾数据loTail = e;}//通过 与操作 计算得出结果不为0else {//如果高位尾为null,证明当前数组位置为空,没有任何数据if (hiTail == null)//将e值放入高位头hiHead = e;//高位尾不为null,证明已经有数据了else//将数据放入next节点hiTail.next = e;//记录高位尾数据hiTail = e;}} //如果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;}
四:总结
HashMap是Java中常用的数据结构之一,用于存储键值对的键值对。以下是HashMap的几个常见的使用场景总结:
1. 缓存管理:HashMap可以用于实现缓存功能,将数据存储在HashMap中,以键值对的形式保存。可以通过查询HashMap来获取需要的数据,避免了再次计算或查询数据库的开销。
2. 数据索引:HashMap是一种快速查找数据的数据结构,可以根据键快速找到对应的值。因此,HashMap可以用于构建索引结构,提高数据的检索效率。
3. 字典:HashMap可以用于实现字典功能,将单词与对应的意义作为键值对存储在HashMap中。通过查询键来获取对应的意义,实现快速查找。
4. 频率统计:HashMap可以用于统计数据中各个元素出现的频率。可以将元素作为键,出现的次数作为值,通过对值进行排序或查询,获取频率最高的元素。
5. 数据存储和检索:HashMap是一种高效的数据结构,可以用于存储和检索大量数据。可以根据键快速找到对应的值,提高数据的存取效率。
总之,HashMap可以在需要存储和检索数据的场景中发挥作用,并且由于其高效的存取方式,在大多数情况下,都是一个不错的选择。
相关文章:
HashMap源码解析
目录 一:put方法流程 二:get方法 三:扩容机制 一: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) {No…...

[Javascript】前端面试基础3【每日学习并更新10】
Web开发中会话跟踪的方法有那些 cookiesessionurl重写隐藏inputip地址 JS基本数据类型 String:用于表示文本数据。Number:用于表示数值,包括整数和浮点数。BigInt:用于表示任意精度的整数。Boolean:用于表示逻辑值…...

C++自定义字典树结构
代码 #include <iostream> using namespace std;class TrieNode { public:char data;TrieNode* children[26];bool isTerminal;TrieNode(char ch){data ch;for (int i 0; i < 26; i){children[i] NULL;}isTerminal false;} }; class Trie { public:TrieNode* ro…...

dockerfile部署wordpress
1.将容器直接提交成镜像 [rootlocalhost ~]# docker commit 8ecc7f6b9c12 nginx:1.1 sha256:9a2bb94ba6d8d952527df616febf3fbc8f842b3b9e28b7011b50c743cd7b233b [rootlocalhost ~]# docker images REPOSITORY TAG IMAGE ID CREATED SIZE nginx …...

CSS(二)——CSS 背景
CSS 背景 CSS 背景属性用于定义HTML元素的背景。 CSS 背景属性 Property描述background简写属性,作用是将背景属性设置在一个声明中。background-attachment背景图像是否固定或者随着页面的其余部分滚动。background-color设置元素的背景颜色。background-image把…...

开机出现grub无法进入系统_电脑开机出现grub解决方法
最近有小伙伴问我电脑开机出现grub无法进入系统怎么回事?电脑开机出grub的情况有很多,电脑上安装了Linux和Win10双系统,但是由于格式化删除了Linux之后,结果win10开机了之后,直接显示grub>,无法…...

uboot 设置bootargs配置内核网络挂载根文件系统
uboot 设置bootargs配置内核网络挂载根文件系统 uboot设置bootargs env set bootargs "mem256M consolettyAMA0,115200 root/dev/nfs init/linuxrc nfsrootnfs主机地址:nfs路径/busybox/rootfs_glibc_arm64,prototcp rw nfsvers3 rootwait ip板子地址:nfs主机地址:网关:2…...

Vue3+.NET6前后端分离式管理后台实战(三十一)
1,Vue3.NET6前后端分离式管理后台实战(三十一)...

22集 如何minimax密钥和groupid-《MCU嵌入式AI开发笔记》
22集 如何获取minimax密钥和groupid-《MCU嵌入式AI开发笔记》 minimax密钥获取 https://www.minimaxi.com/platform 进入minimax网站,注册登录后,进入“账户管理”, 然后再点击“接口密钥”,然后再点击“创建新的密钥”。 之…...
决策树的概念
决策树的概念 决策树是一种监督学习算法,主要用于分类任务。它通过构建一棵树结构模型来进行预测,其中每个内部节点表示一个特征属性上的判断条件,每条边代表一个判断结果对应的分支,而叶节点则代表最终的类别标签。 应用领域 …...

C++《类和对象》(中)
一、 类的默认成员函数介绍二、构造函数 构造函数名与类同名内置类型与自定义类型析构函数拷贝构造函数 C《类和对象》(中) 一、 类的默认成员函数介绍 默认成员函数就是⽤⼾没有显式实现,编译器会⾃动⽣成的成员函数称为默认成员函数。 那么我们主要学习的是1&…...
SpringBoot中JSR303校验
JSR是 Java EE 的一种标准,用于基于注解的对象数据验证。在Spring Boot应用中,你可以通过添加注解直接在POJO类中声明验证规则。这样可以确保在使用这些对象进行操作之前,它们满足业务规则。个人认为非常有用的,因为它减少了代码中…...

图像数据增强方法概述
图像数据增强方法概述 1. 什么是图像数据增强技术?2. 图像数据增强技术分类2.1 几何变换Python 示例代码 2.2 颜色变换2.3 噪声添加 3. 参考文献 1. 什么是图像数据增强技术? 基础概念:图像增强技术是计算机视觉和图像处理领域中的一个关键技术,主要用…...

【学习笔记】无人机系统(UAS)的连接、识别和跟踪(五)-无人机跟踪
目录 引言 5.3 无人机跟踪 5.3.1 无人机跟踪模型 5.3.2 无人机位置报告流程 5.3.3 无人机存在监测流程 引言 3GPP TS 23.256 技术规范,主要定义了3GPP系统对无人机(UAV)的连接性、身份识别、跟踪及A2X(Aircraft-to-Everyth…...

分享从零开始学习网络设备配置--任务6.1 实现计算机的安全接入
项目描述 随着网络技术的发展和应用范围的不断扩大,网络已经成为人们日常生活中必不可少的一部分。园区网作为给终端用户提供网络接入和基础服务的应用环境,其存在的网络安全隐患不断显现出来,如非人为的或自然力造成的故障、事故;…...

双向链表(C语言版)
1. 双向链表的结构 注意:这里的“带头”跟单链表的“头结点”是两个概念,实际上在单链表阶段称呼不太严谨,但是为了更好地理解就直接称为单链表的头结点。带头链表里的头结点,实际为“哨兵位”,哨兵位结点不存储任何有…...

【算法/学习】前缀和差分
前缀和&&差分目录 1. 前缀和的概念及作用 🌈概念 🌈用途 🌙一维前缀和 🌙二维前缀和 2. 差分的概念及用途 🌈概念: 🌈用途 🌙一维差分 🌙二维差分 1. …...
idea Project 不显示文件和目录
idea Project 不显示文件和目录 File - Close Project - 重新打开项目即可删除.idea文件夹,重新打开项目即可。 原因分析: 可能与使用不同ide例如java、python打开同一项目有关 参考: https://blog.csdn.net/hgnuxc_1993/article/details/132595900 解决打开IDE…...

Linux--Socket编程预备
目录 1. 理解源 IP 地址和目的 IP 地址 2.端口号 2.1端口号(port)是传输层协议的内容 2.2端口号范围划分 2.3理解 "端口号" 和 "进程 ID" 2.4理解 socket 3.传输层的典型代表 3.1认识 TCP 协议 3.2认识 UDP 协议 4. 网络字节序 5. socket 编程接…...
100个python的基本语法知识【下】
50. 压缩文件: import zipfilewith zipfile.ZipFile("file.zip", "r") as zip_ref:zip_ref.extractall("extracted")51. 数据库操作: import sqlite3conn sqlite3.connect("my_database.db") cursor conn.c…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...

spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...

macOS 终端智能代理检测
🧠 终端智能代理检测:自动判断是否需要设置代理访问 GitHub 在开发中,使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新,例如: fatal: unable to access https://github.com/ohmyzsh/oh…...