哈希查找

左手的ㄟ右手 2023-02-13 03:37 101阅读 0赞

哈希查找是一种通过设计所存储数据元素 与其存放地址之间的映射关系（函数关系）来实现高效查找的方法。比如我需要查询一个数460，那么根据先前存储时所采取的映射关系就可以准确地得到460相应的存储地址，从而实现高效查找。这是一个给定自变量的值，通过指定函数关系，得到因变量的值的过程。所谓哈希冲突就是一个因变量出现多个自变量的情况。

传统上我们要在数据集中查找某一个数据，都是遍历它进行一一比对，而哈希查找不会执行遍历，它是寻址访问（查找），所以效率会高很多，不过在存储空间的利用率上就相对低一些。

如果存储的数据元素有重复的情况呢？就是同样的因变量有多个，这又应该怎样处理？

以下是几种常用的存储整型类型数据的哈希函数设计方法。

第一步：设计哈希函数

设数据元素为K，数据元素个数为n，申请的内存单元个数为m

1. 除留余数法

h(K) = K mod m

理论研究表明，m取1.1n~1.7n之间的一个素数最好。

2. 直接定址法

不是很好用

3. 数字分析法

感觉也不是很好用

**哈希表设计**

typedef enum {Empty, Active, Deleted} KindOfItem;//表项状态的枚举类型 
    //表项结构体 
    typedef struct
    {
    	DataType data;
    	KindOfItem info;
     } HashItem;
    
    typedef struct
    {
    	HashItem *ht;    //哈希表数组 
     	int tableSize;   //数组最大个数 
    	int currentSize; //当前表项个数 
    }HashTable;//哈希表结构体
    
    //初始化
    int Initiate(HashTable *hash, int mSize)
    {
    	hash->tableSize = mSize;
    	hash->ht = (HashItem *)malloc(sizeof(HashItem)*mSize);
    	if(hash->ht==NULL) return 0;
    	else
    	{
    		hash->currentSize = 0;
    		return 1;
    	}
     } 
    //查找函数
    int Find(HashTable *hash, DataType x)
    {
    	int i = x.key % hash->tableSize;
    	int j = i;
    	while(hash->ht[j].info == Active && hash->ht[j].data.key != x.key)
        //说明存在冲突
    	{
    		j = (j + 1)%hash->tableSize;//哈希冲突函数继续查找
    		if(j==i)//说明已遍历整个哈希表未找到且表已满
    		     return -hash->tableSize;
    	}
    	if(hash->ht[j].info == Active) return j;
    	else return -j;
     } 
    //把数据元素x插入到哈希表hash中
    int Insert(HashTable *hash, DataType x)
    {
    	int i = Find(hash, x);
    	if(i>=0) return 0;
    	else if(i!= -hash->tableSize)
    	{
    		hash->ht[-i].data = x;
    		hash->ht[-i].info = Active;
    		hash->currentSize++;
    		return 1;
    	}
    	else return 0;
     } 
    //删除哈希表hash中的数据元素x
    int Delete(HashTable *hash, DataType x)
    {
    	int i = Find(hash, x);
    	if(i>=0)
    	{
    		hash->ht[i].info = Deleted;
    		hash->currentSize--;
    		return 1;
    	}
    	else return 0;
     } 
    //撤销函数
    void Destroy(HashTable *hash)
    {
    	free(hash->ht);
     }

测试：

#include <stdio.h>
    #include <malloc.h>
    typedef int KeyType;
    typedef struct
    {
    	KeyType key;
    }DataType;
    #include "head.h"
    
    int main()
    {
    	HashTable myHashTable;
    	DataType a[] = {180,750,600,430,541,900,460}, item = {430};
    	int i,j,k,n=7,m=11;
    	Initiate(&myHashTable,m);
    	for(i=0;i<n;i++)
    	{
    		Insert(&myHashTable,a[i]);
    	 } 
    	for(i=0;i<n;i++)
    	{
    		j = Find(&myHashTable,a[i]);
    		printf("j=%d  ht[]=%d\n",j,myHashTable.ht[j].data.key);
    	}
    	k = Find(&myHashTable, item);
    	if(k>=0) printf("查找成功，元素%d的哈希地址为%d\n",item.key,k);
    	else printf("查找失败\n");
    	Delete(&myHashTable,item);
    	k = Find(&myHashTable,item);
    	if(k>=0) printf("查找成功，元素%d的哈希地址为%d\n",item.key,k);
    	else printf("查找失败\n");
    	Destroy(&myHashTable);
    	return 0;
    }