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

为什么要用哈希查找 ?

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

怎么样让查找更快呢?最好是不采用比较的方式 , 而是能用某一个公式 , 就像初中学过的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++;
}

运行结果如图: