数据结构（十七）散列查找

散列查找

1. 基本思想

1. 以关键字 key 为自变量，通过一个确定的函数 h（散列函数），计算出对应的函数值 h(key)，作为数据对象的存储地址
2. 可能不同的关键字会映射到同一个散列地址上，即 h(key $i_{}$i​) = h(key $j_{}$j​)（当 key $i_{}$i​ ≠ key $j_{}$j​），称为“冲突”——需要某种冲突解决策略

2. 基本工作

• 计算位置：构造散列函数确定关键词存储位置
• 解决冲突：应用某种策略解决多个关键词位置相同的问题

时间复杂度几乎为是常数：O(1)

3. 散列函数的构造

1. 考虑因素

1. 计算简单，以便提高转换速度
2. 关键词对应的地址空间分布均匀，以尽量减少冲突

2. 数字关键词

1. 直接定址法

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

2. 除留余数法

​ 散列函数为：h(key) = key mod p （p 一般取素数)

3. 数字分析法

​ 分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址

4. 折叠法

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

5. 平方取中法

​ 将关键词平方，取中间几位

3. 字符串关键字

1. ASCII码加和法

​ h(key) = (Σkey[i]) mod TableSize

2. 前3个字符移位法

​ h(key) = (key[0]×27 $2^{}$2 + key[1]×27 + key[2])mod TableSize

3. 移位法

​ h(key) = ( ${\sum }_{i=0}^{n-1}$∑i=0n−1​ key[n-i-1]×32 $i^{}$i) mod TableSize

例子（移位法）

