数据结构 第十一讲 散列查找（哈希）

一、散列表

编译处理时，涉及变量及属性（如：变量类型）的管理：
插入：新变量定义
查找：变量的引用
编译处理中对变量的管理：动态查找问题

利用查找树（搜索树）进行变量管理？
两个变量名（字符串）比较效率不高
是否可以先把字符串转换为数字，再处理？




“散列（Hashing）”的基本思想是：
①以关键字key为自变量，通过一个确定的函数h（散列函数）计算出对应的函数值h（key），作为数据对象的存储地址。
②可能不同的关键字会映射到同一个散列地址上，即h（key a）=h（key b）（当key a≠key b），称为“冲突（Collision）”——此时需要某种冲突解决策略

二、散列函数的构造方法

一个“好”的散列函数一般应考虑下列两个因素：
1.计算简单，以便提高转换速度
2.关键词对应的地址空间分布均匀，以尽量减少冲突

数字关键词的散列函数构造

1.直接定址法

取关键词的某个线性函数值为散列地址，即
h（key）= a x key + b（a、b为常数）

2.除留余数法

散列函数为：h（key）= key mod p

这里：p = Tablesize = 17
一般，p取素数

3.数字分析法

分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址
比如：取11位手机号码key的后4位作为地址：
散列函数为：h（key）= atoi（key + 7）（char *key）

int atoi(char* s):将类似“5678”的字符串转换为整数5678

4.折叠法

把关键词分割成位数相同的几个部分，然后叠加

5.平方取中法

取中间三位数的原因：使每一位的变化都能对散列结果产生影响

字符关键词的散列函数构造

1.一个简单的散列函数——ASCII码加和法

对字符型关键词key定义散列函数如下：
h（key）= （∑key[i]）mod TableSize
冲突严重： a3、b2、c1；eat、tea

2.简单的改进——前3个字符移位法

h（key）=（key[0] x 27^2 + key[1] x 27 + key[2]）mod TableSize
仍然会产生冲突： string、street、strong、structure等等；
空间浪费： 3000 / 26³ ≈ 30%

3.好的散列函数——移位法

涉及关键词的所有n个字符，并且分布的很好：

如何快速计算：

Index Hash(const char *Key,int TableSize)
{
	unsigned int h = 0;
	while(Key!='\0')
	{
		h = (h<<5) + *Key++;//h = h*32 + *Key++;
	}
	return h % TableSize;
} 

在除留余数法中，H(key) = key%p，为什么p要取素数？ 你可以举些例子分析一下。

如果散列值的因数越多，可能导致的散列分布越不均匀，所以，p的选择需要选择约数少的数值，什么数值的约数最少呢？当然是只有1和它自己的质数了。所以往往将桶个数设置为质数或不包含小于20的质因数的合数。

三、冲突处理的方法

常用处理冲突的思路：
换个位置：开放寻址法
同一位置的冲突对象组织在一起：链地址法（拉链法）

1.开发寻址法（Open Addressing）

一旦产生了冲突（该地址已有其他元素），就按某种规则去寻找另一空地址
若发生了第i次冲突，试探的下一个地址将增加偏移量di，基本公式是：
hi（key）= （h（key）+di）mod TableSize（1≤i＜TableSize）

di决定了不同的解决冲突方案：线形探测、平方探测、双散列

在查找不存在的字符串时，当向右查找到某个位置为空时即停止并返回查找失败

2.平方探测法（Quadratic Probing）——二次探测

平方探测法： 以增量序列1² ,-1²,2²,-2²,……,q²,-q² ，且q≤[TableSize/2]循环试探下一个存储地址

是否有空间，平方探测法（二次探测）就能找得到？

有关负数取余的问题，请参考此博客：负数取余问题

有定理显示：如果散列表长度TableSize是某个4k+3（k是正整数）形成的素数时，平方探测法就可以探查到整个散列表空间

3.双散列探测法（Double Hashing）

双散列探测法：di为ih2（key），h2（key）是另一个散列函数
探测序列成：h2（key）、2h2（key）、3*h2（key），……
注意：对任意的key，h2（key）≠0

探测序列还应该保证所有的散列存储单元都应该能够被探测到。
选择以下形式有良好的效果：
h2（key）= p - （key mod p）
其中：p<TableSize，p、TableSize都是素数。

4.再散列（Rehashing）

当散列表元素太多（即装填因子α太大）时，查找效率会下降，解决的方法是加倍扩大散列表，这个过程叫做“再散列”；
实用最大装填因子一般取0.5 <= α <= 0.85
散列表扩大时，原有元素需要重新计算并放置到新表中

5.分离链接法（Separate Chaining）

分离链接法：将相应位置上冲突的所有关键词存储在同一个单链表中

