线性探测再散列

线性探测再散列哈希表又称散列表。哈希表存储的基本思想是:以数据表中的每个记录的关键字k为自变量,通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间(即数组空间)的单元地址(即下标),将该记录存储到这个单元中。在此称该函数H为哈函数或散列函数。按这种方法建立的表称为哈希表或散列表。处理冲突的方法:开放寻址法:Hi=(H(key)+di)MODm,i=1,2,…,k(k<=…

大家好,又见面了,我是你们的朋友全栈君。

哈希表又称散列表。哈希表存储的基本思想是:以数据表中的每个记录的关键字 k为自变量,通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间(即数组空间)的单元地址(即下标),将该记录存储到这个单元中。在此称该函数H为哈函数或散列函数。按这种方法建立的表称为哈希表或散列表。

处理冲突的方法:

开放寻址法:Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列,可有下列三种取法:

1.di=1,2,3,…, m-1,称线性探测再散列;

2.di=1^2, -1^2, 2^2,-2^2, 3^2, …, ±(k)^2,(k<=m/2)称二次探测再散列;

3.di=伪随机数序列,称伪随机探测再散列。

再散列法:Hi=RHi(key), i=1,2,…,k. RHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间;

链地址法(拉链法):将所有关键字为同义词的记录存储在同一线性链表中;

例:设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是( ) 【南京理工大学 2001 一、15 (1.5分)】
A.8 B.3 C.5 D.9
我的计算步骤如下:
15,38,61,84用哈希函数H(key)=key%11计算后得地址:4,5,6,7
49计算后为5,发生冲突.
用二次探测再散列法解决冲突:
1:(key+1^2)%11=(49+1)%11=6,仍然发生冲突.
2:(key-1^2)%11=(49-1)%11=4,仍然发生冲突.
3:(key+2^2)%11=(49+4)%11=9,不再发生冲突.
得出结果为D

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/146336.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 初识Spring Boot框架[通俗易懂]

    初识Spring Boot框架[通俗易懂]前面的铺垫文章已经连着写了六篇了,主要是介绍了Spring和SpringMVC框架,小伙伴们在学习的过程中大概也发现了这两个框架需要我们手动配置的地方非常多,不过做JavaEE开发的小伙伴们肯定也听说过“约定大于配置”这样一句话,就是说系统,类库,框架应该假定合理的默认值,而非要求提供不必要的配置,可是使用Spring或者SpringMVC的话依然有许多这样的东西需要我们进行配置,这样不仅徒增工作量

  • python换行符使用_python中怎么换行?「建议收藏」

    python换行符使用_python中怎么换行?「建议收藏」Windows换行符是’\r\n’,Unix/Linux的换行符为’\n’,Mac的换行符为’\r’,在python中,对换行符进行了统一处理,定义为’\n。方法一、使用“\”进行换行输入:1、在python中,Python用反斜线(“\”)作为续行符(换行符),这里以python3.5为例。首先运行终端或者cmd命令行(windows下),执行python3.5的命令。2、然后输入如下图所…

  • Linux下文件搜索、查找、查看命令

    Linux下文件搜索、查找、查看命令Linux下文件搜索、查找、查看命令1、最强大的搜索命令:find一、根据文件或目录名称搜索二、根据文件大小搜索三、根据所有者和所属组搜索四、根据时间属性搜索五、根据文件类型或i节点搜索六、组合条件搜索  2、在文件资料中查找文件:locate  3、搜索命令所在的目录及别名信息:which 4、搜索命令所在的目录及帮助文档路径:whereis5、在文件…

  • jsonify

    jsonifyflask提供了jsonify函数供用户处理返回的序列化json数据,而python自带的json库中也有dumps方法可以序列化json对象,那么在flask的视图函数中return它们会有什么不同之处呢?想必开始很多人和我一样搞不清楚,只知道既然框架提供了方法就用,肯定不会错。但作为开发人员,我们需要弄清楚开发过程中各种实现方式的特点和区别,这样在我们面对不同的需求时才能做出相对合理的选择,而…

  • python 正则表达式匹配数字或者小数点_五位小数正则表达式

    python 正则表达式匹配数字或者小数点_五位小数正则表达式在对文本关键信息进行提取的过程中,通常需要使用正则表达式匹配。这篇笔记整理汇总Python中可能用到的与数值相关的正则表达式。正则表达式基础正则表达式是用字符串表示的一种语法,用于描述一种字符串匹配的模式。正则表达式中大多数字符的含义是通用的,比如符号^和$在绝大多数语言的正则表达式中都表示行头和行尾;但也可能在某些语法上存在差异,这需要依据特定语言而定。Python的正则表达式匹…

    2022年10月14日
  • 保姆级-红米AC2100之breed不死后台刷写openwrt官方版&第三方改良版「建议收藏」

    保姆级-红米AC2100之breed不死后台刷写openwrt官方版&第三方改良版「建议收藏」刷机有风险!!!后果自负准备1.红米AC21002.基础的电脑操作breed不死后台第一步:环境准备进入小米路由器原始的管理页,miwifi.com或者192.168.31.1登录之后,检查固件版本第二步:降级这里必须降级,我们降到到2.0.7降级包地址链接提取码:tenk然后等几分钟连接上降级后的wifi,正常是redmi开头无密码连上后重新进入后台192.168.31.1自行设置向导,这里忽略然后检查一下系统版本是否降级成功第三步:写入breed此时注意浏览器

    2022年10月29日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号