哈希查找 订阅
哈希查找是通过计算数据元素的存储地址进行查找的一种方法。 展开全文
哈希查找是通过计算数据元素的存储地址进行查找的一种方法。
信息
操作步骤个数
3步
解决冲突方法
开放地址法、链地址法
中文名
哈希查找
解    释
计算数据元素的存储地址进行查找
哈希查找定义
哈希查找的操作步骤:⑴用给定的哈希函数构造哈希表;⑵根据选择的冲突处理方法解决地址冲突;⑶在哈希表的基础上执行哈希查找。
收起全文
精华内容
下载资源
问答
  • 哈希查找

    2021-02-06 19:57:51
    哈希查找(Hash Search) 提前将数据进行分组(创建哈希表),然后根据分组的特征去相应的组里进行查找。 注:哈希查找不包括创建哈希表的过程,后面在哈希表查找的过程才是哈希查找;先有哈希表,在进行哈希查找。 如果...

    哈希查找(Hash Search)
    提前将数据进行分组(创建哈希表),然后根据分组的特征去相应的组里进行查找。
    注:哈希查找不包括创建哈希表的过程,后面在哈希表查找的过程才是哈希查找;先有哈希表,在进行哈希查找。
    如果对一批数据要进行反复的搜索,用哈希查找是很好的。
    在查找以前先建哈希表(分组):哈希散列函数,常用方法为求整取余(p=key%m,把m定成n值),然后入表,把对应的值放在正确的位置上,但是假如说数据中有1个数字为1,一个数字为11,二者对m为10时,p都为1,那么现在这两个数字都应该在表中的同一个位置,这种情况叫做哈希冲突,解决哈希冲突的办法有两个。
    第一个叫做开放定址法,你占了我的位置,我就去占别人的位置,假如11来了发现位置上有人,那么它如何才能去占别人的位置?方法一,线性探测,一个一个向后寻找空位置,如果连续太多,一时半会找不到位置,就有了第二个方法,线性补偿探测,有一个间隔,假如说间隔是3,每隔三个探测是否是空位,但是可能会造成死循环,第三个方法,线性探测再散列,间隔变成±1、±4、±9、±16 … … 先看1后面的位置有人吗?有人。1前面的位置有人吗?有人,1后面间隔为4的位置空余吗?空余,找到,以此类推,数据个数不足会循环进行。第二个叫拉链法,数据以链表形式链接下来,都在这同一个位置。
    我们采用的就是拉链法来解决哈希冲突,数据为86、17、9、1、16、25、14、38、46、5;先分组,数据10个有10组,超过10组也可有能。哈希表如下,假如我们的想要查找元素为37,37%10=7;遍历p=7的这组(遍历链表),发现没有37这个元素,查找失败。
    在这里插入图片描述

    //哈希查找
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    typedef struct hash
    {
    	int nValue;
    	int nIndex;
    	struct hash *pNext;
    }HashTable;
    
    //造哈希表
    HashTable **CreateHashTable(int arr[],int nLength)
    {
    	if(arr == NULL || nLength <= 0) return NULL;
    
    	//申请表头
    	HashTable **pHash = NULL;
    	pHash = (HashTable **)malloc(sizeof(HashTable*)*nLength);
    	memset(pHash,0,sizeof(HashTable*)*nLength);
    
    	//元素入表
    	int nIndex;
    	int i;
    	HashTable *pTemp = NULL;
    	for(i = 0;i < nLength;i++)
    	{
    		nIndex = arr[i]%nLength;
    
    		pTemp = (HashTable*)malloc(sizeof(HashTable));
    		pTemp->nValue = arr[i];
    		pTemp->nIndex = i;
    		pTemp->pNext = pHash[nIndex];
    		pHash[nIndex] = pTemp;
    	}
    	return pHash;
    }
    
    int HashSearch(HashTable **pHash,int nLength,int nNum)
    {
    	if(pHash == NULL || nLength <=0) return -1;
    
    	int nIndex;
    	HashTable *pTemp = NULL;
    
    	//找到对应的链表
    	nIndex = nNum%nLength;
    	pTemp = pHash[nIndex];
    
    	while(pTemp)
    	{
    		if(pTemp->nValue == nNum)
    		{
    			return pTemp->nIndex;
    		}
    		else
    		{
    			pTemp =pTemp->pNext;
    		}
    
    	}
    	return -1;
    }
    
    int main()
    {
    	int arr[] = {101,12,15,12,11,45,78,1};
    	HashTable **pHash = CreateHashTable(arr,sizeof(arr)/sizeof(arr[0]));
    	int nIndex = HashSearch(pHash,sizeof(arr)/sizeof(arr[0]),1);
    	printf("%d\n",nIndex);
    	return 0;
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,147
精华内容 6,058
关键字:

哈希查找