数据结构——哈希
哈希表 是一种使用哈希函数组织数据的数据结构,它支持快速插入和搜索。
哈希表(又称散列表)的原理为:借助 哈希函数,将键映射到存储桶地址。更确切地说,
1.首先开辟一定长度的,具有连续物理地址的桶数组;
2.当我们插入一个新的键时,哈希函数将决定该键应该分配到哪个桶中,并将该键存储在相应的桶中;
3.当我们想要搜索一个键时,哈希表将使用哈希函数来找到对应的桶,并在该桶中进行搜索。
负载因子 又叫装填因子,是哈希表的一个重要参数,它反映了哈希表的装满程度。
实际利用桶的个数 与 桶的总数 的比值,称为负载因子。
哈希函数
哈希函数是哈希表中最重要的组件,用于将键映射到特定的桶。我们使用 y = x % 5 作为散列函数,其中 x 是键值,y 是映射之后对应的桶的索引。
冲突解决
一般情况下,哈希函数会起到压缩键的地址空间的作用,设键的地址空间为 S,桶的地址空间为 T,则有 S≫T。
因此,经过映射之后,不同的数据会不可避免地分配到同一个桶中,这时便产生了冲突。
线性试探法
线性试探法属于开放定址法的一种,所谓线性试探法,就是当插入键 key 时,如果发现桶单元 bucket[hash(key)] 已经被占用,则向下线性寻找,直到找到可以使用的空桶。具体说来,经过第 i 次试探之后,桶单元应为:bucket[(hash(key)+i) mod M], i=1,2,3…
链地址法
解决冲突的另一种办法是将桶内产生冲突的键串联成一个链表。
再哈希法
再哈希法比较典型的应用是双重哈希法,即发生冲突时,通过使用另一个哈希函数来避免冲突。
然而,双重哈希法同样存在一些问题:
1.与线性试探法相比,双重哈希法会消耗较多的时间。
2.在双重哈希法中,删除会使问题变复杂,如果逻辑删除数量太多,则应重新构造哈希表。
公共溢出区法
顾名思义,公共溢出区法就是建立另一个哈希表 dict_overflow 作为公共溢出区,当发成冲突时则将该键保存在该哈希表中。
简单哈希集合
#define MAX_LEN 100000 // 初始化桶的数量class MyHashSet {
private:vector<int> set[MAX_LEN]; // 使用数组实现哈希集合/** 返回对应的桶的索引 */int getIndex(int key) {return key % MAX_LEN;}/** 在特定的桶中搜索键,如果该键不存在则返回 -1 */int getPos(int key, int index) {// 每个桶中包含一个列表,遍历所有桶中的元素来寻找特定的键for (int i = 0; i < set[index].size(); ++i) {if (set[index][i] == key) {return i;}}return -1;}
public:MyHashSet() {}void add(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos < 0) {// 如果键不存在,则添加set[index].push_back(key);}}void remove(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos >= 0) {// 如果键存在,则删除set[index].erase(set[index].begin() + pos);}}bool contains(int key) {int index = getIndex(key);int pos = getPos(key, index);return pos >= 0;}
};
简单哈希映射
#define MAX_LEN 100000 // 初始化桶的数量class MyHashMap {
private:vector<pair<int, int>> map[MAX_LEN]; // 使用数组实现哈希集合/** 返回指定桶的索引 */int getIndex(int key) {return key % MAX_LEN;}/** 在桶中搜索键,如果不存在则返回 -1 */int getPos(int key, int index) {// 每个桶包含一个数组,遍历桶中的所有元素来查找指定的 keyfor (int i = 0; i < map[index].size(); ++i) {if (map[index][i].first == key) {return i;}}return -1;}public:MyHashMap() {}/** value 始终为正 */void put(int key, int value) {int index = getIndex(key);int pos = getPos(key, index);if (pos < 0) {map[index].push_back(make_pair(key, value));} else {map[index][pos].second = value;}}/** 如果存在映射关系,则返回 value,否则返回 -1 */int get(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos < 0) {return -1;} else {return map[index][pos].second;}}/** 如果存在 key 的映射,则删除该映射关系 */void remove(int key) {int index = getIndex(key);int pos = getPos(key, index);if (pos >= 0) {map[index].erase(map[index].begin() + pos);}}
};相关文章:
数据结构——哈希
哈希表 是一种使用哈希函数组织数据的数据结构,它支持快速插入和搜索。 哈希表(又称散列表)的原理为:借助 哈希函数,将键映射到存储桶地址。更确切地说, 1.首先开辟一定长度的,具有连续物理地址…...
效果好的it监控系统特点
一个好的IT监控系统应该具备以下特点: 全面性:IT监控系统应该能够监视和管理IT系统的所有方面,包括网络、服务器、应用程序和数据库等。这样可以确保系统的各个方面都得到充分的监视和管理。 可靠性:IT监控系统需要保持高可…...
leetcode1288. 删除被覆盖区间(java)
删除被覆盖区间 题目描述贪心法代码演示 题目描述 难度 - 中等 leetcode1288. 删除被覆盖区间 给你一个区间列表,请你删除列表中被其他区间所覆盖的区间。 只有当 c < a 且 b < d 时,我们才认为区间 [a,b) 被区间 [c,d) 覆盖。 在完成所有删除操作…...
Python 虚拟环境相关命令
一 激活 在 cd venv/scripts 进入虚拟环境 执行命令 activate 1、创建虚拟环境 $ python -m venv 2、激活虚拟环境 $ source <venv>/bin/activate 3、关闭虚拟环境 $ deactivate...
使用U盘同步WSL2中的git项目
1、将U盘挂载到WSL2中 假设U盘在windows资源管理器中被识别为F盘,需要在WSL2中创建一个目录挂载U盘 sudo mkdir /mnt/f sudo mount -t drvfs F: /mnt/f后续所有的操作都完成后,拔掉U盘前,可以使用下面的命令从WSL2中安全的移除U盘 umount …...
Stable Diffuse AI 绘画 之 ControlNet 插件及其对应模型的下载安装
Stable Diffuse AI 绘画 之 ControlNet 插件及其对应模型的下载安装 目录 Stable Diffuse AI 绘画 之 ControlNet 插件及其对应模型的下载安装 一、简单介绍 二、ControlNet 插件下载安装 三、ControlNet 插件模型下载安装 四、ControlNet 插件其他的下载安装方式 五、Co…...
CMAK学习
VS中的cmake_cmake vs_今天也要debug的博客-CSDN博客 利用vs2017 CMake开发跨平台C项目实战_cmake vs2017_神气爱哥的博客-CSDN博客 【【入门】在VS中使用CMake管理若干程序】https://www.bilibili.com/video/BV1iz4y117rZ?vd_source0aeb782d0b9c2e6b0e0cdea3e2121eba...
Python 推导式
Python 推导式 Python 推导式是一种独特的数据处理方式,可以从一个数据序列构建另一个新的数据序列的结构体。 Python 支持各种数据结构的推导式: 列表(list)推导式字典(dict)推导式集合(set)推导式元组(tuple)推导式 列表推导式 列表推导式格式为&…...
es6的新特性有哪些
ES6(ECMAScript 2015)是JavaScript的一个重要版本,引入了许多新的语法和功能。以下是ES6的一些主要特性: 块级作用域(Block Scope):引入了let和const关键字,可以在块级作用域中声明变…...
logstash 消费kafka数据,转发到tcp端口
1, logstash 配置文件 [roothost1: ] cat /opt/logstash/kafka-to-tcp.yml input { kafka {bootstrap_servers > "192.168.0.11:9092" #这里可以是kafka集群,如"192.168.149.101:9092,192.168.149.102:9092"consumer_threads &…...
航天智信:严控航天系统研发安全,助力建设“航天强国”
航天智信作为中国航天科工三院在信息装备领域“做大做强”的重要布局,主要从事系统运用与联合体系研究,复杂信息系统的顶层设计、总体论证及研制生产,提供体系级、系统级信息系统整体解决方案,以及信息安全系统的设计研发与集成验…...
阿里云2核4G服务器5M带宽五年租用价格表
阿里云2核4G服务器5M带宽可以选择轻量应用服务器或云服务器ECS,轻量2核4G4M带宽服务器297元一年,2核4G云服务器ECS可以选择计算型c7、c6或通用算力型u1实例等,买5年可以享受3折优惠,阿腾云分享阿里云服务器2核4G5M带宽五年费用表&…...
基于Laravel通用型内容建站企业官网系统源码 可免费商用
是一个基于 Laravel 企业内容建站系统。模块市场拥有丰富的功能应用,支持后台一键快速安装,让开发者能快的实现业务功能开发。 系统完全开源,免费且不限制商业使用 2023年08月23日增加了以下12个特性: [新功能] 手机端Banner支持…...
风力发电常见问题
目录 叶片失速 风力发电机失速状态是指风力发电机的叶片在高风速下无法继续提供升力,导致叶片停止旋转或减速旋转,从而降低了风力发电机的效率和发电能力。判断风力发电机是否处于失速状态通常可以通过以下方法: 监测风速:最简单…...
uniapp 解决跨域的问题
uniapp 解决跨域的问题 我真的是个 沙雕 找对了解决办法 写错了地方 "h5" : {"devServer" : {"disableHostCheck" : true,"https": false,"proxy" : {"/app" : {"target" : "https://192.16…...
Springboot GET和POST请求的常用参数获取方式
GET 使用RequestParam注解 可以在控制器方法的参数上使用RequestParam注解来获取请求中的参数值。例如: GetMapping("/example") public String example(RequestParam String param) {// 使用param参数的值return "Value of param: " param…...
项目(智慧教室)第四部分,页面交互功能
一。页面构思 1.标题栏 大标题:智慧教室管理系统 小标题:灯光,报警,风扇,温度,湿度,光照 2.样式设计 背景设置。字体设置(字体大小,格式,颜色) 3.…...
基于Matlab分析的电力系统可视化研究
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
MySQL为什么不推荐使用in
有的时候博客内容会有变动,首发博客是最新的,其他博客地址可能会未同步,认准https://blog.zysicyj.top 首发博客地址 系列文章地址 当使用IN语句时,MySQL可能会遇到以下问题: 索引问题:MySQL使用索引来加速查询&#x…...
python中的复数
在Python中,复数(Complex Numbers)是一种数值类型,用于表示具有实部和虚部的数值。复数由一个实部和一个虚部组成,形式为 a bj,其中 a 表示实部,b 表示虚部,而 j 表示虚数单位&…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...
Redis上篇--知识点总结
Redis上篇–解析 本文大部分知识整理自网上,在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库,Redis 的键值对中的 key 就是字符串对象,而 val…...
HTML中各种标签的作用
一、HTML文件主要标签结构及说明 1. <!DOCTYPE html> 作用:声明文档类型,告知浏览器这是 HTML5 文档。 必须:是。 2. <html lang“zh”>. </html> 作用:包裹整个网页内容,lang"z…...
