开放地址法

简介: 开放地址法

开放地址法

根据以上hash函数计算数组下标时,当遇到数据存放的冲突时就需要重新找到数组的其他位置。关于开放地址法通常需要有三种方法:线性探测、二次探测、再哈希法。

1.开放地址法:容易产生堆积问题;不适于大规模的数据存储;散列函数的设计对冲突会有很大的影响;插入时可能会出现多次冲突的现象,删除的元素是多个冲突元素中的一个,需要对后面的元素作处理,实现较复杂;结点规模很大时会浪费很多空间;

2.链地址法:处理冲突简单,且无堆积现象,平均查找长度短;链表中的结点是动态申请的,适合构造表不能确定长度的情况;相对而言,拉链法的指针域可以忽略不计,因此较开放地址法更加节省空间。插入结点应该在链首,删除结点比较方便,只需调整指针而不需要对其他冲突元素作调整。

开放地址法只要有三种:

线性探测

方法 就是线性探测空白单元。当数据通过哈希函数计算应该放在700这个位置,但是700这个位置已经有数据了,那么接下来就应该查看701位置是否空闲,再查看702位置,依次类推。需要注意的是:当哈希表中接近被填满时,向表中插入数据就会效率很低,当hash表真的被填满了,这时候算法应该停止,在这之前应该对数组进行扩展,对hash表中的数据进行转移。

聚集

当哈希表越来越满时聚集越来越严重,这导致产生非常长的探测长度,后续的数据插入将会非常费时。通常数据超过三分之二满时性能下降严重,因此设计哈希表关键确保不会超过这个数据容量的一半,最多不超过三分之二。

线性探测的操作流程

线性探测就是使用算术取余的方法计算余数,当产生冲突时就通过线性递增的方法进行探测,一直到数组的位置为空,插入数据项即可。

二次探测

二次探测是过程是x+1,x+4,x+9,以此类推。二次探测的步数是原始位置相隔的步数的平方。

这是有一个算法 Hi=(H(key)+di) di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...kk,-kk(k<=m/2)其中m为表长,di为增量序列

如果di值可能为1,2的平方,3的平方,...,称 二次探测再散列 。

意思就是x为最初算出来的hash值,如果位置上有值了,就加1或者减1或者加2或者减2依次递推;

二次探测可以消除在线性探测中产生的聚集问题,但是二次探测还是会产生一种更明确更细的聚集。二次聚集的产生是在二次探测的基础上产生的现象。例如N个数据经hash函数计算后都映射到到数组下标10,探测第二个数字需要以一步长,第三个数字需要以4步长为单位,第四个数字则需要以九为步长。好在二次探测并不常用,解决聚集问题还是有一种更好的办法:再哈希法。

再哈希法

再哈希是把关键字用不同的哈希函数再做一遍哈希化,用这个结果作为步长,对指定的关键字,探测的步长是不变的,可以说不同的关键字可以使用不同的步长,并且步长可以控制。一般来说,再哈希函数可以采用以下这种:

虽然不同的关键字可能会映射到相同的数组单元,但是可能会有不一样的探测步长。假设可以使用步长1~5进行探测。步长是不能为零的,不然就会形成死循环。再哈希的实现方式可以在线性探测的基础上添加一个再哈希函数即可.

相关文章
|
7月前
|
安全 Windows
服务器中如何检查端口是否开放
服务器中如何检查端口是否开放
|
6月前
|
网络协议 Java 网络安全
如何查看端口是否开放
如何查看端口是否开放
|
6月前
|
安全 网络协议 定位技术
如何简单快速获取公网IP地址:在线工具推荐
如何简单快速获取公网IP地址:在线工具推荐
1460 0
|
6月前
|
安全 网络安全 网络架构
IP地址的主要功能
IP地址是网络设备的唯一标识,用于数据包路由、网络通信、互操作性、安全管理和全球信息共享。它们确保数据准确传输,支持路由决策,允许设备安全互动,并打破地域限制。IP地址在不断发展的网络世界中扮演着核心角色。
|
网络协议 中间件 物联网
网络基础学习:ip地址的知识
网络基础学习:ip地址的知识
157 0
|
网络协议
iptables 开放所有端口, 对特殊端口只开放给指定IP
iptables 开放所有端口, 对特殊端口只开放给指定IP
173 1
|
Linux 网络安全 Apache
无需公网IP——搭建第一个网站
无需公网IP——搭建第一个网站
|
弹性计算 网络协议 安全
阿里云安全组开放端口配置教程
阿里云安全组开放端口配置教程,阿里云服务器端口怎么打开?云服务器ECS端口在安全组中开启,轻量应用服务器端口在防火墙中打开,阿里云服务器网以80端口为例,来详细说下阿里云服务器端口开放图文教程,其他的端口如8080、3306、443、1433也是同样的方法进行开启端口:
704 1
《构建企业私网连接新生态》电子版地址
《构建企业私网连接新生态》PPT
62 0
《构建企业私网连接新生态》电子版地址

相关实验场景

更多