查找算法【哈希表】 - 处理冲突的方法:开放地址法-线性探测法

这篇具有很好参考价值的文章主要介绍了查找算法【哈希表】 - 处理冲突的方法:开放地址法-线性探测法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

查找算法【哈希表】 - 处理冲突的方法

无论如何设计散列函数,都无法避免发生冲突。

如果发生冲突,就需要处理冲突。

处理冲突的方法分为3种:

  • 开放地址法
  • 链地址法
  • 建立公共溢出区。

【开放地址法】

开放地址法是线性存储空间上的解决方案,也被称为闭散列。

当发生冲突时,采用冲突处理方法在线性存储空间上探测其他位置。hash′(key)=(hash(key)+di )%m ,其中,hash(key)为原散列函数,hash′(key)为探测函数,di 为增量序列,m 为表长。

根据增量序列的不同,开放地址法又分为线性探测法、二次探测法、随机探测法、再散列法。

① 线性探测法

线性探测法是最简单的开放地址法,线性探测的增量序列为di =1,…,m -1。

例如,有一组关键字(14,36,42,38,40,15,19,12,51,65,34,25),若表长为15,散列函数为hash(key)=key%13,则可采用线性探测法处理冲突,构造该散列表。

按照关键字顺序,根据散列函数计算散列地址,如果该地址空间为空,则直接放入;如果该地址空间已存储数据,则采用线性探测法处理冲突。

[1] hash(14)=14%13=1,将14放入1号空间(下标为1);hash(36)=36%13=10,将36放入10号空间;hash(42)=42%13=3,将42放入3号空间;hash(38)=38%13=12,将38放入12号空间。

线性探测跟地址开放的区别,正经做题,散列表,算法,哈希算法

[2] hash(40)=40%13=1,1号空间已存储数据,采用线性探测法处理冲突。

hash′(40)=(hash(40)+di )%m ,di =1,…,m -1

d1 =1:hash′(40)=(1+1)%15=2,2号空间为空,将40放入2号空间,即hash(40)=40%13=1→2。

线性探测跟地址开放的区别,正经做题,散列表,算法,哈希算法

[3] hash(15)=15%13=2,2号空间已存储数据,发生冲突,采用线性探测法处理冲突。

hash′(15)=(hash(15)+di )%m ,di =1,…,m -1

  • d1 =1:hash′(15)=(2+1)%15=3,3号空间已存储数据,继续进行线性探测。
  • d2 =2:hash′(15)=(2+2)%15=4,4号空间为空,将15放入4号空间。

即hash(15)=15%13=2→3→4。

线性探测跟地址开放的区别,正经做题,散列表,算法,哈希算法

[4] hash(19)=19%13=6,将19放入6号空间;hash(12)=12%13=12,12号空间已存储数据,采用线性探测法处理冲突。

hash′(12)=(hash(12)+di )%m ,di =1,…,m -1

d 1 =1:hash′(12)=(12+1)%15=13,12号空间为空,将12放入13号空间,即hash(12)=12%13=12→13。

线性探测跟地址开放的区别,正经做题,散列表,算法,哈希算法

[5] hash(51)=51%13=12,12号空间已存储数据,采用线性探测法处理冲突。

hash′(51)=(hash(51)+di )%m,di =1,…,m -1

  • d1 =1:hash′(51)=(12+1)%15=13,13号空间已存储数据,继续进行线性探测。
  • d2 =2:hash′(51)=(12+2)%15=14,14号空间为空,将51放入14号空间。

即hash(51)=51%13=12→13→14。

线性探测跟地址开放的区别,正经做题,散列表,算法,哈希算法

[6] hash(65)=65%13=0,将65放入0号空间;hash(34)=34%13=8,将34放入8号空间;

hash(25)=12%13=12,12号空间已存储数据,采用线性探测法处理冲突。

hash′(25)=(hash(25)+di )%m ,di =1,…,m -1

  • d1 =1:hash′(25)=(12+1)%15=13,13号空间已存储数据,继续进行线性探测。
  • d2 =2:hash′(25)=(12+2)%15=14,14号空间已存储数据,继续进行线性探测。
  • d3 =3:hash′(25)=(12+3)%15=0,0号空间已存储数据,继续进行线性探测。
  • d4 =4:hash′(25)=(12+4)%15=1,1号空间已存储数据,继续进行线性探测。
  • d5 =5:hash′(25)=(12+5)%15=2,2号空间已存储数据,继续进行线性探测。
  • d6 =6:hash′(25)=(12+6)%15=3,3号空间已存储数据,继续进行线性探测。
  • d7 =7:hash′(25)=(12+7)%15=4,4号空间已存储数据,继续进行线性探测。
  • d8 =8:hash′(25)=(12+8)%15=5,5号空间为空,将25放入5号空间

即hash(25)=25%13=12→13→14→0→1→2→3→4→5。

线性探测跟地址开放的区别,正经做题,散列表,算法,哈希算法

