首页 > 其他分享 >散列函数之冲突处理之开地址法

散列函数之冲突处理之开地址法

时间:2022-12-19 18:05:51浏览次数:40  
标签:之开 hash H0 探测 地址 key 散列


开地址法

基本思想:当关键码key的哈希地址H0 = hash(key)出现冲突时,以H0为基础,产生另一个哈希地址H1 ,如果H1仍然冲突,再以H0

为基础,产生另一个哈希地址H2 ,…,直到找出一个不冲突的哈希地址Hi ,将相应元素存入其中。这种方法有一个通用的再散列函

数形式: 

散列函数之冲突处理之开地址法_散列函数

其中H0 为hash(key) ,m为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下四种:

线性探测再散列

二次探测再散列

伪随机探测再散列

双散列法

(一)、线性探测再散列


散列函数之冲突处理之开地址法_结点_02

假设给出一组表项,它们的关键码为 Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly。采用的散列函数是:取其第一个字母在

字母表中的位置。 


          hash (x) = ord (x) - ord (‘A’) 

这样,可得

hash (Burke) = 1hash (Ekers) = 4

hash (Broad) = 1hash (Blum) = 1

hash (Attlee) = 0hash (Hecht) = 7

hash (Alton) = 0hash (Ederly) = 4

又设散列表为HT[26],m = 26。采用线性探查法处理溢出,则上述关键码在散列表中散列位置如图所示。红色括号内的数字表示找

到空桶时的探测次数。比如轮到放置Blum 的时候,探测位置1,被占据,接着向下探测位置2还是不行,最后放置在位置3,总的探

测次数是3。


散列函数之冲突处理之开地址法_散列表_03


堆积现象

散列地址不同的结点争夺同一个后继散列地址的现象称为堆积(Clustering),比如ALton 本来位置是0,直到探测了6次才找到合适位

置5。这将造成不是同义词的结点也处在同一个探测序列中,从而增加了探测序列长度,即增加了查找时间。若散列函数不好、或装

填因子a 过大,都会使堆积现象加剧。

下面给出具体的实现代码,大体跟前面讲过的​​链地址法​​差异不大,只是利用的结构不同,如下:


散列函数之冲突处理之开地址法_结点_04

status 保存状态,有EMPTY, DELETED, ACTIVE,删除的时候只是逻辑删除,即将状态置为DELETED,当插入新的key 时,只要不

是ACTIVE 的位置都是可以放入,如果是DELETED位置,需要将原来元素先释放free掉,再插入。

二次探测再散列

为改善“堆积”问题,减少为完成搜索所需的平均探查次数,可使用二次探测法。

通过某一个散列函数对表项的关键码 x 进行计算,得到桶号,它是一个非负整数。 


散列函数之冲突处理之开地址法_散列表_05

若设表的长度为TableSize = 23,则在​​线性探测再散列​​ 举的例子中利用二次探查法所得到的散列结果如图所示。


散列函数之冲突处理之开地址法_结点_06

比如轮到放置Blum 的时候,本来应该是位置1,已经被Burke 占据,接着探测 H0 + 1 = 2,,发现被Broad 占据,接着探测 H0 - 1 = 

0,发现空位于是放进去,探测次数为3。

下面来看具体代码实现,跟前面讲过的​​线性探测再散列​​ 差不多,只是探测的方法不同,但使用的数据结构也有点不一样,此外还实

现了开裂,如果装载因子 a > 1/2; 则建立新表,将旧表内容拷贝过去,所以hash_t 结构体需要再保存一个size 成员,同样的原因,

为了将旧表内容拷贝过去,hash_node_t 结构体需要再保存 *key 和 *value 的size。


散列函数之冲突处理之开地址法_结点_07



标签:之开,hash,H0,探测,地址,key,散列
From: https://blog.51cto.com/u_15917617/5953450

相关文章

  • git修改远程仓库地址
    修改远程仓库的地址:1、先把当前远程仓库地址删除(删除原有仓库)gitremotermorigin2、添加新的仓库地址(更换的新地址)gitremoteaddorigingit@url......
  • 网络私有IP地址
    A类的:10.0.0.0-10.255.255.255B类的:172.16.0.0-172.31.255.255C类的:192.168.0.0~192.168.255.255以上这些地址都是专用IP地址,不用于公网(互联网)只能用于内网也就是本地局......
  • (转载)ASLR 地址空间随机化
    ASLR,全称为AddressSpaceLayoutRandomization,地址空间布局随机化。该技术在kernel2.6.12中被引入到Linux系统,它将进程的某些内存空间地址进行随机化来增大入侵者预......
  • idea等工具网盘下载地址
    1.idea2020下载地址:https://caiyun.139.com/m/i?1E5C2SkIZbJH4,下载密码微信搜索“白菜拼吧”回复idea2020获取2.secureCRT绿色版下载地址:https://wwb.lanzou......
  • 如何根据IP地址段及掩码计算ACL策略中的通配符
    我们直接通过例子来说明如何计算通配符实例1 172.16.144.17/19第一步计算网络号19=8+8+3,第三字节网络号为前3位,第3字节的块大小为255-128-64-32+1=32144=128(2^7)+16(......
  • ollydbg中加载的DLL基地址确定 IDA里IDA:Edit->segments->Rebase program去设置同步
    ollydbg在工具栏E里点击,找到加载的DLL,可以看到基地址,例如下面的就是6CBE0000,IDA里IDA:Edit->segments->Rebaseprogram去设置同步即可!      好了下面是一些......
  • Postman配置多环境请求地址
    在使用Postman测试接口时,一个项目往往有多个环境(测试、正式等),请求不同环境的接口一般只是IP和端口不一样。这时候我们可以定义多个环境变量,在接口地址中进行引用。一、添......
  • 3、修改docker-compose-sonic.yml文件的2处IP地址
    docker-compose-sonic.yml文件:version:'3'services:sonic-mysql:image:"mysql:5.7"hostname:sonic-mysqlcommand:mysqld--character-set-server......
  • IP地址\端口和协议
    IP地址IP地址,类似生活中的地址,代表的是网络设备在网络中的具体位置,用于访问设备而用.就网络而言,普遍分为局域网和公网.端口计算机中通过端口来区分不同的服务.外面通......
  • KB0001.修改DoraCloud管理系统的IP地址
    KB0001.修改DoraCloud管理系统的IP地址DoraCloud管理系统是一个CentOSLinux的虚拟机。我们既可以通过DoraCloud后台管理系统修改它的IP地址,也可以通过CentOS命令修改它......