h(“abcde”) = 'a’x32 $4^{}$4 + 'b’x32 $3^{}$3 +'c’x32 $2^{}$2 + 'd’x32 + ‘e’
= ((('a’x32+‘b’)x32+‘c’)x32+‘d’)x32+‘e’

Index Hash( const char *Key,int TableSize){
    unsigned int h = 0;   // 散列值函数，初始化为 0 
    while ( *Key != '\0' )    // 位移映射
        h = ( h << 5) + *Key++;
    return h % TableSize;
}

4. 冲突处理方法

1. 常用策略

• 换个位置：开放地址法
• 同一位置的冲突对象组织在一起：链地址法

2. 开放定址法

• 一旦产生了冲突（该地址已有其它元素），就按某种规则去寻找另一空地址
• 若发生了第 i 次冲突，试探的下一个地址将增加 d $i_{}$i​，基本公式是： h $i_{}$i​(key) = (h(key)+d $i_{}$i​) mod TableSize （1 ≤ i ≤ TableSize）
• d $i_{}$i​ 决定了不同的解决冲突方案

1. 线性探测

​ 以增量序列 1,2,…, (TableSize - 1) 循环试探下一个存储地址

2. 平方探测法

​ 以增量序列 1 $2^{}$2,-1 $2^{}$2,2 $2^{}$2,-2 $2^{}$2 , … , q $2^{}$2, -q $2^{}$2 且 q ≤ ⌊ TableSize/2 ⌋ 循环试探下一个存储地址

​ 如果散列表长度是某个 4k+3（k是正整数）形式的素数时，平方探测法就可以探查到整个散列表空间

3. 双散列

​ d $i_{}$i​ 为 i * h $2_{}$2​(key)，h $2_{}$2​(key) 是另一个散列函数，探测序列成：h $2_{}$2​(key),2h $2_{}$2​(key),3h $2_{}$2​(key), …

​ 对任意 key，h $2_{}$2​(key) ≠ 0

​ h $2_{}$2​(key) = p - (key mod p) （p < TableSize，p、TableSize 都是素数）

4. 再散列

​ 当散列表元素太多（即装填因子 α 太大）时，查找效率会下降

​ 解决的方法是加倍扩大散列表，这个过程就叫"再散列"，扩大时，原有元素需要重新计算放置到新表中

3. 分离链接法

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

5. 抽象数据类型定义

• 数据类型：符号表（SymbolTable）

• 数据对象集：符号表是"名字(Name)-属性(Attribute)"对的集合

• 操作集：Table ∈ SymbolTable，Name ∈ NameType，Attr ∈ AttributeType

  主要操作：

  • SymbolTable InitalizeTable(int TableSize)：创建一个长度为 TableSize 的符号表
  • Boolean IsIn(SymbolTable Table,NameType Name)：查找特定的名字 Name 是否在 Table 中
  • AttributeType Find(SymbolTable Table,NameType Name)：获取 Table 中指定名字 Name 对应的属性
  • SymbolTable Modefy(SymbolTable Table,NameType Name,AttributeType Attr)：将 Table 中指定名字 Name 的属性修改为 Attr
  • SymbolTable Insert(SymbolTable Table,NameType Name,AttributeType Attr)：向 Table 中插入一个新名字 Name 及其属性 Attr
  • SymbolTable Delete(SymbolTable Table,NameType Name)：从 Table 中删除一个名字 Name 及其属性

1. 平方探测法实现

#include<iostream>
#include<stdlib.h>
#include<cmath>
#define MAXTABLESIZE 100000 // 定义允许开辟的最大散列表长度 
typedef int Index;
typedef int ElementType; 
typedef Index Position;
typedef enum{   // 分别对应：有合法元素、空、有已删除元素 
	Legitimate,Empty,Deleted
} EntryType;  // 定义单元状态类型 

typedef struct HashEntry Cell;
struct HashEntry{   // 哈希表存值单元 
	ElementType Data;  // 存放元素
	EntryType Info;  // 单元状态 
};

typedef struct HashTbl *HashTable;
struct HashTbl{  // 哈希表结构体 
	int TableSize;   // 哈希表大小 
	Cell *Cells;   // 哈希表存值单元数组 
};

using namespace std;

int NextPrime(int N);  // 查找素数 
HashTable CreateTable( int TableSize); // 创建哈希表 
Index Hash(int Key,int TableSize);   // 哈希函数 

// 查找素数 
int NextPrime(int N){
	int p = (N%2)?N+2:N+1;  // 从大于 N 的下个奇数开始
	int i;
		
	while(p <= MAXTABLESIZE){
		for(i = (int)sqrt(p);i>2;i--)
			if(!(p%i))  // p 不是素数 
				break;
		if(i==2) 
			break; 
		p += 2;  // 继续试探下个奇数 
	}
	return p;
}

// 创建哈希表 
HashTable CreateTable( int TableSize){
	HashTable H;
	int i;
	H = (HashTable)malloc(sizeof(struct HashTbl));
	// 保证哈希表最大长度是素数 
	H->TableSize = NextPrime(TableSize);
	// 初始化单元数组
	H->Cells = (Cell *)malloc(sizeof(Cell)*H->TableSize);
	// 初始化单元数组状态 
	for(int i=0;i<H->TableSize;i++)
		H->Cells[i].Info = Empty;
	return H;
}

// 平方探测查找 
Position Find(HashTable H,ElementType Key){
	Position CurrentPos,NewPos; 
	int CNum = 0 ;   // 记录冲突次数
	CurrentPos = NewPos = Hash(Key,H->TableSize);
	// 如果当前单元状态不为空，且数值不等，则一直做 
	while(H->Cells[NewPos].Info != Empty && H->Cells[NewPos].Data != Key){
		if(++CNum % 2 ){ // 冲突奇数次发生 
			NewPos = CurrentPos + (CNum+1)/2*(CNum+1)/2;
			// 如果越界，一直减直到再次进入边界 
			while(H->TableSize <= NewPos){
				NewPos -= H->TableSize; 
			}
		}else{  // 冲突偶数次发生 
			NewPos = CurrentPos - CNum/2*CNum/2;
			// 如果越界，一直加直到再次进入边界 
			while(NewPos < 0){
				NewPos += H->TableSize; 
			}
		}
	} 
	return NewPos;
}

// 插入
bool Insert( HashTable H,ElementType Key,int i){
	Position Pos = i;
	Pos = Find(H,Key);
	// 如果单元格状态不是"存在合法元素" 
	if( H->Cells[Pos].Info != Legitimate){
		H->Cells[Pos].Info = Legitimate;
		H->Cells[Pos].Data = Key;
	}
	return true;
} 

// 除留余数法哈希函数 
Index Hash(int Key,int TableSize){
	return Key % TableSize;
}


void output(HashTable H){
	for(int i=0;i<H->TableSize;i++)
		cout<<i<<" "<<H->Cells[i].Data<<endl;
} 

int main(){
	HashTable H = CreateTable(9);
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		int tmp;
		cin>>tmp;
		Insert(H,tmp,i);
	}
	output(H);
	return 0;
}

2. 分离链接法实现

#include<iostream>
#include<cstdlib>
#include<cmath>
#define MAXTABLESIZE 100000
typedef int Index;
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode{   // 单链表 
	ElementType Data;
	PtrToLNode Next;
}; 
typedef PtrToLNode Position;
typedef PtrToLNode List;

typedef struct TblNode *HashTable;  // 散列表
struct TblNode{
	int TableSize;   // 表的最大长度 
	List Heads;  // 指向链表头结点的数组 
}; 
using namespace std;

int NextPrime(int N){
	int p = (N%2)?(N+2):(N+1);   // 比 tablesize 大的奇数 
	int i;
	while(p <= MAXTABLESIZE){
		for(i = (int)sqrt(p);i>2;i--)
			if(!(p%i))
				break;
		if(i==2)  // 找到素数了 
			break;
		p += 2; // 下一个奇数
	}
	return p;
}

// 创建哈希表 
HashTable CreateTable( int TableSize){
	HashTable H;
	H = (HashTable)malloc(sizeof(struct TblNode));
	H->TableSize = NextPrime(TableSize);
	H->Heads = (List)malloc(sizeof(struct TblNode) * H->TableSize);
	for(int i=0;i<H->TableSize;i++) 
		H->Heads[i].Next = NULL;  // 链表头：H->Heads[i] 是不存东西的 
	return H;
}

// 除留余数法哈希函数 
Index Hash(	int TableSize,ElementType Key){
	return  Key%TableSize;
}

// 查找
Position Find(HashTable H,ElementType Key){
	Position p;
	Index pos;
	
	pos = Hash(H->TableSize,Key); 
	p = H->Heads[pos].Next;  //获得链表头 
	while(p && p->Data != Key)
		p = p->Next;
	return p;
} 

// 插入
bool Insert(HashTable H,ElementType Key){
	Position p,NewCell;
	Index pos;
	
	p = Find(H,Key);
	if(!p){  // 关键词未找到，可以插入 
		NewCell = (Position)malloc(sizeof(struct LNode));
		NewCell->Data = Key;
		pos = Hash(H->TableSize,Key);   // 初始散列表地址
		// 将新增结点插到最前面
		NewCell->Next = H->Heads[pos].Next;
		H->Heads[pos].Next = NewCell;
		return true;
	}else{
		return false;
	}
}

void output(HashTable H){
	for(int i=0;i<H->TableSize;i++){
		cout<<i;
		List p = H->Heads[i].Next;  
		while(p){
			cout<<" "<<p->Data;
			p = p->Next;
		} 
		cout<<endl;
	}
}

void DestroyTable(HashTable H){
	Position P,tmp;
	for(int i=0;i<H->TableSize;i++){
		P = H->Heads[i].Next;
		while( P ){
			tmp = P->Next;
			free(P);
			P = tmp;
		}
	}
	free(H->Heads);
	free(H);
} 


int main(){
	HashTable H = CreateTable(9);
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		int tmp;
		cin>>tmp;
		Insert(H,tmp);
	}
	output(H);
	DestroyTable(H);
	return 0;
}