关于Hash表,你不得不知道的知识点

定义:

哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,也称为hash函数,存放记录的数组叫做散列表。

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

基础概念:

  • 若关键字为k,则其值存放在f(k)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个思想建立的表为散列表。对于查找一个特定的key,我们仅仅需要进行常数次的运算(考虑到hash冲突)即可得到key对应的位置,因此hash表的查找复杂度为O(1)。

  • 对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)==f(k2),这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称做同义词。hash表的构造过程通常是:根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址区间上,并以关键字在地址区间中的“散列地址(hash值)”作为记录在表中的存储位置。

  • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数,这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

哈希函数:

将关键字映射为hash地址是通过哈希函数来实现的,不同的hash函数

通过将关键字(key)映射到表中一个位置, 可以直接访问记录, 以提高查找的速率,相比较其他的查找结构,哈希表查找的时间复杂度更低。其中用于映射的函数称为哈希函数, 哈希函数有多种,常见的哈希函数包括CRC32,MD5,SHA等。其实哈希函数就是一种特殊的函数,通过输入x,得到唯一的f(x),从而实现尽可能地降低对key对应得hash值得重复问题,减少哈希冲突发生的概率。

常见的hash函数有:

1.直接寻址法:取关键字或关键字的某个线性函数值为散列地址。

2. 数字分析法:分析一组数据,比如一组员工的出生年月日,这时就会发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。

3.平方取中法:当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。 

哈希冲突:

哈希冲突就是两个不同的key,经过哈希函数运算之后,得到了相同的hash值,再对值进行存储时,发现要存储的地址空间已被他值占用,此时发生冲突问题。产生哈希冲突的原因并不是因为我们选取的哈希函数不合理,而是因为我们进行运算的键key,可能性太多了,总会存在一些情况导致hash值出现相同。所以说,hash冲突时必然的,我们需要对哈希冲突进行处理。

小李和小王通过哈希函数的运算之后,映射到了哈希表下标为1的同一位置,此时发生hash碰撞。

常见解决方案:

拉链法

刚刚小李和小王在索引1的位置发生了冲突,发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了。这种解决哈希碰撞的方法就是拉链法,将发生碰撞的下标使用链表链接起来。

哈希表4

(数据规模是dataSize, 哈希表的大小为tableSize)

其实拉链法就是要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法,一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置,放了小李,那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ,要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示:

哈希表5

应用:

我们在写项目或者做算法的过程中,经常会使用到基于hash表实现的数据结构,对程序中的数据进行存储,以下是hash表常见的使用场景:

  1. 数据统计:一个字符或者数字出现了几次,
  2. 快速查找:快速查找某一个键对应着值的情况。

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

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

相关文章

如何在huggingface上申请下载使用llama2/3模型

1. 在对应模型的huggingface页面上提交申请 搜索对应的模型型号 登录huggingface,在模型详情页面上,找到这个表单,填写内容,提交申请。需要使用梯子,country填写梯子的位置吧(比如美国) 等待一小时左右…

非接触式IC卡简介

简介:非接触式IC卡又称射频卡,由IC芯片、感应天线组成,封装在一个标准的PVC卡片内,芯片及天线无任何外露部分。是世界上最近几年发展起来的一项新技术,它成功的将射频识别技术和IC卡技术结合起来,结束了无源(卡中无电源)和免接触这一难题,是电…

【Java】入门

笔者是在C语言基础上学习java 安装Java的过程中我们可能会见到这样几个东西,JVM、JRE、JDK,那它们的关系是怎样的呢? -JVM Java Virtual Machine 是Java虚拟机,Java程序需要运行在虚拟机上,不同的平台有自己的虚拟机…

Linux FT260驱动内核学习笔记

目录 1. 安装ft260驱动 2. 编译ft260源码 3. 通过sysfs配置ft260设备 3.1 多功能GPIO配置 3.2 控制GPIO 3.3 配置i2c总线频率 4. UART 5. 使用i2c-tools交互I2C设备 5.1 安装i2c-tools 5.2 探测I2C设备 5.3 读取所有寄存器数据 5.4 读取和写入 5.5 16位地址的读写…

蓝桥杯-线性动态规划问题背包问题进阶策略详解-

题目&#xff1a;蓝桥云课-青蛙吃虫 解题代码&#xff1a; #include <iostream> #include<cstring> #include<algorithm> using namespace std;const int N106;int f[N][N]; int a[N]; int t,l,r,k,n;int main() {cin>>t;while(t--){scanf("%d%…

ASP.NET一种基于C2C模式的网上购物系统的设计与实现

摘 要 网络购物已经慢慢地从一个新鲜的事物逐渐变成日常生活的一部分&#xff0c;以其特殊的优势而逐渐深入人心。本课题是设计开发一种基于C2C模式的网上购物系统。让各用户使用浏览器进行商品浏览。注册用户可以轻松的展示自己的网络商店&#xff0c;能对自己的用户信息进行…

Sping源码(七)—ConfigurationClassPostProcessor ——@PropertySources解析

序言 先来简单回顾一下ConfigurationClassPostProcessor大致的一个处理流程&#xff0c;再来详细的讲解PropertySources注解的处理逻辑。 详细的步骤可参考ConfigurationClassPostProcessor这篇帖子。 流程图 从获取所有BeanDefinition -> 过滤、赋值、遍历 -> 解析 -&…

