《算法笔记》总结No.4——散列

2024-07-08 12:09:52

散列的英文名是hash，即我们常说的哈希~该知识点在王道408考研的教材里面属于查找的范围。即便各位并无深入了解过，也听说过散列是一种更高效的查找方法。

一.引例

先来考虑如下一个假设：设有数组M和N分别如下：

M[10]=[1,2,3,4,5,6,7,8,9,10];

N[10]=[11,12,13,14,15,16,17,18,19,20];

M和N都是大小为10的一维数组。现在要求判断M中的整数是否在N中出现过，那么最简单暴力的一个办法就是把M中的每一个元素都在N中遍历一遍，由于M和N都是10个，因此一共要执行100次。

不难发现——上述操作主打一个繁琐：当M和N的长度均为10000时，则需要操作1亿次——毫无疑问这是不可取的，且不说总量有多大，如果有相同的数出现，岂不是做了很多重复的步骤？

因此不妨考虑用空间换取时间：新开辟一个数组hashTable[10000]，用来表示N中的元素是否存在——存在时即为true，不存在则赋值为false。这样如果一开始的时候就将N遍历一遍，把hashTable中的元素赋值后，M直接在hashTable中查找元素是否存在即可!

听起来有些抽象，那么举个例子直观感受一下：就拿长度为10的M和N举例：

#include <iostream>
#include <cstdio> 
using namespace std;
  
bool hashTable[10000]={ false };
//一开始所有元素均为false——不存在 
int main(int argc, char** argv) {
	//第一个循环直接用来保存N 
	for(int i=1;i<=10;i++)
	{
		int temp=0;
		cin>>temp;
		hashTable[temp]=true; //输入的元素标识为存在 
	}
	for(int i=1;i<=10;i++)
	{
		int temp=0;
		cin>>temp;
		if(hashTable[temp]==true)   //如果true即为存在 
			cout<<temp<<"在N中出现过！"<<endl; 
		else
			cout<<temp<<"在N中没出现！"<<endl;
	}
}

测试结果如下：

来分析一下：由于存放和查找是两个独立的循环，复杂度为n+n即为2n——在这里为20。相比暴力搜索这种100的量级还是便捷了不少，事实上当出现重复元素时可以进一步细分~

扩展：如果此处要求统计出现的次数，直接将类型改为int，然后赋值为true变成自增即可

不难发现，上述引例中，是将元素直接作为下标来标记的——即7出现N[7]变为true，25出现N[25]变为true。这当然是非常实用且巧妙的一种做法。当下标超出、或者是元素为abcde时，这种方法就不凑效了。这时候就需要我们的散列~

二.整数散列

散列的本质或者说定义可以浓缩为一句话：将元素通过一个函数转换为一个整数，使得该整数可以尽量唯一的代表这个元素。这个转换函数被称为散列函数~

常见的散列函数取法：

直接定址法：恒等变换（即将key的值作为下标值），线性变换（x=a*key+b）。
平方取中法：很少用，即取key值平方的中间若干位作为hash值。
除留取余法：很常用，即H(key)=key%mod，通过这种散列函数，可以把很大的数转换为不超过mod的整数，这样就可以将他作为可行的数组下标！不过表长TSize一定要大于mod，不然显而易见会发生越界。此外，当mod是一个素数时，显而易见空间可以尽可能的覆盖下标的值。为了方便起见，一般来说mod的值与TSize相等。

当然，很明显会存在两个不同的key1和key2——他们的哈希值H(key1)、H(key2)有可能是相同的，当其中一个占领了目标单元格，另一个显而易见不能使用——这种情况被称之为冲突。以下为三种解决冲突的常见方法：

1.开放定址法

A.线性探测法

当目标的H(key)被占领时，直接检查下一个位置即H(key)+1上的位置是否被占，如果还被占就继续寻找n+1，以此类推；如果超过了表长，就回到首位继续循环，直到所有位置都被占用。该种方法会导致扎堆，会一定程度上降低效率。

B.平方探测法

为了避免扎堆现象，发生冲突后将依次查找如下位置：H(key)+1^2，H(key)-11^2，H(key)+2^2，以此类推。如果超出表长，则对表长完成取模；如果为负数，则对结果不断加表长直到出现第一个非负数。

如果在0~TSize范围内都无法找到位置，当k大于表长时，也一定无法找到位置。

2.链地址法（拉链法）

不计算新的hash值，而是把所有H(key)相同的key连接成一条单链表。

三.字符串散列

给出N个由3位大写字母组成的字符串，再给出M个查询字符串，问每个字符串在N个字符串中出现的次数。

#include <iostream>
#include <cstdio> 
using namespace std;
  
const int maxn=100;
char S[maxn][5],temp[5];
int hashTable[26*26*26+10];

int hashFunc(char S[],int len)
{
	int id=0;
	for(int i=0;i<len;i++)
		id=id*26+(S[i]-'A');
	return id;	
} 

int main(int argc, char** argv) {
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		int id=hashFunc(S[i],3);
		hashTable[id]++;
	}
	for(int i=0;i<m;i++)
	{
		cin>>temp;
		int id=hashFunc(temp,3);
		cout<<hashTable[i]<<endl;
	}
}

码农公寓