四、散列表的性能分析

平均查找长度（ASL）用来度量散列表的查找效率：成功、不成功
关键词的比较次数，取决于产生冲突的多少
影响产生冲突多少有以下三种因素：
①散列函数是否均匀
②散列表的装填因子α
③处理冲突的方法

1.线形探测法的查找性能

2.平方探测法和双散列探测法的查找性能

合理的最大装填因子α应该不超过0.85

3.分离链接法的查找性能

总结

选择合适的h（key），散列表的查找效率期望是常数O（1），它几乎与关键字的空间的大小n无关！也适合于关键字直接比较计算量大的问题

它是以较小的α为前提。因此，散列方法是一个以空间换时间

散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适合于范围查找，或最大值最小值查找

开放地址法
散列表是一个数组，存储效率高，随机查找。然而散列表有“聚集”现象
分离链接法
散列表是顺序和链式存储的结合，链表部分的存储效率和查找效率都比较低。
关键字“删除”不需要“懒惰删除”法，从而没有存储“垃圾”。
太小的α可能导致空间浪费，大的α又将付出更多的时间代价。不均匀的链表长度导致时间效率的严重下降。

五、哈希表的构造（代码实现）

结构体数组的哈希表

typedef struct HashTbl *HashTable;
struct Cell
{
	int Info;
	ElementType Element;
}Cell;
struct HashTbl
{
	int TableSize;
	Cell *TheCells;
}H;

HashTable InitializeTable(int TableSize)
{
	HashTable H;
	int i;
	if(TableSize < MinTableSize)
	{
		Error("散列表太小");
		return NULL;
	}
	H = (HashTable)malloc(sizeof(struct HashTbl));
	if(H == NULL)
	{
		FatalError("空间溢出！");
	}
	H->TableSize = NextPrime(TableSize);//比TS大的最小素数，作为哈希表的容量
	H->TheCells = (Cell*)malloc(sizeof(Cell) * H->TableSize);//分配散列表Cells
	if(H->TheCells == NULL)
	{
		FatalError("空间溢出！");
	}
	for(int i=0;i<H->TableSize;i++)//设置哈希表的每个位置的状态为空 
	{
		H->TheCells[i].Info = Empty;
	}
	return H; 
}

Position Find(ElementType Key,HashTable H)
{
	Position CurrentPos,NewPos;
	int CNum = 0;//记录冲突次数
	NewPos = CurrentPos = Hash(Key,H->TableSize);//获取哈希值 
	while(H->TheCells[NewPos].Info!=Empty&&H->TheCells[NewPos].Element!=Key)//当发生冲突时 
	//字符串类型的关键字需要用到strcmp() 
	{
		CNum++;
		if(CNum%2==0)
		{
			NewPos = CurrentPos - CNum/2 * CNum/2;
			while(NewPos<0)//等价于对TableSize取余 
			{
				NewPos = NewPos + H->TableSize;	
			}
		}
		else
		{
			NewPos = CurrentPos + (CNum+1)/2 * (CNum+1)/2;
			while(NewPos >= H->TableSize)//等价于对TableSize取余  
			{
				NewPos = NewPos - H->TableSize;	
			}
		}
	}
	return NewPos;
}
void Insert(ElementType Key,HashTable H)
//插入操作 
{
	Position Pos;
	Pos = Find(Key,H);
	if(H->TheCells[Pos].Info != Legitimate)
	//确认在此插入 
	{
		H->TheCells[Pos].Info = Legitimate;
		H->TheCells[Pos].Element = Key;
	}
	//字符串类型的关键词需要strcpy()函数！ 
}

在开放地址散列表中，删除操作要很小心。通常只能用“懒惰删除”，即需要增加一个“删除标记（Deleted）”，而并不是真正删除它。以便查找时不会“断链”。其空间可以在下次插入时重用

分离链式法的哈希表

typedef struct ListNode *Position,*List;
struct ListNode
{
	ElementType Element;
	Position Next;
};
typedef struct HashTbl *HashTable;
struct HashTbl
{
	int TableSize;
	List TheLists;
};

Position Find(ElementType key,HashTable H)
{
	Position P;
	int Pos;
	Pos = Hash(key,H->TableSize);
	P = H->TheLists[Pos].Next;
	while(P!=NULL && P.Element!=key)//若关键字为字符串，则使用strcmp()函数 
	{
		P = P->Next; 
	}
	return P;
}

课后练习

已知散列表元素状态，推测可能的元素输入顺序?

若采用开放定址法，选取散列函数所得位置与实际位置相同的任意一个元素作为首个插入的元素，根据处理冲突的方法更新散列函数的取值，再依次以相同的方法选取余下的元素。可以归纳证明这样的插入序列能得到给出的表状态。