注意: 线性探测法很简单,只要有空间,就一定能够探测到位置。但是,在处理冲突的过程中,会出现非同义词之间对同一个散列地址发生争夺的现象,称之为“堆积”。例如,上图中25和38是同义词,25和12、51、65、14、40、42、15均非同义词,却探测了9次才找到合适的位置,大大降低了查找效率。

性能分析:

1 查找成功的平均查找长度。假设查找的概率均等(12个关键字,每个关键字查找的概率均为1/12),查找成功的平均查找长度等于所有关键字查找成功的比较次数ci 乘以查找概率 之和,即

线性探测跟地址开放的区别,正经做题,散列表,算法,哈希算法

。可以看出,1次比较成功的有7个,2次比较成功的有2个,3次比较成功的有2个,9次比较成功的有1个,乘以查找概率求和,因为查找概率均为1/12,也可以理解为比较次数求和后除以关键字个数12。其查找成功的平均查找长度为ASLsucc =(1×7+2×2+3×2+9)/12=4/3。

2 查找失败的平均查找长度。本题中的散列函数为hash(key)=key%13,计算得到的散列地址为0,1,…,12,一共有13种情况,那么有13种查找失败的情况,查找失败的平均查找长度等于所有关键字查找失败的比较次数 乘以查找概率 之和,即

线性探测跟地址开放的区别,正经做题,散列表,算法,哈希算法

。当hash(key)=0时,如果该空间为空,则比较1次即可确定查找失败;如果该空间非空,关键字又不相等,则继续采用线性探测法向后查找,直到遇到空,才确定查找失败,计算比较次数。类似地,在hash(key)= 1,…,12时也如此计算。

本题的散列表如下表所示。

线性探测跟地址开放的区别,正经做题,散列表,算法,哈希算法

  • hash(key)=0:从该位置向后一直比较到7时为空,查找失败,比较8次。
  • hash(key)=1:从该位置向后一直比较到7时为空,查找失败,比较7次。
  • hash(key)=2:从该位置向后一直比较到7时为空,查找失败,比较6次。
  • hash(key)=3:从该位置向后一直比较到7时为空,查找失败,比较5次。
  • hash(key)=4:从该位置向后一直比较到7时为空,查找失败,比较4次。
  • hash(key)=5:从该位置向后一直比较到7时为空,查找失败,比较3次。
  • hash(key)=6:从该位置向后一直比较到7时为空,查找失败,比较2次。
  • hash(key)=7:该位置为空,查找失败,比较1次。
  • hash(key)=8:从该位置向后一直比较到9时为空,查找失败,比较2次。
  • hash(key)=9:该位置为空,查找失败,比较1次。
  • hash(key)=10:从该位置向后一直比较到11时为空,查找失败,比较2次。
  • hash(key)=11:该位置为空,查找失败,比较1次。

hash(key)=12:从该位置向后比较到表尾,再从表头开始向后比较(像循环队列一样),一直比较到7时为空,查找失败,比较11次。

假设查找失败的概率均等(13种失败情况,每种情况发生的概率都为1/13),查找失败的平均查找长度等于所有关键字查找失败的比较次数乘以概率之和。查找失败的平均查找长度为ASLunsucc =(1×3+2×3+3+4+5+6+7+8+11)/13=53/13。

算法实现:文章来源地址https://www.toymoban.com/news/detail-521024.html

int H(int key){ //哈希函数
	return key % 13;
}

int Linedetect(int HT[] , int H0 , int key , int &cnt){
	
	int Hi;
	for(int i = 1 ; i < m ; i++){
		cnt ++;
		Hi = (H0 + i) % m; //按照线性探测法计算下一个哈希地址Hi
		if(HT[Hi] == NULLKEY){
			return Hi; //若单元Hi为空,则所查元素不存在
		}
		else if(HT[Hi] == key){
			return Hi; //若单元Hi 中元素的关键字为key
		}
	}
	return -1;
}

int SearchHash(int HT[] , int key){
	//在哈希表HT中查找key,若查找成功,则返回下标,否则返回-1
	int H0 = H(key);  //根据哈希函数计算哈希地址
	int Hi , cnt = 1;
	if(HT[H0] == NULLKEY){ //若单元H0为空,则所查元素不存在
		return -1;
	}
	else if(HT[H0] == key){ //若单元H0 中元素的关键字为key,则查找成功
		cout << "查找成功,比较次数:" << cnt << endl;
		return H0;
	}
	else{
		Hi = Linedetect(HT , H0 , key , cnt);
		if(HT[Hi] == key){ //若单元Hi 中元素的关键字为key,则查找成功
			cout << "查找成功,比较次数:" << cnt << endl;
			return Hi;
		}
		else{
			return -1; //若单元Hi为空,则所查元素不存在
		}
	}
}

