HashMap底层源码分析

在这里插入图片描述

HashMap底层源码分析

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

HashMap可以存放null的Key和value,但是null作为键只能有一个,作为value可以有多个

方法名称说明
V put(K key, V value)添加元素
V remove(Object key)根据键删除键值对元素
void clear()移除所有的键值对元素
boolean containsKey(Object key)判断集合是否包含指定的键
boolean containsValue(Object value)判断集合是否包含指定的值
boolean isEmpty()判断集合是否为空
int size()集合的长度,也就是集合中键值对的个数

HashMap结构

HashMap内部方法

图标为m表示method

image-20240318161136018

HashMap内部类

图标为c表示class

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

HashMap内部属性

图标为f表示field

image-20240318161341292

static class Node<K,V> implements Map.Entry<K,V> {}

HashMap中每个元素都是一个Entry对象,

数组+链表+红黑树

// 表示数组默认的大小 为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 表示默认的负载因子(加载因子)为0.75
// 当数组元素个数超过0.75*16=12的时候就进行扩容,扩容为原来的2倍空间大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 表示HashMap最大的空间为 1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;

构造方法

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

HashMap中的Hash值只与键有关系与值无关

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}// 返回键所对应的哈希值
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

>>> 表示无符号右移

扩容机制

调用空参构造的时候,只把属性loadFactor初始化为0.75

剩余的核心源码主要涉及到put操作:

  • 如果当前位置没有值,则直接在数组中添加该键值对,即Node对象
    • 如果数组长度超过其初始长度16*0.75=12的时候,则会进行扩容,扩容成原来的2倍
  • 如果当前位置有值,需要判断和当前新添加的键是否一致: PUT操作
    • 一致:
      • 则进行覆盖更新
    • 不一致:
      • 则在其后以链表的形式进行追加。
      • 当链表的长度达到8【TREEIFY_THRESHOLD】的时候,则会调用treeifyBin()方法,此方法会根据HashMap数组长度来判断是否需要转成红黑树。只有当数组长度大于或者等于64【MIN_TREEIFY_CAPACITY】的情况下,才会执行转换红黑树的操作,以减少搜索时间。否则就只执行resize()方法对数组进行扩容。

get操作:

判断hash和key是否相等,如果是就直接返回,如果不是,需要判断是否是红黑树,是的话按照红黑树的方式进行搜索;如果也不是红黑树就按照链表的顺序从前往后进行遍历查找。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Java 开发篇+一个简单的数据库管理系统ZDB

说明&#xff1a;本文供数据库爱好者和初级开发人员学习使用 标签&#xff1a;数据库管理系统、RDBMS、Java小程序、Java、Java程序 系统&#xff1a;Windows 11 x86 CPU &#xff1a;Intel IDE &#xff1a;IntelliJ IDEA Community Edition 2024 语言&#xff1a;Java语言 标…

Kubernetes的Ingress Controller

前言 Kubernetes暴露服务的方式有一下几种&#xff1a;LoadBlancer Service、ExternalName、NodePort Service、Ingress&#xff0c;使用四层负载均衡调度器Service时&#xff0c;当客户端访问kubernetes集群内部的应用时&#xff0c;数据包的走向如下面流程所示&#xff1a;C…

vue3 uniapp微信登录

根据最新的微信小程序官方的规定&#xff0c;uniapp中的uni.getUserInfo方法不再返回用户头像和昵称、以及手机号 首先&#xff0c;需获取appID&#xff0c;appSecret&#xff0c;如下图 先调用uni.getUserInfo方法获取code&#xff0c;然后调用后台的api&#xff0c;传入code&…

传送指令三菱

1&#xff0c;mov指令表示接通后一直传送 2&#xff0c;movP 接通后只传送一次 3&#xff0c;DMOV 32位传送 1&#xff0c; m0 接通 执行一次写入 值改变了 2&#xff0c;m1 接通 执行写入 值变为6 断开M1 值未发生变化 断开M0 在执行写入 值变为5 dmov 32 位 mov 16位 实…

【电子通识】电热水壶组成结构及主要器件原理

电热水壶&#xff08;又名电水壶、电烧水壶&#xff09;是目前市场上极为普及的小型家用电器之一。电热水壶是一种具有蒸汽智能感应控制、过热保护、水沸或水干自动断电功能的器具&#xff0c;可将水快速煮沸&#xff0c;使用便捷。 电热水壶主体分为壶身、壶盖、提手、底座、开…

[linux api] of_irq_init

总结: 以如下级联的中断控制器为例: of_irq_init会确保先初始化父控制器再初始化子控制器,也即整体按照层序遍历的顺序进行初始化,以上图为例,其初始化顺序为: intc0intc1-2intc3-6具体实现则分为两个阶段: 第一阶段 遍历所有设备节点,并与参数matches进行匹配,找…

策略为王股票软件源代码\StkUI\View\InfoView.cpp-------在线资讯视图---------程序代码都在里面了

void CInfoView::OnRefresh( ) { OnUpdate( NULL, UPDATE_HINT_INFOVIEW, NULL ); } char szInfoSelf[] = "http://%s/info/%s/?market=%s&code=%s"; char szInfoF10[] = "http://www.f10.com.cn/ggzx/ggzl.asp?zqdm=%s"…

