数据结构——哈希
哈希表 是一种使用哈希函数组织数据的数据结构,它支持快速插入和搜索。
哈希表(又称散列表)的原理为:借助 哈希函数,将键映射到存储桶地址。更确切地说,
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 表示虚数单位&…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
