精华内容
下载资源
问答
  • 算法之哈希查找法

    2019-07-14 15:51:38
    【算法解释】:哈希查找法又称为散列表 【引入问题】:假设一家杂物店,有顾客来买东西,你得从本子中找到价格。但是随着商品的增加,使用二分法,无法做到顾客想问任何商品的价格,就立即回答。这时候就需要用到...

    【算法解释】:哈希查找法又称为散列表

    【引入问题】:假设一家杂物店,有顾客来买东西,你得从本子中找到价格。但是随着商品的增加,使用二分法,无法做到顾客想问任何商品的价格,就立即回答。这时候就需要用到哈希表。

    【解决冲突】:散列是能一种快速实现访问的存储方式。通常作为检索部分的数据项是整形或者字符串,当是字符串时,字符串的数量要远远大于数组的长度,这时候就会有多个字符串映射到一个存储位置的情况,这就是所谓的冲突问题,而且冲突时肯定存在的,这时候如何实现数据的存储又是需要解决的。

    【程序设计】:

    /* 	散列表查找算法(hash) */
    #define HASHSIZE 7
    #define NULLKEY -32768
    
    typedef int Status;
    typedef struct
    {
    	int *elem;	/*	基址 */
    	int count;	/*	当前数据元素个数 */
    }HashTable;
    
    uint8_t m = 0;  /* 散列表表长 */
    
    /*	初始化 */
    Status Init(HashTable *hashTable)
    {
    	uint8_t i;
    	m = HASHSIZE;
    	hashTable->elem = (uint8_t *)malloc(m * sizeof(int));
    	hashTable->count = m;
    	for( i = 0; i < m; i++ )
    	{
    		hashTable->elem[i] = NULLKEY;
    	}
    	return TRUE;
    }
    
    /*	哈希函数(除留余数法) */
    uint8_t Hash(uint8_t data)
    {
    	return data % m;
    }
    
    /*	插入 */
    void Insert(HashTable *hashTable,uint8_t data)
    {
    	uint8_t hashAddress = Hash(data); /*	求哈希地址 */
    
    	/*	发生冲突 */
    	while(hashTable->elem[hashAddress] != NULLKEY)
    	{
    		/* 	利用开放地址的线性探测法解决冲突 */
    		hashAddress++;
    		hashAddress = (hashAddress) % m;
    	}
    
    	/*	插入值*/
    	hashTable->elem[hashAddress]= data;
    }
    
    /*	查找 */
    uint8_t Search(HashTable *hashTable,uint8_t data)
    {
    	uint8_t hashAddress = Hash(data); /*	求哈希地址 */
    
    	/*	发生冲突 */
    	while(hashTable->elem[hashAddress] != data)
    	{
    		/* 	利用开放地址的线性探测法解决冲突 */
    		hashAddress++;
    		hashAddress = (hashAddress) % m;
    
    		if(hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(data))
    		{
    			return -1;
    		}
    	}
    
    	/*	查找成功 */
    	return hashAddress;
    }
    
    /*	打印结果 */
    void Display(HashTable *hashTable)
    {
    	uint8_t i;
    	for ( i = 0; i < hashTable->count; i++)
    	{
    		printf("%5d",hashTable->elem[i]);
    	}
    	printf("\n");
    }

    【调用示例】:

    int main()
    {
    	uint8_t i;
    	uint8_t result;
    	HashTable hashTable;
    	uint8_t arr[HASHSIZE] = {13,29,27,28,26,30,38};
    
    	/*	初始化hash*/
    	Init(&hashTable);
    
    	printf("	4.哈希查找算法:\n");
    
    	/*	插入数据*/
    	for( i = 0; i < HASHSIZE; i++)
    	{
    		Insert(&hashTable,arr[i]);
    	}
    	Display(&hashTable);
    
    	/*	查找数据*/
    	result = Search(&hashTable,29);
    	if(result == -1)
    	{
    		printf("error\n");
    	}
    	else
    	{
    		printf("data is %d",result);
    		printf("\n");
    	}
            return 0;
    }

     

    展开全文
  • 【查找算法】哈希查找法

    千次阅读 2020-02-26 12:44:45
    本篇文章将介绍一种新的查找算法——哈希查找。 文章目录何为哈希查找?散列表冲突构造散列函数直接定址除留余数解决冲突的方式开放地址链地址 何为哈希查找? 先看定义: 哈希查找是通过计算数据元素的...

    本篇文章将介绍一种新的查找算法——哈希查找。

    何为哈希查找?

    先看定义:

    哈希查找是通过计算数据元素的存储地址进行查找的一种方法。

    哈希查找通过给定的哈希函数构造哈希表(也叫散列表),然后通过计算存储地址进行元素查找。

    所以我们先来聊聊散列表。

    散列表

    散列是一种新的存储方式,它既不是按给定形式顺序存储,也不是毫无规律地进行存储,而是通过计算元素的存储地址实现存储。

    计算元素存储地址的基本思想是:记录的存储位置与关键字之间存在对应关系,这个对应关系称为一个hash函数。

    举个例子,现有一个数据元素序列,{1,3,5,7,9},若规定每个元素k的存储地址H(k) = k,则其存储结构如下:
    在这里插入图片描述
    这样的存储方式在查找元素的时候是非常方便的,比如想要查找元素值7,就把7代入hash函数,得到存储地址为7,此时比较下标为7的元素值,若相等,查找成功;或不相等,查找失败。

    由此可以发现,哈希查找法的查找效率是非常高的,甚至可以达到O(1),
    但是缺点也很明显,比较浪费存储空间。

    冲突

    散列表在构造过程中难免会产生一些冲突,何为冲突?

    冲突指的是不同的元素值被映射到了同一个散列地址。

    举个例子,有一个数据元素序列,{25,21,39,9,23,11},其hash函数为H(k) = k mod 7,则其存储结构为:
    在这里插入图片描述
    该元素序列中的每个元素求模7,其结果均在0~6之间,先看第一个元素25,因为25 % 7 = 4,所以25存放在下标为4的位置:
    在这里插入图片描述
    因为21 % 7 = 0,所以21存放在下标为0的位置:
    在这里插入图片描述
    因为39 % 7 = 4,按理说39应该存放在下标为4的位置,但你会发现,下标为4的位置已经有元素值了,而你第二次准备存入的元素值又跟其不同,所以冲突便产生了。

    这些具有相同函数值的关键字被称为同义词。

    构造散列函数

    我们说冲突是不同的元素映射到了同一个散列地址,而地址是由hash函数决定,所以想要避免冲突,就需要设计完美的hash函数。

    但这是无法实现的,在散列查找方法中,冲突是不可避免的,只能说是尽可能地避免冲突的产生。

    为了尽可能减少冲突,hash函数的设计就有一些讲究:

    1. 所选函数尽可能简单,以便提高转换速度
    2. 所选函数对元素值计算出的地址,应在散列地址中均匀分布,以减少空间浪费

    构造hash函数需要考虑的因素有:

    • 元素长度
    • 散列表的大小
    • 元素的分布情况
    • 查找频率

    这里介绍两种构造hash函数的方式:

    1. 直接定址法
    2. 除留余数法

    直接定址法

    先看第一种方式,直接定址法。

    Hash(key)=akey+b(ab)Hash(key) = a * key + b(a、b为常数)

    它的优点是:以关键码key的某个线性函数值为散列地址,不会产生冲突。

    除留余数法

    这种方法较直接定址法更为常用一些。

    Hash(key)=keymodp(p)Hash(key) = key mod p(p为整数)

    该方法的关键是如何能够取到合适的p值?

    若表长为m,则p应取小于等于m的质数。

    解决冲突的方式

    前面说过了,冲突是无法避免的,那么在产生冲突时该如何解决如何处理呢?

    这里介绍两种方式:

    1. 开放地址法
    2. 链地址法

    开放地址法

    开放地址法的基本思想为:有冲突时就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将数据元素存入。

    这下一个散列地址该如何找呢?也可以分为三种方式:

    1. 线性探测法:即以线性序列(如1、2、3、…、m - 1)为间隔寻找下一个散列地址
    2. 二次探测法:即以二次序列(如12、-12、22、-22、…、q2)为间隔寻找下一个散列地址
    3. 伪随机探测法:即以一个伪随机数为间隔寻找下一个散列地址

    举个例子,比如有一个序列{47,7,29,11,16,92,22,8,3},散列表的表长为m = 11,hash函数为Hash(key) = key mod 11,我们试着用线性探测法来解决一下存储过程中的冲突。
    在这里插入图片描述
    现在准备存入元素47,因为47 % 11 = 3,所以将47存放在下标为3的位置:
    在这里插入图片描述
    因为7 % 11 = 7,所以将7存放在下标为7的位置:
    在这里插入图片描述
    因为29 % 11 = 7,所以将29存放在下标为7的位置,但该位置已经有了元素值,且两者不相同,此时产生冲突。现在我们利用线性探测法,即在该位置上加上一个序列值,7 + 1 = 8,所以将其存放到下标为8的位置:
    在这里插入图片描述
    接下来是11、16、92,它们在存放过程中均没有产生冲突,直接存入即可:
    在这里插入图片描述
    下一个元素是22,因为22 % 11 = 0,而下标0的位置已经有了元素值,所以采用线性探测法,在此位置的基础上加上一个序列值,0 + 1 = 1,所以将其存放到下标为1的位置:
    在这里插入图片描述
    元素8也是如此,它应该存放到下标为9的位置:
    在这里插入图片描述
    最后看元素3,因为3 % 11 = 3,所以存放位置应为下标3,但下标3位置已有元素,于是采用线性探测法,加上一个序列值,3 + 1 = 4,但下标4的位置仍然有元素,那就加第二个序列值,3 + 2 = 5,下标5的位置还是有元素,那就再加第三个序列值,3 + 3 = 6,直至找到空的散列地址。

    此时下标为6的位置是空的,所以存入元素3:
    在这里插入图片描述
    查找过程也是一样的,比如11,让其与11求模,余数为0,所以到下标为0的位置找出元素值比较,相等则查找成功;

    或者8,让其与11求模,余数为8,所以到下标为8的位置找出元素值比较,发现不相等,根据线性探测法,你就需要到下一个序列值对应的位置查找,也就是下标9,此时元素值相等,查找成功。

    还有两种方式,二次探测法和伪随机探测法,原理是一样的,无非就是地址间隔不一样,就不重复讲解了。

    链地址法

    第二种处理冲突的方法就是链地址法。

    其基本思想为:相同散列地址的记录链成一个单链表,m个散列地址就有m个单链表,然后用一个数组将m个单链表的表头指针存储起来,形成一个动态的结构。

    比如一个元素序列{19,14,23,1,68,20,84,27,55,11,10,79},其hash函数为
    Hash(key)=keymod13Hash(key) = key mod 13

    这里面很多元素就会产生冲突,比如元素14、1、27、79求模13的结果都是1,所以我们可以将这些同义词链成一个单链表,然后存储在数组中对应的位置,其函数结果为1,就将单链表的表头指针存储在数组下标为1的位置。
    在这里插入图片描述
    其建立散列表的方式也非常简单:

    1. 取数据元素的关键字key,计算其散列函数值。若该地址对应的链表为空,则将该元素插入此链表,否则执行步骤2解决冲突
    2. 根据选择的冲突解决方案,计算关键字key的下一个存储地址。若该地址对应的链表不为空,则利用链表的前插法或后插法将该元素插入到此链表中

    查找效率分析

    若使用平均查找长度ASL来衡量查找算法,ASL取决于:

    • hash函数
    • 处理冲突的方法
    • 散列表的装填因子α

    其中
    α=α = \frac{表中填入的记录数}{哈希表的长度}

    α越大,表中记录数越多,说明表装得越满,发生冲突的可能性就越大,查找时比较次数就越多;反之,相反。

    所以哈希查找的效率只是理论上能达到O(1),根据解决冲突的方式不同,查找效率也有所不同:

    • ASL1+α2ASL ≈ 1 + \frac{α}{2} (链地址法)
    • ASL12(1+11α)ASL ≈ \frac{1}{2}(1 + \frac{1}{1 - α}) (线性探测法)
    • ASL1αIn(1α)ASL ≈ -\frac{1}{α}In(1 - α) (随机探测法)
    展开全文
  • C++哈希查找法

    2019-06-05 12:52:24
    查找数据:求数据的哈希值,若匹配成功返回数组下标,否则线性探测下一个位置。 #include<iostream> using namespace std; #define m 13//哈希表长度 int Hash(int key) { int H = key % m;//...

    思路:这里的哈希表为数组。
    哈希函数:h=key%m
    构建随机数组初始化为-1并根据哈希函数放在数组指定下标。
    查找数据:求数据的哈希值,若匹配成功返回数组下标,否则线性探测下一个位置。

    
    #include<iostream>
    using namespace std;
    #define m 13//哈希表长度
    int Hash(int key)
    {
    	int H = key % m;//哈希函数
    	return H;
    }
    void InitHashTable(int data[])
    {
    	for (int i = 0; i < m; i++)//初始化数组为-1
    		data[i] = -1;
    	for (int i = 0; i < 10; i++)
    	{
    		int n = rand() % 100;//随机值
    		int x = Hash(n);//随机值的哈希值同时也是数组下标
    		if (data[x]!=-1)//位置被占
    		{
    			x = (x + 1) % m;//线性探测下一个位置
    			while (data[x]!=-1 && x != Hash(n))
    				x = (x + 1) % m;
    		}
    		data[x] = n;
    		cout << n << ":" << x << "\t";
    	}
    }
    
    int SearchHash(int* data, int key)
    {
    	int H = Hash(key);
    	if (data[H]==-1)//如果未重新赋值
    		return-1;
    	else if (data[H] == key)//查找成功
    		return H;
    	else
    	{
    		for (int i=1; i<m;i++)
    		{
    			int H1 = (H + i) % m;//线性探查
    			if (data[H1]==-1)//查无
    				return -1;
    			else if (data[H1] == key)//查找成功
    				return H1;
    		}
    		return -1;
    	}
    }
    int main()
    {
    	int data[m];
    	InitHashTable(data);
    	int key;
    	cout << endl << "输入需要查找的数值";
    	while (cin >> key)
    	{
    		if (SearchHash(data, key) == -1)
    			cout << "查找失败";
    		else
    			cout << endl << "查找成功数据下标为:" << SearchHash(data, key)<<endl;
    	}
    
    展开全文
  • 哈希查找

    2019-06-27 16:42:47
    哈希查找法 概念: 哈希法:又称散列法、杂凑法或关键字地址计算法等,相应的表称为哈希表。 哈希表的装填因子α: α = 哈希表中元素个数 / 哈希表的长度 α可描述哈希表的装满程度。 显然,α越小, 发生冲突的...

    哈希查找法

    概念:
    哈希法:又称散列法、杂凑法或关键字地址计算法等,相应的表称为哈希表。

    哈希表的装填因子α: α = 哈希表中元素个数 / 哈希表的长度
    α可描述哈希表的装满程度。 显然,α越小, 发生冲突的可能性越小, 而α越大, 发生冲突的可能性也越大。

    基本思想
    首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H,使得p=H(k),H称为哈希函数。

    除留余数法:假设哈希表长为m, p为小于等于m的最大素数, 则哈希函数为
    H(k)=k%p, 其中%为模p取余运算。

    处理冲突的方法

    开放定址法: 这种方法也称再散列法
    这种方法有一个通用的再散列函数形式:
    Hi=(H(key)+di)%m, i=1,2,…, n

    其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下三种:

    线性探测再散列: di=1,2,3,…:, m-1
    二次探测再散列:di=12,-12,22,-22,…,k2,-k2 (k≤m/2)
    伪随机探测再散列:di=伪随机数序列。

    设有一组关键字为:(13,29,01,23,44,55,20,84,27,68,11,10,79,14),n=14,选取a=0.75, 则哈希表长m=19,哈希表为T[0…18],用除留余数法构造哈希函数,选p=17,分别用平方探测再散列和随机探测再散列解决冲突,并计算平均查找长度。其中随机数序列为:3,16,55,44,…
    在这里插入图片描述

    再哈希法
    这种方法是同时构造多个不同的哈希函数:
    Hi=RH1(key), i=1,2, …, k
    当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

    链地址法
    这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中, 因而查找、插入和删除主要在同义词链中进行。 链地址法适用于经常进行插入和删除的情况。
    例如,已知一组关键字(32,40,36,53, 16,46,71,27,42,24,49,64),哈希表长度为13,哈希函数为:H(key)=key%13,则用链地址法处理冲突的结果为:
    在这里插入图片描述

    哈希法性能分析:
    在这里插入图片描述

    ASl=查找总次数 / 查找元素的个数(n)

    展开全文
  • 查找-哈希查找

    2019-02-26 22:54:12
    参考:... ... 目录:顺序查找 二分查找 插值查找 斐波那契查找 ...哈希查找 二叉树查找 红黑树查找 查找-哈希查找 算法简介 哈希表就是一种以键-值(key-indexed) 存储数据...
  • 查找算法之哈希查找

    2019-04-26 09:22:33
    哈希查找定义: 哈希查找是通过计算数据元素的存储地址进行查找的一种方法。O(1)的查找,即所谓的秒杀。哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函数,它将原来直观、整洁的数据...
  • 数据结构哈希查找

    2021-01-30 22:36:04
    数据结构之查找哈希查找哈希函数构造方法冲突解决办法哈希查找分析 哈希查找 哈希查找是通过设定的哈希函数H(key)和处理冲突的办法将关键字映射的一个地址集(区间),并将关键字在地址集中的“像”作为在表中的存储...
  • 算法:哈希查找

    2016-03-26 00:44:36
    哈希查找要用到的概念: 哈希查找:在记录的存储地址和它关键字之间建立一个确定的对应关系。不经过比较,一次存取就能得到所查元素的查找方法。 哈希函数:在记录的关键字与记录的存储地址之间建立的一种对应关系...
  • Console.WriteLine("********************哈希查找(C#版)********************\n"); //创建哈希表 for (int i = 0; i < list.Count; i++) { Insert(hashTable,list[i]); } Console.WriteLine("展示哈希...
  • 哈希查找--链地址

    2020-12-26 13:41:45
    哈希查找–链地址 题目描述 给出一个数据序列,建立哈希表,采用求余法作为哈希函数,模数为11,哈希冲突用链地址和表头插入 如果首次查找失败,就把数据插入到相应的位置中 实现哈希查找功能 输入 第一行输入n...
  • 哈希查找算法

    2021-05-12 17:02:43
    哈希查找(Hash Search) 概念: 哈希法:又称散列、杂凑或关键字地址计算等,相应的表称为哈希表。 哈希表的装填因子α: α = 哈希表中元素个数 / 哈希表的长度 α可描述哈希表的装满程度。显然,α越小,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,111
精华内容 22,444
关键字:

哈希查找法