Scott's world.

第十一讲-散列查找

Word count: 2.4kReading time: 9 min
2019/08/22 Share

第十一讲 散列查找

散列表

编译处理时,涉及变量及属性(如:变量类型)的管理:

插入:新变量定义

查找:变量的引用

  • 编译处理中对变量管理

    • 动态查找问题

      常用的查找方法

      顺序查找 O(N)

      二分查找(静态查找) O(log_2N)

      二叉搜索树 O(h)

      平衡二叉树 O(log_2N)

  • 问题:如何快速搜索到需要的关键词?如果关键词不方便比较怎么办?

当我们思考这个问题的时候,先来想想查找的本质

所以接下来我们继续来介绍散列表(哈希表)

  • 散列表的抽象数据类型

接下来我们来看一个例子

  • 在这个例子中我们可以看到当使用散列的思想来解决问题时,首先要考虑散列函数,选择一个好的散列函数即会节约空间也会大幅度地增加效率,还可以降低其冲突

装填因子(Loading Factor):

设散列表空间大小为m,填入表中元素个数是n,则称a=n/m为散列表的装填银子

如本例中a=11/17≈0.65

接下来,我们再来看一个例子

归纳

散列函数的构造

一个优秀的散列函数一般应该考虑以下两个因素:

1.计算简单,以便提高转换速度

2.地址空间分布均匀,以尽量减少冲突

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

  • 直接定址法

  • 除留余数法

  • 数字分析法

  • 折叠法

  • 平方法

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

  • ASCII码加和法

我们来快速计算一下移位法的值

比如:

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

我们用一种巧妙的方法可以减少大量计算过程

原式=((((ax32+b)x32+c)x32+d)x32+e)

且大家可以发现32是2^5所以我们可以用位运算来解决

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

散列冲突处理方法

常规处理冲突的思路有两种

开放地址法(Open Addressing)

换个位置:开放地址法(Open Addressing)

即一旦发生冲突,就按某种规则去寻找另一空地址

线性探测法(Linear Probing)

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

  • 接下来我们来看一个例子

散列表查找性能分析

  • 接下来我们根据此分析法则来看一个例子

平方探测法(Quadratic Probing)

是否有空间,平方探测(二次探测)就能找得到?

  • 有定理显示:如果散列表长度TableSize是某个4k+3(k是正整数)形式的素数时,平方探测法就可以探查到整个散列表空间
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>
#include <vector>
#include <math.h>
#define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */
typedef int ElementType; /* 关键词类型用整型 */
typedef int Index; /* 散列地址类型 */
typedef Index Position; /* 数据所在位置与散列地址是同一类型 */
/* 散列单元状态类型,分别对应:有合法元素、空单元、有已删除元素 */
typedef enum { Legitimate, Empty, Deleted } EntryType;

typedef struct HashEntry Cell; /* 散列表单元类型 */
struct HashEntry{
ElementType Data; /* 存放元素 */
EntryType Info; /* 单元状态 */
};

typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode { /* 散列表结点定义 */
int TableSize; /* 表的最大长度 */
Cell *Cells; /* 存放散列单元数据的数组 */
};

int NextPrime( int N )
{ /* 返回大于N且不超过MAXTABLESIZE的最小素数 */
int i, p = (N%2)? N+2 : N+1; /*从大于N的下一个奇数开始 */

while( p <= MAXTABLESIZE ) {
for( i=(int)sqrt(p); i>2; i-- )
if ( !(p%i) ) break; /* p不是素数 */
if ( i==2 ) break; /* for正常结束,说明p是素数 */
else p += 2; /* 否则试探下一个奇数 */
}
return p;
}

HashTable CreateTable( int TableSize )
{
HashTable H;
int i;

H = (HashTable)malloc(sizeof(struct TblNode));
/* 保证散列表最大长度是素数 */
H->TableSize = NextPrime(TableSize);
/* 声明单元数组 */
H->Cells = (Cell *)malloc(H->TableSize*sizeof(Cell));
/* 初始化单元状态为“空单元” */
for( 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; /* 记录冲突次数 */

NewPos = CurrentPos = Hash( Key, H->TableSize ); /* 初始散列位置 */
/* 当该位置的单元非空,并且不是要找的元素时,发生冲突 */
while( H->Cells[NewPos].Info!=Empty && H->Cells[NewPos].Data!=Key ) {
/* 字符串类型的关键词需要 strcmp 函数!! */
/* 统计1次冲突,并判断奇偶次 */
if( ++CNum%2 ){ /* 奇数次冲突 */
NewPos = CurrentPos + (CNum+1)*(CNum+1)/4; /* 增量为+[(CNum+1)/2]^2 */
if ( NewPos >= H->TableSize )
NewPos = NewPos % H->TableSize; /* 调整为合法地址 */
}
else { /* 偶数次冲突 */
NewPos = CurrentPos - CNum*CNum/4; /* 增量为-(CNum/2)^2 */
while( NewPos < 0 )
NewPos += H->TableSize; /* 调整为合法地址 */
}
}
return NewPos; /* 此时NewPos或者是Key的位置,或者是一个空单元的位置(表示找不到)*/
}

bool Insert( HashTable H, ElementType Key )
{
Position Pos = Find( H, Key ); /* 先检查Key是否已经存在 */

if( H->Cells[Pos].Info != Legitimate ) { /* 如果这个单元没有被占,说明Key可以插入在此 */
H->Cells[Pos].Info = Legitimate;
H->Cells[Pos].Data = Key;
/*字符串类型的关键词需要 strcpy 函数!! */
return true;
}
else {
printf("键值已存在");
return false;
}
}

Position Hash(int Key,int TableSize)
{
return Key%TableSize;
}

双散列探测法(Double Hashing)

再散列(Rehashing)

链地址法(Spearate Chaining)

同一位置的冲突对象组织在一起:链地址法(分离链接法)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#define KEYLENGTH 15                   /* 关键词字符串的最大长度 */
typedef char ElementType[KEYLENGTH+1]; /* 关键词类型用字符串 */
typedef int Index; /* 散列地址类型 */
/******** 以下是单链表的定义 ********/
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; /* 指向链表头结点的数组 */
};