bool InsertHash(int HT[] , int key){
	
	int H0 = H(key);  //根据哈希函数H(key) 计算哈希地址
	int Hi = -1 , cnt = 1;

	if(HT[H0] == NULLKEY){
		HC[H0] = 1; //统计提交次数
		HT[H0] = key; //若单元H0 为空,则放入
		return 1;
	}
	else{
		Hi=Linedetect(HT , H0 ,key , cnt); //线性探测
		if((Hi != -1) && (HT[Hi] == NULLKEY) ){
			HC[Hi] = cnt;
			HT[Hi] = key; //若单元Hi为空,则放入
			return 1;
		}
	}
	return 0;
}

到了这里,关于查找算法【哈希表】 - 处理冲突的方法:开放地址法-线性探测法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Python查找算法】二分查找、线性查找、哈希查找

    目录 1 二分查找算法  2 线性查找算法 3 哈希查找算法         二分查找(Binary Search)是一种用于在有序数据集合中查找特定元素的高效算法。它的工作原理基于将数据集合分成两半,然后逐步缩小搜索范围,直到找到目标元素或确定目标元素不存在。 以下是二分查找的

    2024年02月08日
    浏览(52)
  • 比特币 ZK 赏金系列:第 2 部分——查找哈希冲突

    在我们的零知识赏金 (ZKB) 系列的第二部分中,我们将其应用于解决哈希冲突难题。在这样的谜题中,两个不同的输入散列到相同的输出。此类赏金可用于: 充当煤矿中的金丝雀,给我们一个有价值的提醒。存在冲突是散列函数较弱的标志,因此我们可以尽早升级以减轻损失

    2024年02月08日
    浏览(48)
  • 什么是redis中的哈希桶、哈希冲突及解决方法

    Redis中的哈希桶是一种数据结构,用于在Redis的哈希表(如字典结构)中存储键值对。 哈希桶是哈希表数组中的每个元素,可以视为一个容器或槽位,用于存放数据。在Redis中,当插入一个新的键值对时,会根据键的哈希值计算出一个索引,该索引指向特定的哈希桶。 每个哈

    2024年04月08日
    浏览(50)
  • 解决哈希冲突的几种方法

    哈希函数是一个映像,把任意长度的输入,通过Hash算法变换成固定长度的输出,这个输出就是Hash值; 当两个不同的输入,产生了同一个输出值即为哈希冲突 开放寻址法的核心思想是, 如果出现了散列冲突,我们就重新探测一一个空闲位置,将其插入 。比如,我们可以使用

    2024年01月17日
    浏览(37)
  • 【算法系列 | 9】深入解析查找算法之—哈希表查找

    心若有阳光,你便会看见这个世界有那么多美好值得期待和向往。 决定开一个算法专栏,希望能帮助大家很好的了解算法。主要深入解析每个算法,从概念到示例。 我们一起努力,成为更好的自己! 今天第9讲,讲一下查找算法的哈希表查找 查找算法是计算机科学中的一类

    2024年02月08日
    浏览(54)
  • Java 语言哈希查找算法实现

    哈希查找,也称为散列查找,是一种高效的查找算法。它利用哈希函数将映射到数组中的一个位置,通过直接访问该位置来获取元素,从而实现快速查找。Java语言提供了一些类和接口,例如 HashMap 和 HashTable ,使得我们可以方便地使用哈希查找算法。本文将详细介绍

    2024年02月10日
    浏览(46)
  • 数据结构,查找算法(二分,分块,哈希)

    一、查找算法         1、二分查找:(前提条件: 必须有序的序列) 2、分块查找:(块间有序,块内无序)     索引表  +  源数据表     思路:     (1)先在索引表中确定在哪一块中     (2)再遍历这一块进行查找 //索引表 typedef  struct  {     int max; //块中最大值

    2024年02月11日
    浏览(60)
  • 哈希(Hash)查找算法详解之C语言版

    哈希查找是一种快速查找算法,该算法不需要对进行比较,而是以为自变量,以该在存储空间中的地址为因变量,建立某种函数关系,称为哈希函数,这样在查找某一的时候,就可以通过哈希函数直接得到其地址,有效的提高了查找效率。 选取哈希

    2024年01月19日
    浏览(39)
  • 【算法系列 | 10】深入解析查找算法之—线性查找

    心若有阳光,你便会看见这个世界有那么多美好值得期待和向往。 决定开一个算法专栏,希望能帮助大家很好的了解算法。主要深入解析每个算法,从概念到示例。 我们一起努力,成为更好的自己! 今天第10讲,讲一下查找算法的线性查找算法 查找算法是计算机科学中的一

    2024年02月08日
    浏览(46)
  • C++哈希表:一种快速查找和插入的方法

    哈希表是一种非常重要的数据结构,它在各种场合中都有广泛的应用。在C++中,哈希表通常是通过 标准模板库(STL)中的unordered_map或unordered_set来实现 的。本篇文章将向读者介绍哈希表的基本概念、原理、实现方法以及优化策略。通过掌握哈希表,我们可以实现高效的查找和插

    2024年02月08日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包