Java之HashMap的底层实现

Java之HashMap的底层实现

  • 摘要
    • HashMap的底层原理
    • 哈希值转换为数组下标
    • 节点
    • 初始化
    • put(Object key, Object value)
    • 重写toString()
    • get(Object key)
    • 增加泛化
    • remove(K key)

摘要

本博客主要讲述了Java的HashMap的底层实现

HashMap的底层原理

底层原理:数组+链表
在这里插入图片描述
在这里插入图片描述
过程总结:每一个Object的有一个哈希值,通过hashCode()函数获取哈希值,再通过自定义的hash()函数,得到一个值,也就是数组的下标。数组中的每个元素都是一个链表或为空。

哈希值转换为数组下标

在这里插入图片描述

//这就是hash函数,val就是key的哈希值,即val = key.hashCode()
//length 必须是2的整数幂
private int  hash(int val, int length){return val & (length - 1);}

节点

定义链表中的节点

public class Node2 {int hash;//hash对应数组下标Object key;Object value;Node2 next;
}

初始化

//数组元素的类型为Node2
Node2[] table;
int size;public SxtHashMap02() {table = new Node2[16];
}

put(Object key, Object value)

public void put(Object key, Object value){Node2 newNode = new Node2();newNode.hash = hash(key.hashCode(),table.length);newNode.key = key;newNode.value = value;newNode.next = null;Node2 last = null;//这个学习一下,记录最后一个节点int index = hash(key.hashCode(),table.length);if(table[index] == null){table[index] = newNode;size ++;}else{Node2 tmp = table[index];while(tmp != null){if(key.equals(tmp.key)){System.out.println("key重复了");tmp.value = value;return;}else {last = tmp;tmp = tmp.next;}}last.next = newNode;size ++;//size的增加与减少不要忘记}}

重写toString()

public String toString() {StringBuilder sb = new StringBuilder();sb.append("[");for(int i = 0; i < table.length; i ++){Node2 temp = table[i];while(temp != null){sb.append(temp.key + ":" + temp.value + ",");temp = temp.next;}}//这个套路学一下,将最后改为']'sb.setCharAt(sb.length() - 1,']');return sb.toString();
}	

这个toString()有什么用呢?在使用system.out.println()打印的时候,就会用到toString()。

get(Object key)

//根据Map的底层原理,就十分简单
public Object get(Object key){int hashCode = key.hashCode();int hash = hash(hashCode,table.length);Node2 temp = table[hash];while(temp != null){if(temp.key.equals(key)) return temp.value;temp = temp.next;}return null;
}

增加泛化

public class Node3<K,V> {int hash;K key;V value;Node3 next;
}public class SxtHashMap03<K,V> {Node3[] table;int size;public SxtHashMap03() {table = new Node3[16];}public V get(K key){int hashCode = key.hashCode();int hash = hash(hashCode,table.length);V value = null;Node3 temp = table[hash];while(temp != null){if(temp.key.equals(key)){value = (V)temp.value;}temp = temp.next;}return value;}public void put(K key, V value){Node3 newNode = new Node3();newNode.hash = hash(key.hashCode(),table.length);newNode.key = key;newNode.value = value;newNode.next = null;Node3 last = null;int index = hash(key.hashCode(),table.length);if(table[index] == null){table[index] = newNode;size ++;}else{Node3 tmp = table[index];while(tmp != null){if(key.equals(tmp.key)){System.out.println("key重复了");tmp.value = value;return;}else {last = tmp;tmp = tmp.next;}}last.next = newNode;size ++;}}
}

remove(K key)

 public void remove(K key){int index = hash(key.hashCode(), table.length);Node3 temp = table[index];if(temp == null) return;if(temp.key.equals(key)){table[index] = temp.next;size --;return;}Node3 last = null;while(temp != null){if(temp.key.equals(key)){last.next = temp.next;size --;return;}last = temp;temp = temp.next;}
}

参考: 手工实现HashMap

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

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

相关文章

Golang | Leetcode Golang题解之第352题将数据流变为多个不相交区间

题目&#xff1a; 题解&#xff1a; type SummaryRanges struct {*redblacktree.Tree }func Constructor() SummaryRanges {return SummaryRanges{redblacktree.NewWithIntComparator()} }func (ranges *SummaryRanges) AddNum(val int) {// 找到 l0 最大的且满足 l0 < val…

Elasticsearch 使用误区之四——不合理的使用 track_total_hits

0、企业级实战问题 在使用 Elasticsearch 进行搜索时&#xff0c;我们常常关心匹配查询的文档总数而将 track_total_hits 设置为 true&#xff0c;如下截图所示&#xff0c;在数据量非常大的情况下这种检索导致的问题是&#xff1a;查询特别慢&#xff0c;聚合会更慢&#xff0…

机器学习:逻辑回归实现下采样和过采样

1、概述 逻辑回归本身是一种分类算法&#xff0c;它并不涉及下采样或过采样操作。然而&#xff0c;在处理不平衡数据集时&#xff0c;这些技术经常被用来改善模型的性能。下采样和过采样是两种常用的处理不平衡数据集的方法。 2、下采样 1、概念 下采样是通过减少数量较多的类…

MaxKB(二):Ubuntu24.04搭建maxkb开发环境

接上文&#xff1a;windows10搭建maxkb开发环境&#xff08;劝退指南&#xff09; 上文在windows10环境搭建maxkb开发环境遇到各种坑&#xff0c;后面就转战ubuntu平台&#xff0c;果然比较顺利的完成开发环境搭建。当然遇到相关的问题还是可以参考上文《windows10搭建maxkb开发…

Stable Diffusion赋能“黑神话”——助力悟空走进AI奇幻世界

《黑神话&#xff1a;悟空》是由游戏科学公司制作的以中国神话为背景的动作角色扮演游戏&#xff0c;将于2024年8月20日发售。玩家将扮演一位“天命人”&#xff0c;为了探寻昔日传说的真相&#xff0c;踏上一条充满危险与惊奇的西游之路。 同时&#xff0c;我们还可以借助AI绘…

向量数据库Faiss的搭建与使用

​ ​ 您好&#xff0c;我是程序员小羊&#xff01; 前言 向量数据库在处理大量高维数据时非常有用&#xff0c;尤其在机器学习、推荐系统、图像检索和自然语言处理等领域。Faiss是 Facebook AI Research (FAIR) 开发的一款高效的开源向量数据库&#xff0c;专注于大规模、高维…

SpringBoot整合Sharding-JDBC分库分表

SpringBoot整合Sharding-JDBC分库分表 本文介绍SpringBoot使用当当Sharding-JDBC进行分库分表。 1、有关Sharding-JDBC 有关Sharding-JDBC介绍这里就不在多说&#xff0c;之前Sharding-JDBC是当当网自研的关系型数据库的水平扩展框架&#xff0c;现 在已经捐献给Apache&…

macOS安装搭建python环境

安装Homebrew apt-get是一个常见于Debian和Ubuntu等基于Linux的操作系统中的包管理工具&#xff0c;用于安装、更新和移除软件包。然而&#xff0c;macOS使用的是Homebrew或者MacPorts等其他的包管理工具&#xff0c;并不使用apt-get。 如果你想在macOS上使用类似apt-get的功…

【大模型理论篇】大模型时代下Bert去哪啦?

这个标题是最近看到的一篇文章《What happened to BERT & T5? On Transformer Encoders, PrefixLM and Denoising Objectives》有感而发&#xff0c;也感觉很有意思。在几年前&#xff0c;在项目中还经常会用到Bert。本文主要回顾一下Bert的原理、Bert的继续训练和使用&am…

JavaScript高级程序设计 -- -- 观后记录

一、什么是 JavaScript 1、JavaScript 实现 完整的 JavaScript 实现包含以下几个部分&#xff1a; -- --  核心&#xff08;ECMAScript&#xff09;  文档对象模型&#xff08;DOM&#xff09;  浏览器对象模型&#xff08;BOM&#xff09; 2、DOM 文档对象模型&#…

UE5 datetime 创建日期时间节点 进行加法减法。个人理解

以下均为个人实验和个人理解&#xff0c;仅供参考。 目录 目标节点&#xff1a; 年月日 时分秒毫秒 目标节点&#xff1a; 年月日 年月日以1 为基底。若填的数字<0&#xff0c;该节点会失效。 试验&#xff1a; year基底为1&#xff0c;正常 year基底为0&#xff0c;异…

SpringBoot 整合 Excel 轻松实现数据自由导入导出

01、背景介绍 在实际的业务系统开发过程中&#xff0c;操作 Excel 实现数据的导入导出基本上是个非常常见的需求。 之前&#xff0c;我们有介绍一款非常好用的工具&#xff1a;EasyPoi&#xff0c;有读者提出在数据量大的情况下&#xff0c;EasyPoi 会占用内存大&#xff0c;…

k8s综合项目

一、准备环境 1.1 部署服务器 在centos7.9系统里搭建v1.23版本的k8s集群&#xff0c;准备四台服务器&#xff0c;两台作为master&#xff0c;主机名分别为 k8s-master和k8s-master-2&#xff0c;主机名为k8s-master&#xff0c;两台作为 node&#xff0c;主机名分别为k8s-nod…

11-sentinel利用nacos作持久化

本文介绍sentinel配置数据的持久化方法。由于sentinel官方并没有提供持久化功能&#xff0c;大家在测试过程中也能发现sentinel服务重启后&#xff0c;原来配置的数据就丢了&#xff0c;本文就是来处理这一问题的。 做好心理准备&#xff0c;我们要修改sentinel的源代码&#…

C++ | Leetcode C++题解之第350题两个数组的交集II

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());int length1 nums1.size(), length2 nums2…

