HashMap实现原理

news/2024/3/29 13:51:44/文章来源:https://blog.csdn.net/fggdgh/article/details/130291923

HashMap是基于散列表的Map接口的实现。插入和查询的性能消耗是固定的。可以通过构造器设置容量负载因子,一调整容易得性能。

散列表:给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。HashMap中散列表由数组实现。

容量:散列表数组的长度。

负载因子:散列表中当前存储的项/容量。HashMap默认使用的负载因子是0.75。

HashMap是键-值对结构。HashMap的键不能重复(可以是null),而值可以重复。在Java中如果一个类作为HashMap的key要能正确的工作,那么这个类就需要同时实现hashCode()方法和equals()方法。

HashMap使用equals()判断当前键是否与表中存在的键相同。使用hashCode()生成散列码。hashCode()就是散列函数(也称为哈希函数)。

正确的equals()方法必须满足下列5个条件:

  • 自反性:对任意x,x.equals(x)一定返回true
  • 对称性:对任意x,y,如果x.equals(y)返回true,则y.equals(x)也返回true
  • 传递性:对任意x,y,z,如果x.equals(y)返回true,y.equals(z)返回true,那么x.equals(z)也返回true
  • 一致性:对任意x,y,如果对象中用于等价等价比较的信息没有改变,那么无论调用x.equals(y)多少次,返回的结果应该保持一致。
  • 对任何不是null的x,x.equlas(null)一定返回false

HashMap通过散列的方式决定如何存储以达到更快的查找速度。

首先看一下HashMap是如何表示一个键-值对的对象的。

Map.java

public interface Map<K, V> {interface Entry<K, V> {K getKey();V getValue();V setValue(V value);boolean equals(Object o);int hashCode();/// ......}/// ......
}

Map.java中定义了Entry<K, V>接口表示一个键-值对。具体的实现由Map的实现类定义。

HashMap.java

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {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;}public final K getKey()        { return key; }public final V getValue()      { return value; }public final String toString() { return key + "=" + value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}public final boolean equals(Object o) {if (o == this)return true;return o instanceof Map.Entry<?, ?> e&& Objects.equals(key, e.getKey())&& Objects.equals(value, e.getValue());}}/// ......
}

HashMap基于散列表实现,在Java中使用一个数组表示散列表。通过散列将键信息(就是Map.Entry<K,V>对象)保存在数组中。散列通过键对象生成一个数字,将其作为数组的下标。这个数字就是散列码

在调用HashMap的put方法时,首先通过散列计算散列码得到数组的下标,然后查询指定下标的数组位置上是否有值(Map.Entry<K,V>),如果没有值则将put的键-值对生成Map.Entry<K,V>对象存在该位置。如果有值则对比当前put的值是否已经存在,如果存在则替换,不存在则将put的键-值对生成Map.Entry<K,V>对象添加到最后一个Map.Entry<K,V>next域上。

在调用HashMap的get方法时,同样先计算散列码得到数组的下标然后查询该位置的值,如果不存在则返回null,存则查找**Map.Entry<K,V>**链,直到找到对应键的值返回。

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

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

相关文章

确定因果随机森林的树木数量 the number of trees

前言 推断因果性和分析异质性是统计学家在处理混杂任务中的圣杯。传统且主流的方法有:倾向性评分、分层分享、比例风险模型等。新的方法也有很多,代表就是:因果随机森林。这种算法,浅看难度一般,深入探索发现坑还是很多的。这篇博客不对算法做深入探讨,仅仅是我在阅读文…

Nautilus Chain :基于模块化架构的Layer3正在走向成熟

Nautilus Chain 是一个基于 Eclipse 和 Celestia 构建的模块化 Layer3 链。作为定位在 Layer0 的链基建概念&#xff0c;Eclipse 和 Celestia 为面向未来的区块链扩容技术提供了一套开发工具和基础框架。尽管这种前沿技术过去一直处于概念验证阶段&#xff0c;尚未推出适用于大…

Java并发(三)----创建线程的三种方式及查看进程线程

一、直接使用 Thread // 创建线程对象 Thread t new Thread() {public void run() {// 要执行的任务} }; // 启动线程 t.start(); 例如&#xff1a; // 构造方法的参数是给线程指定名字&#xff0c;推荐 Thread t1 new Thread("t1") {Override// run 方法内实现…

手把手教你PXE高效网络装机、Kickstart无人值守安装(详细版)

目录 一、部署PXE远程安装服务1.1PXE定义1.2PXE服务优点1.3搭建网络体系前提条件1.4 搭建PXE远程安装服务器 二. 实验2.1 服务器操作2.2 安装启动TFTP服务并修改TFTP服务的配置文件2.3 安装并启用DHCP服务2.4 准备linux内核&#xff0c;初始化镜像文件2.5 准备PXE引导程序2.6 安…

22、Tweak原理及部分逆向防护

一、Tweak原理 1.1 Tweak产物.dylib 执行make命令时,在 .theos的隐藏目录中,编译出obj/debug目录,包含 arm64、arm64e两种架构,同时生成readbadges.dylib动态库 在arm64、arm64e目录下,有各自架构的readbadges.dylib,而debug目录下的readbadges.dylib,是一个胖二进制文件 fi…

【Java-01】深入浅出匿名对象 , 继承 , 抽象类

主要内容 面向对象回顾 匿名对象介绍 面向对象特征 - 继承 抽象类的使用 模板设计模式 1 面向对象回顾 面向对象的核心思想是什么 ? 用代码来模拟现实生活中的事物 , 比如学生类表示学生事物 , 对象表示的就是具体的学生 , 有了类就可以描述万千世界所有的事物了 现有的…

看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题142环形链表II) 2023.4.24

