当前位置： 首页 > news >正文

HashMap源码分析 (1.基础入门) 学习笔记

news 文章来源：https://blog.csdn.net/weixin_44449838/article/details/129923048 2025/5/16 14:45:17

本章为 《HashMap全B站最细致源码分析课程》 + 拉钩教育HashMap 学习笔记

文章目录

  • 1. HashMap的数据结构
    • 1. 数组
    • 2. 链表
    • 3. 哈希表
      • 3.1 Hash

1. HashMap的数据结构

数据结构中有数组和链表来实现对数据的存储，但这两者基本上是两个极端。

1. 数组

  • 在生成数组的时候数组的长度是固定的，在增加元素时常常会遇到长度不足的问题，此时就需要进行扩容——生成一个更长的数组，并将原数组中所有元素复制到新数组中，这个过程是很消耗资源的，故插入操作比较困难。
  • 数组存储区间是连续的，占用内存严重，故空间复杂的很大。
  • 数组的二分查找时间复杂度小，为O(1)；
  • 数组的特点是：寻址容易，插入和删除困难；

2. 链表

  • 链表存储区间离散，占用内存比较宽松，故空间复杂度很小，
  • 查询时必须从头节点一个个向后查询，时间复杂度很大，达O（N）。
  • 链表的特点是：寻址困难，插入和删除容易。

3. 哈希表

  • 哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法—— 拉链法，我们可以理解为“链表的数组” ，如图：

Hash表示意图

  • 从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。
  • HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性 key,value 我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，
  • HashMap其实也是一个线性的数组实现的，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。
  • 一般情况下存储规则为： hash(key)%len，也就是元素的key的哈希值对数组长度取模得到

3.1 Hash

  • 理论：Hash 也称散列表, 基本原理就是把任意长度的输入，通过Hash变成固定长度的输出。这个映射规则对应的就是 Hash算法，而原始数据映射后的二进制串就是哈希值
  • 特点：
  • 从 Hash值 不能反向推导出原始数据
  • 输入数据的微小变化，会得到完全不一样的hash值。相同数据的得到的hash值完全一样
  • Hash 算法执行效率高
  • Hash 算法冲突概率较小
  • 由于 Hash 的原理是将输入空间的值映射到Hash空间内， 而由于Hash空间远小于输入空间，根据抽屉原理，一定会存在不同输入空间的值映射到相同的hash空间的情况

相关文章：

HashMap源码分析 (1.基础入门) 学习笔记

本章为 《HashMap全B站最细致源码分析课程》 拉钩教育HashMap 学习笔记 文章目录1. HashMap的数据结构1. 数组2. 链表3. 哈希表3.1 Hash1. HashMap的数据结构 数据结构中有数组和链表来实现对数据的存储，但这两者基本上是两个极端。 1. 数组 在生成数组的时候数…...

编程日记 2023/4/30 0:34:41

6 使用强制类型转换的注意事项

概述 在C语言中，强制类型转换是通过直接转换为特定类型的方式来实现的，类似于下面的代码。 float fNumber = 66.66f; // C语言的强制类型转换 int nData = (int)fNumber; 这种方式可以在任意两个类型间进行转换，太过随意和武断，很容易带来一些难以发现的隐患和问题。C++为…...

编程日记 2023/4/29 10:40:00

Leetcode.939 最小面积矩形

题目链接 Leetcode.939 最小面积矩形 Rating ： 1752 题目描述 给定在 xy平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。 如果没有任何矩形，就返回 0。 示例 1： 输入&#xff1…...

编程日记 2023/4/29 18:07:19

Springboot项目快速实现过滤器功能

前言很多时候，当你以为掌握了事实真相的时间，如果你能再深入一点，你可能会发现另外一些真相。比如面向切面编程的最佳编程实践是AOP，AOP的主要作用就是可以定义切入点，并在切入点纵向织入一些额外的统一操作&#xff0…...

编程日记 2023/5/17 12:27:51

基于springboot的简历系统的实现

摘 要 随着科学技术的飞速发展，社会的方方面面、各行各业都在努力与现代的先进技术接轨，通过科技手段来提高自身的优势，简历系统当然也不能排除在外。简历系统是以实际运用为开发背景，运用软件工程原理和开发方法，采用…...

编程日记 2023/5/2 10:16:33

Vue3中watch的用法

watch函数用于侦听某个值的变化&#xff0c;当该值发生改变后&#xff0c;触发对应的处理逻辑。 一、watch的基本实例 <template><div><div>{{ count }}</div><button click"changCount">更改count的值</button></div> …...

编程日记 2023/4/30 16:35:28

MS python学习（18）

学习Pandas.DataFrame(2) load csv(comma seperated variable) files to DataFrame and vice versa upload csv files read/write csv files load data into jupyter notebook, create a new folder and then upload the csv files into it. (CSV comma seperated variable)…...

编程日记 2023/4/29 9:44:36

java笔记

