欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基于开放定址法的哈希造表和查找

程序员文章站 2022-05-11 09:13:51
...

为什么要用哈希查找 ?

在之前学过的所有查找算法里 ,  不论是折半查找 , 亦或静态数表查找 , 还是索引顺序表查找 ,这些查找方式都是基于 "比较" 的查找方式.也就是说 , 想知道自己要查的元素在集合里有没有 , 把集合里的元素拿出来跟自己的元素一个一个比较 , 一样的话 , 就说明集合里有 , 找不到就是没有. 这种方式简单 , 可简单 , 并不快! 

怎么样让查找更快呢?最好是不采用比较的方式 , 而是能用某一个公式 , 就像初中学过的y = f(x) 一样 ,  知道x , 就能知道y .只要知道自己手中的待查找数据 ,待入公式里 , 就能找到它在集合里的位置.

哈希就实现了这样的 想法.

哈希之所以不同 , 就是因为y =f(x)不同 ,即要待入的公式不同.

常见的哈希构造方法有:

1:直接定址法  2: 数字分析法   3:平方取中法   4:折叠法  5:除留取余法

这次的哈希构造采用除留取余法 , 解决冲突的方式采用开放定址法中的线性探测在散列

节点HashTable中的int * elem指向哈希表元素 , 在代码中可以看到 , 只有在Hash表全部放满数据后造表才结束.更好的算法是 , 如果线性探测再散列导致索引超出表大小 , 需要在扩大哈希表 , 但这里并没有采用这样的算法 , 为简单起见 , 当冲突次数较多导致插入位置超出表大小后 , 直接提示无法插入.

具体代码如下:

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct
{
	int *elem;       //数据元素存储基址 
	int count;      //当前元素个数 
	int sizeindex;  //哈希表的当前容量 
}HashTable;

#define  SUCCESS      1
#define  UNSUCCESS    0
#define  DUPLICATE   -1
#define  NULLKEY    -99   //设定-99为哈希表初值,代表此处哈希表没有元素 
#define  EQ(a,b)    ((a) == (b))
typedef int KEYTYPE; //在searchHash()中作为参数使用 

int main()
{
	int createHashTable(HashTable &H);
	int searchHash(HashTable &H , KEYTYPE K , int &p , int &c);
	HashTable H;
	createHashTable(H);
	cout<<"hash表中的元素依此是:"<<endl; 
	for(int i=0 ; i<10 ;i++)
	{
		cout<<H.elem[i]<<endl;
	}
	
	//接着查找元素27
	int K =27, p ,c;
	if(searchHash(H , K , p ,c) == SUCCESS) 
	{
		cout<<"查找成功,元素位置是:"<<p<<"        元素值是:"<<H.elem[p]<<endl; 
	}
	else
	{
		cout<<"查找失败,hash表中没有这个元素!"<<endl; 
	}
	
}

int  createHashTable(HashTable &H)  
{
	int Hash(int); //申明 
	H.elem = (int *) malloc(sizeof(int)*10);  //创建hash表长度为10,录入的数据将放在这个数组里
	H.sizeindex =10;
	for(int i=0 ; i<10 ; i++)  //初始化表中元素 
	{
		H.elem[i] = NULLKEY;
	}
	H.count =0;  //初始时表中元素为0 
	cout<<"构造hash函数"<<endl;
	int hashValue;     //记录元素 
	int hashValueIndex=0;  //记录元素哈希后的位置 
	while(H.count<H.sizeindex)
	{
		cout<<"输入要插入的数据:"<<endl;
		cin>>hashValue;
		hashValueIndex = Hash(hashValue);   //除留取余法 
		while(H.elem[hashValueIndex] != NULLKEY  &&  hashValueIndex < 10)
		{
			hashValueIndex++;
		}	 
		if(hashValueIndex == 10 && H.elem[hashValueIndex-1]  != NULLKEY) //如果冲突元素排到数组边界,则不将这个元素插入 
		{
			cout<<"元素"<<hashValue<<"无法插入"<<endl; 
		}
		else
		{
			H.elem[hashValueIndex] = hashValue;
			H.count++;
			cout<<"插入成功,插入的位置是"<<hashValueIndex<<"此时count是:"<<H.count<<endl; 
		}
	}
	return SUCCESS;
}

int Hash(int hashValue)  //p取质数7--------H(key) = key MOD p , p<= m 
{
	hashValue %= 7;
	return hashValue-1;
}
 

int searchHash(HashTable &H , KEYTYPE K , int &p , int &c)
{
	//在开方定址法中查找 关键码为K 的元素,若查找成功,以p指示待查元素在表中位置,并返回SUCCESS , 否则, 返回UNSUCCESS
	int Hash(int); //申明
	void collision(int& ,int&);
	p = Hash(K); 
	while(H.elem[p] != NULLKEY && !EQ(K ,H.elem[p]) )  //该位置已有记录且关键字不相等 ,探查下一记录
	collision(p ,++c); 
	if(EQ(K , H.elem[p]) )  return SUCCESS;
	else   return  UNSUCCESS;
}

void collision(int &p ,int &c)  //线性探测再散列, 后移一位 
{
	p++;
}

运行结果如图:

基于开放定址法的哈希造表和查找

相关标签: 哈希查找