线性探测再散列

线性探测再散列哈希表又称散列表。哈希表存储的基本思想是:以数据表中的每个记录的关键字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)


相关推荐

  • Qt编写安防视频监控系统(界面很漂亮)「建议收藏」

    Qt编写安防视频监控系统(界面很漂亮)「建议收藏」一、前言视频监控系统在整个安防领域,已经做到了烂大街的程序,全国起码几百家公司做过类似的系统,当然这一方面的需求量也是非常旺盛的,各种定制化的需求越来越多,尤其是这几年借着人脸识别的东风,发展更加迅猛,人脸识别相关的技术和应用这几年处于风口浪尖,衍生了特别多的应用产品,各种人脸识别的产品遍地开花,刷脸门禁,车站机场人脸识别,刷脸取票等,但是其实大部分内行人士可能都比较绝望,外行感觉像看科幻片一样…

  • 互联网圈内的域名大战[通俗易懂]

    互联网圈内的域名大战[通俗易懂]拥有1亿元人民币,我们可以买下一栋超级豪宅,一件绝世珍品,甚至是一家公司。360为如何花这笔钱提供了新思路:他们以1700万美元的天价,从沃达丰手中拿下了梦寐以求的域名360.com。为得到这颗皇冠上的明珠,360和沃达丰进行了长达3年的反复谈判,他们一度开出了1400万美元的高价却仍被对方拒绝。据说,双方是经过周鸿祎的朋友从中斡旋才以这个“相对优惠”的价码最终成交。域名,对于互联

  • linuxtop命令详解(xargs命令详解)

    查看多核CPU命令 mpstat-PALL 和 sar-PALL  说明:sar-PALL>aaa.txt  重定向输出内容到文件aaa.txt top命令经常用来监控linux的系统状况,比如cpu、内存的使用,程序员基本都知道这个命令,但比较奇怪的是能用好它的人却很少,例如top监控视图中内存数值的含义就有不少的曲解。本文通过一个运行中的WEB服务器的top监控截图,讲

  • 把AutoEventWireup属性关闭

    把AutoEventWireup属性关闭1、关于AutoEventWireup属性的作用:,自动关联页面的Page_Load、Page_Init事件,好处就是不用再多写委托代码或重载代码了啦,坏处就是性能(听说的)和不直观性(影响菜鸟升级,“没见到事件关联它为什么会执行这段代码呢?”)。2、删除:(1)、在aspx页面一个个将“AutoEventWireup=true”改为“AutoEventWireup=false”了

  • java voliate,voliate 的实现原理是什么【面试题详解】「建议收藏」

    java voliate,voliate 的实现原理是什么【面试题详解】「建议收藏」今天爱分享给大家带来voliate的实现原理是什么【面试题详解】,希望能够帮助到大家。volatile可以保证线程可见性且禁止指令重排序,但是无法保证原子性。在JVM底层volatile是采用“内存屏障”来实现的,加入volatile关键字时,汇编后会多出一个lock前缀指令。lock前缀指令其实就相当于一个内存屏障。happen-before原则保证了程序的“有序性,对volatile变量的…

  • 软件工程系统设计说明书(软件详细设计说明书模板)

    1引言1.1编写目的该文档在概要设计的基础上,进一步的细化系统结构,展示了软件结构的图标,物理设计、数据结构设计、及算法设计、详细的介绍了系统各个模块是如何实现的,包括涉及到的算法,逻辑流程等。预期的读者:程序员1.2背景a. 待开发软件系统的名称:机房收费系统b. 项目的任务提出者:米新江教授c. 项目的开发者:齐智d. 项目的用户:廊坊师范学院全体在职员工及学生e. 运行该软…

发表回复

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

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