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

---

前言

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

---

一、散列表

1.什么是直接寻址表？

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

2.什么是散列表？

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

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

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

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

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

3.为什么需要散列表？

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

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

4.散列表的核心点

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

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

二、散列表的基本思想

1.散列函数

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

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

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

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

除法散列法

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

乘法散列法

公式：
$$h(k)=\lfloor m(kAmod1)\rfloor$$
乘法散列法的优点是对m的选择不是特别关键，一般选择 m = 2 x ， x 为某整数 m=2^x，x为某整数 m=2x，x为某整数
根据Knuth的证明， A = 5 − 1 2 = 0.6180339887... A=\frac{\sqrt{5}-1}{2}=0.6180339887... A=25 −1=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值以链表结点的方式，插入对应的那个链表中。
本质上是一个链表数组的结构
注意：

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

（2）开放寻址法

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

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

线性探查

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

二次探查

公式：
依旧选择一个辅助散列函数 h , h ( k , i ) = ( h , ( k ) c 1 i c 2 i 2 ) m o d   m , i = 0 , 1 , . . . , m − 1 i 为存储空间的编号 , c 1 , c 2 为正整数 依旧选择一个辅助散列函数h^,\\ h(k,i)=(h^,(k) c_1i c_2i^2)mod\ m,\quad i=0,1,...,m-1\\ i为存储空间的编号,c_1,c_2为正整数 依旧选择一个辅助散列函数h,h(k,i)=(h,(k) c1i c2i2)mod m,i=0,1,...,m−1i为存储空间的编号,c1,c2为正整数
这种方法比线性探查要多加一个偏移量，但是经过证明，它不会避免元素在后期的集中，会造成轻微的群集

双重散列

公式：
选择辅助散列函数 h 1 , h 2 h ( k , i ) = ( h 1 ( k ) i h 2 ( k ) ) m o d   m , i = 0 , 1 , . . . , m − 1 i 为存储空间的编号 选择辅助散列函数h_1,h_2\\ h(k,i)=(h_1(k) ih_2(k))mod\ m,\quad i=0,1,...,m-1\\ i为存储空间的编号 选择辅助散列函数h1,h2h(k,i)=(h1(k) ih2(k))mod m,i=0,1,...,m−1i为存储空间的编号
为了能查找整个散列表，有如下条件要满足：
取 m 为素数 并设计一个总返回小于 m 的 h 2 取m为素数\\并设计一个总返回小于m的h_2 取m为素数并设计一个总返回小于m的h2

三、散列表的C语言实现

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

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

#include<stdio.h>
#include<stdlib.h>
#include<time.h>



//要存的数据的个数 
#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("]",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("]",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()0;
	}
	for(i=0;i<SIZE;i  )
	{
		printf("]",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;
}

---

总结

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

这篇好文章是转载于：学新通技术网