10.哀家要长脑子了!

1. 704. 二分查找 - 力扣&#xff08;LeetCode&#xff09; 哎哟 我去 我还以为你都搞懂了 呵呵 当时问题出现在右边界初始化 左闭右开 右边界是取不到的 int left 0, right nums.size() ; while(left < right) { int mid left (right - left) / 2; if( target > …

Spring框架中的单例bean是线程安全的吗?

无状态bean&#xff1a; 无状态的Bean的行为不受其内部状态的影响&#xff0c;每次调用都是基于传入的参数进行计算&#xff0c;而不依赖于任何之前的状态。 (例如上面例子&#xff1a;userService是不能修改的&#xff0c;是无状态的bean) 因此&#xff1a; Spring框架中的…

Qt 窗⼝

Qt 窗⼝ 菜单栏创建菜单栏在菜单栏中添加菜单创建菜单项在菜单项之间添加分割线综合⽰例 ⼯具栏创建⼯具栏设置停靠位置设置浮动属性设置移动属性综合⽰例状态栏状态栏的创建在状态栏中显⽰实时消息在状态栏中显⽰永久消息 浮动窗⼝浮动窗⼝的创建设置停靠的位置 对话框对话框介…

1. 编译和链接----你真的了解HelloWord吗

平时的应用程序开发&#xff0c;很少需要关注编译和链接的过程&#xff0c;因为通常的开发环境都是流行的集成开发环境&#xff08;IDE&#xff09;&#xff0c;比如VS等&#xff0c;这些IDE通常将编译和链接的过程一步完成&#xff0c;我们通常将这种合并到一起的过程称为构建…

Pytest精通指南(09)利用Fixture给函数设置别名

文章目录 前言测试用例默认显示传递一个参数传递多个参数 利用Fixture修改测试函数名称传递一个参数传递多个参数 验证ids和params长度不一致修改Fixture函数名称 前言 在 pytest 中&#xff0c;pytest.fixture 装饰器用于定义可以在多个测试函数中重用的设置和清理代码。 name…

【复习笔记】FreeRTOS(六) 队列操作

本文是FreeRTOS复习笔记的第六节&#xff0c;队列操作。 上一篇文章&#xff1a; 【复习笔记】reeRTOS(四) 列表项的插入和删除 文章目录 1.队列操作1.1.队列操作过程1.2.队列操作常用的API函数 二、实验设计三、测试例程四、实验效果 1.队列操作 队列是为了任务与任务、任务与…

1038: 顺序表中重复数据的删除

解法&#xff1a; #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() {int n, k;cin >> n;vector<int> arr(n);for (auto& x : arr) cin >> x;cin >> k;int sum 0;for (auto x : arr…

视频生成Sora的全面解析:从AI绘画、ViT到ViViT、TECO、DiT、VDT、NaViT等

前言 真没想到&#xff0c;距离视频生成上一轮的集中爆发(详见《Sora之前的视频生成发展史&#xff1a;从Gen2、Emu Video到PixelDance、SVD、Pika 1.0》)才过去三个月&#xff0c;没想OpenAI一出手&#xff0c;该领域又直接变天了 自打2.16日OpenAI发布sora以来(其开发团队包…

RTC的基本概念以及相关例程

实时时钟(RTC) 北京时间跟伦敦时间错8个小时 BKP简介 BKP本质上是RAM存储器&#xff0c;没有掉电不丢失的能力。 VBAT的作用就是&#xff0c;当VDD断电时&#xff0c;BKP会切换到VBAT供电&#xff0c;这样可以继续维持BKP里面的数据&#xff0c;如果VDD断电&#xff0c;VBAT也…

【Hello算法】 > 第 1 关 > 初识 算法 与 复杂度分析

初识 算法 与 复杂度分析 What are algorithms and data structures ?-什么是算法与数据结构&#xff1f;How to conduct complexity analysis ?-如何进行复杂性分析&#xff1f;时间复杂度空间复杂度 小结Tips&#xff1a; ————————————————————————…

Centos7查看内存使用情况

Centos7查看内存使用情况 free -b&#xff1a;以字节为单位显示内存使用情况。-k&#xff1a;以KB为单位显示内存使用情况&#xff08;默认选项&#xff09;。-m&#xff1a;以MB为单位显示内存使用情况。-g&#xff1a;以GB为单位显示内存使用情况。-t&#xff1a;在输出的最…

vue3语法糖使用ref和refs

标签页里面正常定义ref&#xff0c;写法跟Vue2一样 在语法糖里的写法就跟Vue2不同&#xff0c;语法糖里不用使用$refs <script setup lang"ts"> // 定义一个跟标签页中的ref一样名称的变量 const multipleTable ref(null) const tableRowClick (row, column…

29、链表-删除链表的倒数第N个结点

思路: 首先找到倒数第N个结点 第一种方式 先统计链表的节点数&#xff0c;然后再次遍历len-N即可得到倒数第N个结点&#xff0c;然后将前一个节点的next指针指向next的下一个节点使用快慢指针&#xff0c;快指针先跑N个结点然后慢指针开始跑&#xff0c;等快指针到达尾节点后…