前言 以下是一名java初学者在自学过程中所整理的笔记&#xff0c;欢迎大家浏览并留言&#xff0c;若有错误的地方请大家指正。 java语言特性 简单性&#xff1a;相对于其他编程语言而言&#xff0c;java较为简单&#xff0c;例如&#xff1a;java不再支持多继承&#xff0c;C…...

编程日记 2023/5/5 4:40:46

对象的构造及初始化

目录 一、如何初始化对象 二、构造方法 1.概念 2.特性 三、默认初始化 四、就地初始化 总结 一、如何初始化对象 在Java方法内部定义一个局部变量的时候&#xff0c;我们知道必须要进行初始化。 public class Test4 {public static void main(String[] args) {//未初始化…...

编程日记 2023/4/30 13:55:20

Socket 读取数据

1. Socket 配置参数中添加 1.1 读取 Socket 字节时的字节序 1.2 读取数据时&#xff0c;单次读取最大缓存值 1.3 从 Socket 读取数据时&#xff0c;遵从的数据包结构协议 1.4 服务器返回数据的最大值&#xff0c;防止客户端内存溢出 /*** Description: Socket 配置参数*/public…...

编程日记 2023/5/5 1:53:03

小白的Git入门教程（一）

这是本人的git的入门过程仅供参考 先是在官网下载git版本下载链接&#xff0c;安装步骤可以搜索其他大神的文章然后就是创建一个属于你的git本地库首先是创建一个文件夹作为根目录&#xff0c;这里我创建了一个叫test_git文件夹紧接着便进去新建文件夹&#xff0c;点击这里的g…...

编程日记 2023/5/1 21:18:57

第一个Vue程序

第一个Vue程序 <body> <!--view层 变成了一个模板--> <div id"app">{{message}} </div><!--导入vue.js--> <script src"https://cdn.jsdelivr.net/npm/vue2.5.16/dist/vue.min.js"></script> <script>va…...

编程日记 2023/5/17 12:29:05

2023上学期学习计划

目前&#xff1a;根据答辩的情况来看&#xff0c;目前去项目组&#xff0c;着重写好算法是相对较优的打算&#xff0c;先将项目写好&#xff0c;之后着重提升算法水平&#xff0c;这学期主要啃《算法导论》与《大话数据结构》这俩本书&#xff0c;同时刷题量要达到160题 四月份…...

编程日记 2023/5/2 13:05:57

深入了解MySQL锁机制及应用场景

深入了解MySQL锁机制及应用场景锁的概述锁的分类锁的应用场景数据库事务管理多线程程序开发数据库的备份和恢复对于在线游戏等高并发应用场景锁的具体使用方法锁的应用实例总结锁的概述 MySQL锁是操作MySQL数据库时常用的一种机制。MySQL锁可以保证多个用户在同时执行读写操作…...

编程日记 2023/4/30 21:46:37

Java类和对象

目录 一、什么是面向对象&#xff1f; 二、类与对象的基本概念 1.类 2.对象 三、类的定义格式 四、类与对象的定义与使用 1.什么是实例化 2.实例化对象 3.类的使用 4.类与对象的说明 总结 一、什么是面向对象&#xff1f; 面向对象是一种现在最为流行的程序设计方法&a…...

编程日记 2023/5/17 12:30:40

aspnet053+sqlserver在线考试系统xns

目 录 基于.NET的考试系统 1 摘 要 3 前 言 4 第一章　 系统概述 5 1.1 本课题的研究意义 5 1.2 本论文的目的及内容 5 第二章 在线考试系统概述 7 2.1 现行在线考试系统现状 7 2.2 电子管理平台的开发方法介绍 8 2.2.1 B/S体系结构 8 2…...

编程日记 2023/5/1 2:05:41

新一代大学英语（提高篇）

词汇题&#xff08;55道&#xff09; 1. You should carefully think over_____ the manager said at the meeting. A. that B. which C. what D. whose 1.选C,考察宾语从句连接词&#xff0c;主句谓语动词think over后面缺宾语&#xff0c;后面的宾语从句谓语动…...

编程日记 2023/5/17 12:31:54

阿里云OSS 203 Non-Authoritative Information问题解决

问题描述&#xff1a; 203 Non-Authoritative Information 问题分析&#xff1a; 1、跨域问题&#xff0c;阿里云OSS没有配置跨域规则。 解决办法请参考以下博客。 阿里云OSS No ‘Access-Control-Allow-Origin‘ header is present on the requested resource问题解决_旭东…...

编程日记 2023/4/29 6:55:51

【数据结构】你真的认识“”吗？它真的就只是“取地址”吗？或许你一直都在误解它。

我们有时候在看数据结构相关书籍时&#xff0c;经常会看到这样的写法&#xff1a; void StackInit(ST& ps) {assert(ps);ps.a NULL;ps.top 0;ps.capacity 0; } 注意&#xff0c;这里的&可不是表示取地址。如果你把它理解为取地址&#xff0c;那就在错误的路上狂奔&…...

编程日记 2023/4/30 17:28:12

