`
hm4123660
  • 浏览: 282415 次
  • 性别: Icon_minigender_1
  • 来自: 广州
博客专栏
Dea4ce76-f328-3ab2-b24a-fb268e1eeb75
数据结构
浏览量:69994
社区版块
存档分类
最新评论

查找算法--哈希表查找

阅读更多

 

  哈希表的概念

        哈希表又称散列表,是一种线性的存储结构。是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的数组叫做散列表。

 

哈希表存储思路

      以数据中每个元素的关键字K为自变量,通过散列函数h(k)计算出函数值,以该函数值作为一块连续存储空间的的单元地址,将该元素存储到函数值对应的单元中。但是存在这样的问题,对于两个关键字K1和k2,可能k1!=k2,但是h(k1)==h(k2),此时就发生了冲突,这种叫做哈希冲突。

 

哈希函数的构造方法

     构造哈希函数的目标是使得到的哈希地址尽可能均匀地分布在n个连续内存单元地址,同时使计算过程尽可能简单,以达到尽可能高的时间效率。根据关键字的结构和分布的不同,可构造出许多不同的哈希函数。

 

1.直接定址法

       直接定址法是以关键字k本身或关键字加上某个数字常量c作为哈希地址的方法。哈希函数为

                                                       h(k)=k+c

      这种哈希函数计算简单,并且不可能发生冲突。若关键字分布不连续将造成内存单元的大量浪费。

 

2.数字分析法

      分 析一组数据,比如一组员工的出生年月,这时我们发现出生年月的前几位数字一般都相同,因此,出现冲突的概率就会很大,但是我们发现年月日的后几位表示月 份和具体日期的数字差别很大,如果利用后面的几位数字来构造散列地址,则冲突的几率则会明显降低.因此数字分析法就是找出数字的规律,尽可能利用这些数据 来构造冲突几率较低的散列地址

 

3.除留余数法

       除留余数法是用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希地址方法,哈希函数为:

                                                         h(k)=k %p(取余)

其中,p<=m;

       除留余数法是最经常使用的一种哈希函数。这种方法关键是选好p,研究表明,p应该选取不大于m的素数时效果最好

 

哈希表冲突处理

 

1.开放定址法

        当 关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址 p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:Hi=(H(key)+di)%m   i=1,2,…,n,其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下两种:

 

(1)线性探索法

    线性探索法是从发生冲突的地址d开始,一次探索d的下一个地址(当到达表尾时,下一个地址就是表头),直到找到空闲单元为止。线性探索的数学表达式为:

                                                    d0=h(k);

                                                     di=(d0+i )% m(取向下一个地址单元)

 

   线性探索容易产生堆积问题。

 

(2)平方探测法

       设发生冲突的地址为d,则平方探测法的探测序列为d+1^2;d+2^2;d+3^2,......其数学表达式为:

 

                                     d0=h(k);

                                     di=(d0+i^2)%m

平方探测法是一种比较好的处理冲突方法,可以避免出现堆积问题。缺点是不能探索到哈希表上的所有单元。

 

下面使用除留余数法加线性探索法来建立查找哈希表

设哈希表长度为13,插入数据为:{16,74,60,43,54,90,46,31,29,88,77};

根据除留余数法应取不大于哈希表长度的素数,所有取p=13;

定义哈希表结构:

#define MAX 13//哈希表长度

#define p 13  //不大于哈希表长度的素数

#define NULLKEY -1  //空关键字

#define DELKEY -2  //删除关键字

//除留余数法加线性探索法建立哈希表
struct node
{
	int key;//关键字
	string data;//数据域
	int num;//探测次数
	//初始化探索次数为0,关键字为空关键字
	node()
	{
		num=0;
		key=NULLKEY;
	}
};

 

 

建立哈希表的代码为:

//建立哈希表
void Create(node hash[])
{
	int data[11]={16,74,60,43,54,90,46,31,29,88,77};//生成哈希表数据

	

	for(int i=0;i<11;i++)
	{
		int count=0;
		int temp=data[i];

		//关键字插入
		while(true)
		{
			if(hash[temp%p].key==NULLKEY||hash[temp%p].key==DELKEY)//没冲突
			{
				
				count++;
				hash[temp%p].key=data[i];//关键字插入
				hash[temp%p].num=count;//探索次数
				break;
			}
			else
			{
				temp=(temp+1)%p;//线性探查法
				count++;//探测次数加一
			}
		}
	}

	for(int i=0;i<13;i++)
		cout<<"下标: "<<i<<"  key :  "<<hash[i].key<<" 探索次数: "<<hash[i].num<<endl;

}

 

哈希表查询

//哈希表查找
int Search(node hash[],int key)
{
	int adr=key%p;

	while(hash[adr].key!=NULLKEY&&hash[adr].key!=key)
	{
		adr=(adr+1)%p;
	}
	if(hash[adr].key==key) //查找成功返回地址
		return adr;

	else     //查找失败
		return -1;
}

 

调用main函数为:

int main()
{
	node hash[MAX];//哈希表数组
    Create(hash);

	int result=Search(hash,88);
	cout<<result<<endl;
	return 0;
}

 

最后运行结果为:



 

2.拉链法

      拉链法是把所有同义词用链表连接起来的方法,这样,哈希表每个单元中存放的不再是记录本身,而是相应同义词单链表的头指针。拉链法需要额外的空间来存放指针

 

 

拉链法的优点与开放定址法相比,拉链法有如下几个优点:

 

(1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

 

(2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

 

(3)开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取  α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

 

(4) 在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地 将被删结点的空间置为空,否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条 件。 因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

 

拉链法的缺点

 拉链法的缺点是:指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

 

 

  拉链法的实现使用链表实现,实现过程比较简单,这里就不再编写拉链法实现的代码了。

 


 
 

 

4
0
分享到:
评论

相关推荐

    算法-理论基础- 查找- 哈希查找(包含源程序).rar

    哈希查找是计算机科学中一种高效的数据查找方法,它的核心思想是通过哈希函数将数据的键(key)映射到一个固定大小的数组(哈希表)中的索引位置,以此实现快速定位数据。本资源包含哈希查找的理论基础和源程序,...

    大数据结构课程设计--哈希表实验报告材料

    查找算法是哈希表的核心组件,用于快速查找哈希表中的数据。在本实验中,我们使用哈希函数将关键字映射到哈希表的索引上,然后使用线性探测再散列法处理冲突,直到找到所需的数据。 查找算法的设计可以影响哈希表的...

    最快的排序算法 最快的内容查找算法-----暴雪的Hash算法,排序算法数据结构

    Hash算法是一种常用的字符串查找算法,能够快速地从庞大的字符串数组中查找特定的字符串。 Hash算法的基本原理是将字符串压缩成一个整数,然后通过某种算法将其转换为一个哈希值。 在暴雪的Hash算法中,使用了一个...

    哈希表生成及哈希查找算法

    输入:待哈希数据序列 功能要求:输出哈希方法和解决冲突的方法(文字输出),输出哈希表

    10.数据结构与算法基础-哈希表

    总的来说,哈希表是数据结构与算法中的重要工具,它通过高效的查找机制,为许多实际问题提供了快速解决方案。尽管学习过程中可能会遇到一些挑战,但只要我们深入理解并不断实践,就能熟练掌握这个强大的工具。

    哈希查找-表长101

    建立哈希表查找c++中32个关键字,其中哈希表长为M=101 32个关键字为auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof ...

    综合查找算法(顺序查找、折半查找、二叉排序树、哈希表)-数据结构课程设计

    本文将详细探讨四种常见的查找算法:顺序查找、折半查找、二叉排序树查找以及哈希表查找,并结合提供的"综合查找算法"课程设计项目,解析其在实际应用中的特点和优势。 **顺序查找**是最基础的查找算法,适用于任何...

    数据结-构查找算法二分查找二叉顺序数哈希查找

    本章主要探讨了三种常见的查找算法:线性表的查找、树表的查找和哈希表的查找,以及它们的性能分析。 1. **二分查找**: 二分查找,也称为折半查找,适用于有序的线性表,如数组。算法的基本思路是将查找区间不断...

    哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找

    在本主题中,我们将深入探讨哈希表的建立和查找过程,以及相关的算法和设计策略。 一、哈希函数的选择与设计 哈希函数是哈希表的核心,它的主要任务是将输入(通常为字符串或整数)转化为数组的索引。一个好的哈希...

    基于python的查找算法-顺序查找Sequential Search

    相比于其他高级查找算法,如二分查找、哈希表查找等,顺序查找的效率较低。但这些高级算法通常需要数据已经排序或特定的数据结构,而顺序查找则没有这样的限制。 例如,**二分查找**适用于已排序的数组,它的时间...

    散列查找算法_哈希表

    程序先调用自己写的Create函数创建一个长度为13的哈希表,原始数据是:{10,9,8,7,5,4,6,3,2,1,95},长度为11,这个程序使用的是除留余数法,构建的哈希表为:{0,1,2,3,4,5,6,7,8,9,10,95,0}. 然后再调用Haxi_Sou...

    【力扣刷题】数组-链表-哈希-双指针

    二分查找是一种常用的查找算法,用于在有序数组中查找目标值。二分查找的前提条件是:数组为有序数组,数组中无重复元素。(因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的。) 二分查找法的实现...

    C++查找算法大集锦

    在IT领域,查找算法是计算机科学中的核心概念,特别是在数据结构和算法设计中。本文将深入探讨《C++查找算法大集锦》中所涵盖的各种查找技术,包括差值查找法、斐波那契查找、哈希查找(拉链法与探测法)以及顺序和...

    数据结构哈希表查找算法

    哈希表算法实现的C语言源程序 数据结构课程设计用

    C++源代码:哈希表算法

    哈希表是一种高效的数据结构,它通过特定的函数——哈希函数,将数据映射到一个固定大小的数组中,从而实现快速的插入、查找和删除操作。在C++编程中,哈希表通常被用来解决需要高效查找的问题,比如字典、缓存或者...

    顺序查找,折半查找,二叉排序树,哈希表

    下面,我们将介绍四种常见的查找算法:顺序查找、折半查找、二叉排序树和哈希表。 顺序查找 顺序查找是最简单的一种查找算法。它的工作原理是从数据集合的开始处依次比较每个元素,直到找到目标元素或者达到集合的...

    Python版数据结构与算法-查找算法源代码,含顺序搜索、二分查找、哈希表搜索、树(图)数据查找源代码

    本资源包含的是Python实现的各种查找算法的源代码,这些查找算法在实际编程中有着广泛的应用。以下将详细介绍标题和描述中提到的几个关键知识点: 1. **顺序搜索(Sequential Search)**: 顺序搜索是最基础的查找...

    查找算法的合计与实现

    这篇实验报告,来源于云南大学数据结构课程的第七次实践,聚焦于查找算法的理论和实现,特别是哈希表这一高效的数据结构。哈希表,也称为散列表,是一种能够实现快速查找的结构,它通过哈希函数将数据映射到一个固定...

    哈希函数ppt包括静态查找,动态查找表,哈希表

    - **哈希表的查找及其分析**:理想情况下,哈希表能实现O(1)的查找时间复杂度,但在存在冲突的情况下,查找效率会降低。 哈希函数是哈希表的核心,它将关键字转换成存储位置。例如,对于一个以字母开头的关键字...

Global site tag (gtag.js) - Google Analytics