璞华科技中标苏州工业园区“科技发展公司运营管理系统”升级改造项目

近日&#xff0c;璞华科技中标苏州工业园区科技发展有限公司“科技发展公司运营管理系统”升级改造项目。 苏州工业园区科技发展有限公司成立于2000年&#xff0c;是苏州工业园区管委会直属国有企业&#xff0c;聚焦以人工智能为引领的数字经济产业创新集群&#xff0c;重点布局…

Web自动化 - selenium

文章目录 一、selenium的使用selenium的安装 二、元素1. 定位选择元素1.id 定位2. class_name 定位find_element 和 find_elements的区别3. TAG_NAME 定位4. 超链接 定位 2. 操控元素1. 查询内容2. 获取元素文本内容3. 获取元素属性 3. 浏览器常用操作API4. 鼠标操作 - perform…

17 M-LAG 配置思路

16 华三数据中心最流行的技术 M-LAG-CSDN博客 M-LAG 配置思路 什么是M-LAG&#xff1f;为什么需要M-LAG&#xff1f; - 华为 (huawei.com) 1 配置 M-LAG 的固定的MAC地址 [SW-MLAG]m-lag system-mac 2-2-2 2 配置M-LAG 的系统标识符系统范围1到2 [SW-MLAG]m-lag system-nu…

【算法】动态规划之线性DP问题

前言&#xff1a; 本系列是看的B站董晓老师所讲的知识点做的笔记 董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com) 树塔-记忆化搜索 特点&#xff08;前提&#xff09;&#xff1a;从上向下的累加和是不能重复使用的&#xff0c;从下向上的累加和是可以重…

人民币汇率相关历史数据集(2006-2022年)

01、数据简介 汇率指的是两种货币之间兑换的比率&#xff0c;亦可视为一个国家的货币对另一种货币的价值。具体来说&#xff0c;汇率亦可视为一个国家的两种货币之间所存在的兑换比率&#xff0c;亦可视为一个国家的货币对另一种货币的价值。汇率的变动对一国的进出口贸易有着…

k8s 数据流向 与 核心概念详细介绍

目录 一 k8s 数据流向 1&#xff0c;超级详细版 2&#xff0c;核心主键及含义 3&#xff0c;K8S 创建Pod 流程 4&#xff0c;用户访问流程 二 Kubernetes 核心概念 1&#xff0c;Pod 1.1 Pod 是什么 1.2 pod 与容器的关系 1.3 pod中容器 的通信 2&#xff0c; …

94、动态规划-最长公共子序列

递归的基本思路&#xff1a; 比较两个字符串的最后一个字符。如果相同&#xff0c;则这个字符一定属于最长公共子序列&#xff0c;然后在剩余的字符串上递归求解。如果最后一个字符不相同&#xff0c;则分两种情况递归求解&#xff1a; 去掉 text1 的最后一个字符&#xff0c;保…

中国当代最具影响力的人物颜廷利:死神(死亡)并不可怕,可怕的是…

中国当代最具影响力的人物颜廷利&#xff1a;死神&#xff08;死亡&#xff09;并不可怕&#xff0c;可怕的是… 在中国优秀传统文化之中&#xff0c;汉语‘巳’字与‘四’同音&#xff0c;在阿拉伯数字里面&#xff0c;通常用‘4’来表示&#xff1b; 作为汉语‘九’字&#x…

mysql设置远程访问权限,允许其他IP访问

文章目录 更改mysql配置文件登录mysql 更改mysql配置文件 查找.ini或者.cnf文件 更改bind-address为0.0.0.0 [mysqld] character-set-serverutf8mb4 bind-address0.0.0.0 default-storage-engineINNODB [mysql] default-character-setutf8mb4 [client] default-character-s…

【getopt函数用法】

这里写目录标题 一、概述二、选项字符串规则&#xff1a;三、getopt 返回值四、会用到的全局变量&#xff1a;三、示例代码四、上机实验 一、概述 int getopt(int argc, char * const argv[], const char *optstring); extern char *optarg; //这个最常用&#xff0c;保存一个…

conan2 基础入门(06)-conanfile.py入门

conan2 基础入门(06)-conanfile.py入门 文章目录 conan2 基础入门(06)-conanfile.py入门⭐准备预备文件和Code ⭐使用流程指令 ⭐具体讲解conanfile.pyconan install END视频教学 ⭐准备 注意&#xff0c;如果想跟好的学习conanfile.py建议使用python来安装conan。 当然使用其…

C++之STL-priority_queue和仿函数的讲解

目录 一、priority_queue的介绍和使用 1.1 priority_queue的介绍 1.2 priority_queue的基本接口 二、仿函数的介绍 2.1 基本概念 2.2 适用场景 三、模拟实现priority_queue 3.1 向上调整算法 3.2 向下调整算法 3.3 整体框架 一、priority_queue的介绍和使用 1.1 prio…

U盘文件遇损?拯救“文件或目录损坏且无法读取”的秘籍!

在数字化时代&#xff0c;U盘已成为我们日常生活与工作中不可或缺的数据存储和传输工具。然而&#xff0c;有时我们可能会遇到一个非常令人沮丧的问题——U盘中的文件或目录突然损坏且无法读取。这种突发状况往往让人措手不及&#xff0c;甚至可能引发数据丢失的严重后果。那么…