《算法导论》学习（十四）----散列表（哈希表）（C语言）

---

前言

本文主要讲解散列表（也可以称作哈希表）的相关内容，并且重点讲解了散列函数，以及用C语言是实现了链式散列表

---

一、散列表

1.什么是直接寻址表？

对于直接寻址表，我们可以简单地将它看作是一个普通数组。
我们可以通过数组的下标，来直接访问对应存储空间的元素。，这样的搜索寻找对应元素的过程，就是直接寻址
而类似的存储空间就是直接寻址表

2.什么是散列表？

散列表是普通数组概念的推广
散列表像直接寻址表一样，都是一种动态的集合结构，为使用者提供插入元素，删除元素，查找元素的功能
散列表与直接寻址表的区别集中体现在：

1.散列表的存储位置是散列函数处理k值后得到的。
2.直接寻址表的位置直接就是k值
1
2

举一个形象但是不是很贴切的例子：

如果将两种方法用在设置wife密码：

1.直接寻址就像将密码设置为88888888，8个8，甚至可以说没有加密过程
2.散列表就是将密码设置成了类似于姓名首字母+身份证尾号，是仅有个人信息这个“散列函数”，经过处理得到的
1
2

3.为什么需要散列表？

散列表应用场景远远大于直接寻址表：
原因有：

1.k值的大小范围可能远超计算机的内存，直接将k作为存储位置，显然不可能
2.k值直接作为存储位置，是很不安全的。在安全性要求高的领域运用，是很容易被提取保密信息，安全隐患极大
1
2

4.散列表的核心点

=散列表的关键其实集中在两个问题的解决上：

1.一个优良的散列函数
2.如果两个元素必须要放入同一个内存空间，该如何解决冲突
3.k值可能不是在自然数集中，不能直接当作存储空间的位置
1
2
3

二、散列表的基本思想

1.散列函数

（1）优良的散列函数的特点

一个好的散列函数，要满足以下的特点：

1.首先要保证每一个关键字都被等可能地散列在m个存储空间中的任何一个
2.非自然数要被转化到自然数集中（0，1，2，......）
3.要将k值的集合转化到0~m-1的范围内，m是存储空间的个数
1
2
3

（2）链接法中三种可行的散列函数

除法散列法

公式：
$$h(k)=kmodm$$
这个方法可以将k值映射到m个内存空间的某一个上面。
若要采用除法散列法，需要m是一个不太接近2的整数幂的素数，证明过程不在此赘述，这个取值的出发散列法往往性能优良

乘法散列法

公式：
$$h(k)=\lfloor m(kAmod1)\rfloor$$
乘法散列法的优点是对m的选择不是特别关键，一般选择$m=2^x，x为某整数$
根据Knuth的证明，$A=\frac{\sqrt{5}-1}{2}=\mathrm{0.6180339887...}$是一个理想的取值。

全域散列法

公式：
h a b ( k ) = ( ( a k + b ) m o d   p ) m o d   m 其中 a ∈ { 0 , 1 , 2 , . . . , p − 1 } b ∈ { 1 , 2 , 3 , . . . , p − 1 } 注： p 为一个足够大的素数，对任意 k 都有 0 ⩽ k ⩽ q − 1 h_{ab}(k)=((ak+b)mod\ p)mod \ m\\其中a\in \{ {0,1,2,...,p-1}\}\quad b\in\{{1,2,3,...,p-1}\}\\注：p为一个足够大的素数，对任意k都有0\leqslant k\leqslant q-1 hab​(k)=((ak+b)mod p)mod m其中a∈{0,1,2,...,p−1}b∈{1,2,3,...,p−1}注：p为一个足够大的素数，对任意k都有0⩽k⩽q−1
全域散列法就是得到一个散列函数类，里面包含$p(p-1)$种散列函数
已经证明其可以有效地将任意k值等概率地散列到m个存储空间中，有更稳定的均匀性质

2.解决冲突的两种方案

（1）链接法

链接法就是将m个存储空间变成链表，然后将有冲突的k值以链表结点的方式，插入对应的那个链表中。
本质上是一个链表数组的结构
注意：

双向链表更加利于元素的删除
1

（2）开放寻址法

开放寻址法其实就是将所有的元素都放入一个散列表中。
它的优点在于减少了冲突，不需要指针的额外存储空间，使得检索效率提高
它的缺点是散列函数解决冲突较为复杂，同时如果需要删除元素，会很麻烦
它的难点在于散列函数的选取：
注意：

三种散列函数都不能良好地满足均匀散列的要求，只能说双重散列的小姑哦接近最好
1

线性探查

公式：
$$\begin{gathered} 先取一个普通的散列函数h^{,},称之为辅助散列函数 \\ 有h(k,i)=(h^{,}(k)+i)modm,i=0,1,...,m-1 \\ i为存储空间的编号 \end{gathered}$$
这个方法是首先探测空间$T[h^{,}(k)]$，然后依次向下探查。
这种简单的方法特别容易造成k元素集中在一个存储范围内，使得探查越来越耗时间

二次探查

公式：
$$\begin{gathered} 依旧选择一个辅助散列函数h^{,} \\ h(k,i)=(h^{,}(k)+c_{1}i+c_2{i}^2)modm,i=0,1,...,m-1 \\ i为存储空间的编号,c_1,c_2为正整数 \end{gathered}$$
这种方法比线性探查要多加一个偏移量，但是经过证明，它不会避免元素在后期的集中，会造成轻微的群集