[深入理解SSD 21] 固态硬盘GC机制 | GC 分类 | GC 过程 | GC 和 Trim 的关系

Hello 大家好&#xff0c; 我是元存储~主页&#xff1a;元存储的博客_CSDN博客-深入理解SSD:固态存储特性与实践,深入浅出SSD:固态存储原理与特性,深入理解Flash:闪存特性与实践领域博主前言SSD上已经被写入过的Page页在重新被写入之前&#xff0c;必须要将page页所在的block块…...

编程日记 2023/5/1 11:43:26

大数据未来发展怎么样？

就目前情况来看&#xff0c;大数据行业前景不错薪资待遇好&#xff0c;也有越来越多的人选择大数据行业&#xff0c;各大名企对于大数据人才需求不断上涨。 大数据从业领域很宽广&#xff0c;不管是科技领域还是食品产业&#xff0c;零售业等都是需要大数据人才进行大数据的处…...

编程日记 2023/5/2 5:27:10

【Linux】进程和线程间的区别与联系

带你轻松理解进程与线程的区别与联系&#xff1a; 进程线程定义资源分配和拥有的基本单位CPU调度的基本单位切换情况对应进程的CPU环境的保存以及新进程环境的设置保存和设置程序计数器&#xff0c;少量的寄存器&#xff0c;以及对应的线程栈切换者操作系统操作系统切换过程用…...

编程日记 2023/5/2 20:48:47

【C语言】变量和常量

目录 1. 变量 1.1 变量的分类 1.1.1 局部变量 1.1.2 全局变量 1.2 变量的使用——声明、赋值、初始化 1.3 变量的作用域和生命周期 1.3.1 作用域 1.3.2 生命周期 2. 常量 2.1 字面常量 2.2 常变量&#xff08;const常量&#xff09; 2.3 简单的宏&#xff08;对象式…...

编程日记 2023/5/2 15:05:17

蓝桥杯-卡片换位(BFS)

蓝桥杯-卡片换位 1、题目描述2、解题思路3、完整代码(AC)1、题目描述 你玩过华容道的游戏吗？ 这是个类似的，但更简单的游戏。 看下面 3 x 2 的格子 +---+---+---+| A | * | * |+---+---+---+| B | | * |+---+---+---+在其中放 5 张牌，其中 A 代表关羽，B 代表张飞，* 代表士…...

编程日记 2023/5/2 3:36:09

霍夫曼编码 | 贪心算法 2

霍夫曼编码是一种无损数据压缩算法。其思想是为输入字符分配可变长度代码&#xff0c;分配代码的长度基于相应字符的频率。 分配给输入字符的可变长度代码是​​​​​​​前缀代码&#xff0c;意味着代码&#xff08;位序列&#xff09;的分配方式是分配给一个字符的代码不是…...

编程日记 2023/4/29 12:26:45

async 与 await

目录一、async函数二、await表达式三、async与await结合一、async函数 函数的返回值为promise对象promise对象的结果由async函数执行的返回值决定 async function main(){//1.如果返回的是一个非promise类型的数据&#xff0c;那么返回的就是成功的状态// return 521//2.如果…...

编程日记 2023/4/29 23:41:04

MYSQL语句

在 Navicat Premium 里面test_database数据库 &#xff0c;右击 “命令列界面..” 命令列界面 中 输入命令 查看所有的数据库 show databases; 选择数据库 -- use 数据库名; use test_database; 创建表 creat table 表名(字段名1 数据类型,字段名2 数据类型) -- 创建…...

编程日记 2023/5/18 11:01:09

C语言函数：内存函数memcpy()以及实现

C语言函数&#xff1a;内存函数memcpy() 引言&#xff1a; #define _CRT_SECURE_NO_WARNINGS#include <stdlib.h>int main() {int arr1[20] { 1,2,3,4,5,6,7,8,9 };int arr2[20] { 0 };strcpy(arr2, arr1);return 0; } strcpy函数&#xff1a;C语言函数&#xff1a;字…...

编程日记 2023/4/30 1:26:50

ArcGIS基础：栅格分区转矢量再裁剪面图层【重分类】【栅格转面】

如上所示&#xff0c;是一个原始的栅格数据&#xff08;DEM&#xff09;&#xff0c;本操作将其转为矢量要素并裁剪另外的面图层 右键属性查看数据类型&#xff0c;可以发现此栅格数据属于【浮点型】&#xff0c;这里需要注意的是&#xff1a;栅格转为矢量数据时&#xff0c;必…...

编程日记 2023/4/29 6:56:40

vue尚品汇商城项目-day02【11.对axios二次封装+12.接口统一管理】

文章目录11.对axios二次封装11.1为什么需要进行二次封装axios&#xff1f;11.2在项目当中经常有API文件夹【axios】12.接口统一管理12.1跨域问题12.2接口统一管理12.3不同请求方式的src/api/index.js说明本人其他相关文章链接11.对axios二次封装 安装命令&#xff1a;cnpm inst…...

编程日记 2023/5/2 20:48:57