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

约定不等于承诺〃 2022-04-13 05:57 340阅读 0赞

### 文章目录 ###

*   *  散列查找
     *   *  1. 基本思想
         *  2. 基本工作
         *  3. 散列函数的构造
         *   *  1. 考虑因素
             *  2. 数字关键词
             *   *  1. 直接定址法
                 *  2. 除留余数法
                 *  3. 数字分析法
                 *  4. 折叠法
                 *  5. 平方取中法
             *  3. 字符串关键字
             *   *  1. ASCII码加和法
                 *  2. 前3个字符移位法
                 *  3. 移位法
         *  4. 冲突处理方法
         *   *  1. 常用策略
             *  2. 开放定址法
             *   *  1. 线性探测
                 *  2. 平方探测法
                 *  3. 双散列
                 *  4. 再散列
             *  3. 分离链接法
         *  5. 抽象数据类型定义
         *   *  1. 平方探测法实现
             *  2. 分离链接法实现

## 散列查找 ##

### 1. 基本思想 ###

1.  以关键字 key 为自变量，通过一个确定的函数 h（**散列函数**），计算出对应的函数值 h(key)，作为数据对象的存储地址
2.  可能不同的关键字会映射到同一个散列地址上，即 h(key i \_i i) = h(key j \_j j)（当 key i \_i i ≠ key j \_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 2 \+ key\[1\]×27 + key\[2\])mod TableSize

##### 3. 移位法 #####

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

例子（移位法）

h(“abcde”) = 'a’x32 4 ^4 4 \+ 'b’x32 3 ^3 3 \+'c’x32 2 ^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 i，基本公式是： h i \_i i(key) = (h(key)+d i \_i i) mod TableSize （1 ≤ i ≤ TableSize）
 *  d i \_i i 决定了不同的解决冲突方案

##### 1. 线性探测 #####

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

##### 2. 平方探测法 #####

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

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

##### 3. 双散列 #####

d i \_i i 为 i \* h 2 \_2 2(key)，h 2 \_2 2(key) 是另一个散列函数，探测序列成：h 2 \_2 2(key),2h 2 \_2 2(key),3h 2 \_2 2(key), …

对任意 key，h 2 \_2 2(key) ≠ 0

h 2 \_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;
    }