[数据结构] 哈希结构的哈希冲突解决哈希冲突

2024-09-08 04:28

本文主要是介绍[数据结构] 哈希结构的哈希冲突解决哈希冲突,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

标题:[C++] 哈希结构的哈希冲突 && 解决哈希冲突

@水墨不写bug



目录

一、引言

        1.哈希

        2.哈希冲突

        3.哈希函数

 二、解决哈希冲突

1.闭散列

 I,线性探测

II,二次探测

2.开散列


正文开始:

一、引言

        哈希表是一种非常实用而且好用的关联式容器,如果你刷过不少题,一定会惊叹哈希竟然能解决如此多的实际问题。

        但是哈希表令人头疼的问题是哈希冲突的问题。在具体讲解之前,我们先铺垫引入几个概念:哈希,哈希函数,哈希冲突。

        1.哈希

         哈希结构最明显的特点是高效。在以往的顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(log2 N),搜索的效率取决于搜索过程中元素的比较次数。

最优的搜索方法:不经过任何比较,一次直接从表中得到要搜索的元素。

        如果存在一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码(key)之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。

        当我们向该结构中:

插入元素的时候:根据插入元素的关键码,根据这个关键码来通过某种映射关系来得到哈希表中对应的存储位置,然后将这个元素存入哈希表的对应位置。

搜索元素的时候:对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在哈希表中按照此位置进行查找,若关键码相等,则搜索成功。

        这种存储结构和方法统称为哈希

        哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表).

        2.哈希冲突

        我们可以设计一个简单的哈希表:10个位置,哈希函数也是非常简单的除留取余(插入元素除以表的大小,就通过哈希函数得到了这个值应该在表中存储的位置):

        用该方法进行搜索可以一次找到存储对应值的位置,因此搜索的速度比较快。

但是,如果向上面这样的哈希表中插入14呢?

        我们发现14的位置被4占据了,这就是哈希冲突。

        即:不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。

        把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”.

        3.哈希函数

 引起哈希冲突的一个原因可能是:哈希函数设计不够合理。

哈希函数设计原则:

        1.哈希函数的定义域必须包括需要存储的全部关键码,同时如果散列表允许有m个地址时,其值域必须在0到m-1之间。

        2.哈希函数计算出来的地址能尽可能的均匀分布在整个空间中。

        3.哈希函数应该比较简单

         我们需要了解一下常见的哈希函数的设计方法:

1. 直接定址法

        取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B

        优点:简单、均匀、一般不会出现哈希冲突

        缺点:需要事先知道关键字的分布情况

        使用场景:适合查找比较小且连续的情况

2. 除留余数法.

        设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址.

        优点:适用情况广泛

        缺点:会出现哈希冲突,需要解决哈希冲突的问题

 二、解决哈希冲突

        哈希冲突的解决方法常用的有两种:闭散列与开散列。

1.闭散列

         闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。

        寻找下一个“空位置”也有多种方法,这里介绍常见的两种:线性探测,二次探测。

 I,线性探测

         在上面的例子中,我们想要插入14,本来14经过哈希函数计算得到的位置是4,但是4这个位置已经被占据了。

        线性探测就是:从发生冲突的位置开始,一个一个向后探测,直到寻找到下一个空位置为止。

        a.插入

        首先通过哈希函数获取待插入元素在哈希表中的位置。 如果该位置中没有元素则直接插入新元素;如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素:

        b.删除

        采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。

        比如:删除元素4,如果直接删除掉,14查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

        我们可以通过一个标记状态的变量来表示哈希表内的数据的状态:存在,删除,空(EXIST,DELETE,EMPTY):

enum STATE
{EXIST,DELETE,EMPTY
}    

        在封装哈希表中每一个数据的类型时,在每个数据结构体内加入一个表示状态的变量即可。对于一个哈希表的位置,如果没有元素插入过,状态为EMPTY;

        如果存在元素,状态为EXIST;

        如果原来存在元素,但是之后删除了,状态为DELETE;

不同的状态对于将来查找(find)的处理会有影响。 

II,二次探测

         通过了解上面的线性探测,你自然也会发现线性探测的困难:

        产生冲突的数据堆积在一块,这与其一个一个向下找空位置有关系,找空位置的方式就是挨着往后逐个去找.

        二次探测的找下一个空位置的方法就大不相同了:二次探测向下找的方式是依次加上位置差的平方:

H_i = (H_0 + i^2 )% m 或者H_i = (H_0 - i^2 )% m

        其中:i = 1,2,3…, H_0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。

        对于上面的例子,如果使用二次探测,插入的过程:

插入 44 的过程:
    1.44 的初始哈希值是  14 % 10 = 4 ,但是位置 4 已经被占用了。
    2.触发二次探测,从  i = 1  开始。对于  i = 1 ,探测位置是:(4 + 1^2) % 10 = 5 但位置 5 也被占用了。
    3.继续探测, i = 2  时,探测位置是:(4 + 2^2) % 10 = 8

位置 8 是空的,所以 14 被插入到位置 8。

        对于闭散列而言,哈希表是需要扩容的,因为我们每次插入的时候都需要保证哈希表有空余的位置,所以我们需要一个判断哈希表内数据 装满程度的标志因子:载荷因子

        载荷因子记为a,a越大,表明填入表中的数据越多,产生哈希冲突的可能就越大。反之则相反。

        对于开放定址法,载荷因子需要严格控制在0.7-0.8以下。当载荷因子接近这个值时,就需要扩容。

2.开散列

         开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中:

        

        当插入14时,对4这个位置的链表头插即可:

 

 以上是哈希结构解决哈希冲突的方法。


完~

未经作者同意禁止转载 

这篇关于[数据结构] 哈希结构的哈希冲突解决哈希冲突的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1147113

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

如何解决线上平台抽佣高 线下门店客流少的痛点!

目前,许多传统零售店铺正遭遇客源下降的难题。尽管广告推广能带来一定的客流,但其费用昂贵。鉴于此,众多零售商纷纷选择加入像美团、饿了么和抖音这样的大型在线平台,但这些平台的高佣金率导致了利润的大幅缩水。在这样的市场环境下,商家之间的合作网络逐渐成为一种有效的解决方案,通过资源和客户基础的共享,实现共同的利益增长。 以最近在上海兴起的一个跨行业合作平台为例,该平台融合了环保消费积分系统,在短

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

自定义类型:结构体(续)

目录 一. 结构体的内存对齐 1.1 为什么存在内存对齐? 1.2 修改默认对齐数 二. 结构体传参 三. 结构体实现位段 一. 结构体的内存对齐 在前面的文章里我们已经讲过一部分的内存对齐的知识,并举出了两个例子,我们再举出两个例子继续说明: struct S3{double a;int b;char c;};int mian(){printf("%zd\n",s

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

【VUE】跨域问题的概念,以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念 跨域问题是由于浏览器实施了同源策略,该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同,则需要服务器显式地允许这种跨域请求。一般在springbo

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In