HashTable CreateTable( int TableSize )
{
HashTable H;
int i;

H = (HashTable)malloc(sizeof(struct TblNode));
/* 保证散列表最大长度是素数,具体见代码5.3 */
H->TableSize = NextPrime(TableSize);

/* 以下分配链表头结点数组 */
H->Heads = (List)malloc(H->TableSize*sizeof(struct LNode));
/* 初始化表头结点 */
for( i=0; i<H->TableSize; i++ ) {
H->Heads[i].Data[0] = '\0';
H->Heads[i].Next = NULL;
}

return H;
}

Position Find( HashTable H, ElementType Key )
{
Position P;
Index Pos;

Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */
P = H->Heads[Pos].Next; /* 从该链表的第1个结点开始 */
/* 当未到表尾,并且Key未找到时 */
while( P && strcmp(P->Data, Key) )
P = P->Next;

return P; /* 此时P或者指向找到的结点,或者为NULL */
}

bool Insert( HashTable H, ElementType Key )
{
Position P, NewCell;
Index Pos;

P = Find( H, Key );
if ( !P ) { /* 关键词未找到,可以插入 */
NewCell = (Position)malloc(sizeof(struct LNode));
strcpy(NewCell->Data, Key);
Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */
/* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */
NewCell->Next = H->Heads[Pos].Next;
H->Heads[Pos].Next = NewCell;
return true;
}
else { /* 关键词已存在 */
printf("键值已存在");
return false;
}
}

void DestroyTable( HashTable H )
{
int i;
Position P, Tmp;

/* 释放每个链表的结点 */
for( 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 ); /* 释放散列表结点 */
}

散列表的性能分析

线性探测法的查找性能

可以证明,线性探测法的期望探测次数满足下列公式:

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

  • 而期望探测次数与装填因子a的关系,就如下图

合理的最大装载因子a应该不超过0.85

分离链接法的查找性能

总结

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

  • 它是以较小的a为前提.因此,散列方法是一个空间换时间

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

开放地址法

  • 散列法是一个数组存储效率高,随机查找
  • 散列表有”聚集”现象

分离链法

  • 散列表是顺序存储和链式存储的结合,链表部分的存储效率和查找效率都比较低
  • 关键字删除不需要”懒惰删除”法,从而没有存储”垃圾”
  • 太小的a可能导致空间浪费,大的a又将付出更多的时间代价.不均匀的链表长度导致时间效率的严重下降.

应用-文件中单词词频统计

例题-电话狂人

题意理解

解法1-排序

  • 编程简单快捷

解法2-直接映射

  • 下标超过了unsingned long (且超过了37GB)

    为看2x10^5个号码扫描2x10^10个单元

解法3-更好的散列

程序框架搭建

.

模块的引用与裁剪

CATALOG
  1. 1. 第十一讲 散列查找
    1. 1.1. 散列表
      1. 1.1.1. 归纳
    2. 1.2. 散列函数的构造
      1. 1.2.1. 数字关键词的散列函数构造
      2. 1.2.2. 字符关键词的散列函数构造
    3. 1.3. 散列冲突处理方法
      1. 1.3.1. 开放地址法(Open Addressing)
        1. 1.3.1.1. 线性探测法(Linear Probing)
          1. 1.3.1.1.1. 散列表查找性能分析
        2. 1.3.1.2. 平方探测法(Quadratic Probing)
          1. 1.3.1.2.1. 代码实现
        3. 1.3.1.3. 双散列探测法(Double Hashing)
        4. 1.3.1.4. 再散列(Rehashing)
      2. 1.3.2. 链地址法(Spearate Chaining)
        1. 1.3.2.1. 代码实现
    4. 1.4. 散列表的性能分析
      1. 1.4.1. 线性探测法的查找性能
      2. 1.4.2. 平方探测法和双散列探测法的查找性能
      3. 1.4.3. 分离链接法的查找性能
    5. 1.5. 总结
      1. 1.5.1. 开放地址法
      2. 1.5.2. 分离链法
    6. 1.6. 应用-文件中单词词频统计
    7. 1.7. 例题-电话狂人
      1. 1.7.1. 题意理解
      2. 1.7.2. 解法1-排序
      3. 1.7.3. 解法2-直接映射
      4. 1.7.4. 解法3-更好的散列
      5. 1.7.5. 程序框架搭建
        1. 1.7.5.1. 模块的引用与裁剪