【C++ 第十五章】map 和 set 的封装(封装红黑树)

1. map 和 set 的介绍 ⭐map 与 set 分别是STL中的两种序列式容器; 它们是一种树形数据结构的容器&#xff0c;且其的底层构造为一棵红黑树; 而在上一篇文章中提到,其实红黑树本身就是一棵二叉搜索树,是基于二叉搜索树的性质对其增加了平衡的属性来提高其综合性能 ⭐当然也…

【论文阅读】Retargeting and Respecializing GPU Workloads for Performance Portability

摘要 为了接近峰值性能&#xff0c;像gpu这样的加速设备需要大量的特定于架构的调优&#xff0c;以了解共享内存、并行性、tensor core等的可用性。不幸的是&#xff0c;对更高性能和更低成本的追求导致了架构设计的显著多样化&#xff0c;甚至是产自同一供应商的产品也是如此。…

Apache CloudStack Official Document 翻译节选(七)

关于 Apache CloudStack 的 最佳实践 &#xff08;一&#xff09; Best Practices 部署Apache CloudStack是极具挑战性的&#xff0c;在整个部署过程中需要你做出形形色色的技术性选择。Apache CloudStack的配置条目是相当灵活的&#xff0c;这是因为在组合和配置具体条目时有…

【深入浅出Docker】【三】Docker容器详解

文章目录 一. Docker容器简介二. Docker容器详解1. 容器vs虚拟机1.1. 虚拟机模型1.2. 容器模型1.3. 虚拟机的额外开销 2. 容器启动过程描述3. 容器进程4. 容器生命周期与文件保存5. 优雅地停止容器&#xff1a;两阶段方式停止并删除容器6. 利用重启策略进行容器的自我修复6.1. …

SpringBoot依赖之Spring Data Redis实现位图Bitmap

Spring Boot 项目中使用 Spring Data Redis 实现位图Bitmap 暂未发表&#xff0c;记录于20240820 概念 Spring Data Redis (AccessDriver) 依赖名称: Spring Data Redis (AccessDriver)功能描述: Advanced and thread-safe Java Redis client for synchronous, asynchronous,…