目录 前言算法题&#xff08;LeetCode刷题142环形链表II&#xff09;—&#xff08;保姆级别讲解&#xff09;分析题目&#xff1a;算法思想环形链表II代码&#xff1a;补充 结束语 前言 本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可&#xff0c;撰写…

前端食堂技术周刊第 80 期:Vite 4.3、Node.js 20、TS 5.1 Beta、Windi CSS 即将落幕

美味值&#xff1a;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f; 口味&#xff1a;东坡肉 食堂技术周刊仓库地址&#xff1a;https://github.com/Geekhyt/weekly 本期摘要 Vite 4.3Node.js 20TypeScript 5.1 BetaWindi CSS 即将落幕Pretty TypeScri…

中医脉诊仪:结合传统与现代技术的诊断工具

一、引言 随着科技的不断发展&#xff0c;医学领域也取得了举世瞩目的进步。中医作为一种古老的医学体系&#xff0c;始终保持着其独特的魅力。脉诊作为中医诊断的重要方法之一&#xff0c;历经千年的发展和传承&#xff0c;如今在现代科技的助力下&#xff0c;诞生了中医脉诊…

信息安全复习六:公开密钥密码学

一、章节梗概 1.公开密钥密码模型的基本原理 2.两个算法&#xff1a;RSA&D-H算法 主要内容 1.对称密钥密码的密钥交换问题 2.公钥密码模型的提出 3.设计公钥密码的基本要求 4.数字签名 5.RSA算法 6.公钥密码的特征总结 二、对称密钥密码 对称加密算法中&#xff0c;数据…

实例分割算法BlendMask

实例分割算法BlendMask 论文地址&#xff1a;https://arxiv.org/abs/2001.00309 github代码&#xff1a;https://github.com/aim-uofa/AdelaiDet 我的个人空间&#xff1a;我的个人空间 密集实例分割 ​ 密集实例分割主要分为自上而下top-down与自下而上bottom-up两类方法…

基于趋动云的chatGLM-6B模型的部署

首先根据官方示例教程&#xff0c;学会怎么创建项目&#xff0c;怎么使用数据&#xff0c;怎么进入开发环境&#xff0c;以及了解最重要的2个环境变量&#xff1a; 这个是进入开发环境以后的代码目录 $GEMINI_CODE 这个是引用数据集后&#xff0c;数据集存放的路径 $GEMINI_DA…

Linux内核进程管理与调度:策略优化与实践分析

Linux内核进程管理与调度 一、前言二、进程管理和多进程调度2.1 进程标识符和控制块2.2 进程状态和转换2.3 进程间通信 三、单处理器下的Linux进程调度3.1 Linux进程调度器3.2 时间片轮转调度算法3.3 最短剩余时间优先调度算法3.4 其他调度算法的不足 四、多处理器下的Linux进程…

Layui 2.8.0 正式发布,朴实归来

Layui 是一套开源的 Web UI 组件库&#xff0c;采用自身轻量级模块化规范&#xff0c;遵循原生态的 HTML/CSS/JavaScript 开发模式&#xff0c;极易上手&#xff0c;拿来即用。其风格简约轻盈&#xff0c;而内在雅致丰盈&#xff0c;甚至包括文档在内的每一处细节都经过精心雕琢…

【Linux网络】PXE高效批量网络装机

PEX高效批量网络装机 一、部署PXE远程安装服务1.1PXE的优点1.2搭建PXE网络体系的前提条件 二、实现Kincksatrt无人值守安装2.1实验思路&#xff0c;2.2实验&#xff1a;无人值守远程安装2.2.1实现 Kickstart 无人值守安装 一、部署PXE远程安装服务 PXE&#xff08;预启动执行环…

Flutter ListView组件详解

今天是2023年4月24日 今天重新复习了一下关于ListView的内容&#xff0c;现在就重新整理一下关于ListView的内容和理解 : (1)ListView和Column之间有什么区别&#xff1f; 在我理解中ListView和Column都是可以有很多子组件的组件&#xff0c;它们之间区别在于它们排列的形式和…

100天涨薪4k,从功能测试到自动化测试,我整理的3000字超全学习指南

去年6月份&#xff0c;由于经济压力让我下定决心进阶自动化测试&#xff0c;已经24的我做了3年功能测试&#xff0c;坐标广州薪资定格在8k&#xff0c;可能是生活过的太安逸&#xff0c;觉得8000的工资也够了&#xff0c;但是生活总是多变的&#xff0c;女朋友的突然怀孕&#…

Bsah shell的操作环境

文章目录 Bsah shell的操作环境路径与命令查找顺序使用案例 bash的登录与欢迎信息&#xff1a;/etc/issue、/etc/motdbash的环境配置文件如下login与non-login shell/etc/profile(login shell 才会读)~/.bash_profile(login shell 才会读)source&#xff1a;读入环境配置文件的…

上新了丨高性价比5G智能模组,美格智能SRM700正式发布

伴随着5G、AI、云计算等技术与物联网技术的融合发展&#xff0c;一个万物智联的智能世界正在到来。5G已经成为数字经济重要的基础设施&#xff0c;千行百业的用户都需要依靠高速率、大带宽、低延时的5G技术来构建数字化转型能力。 作为全球领先的无线通信模组及解决方案提供商…

51单片机(一)软硬件环境和单片机介绍

❤️ 专栏简介&#xff1a;本专栏记录了从零学习单片机的过程&#xff0c;其中包括51单片机和STM32单片机两部分&#xff1b;建议先学习51单片机&#xff0c;其实STM32等高级单片机的基础&#xff1b;这样再学习STM32时才能融会贯通。 ☀️ 专栏适用人群 &#xff1a;适用于想要…