双重散列

公式：
$$\begin{gathered} 选择辅助散列函数h_1,h_2 \\ h(k,i)=(h_1(k)+i{h}_2(k))modm,i=0,1,...,m-1 \\ i为存储空间的编号 \end{gathered}$$
为了能查找整个散列表，有如下条件要满足：
$$\begin{gathered} 取m为素数 \\ 并设计一个总返回小于m的h_2 \end{gathered}$$

三、散列表的C语言实现

散列表的关键在于一个良好的散列函数，在编程逻辑上不具复杂性，因此：
这里用C语言只实现了相对简单的散列表。
运用了：

1.链接发解决冲突
2.除法散列法作为散列函数
1
2

#include
#include
#include



//要存的数据的个数 
#define SIZE 10
//得到散列表大小
//要求是m较小于2的整数幂的素数
//同时我们接受平均每个链表中有三个元素
//因此我们选择了此值 
#define M 10



//设计链表的数据结构 
typedef struct list
{
	//值 
	int key;
	//指向下一个结点的指针 
	list* p;
}list; 



//除法散列函数 
int HASH(int k)
{
	int n=0;
	n=k%M;
	return n;
} 



//获取链表的长度
//该长度也可以称为值的数量 
int list_length(list *a,int i)
{
	int length=0;//声明长度变量 
	//链表循环变量 
	list *temp;
	temp=a[i].p;
	//如果temp没有指向的空间，那么结束循环 
	while(temp!=NULL)
	{
		printf("success\n");
		length++;//一次循环代表有一个结点空间 
		temp=temp->p;//将循环变量指向下一个结点 
	}
	return length;//返回长度 
}



//释放动态分配的内存 
void destroy_list(list *a,int n)
{
	list *temp1;
	list *temp2;
	temp1=a[n].p;
	while(temp1!=NULL)
	{
		temp2=temp1;
		temp1=temp1->p;
		free(temp2);
	}
}



//插入值到链表
//该插入函数是将新值永远插入第一个位置 
void list_insert(list *a,int n,int num)
{
	list* temp;
	//如果不动态分配内存，那么内存会被系统在程序运行到某个结点被回收
	//导致无法存储值到程序结束 
	temp=(list *)malloc(sizeof(list));//动态分配内存 
	temp->key=num;
	//如果链表是空的，那么直接插入到头节点 
	if((a[n].p)==NULL)
	{
		temp->p=NULL;
		a[n].p=temp;
	}
	//如果链表不空，那么需要插入到头节点后，还要与原头结点连接 
	else
	{
		temp->p=a[n].p;
		a[n].p=temp;
	}
}



//链表信息打印 
void list_print(list *a,int n)
{
	list* temp;
	temp=(list *)malloc(sizeof(list));
	temp->p=a[n].p;
	printf("%d  |||",list_length(a,n));//打印大小
	//大小之后打印具体的值 
	while(temp->p!=NULL)
	{
		printf("%5d",temp->p->key);
		temp->p=temp->p->p;
	}
	free(temp);
	printf("\n");
}



//插入k值到散列表 
void LIST_HASH_INSERT(list *a,int k)
{
	int n=0;
	n=HASH(k);
	printf("%5d",n);
	list_insert(a,n,k);	
} 



//搜索k值的位置
int LIST_HASH_SEARCH(list *a,int k)
{
	int n=0;
	int j=0;
	n=HASH(k);
	list *temp;
	temp=a[n].p;
	while(temp!=NULL)
	{
		if(temp->key==k)
		{
			j++;
			return j; 
		}
		temp=temp->p;
	}
	if(j==0)
	{
		return 0;
	}
}



//打印位置信息函数
void HASH_PRINT(int n,int k)
{
	int num=0;
	num=HASH(k);
	if(n>0)
	{
		printf("k is the %dth data in %dth list\n",n,num);
	}
	else
	{
		printf("There is no k inside of LIST_HASH\n");
	}
} 

 

int main()
{
	int a[SIZE];
	list b[M];
	srand((unsigned)time(NULL));
	int ID;
	int i=0;
	//得到随机数组 
	for(i=0;i<SIZE;i++)
	{
		a[i]=rand()%100;
	}
	for(i=0;i<SIZE;i++)
	{
		printf("%5d",a[i]);
	}
	printf("\n");
	//将数据插入HASH
	for(i=0;i<SIZE;i++)
	{
	 	LIST_HASH_INSERT(b,a[i]);
	}
	//打印出HASH_LIST
	for(i=0;i<M;i++)
	{
		list_print(b,i);
	} 	
	//搜索一个在散列表中的数据 
	ID=LIST_HASH_SEARCH(b,250);
	HASH_PRINT(ID,250);		
	//搜索一个不在散列表中的数据 
	ID=LIST_HASH_SEARCH(b,5200);
	HASH_PRINT(ID,5200);
	//销毁链表
	for(i=0;i<M;i++)
	{
		destroy_list(b,i);		
	}			
	return 0;
}
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210

---

总结

文章的错误和不妥之处，请各位读者包涵指正
关于链表的知识可以参考文章：
《算法导论》学习（十二）----链表（C语言）