泰州网站建设优化,wordpress源码整合,少儿编程哪个教育平台比较好,知名跨境电商平台有哪些标题#xff1a;[C] 哈希结构的哈希冲突 解决哈希冲突
水墨不写bug 目录
一、引言 1.哈希 2.哈希冲突 3.哈希函数 二、解决哈希冲突
1.闭散列 I#xff0c;线性探测
II#xff0c;二次探测
2.开散列 正文开始#xff1a;
一、引言 哈希表是一种非常实用而…标题[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. 直接定址法 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀、一般不会出现哈希冲突 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况 2. 除留余数法. 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址. 优点适用情况广泛 缺点会出现哈希冲突需要解决哈希冲突的问题 二、解决哈希冲突 哈希冲突的解决方法常用的有两种闭散列与开散列。
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。 对于闭散列而言哈希表是需要扩容的因为我们每次插入的时候都需要保证哈希表有空余的位置所以我们需要一个判断哈希表内数据 装满程度的标志因子载荷因子 载荷因子记为aa越大表明填入表中的数据越多产生哈希冲突的可能就越大。反之则相反。 对于开放定址法载荷因子需要严格控制在0.7-0.8以下。当载荷因子接近这个值时就需要扩容。 2.开散列 开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中: 当插入14时对4这个位置的链表头插即可 以上是哈希结构解决哈希冲突的方法。 完~
未经作者同意禁止转载
