11 |「哈希表」简析

article/2024/4/13 15:00:55

前言

前言:刷「哈希表」高频面试题。

文章目录

  • 前言
  • 一、简介
    • 1、离散化
      • 1)什么是离散化
      • 2)离散化存储
      • 3)离散化映射
    • 2、哈希表
      • 1)什么是哈希表
      • 2)哈希表存储
      • 3)哈希函数
      • 4)哈希冲突
  • 二、参考链接

一、简介

1、离散化

1)什么是离散化

假设一个数组长度为 6,这 6 个元素的数据范围为 1-2000,数据元素范围远大于数组长度范围(2000 > 6)。

2)离散化存储

将 6 个数值差距很大的元素,放到离散化数组中,离散化数组的特点就是元素的下标与元素的内容是一致的。这种情况下,我们的离散化数组就会浪费了非常大的空间。

如下图所示,其中紫色数组原始数组黄色数组离散化之后的数组

3)离散化映射

实现映射即通过将几个分散存储的数据通过下标的方式聚合到一起,就可以通过下标访问被聚合到一起的离散化数据,离散化的对象就是每次访问数组的下标,如下图所示。


2、哈希表

1)什么是哈希表

前面讲的离散化需要先排序,效率较低。

哈希表又称散列表,一种以「key-value」形式存储数据的数据结构,哈希表同样是为了解决离散化的问题,时间复杂度为 O(1)O(1)O(1)

所谓以「key-value」形式存储数据,是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值,就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组,这种数组的下标可以是很大的整数浮点数字符串甚至结构体,如下图所示。

2)哈希表存储

哈希表存储的基本思路是:设要存储的元素个数为 n,设置一个长度为 m (m > n) 连续的内存单元,以每个元素的关键字 ki (1 ≤ i ≤ n),通过一个哈希函数 h 把 ki 映射为内存单元的地址 h(ki),并把该元素存储在内存单元中。

例如,我们可以开辟一个长度大于等于 n 的数组 a,并以 a[h(key)] = value 的方式来存储键值对 (key, value)

3)哈希函数

假设存在一个哈希函数(hash),作用是将一个大范围的数字映射到一个小范围的数字

例如,将一系列的数字与 100 取模,最终得到的映射值的范围为 0~99 ,则哈希函数为取模运算,同时哈希函数取模的数,最好取为质数。

但是存在一个问题。例如,101 % 100 = 11001 % 100 = 1,101 和 10001 映射到了同一个映射值,发生了冲突。

4)哈希冲突

解决哈希冲突如下如所示,创建一个数组,这个数组存储不同的映射值,每个映射值都连接一个链表,这个链表存储的都是具有相同映射值的原值。

这样的话,可以先去寻找映射后的值,找到对应的链表,再去遍历链表,得到对应的原值。


二、参考链接

[1]  https://blog.csdn.net/raelum/article/details/128793474

[2]  https://blog.csdn.net/weixin_72060925


http://www.ngui.cc/article/show-861247.html

相关文章

C++入门:运算符

运算符是一种告诉编译器执行特定的数学或逻辑操作的符号。C 内置了丰富的运算符,并提供了以下类型的运算符:算术运算符关系运算符逻辑运算符位运算符赋值运算符杂项运算符& :只有2个都为1,那么结果是1,否则为0&…

密钥格式梳理

文章目录各种密钥格式简介DERPyCryptodome源码参考PEMOpenSSL命令操作参考资料各种密钥格式简介 两种编码方式: .der:用ASN.1语法编码的der格式; .pem:用BASE64编码的密钥; # ASN.1 ------(序列化&…

【C++】对象与类

【C】对象与类 文章目录【C】对象与类1、定义1.1 对象的定义1.2 类的定义2、对象与类的创建2.1 类的创建2.2 对象的创建3、封装3.1 访问限定符3.2 对封装的解释4、类的实例化5、类、对象大小6、this指针6.1 this指针概念6.2 this指针特点1、定义 1.1 对象的定义 现实世界对对…

Spring Security 源码解读 :基本架构及初始化

Spring Security 是基于web的安全组件,所以一些相关类会分散在 spring-security包和web包中。Spring Security通过自定义Servlet的Filter的方式实现,具体架构可参考官网Spring Security: Architecture 这里使用Spring Boot 2.7.4版本,对应Sp…

MYSQL常用工具

1、字符串截取 substring(INDEX_NAME, 3, 2) -----------INDEX_NAME 2、String 转 Int CAST(INDEX_NAME AS SIGNED integer) ------------INDEX_NAME 3、时间格式化 date_format(INDEX_NAME, ‘%Y-%m-%d %H:%i:%s’) ----------------INDEX_NAME 4、IFNULL()、CASE-WHEN …

关于splitChunks的一次原理探索

前言 前端时间在做项目加载优化时用到了splitChunks自动拆包,后了解了一下原理写下了此文。 Modules和Chunks Modules简单来理解就是我们写的功能模块,不管是CommonJS还是ESM都算是一个Module,而Chunks则是webpack根据我们的规则/默认规则…

贝克制药冲刺上市:资产负债率高,抗乙肝制剂产品收入和占比下滑

2月3日,安徽贝克制药股份有限公司(下称“贝克制药”)在上海证券交易所递交招股书,准备在科创板上市,国元证券为其保荐机构。 本次冲刺上市,贝克制药计划募资14.20亿元,其中5.32亿元用于年产单方…

矿山安全生产监测预警系统 opencv

矿山安全生产监测预警系统通过pythonopencv网络模型计算机视觉技术,对现场画面中人的不安全行为”、“物的不安全状态”、“环境的不安全因素”三方面出发进行实时监测,当监测到现场画面中人员未穿反光衣行为、明火烟雾、未穿安全帽行为、矿车掉道识别、…

Mybatis一对多以及多对一

场景: 多个学生对应一个老师 如果对于学生这边,就是一个多对一的现象,即从学生这边关联一个老师! 数据库设计 CREATE TABLE teacher (id INT(10) NOT NULL,name VARCHAR(30) DEFAULT NULL,PRIMARY KEY (id) ) ENGINEINNODB DEF…

高质量有效编程笔记

来自李云的高质量有效编程电子书的摘抄,有些需要进一步实践 高质量有效编程笔记: 硬件部分 1、 微处理器、微控制器,从编程角度无区别。 2、 寄存器:通用寄存器GPR、浮点寄存器FPR 3、 通用寄存器GPR:执行指令、整数运…