数据结构：哈希表

1.散列表的概念:

根据要存储的数据记录的关键字值计算出应该存储的位置

基本思想:记录的存储位置与关键字之间存在对应关系

Loc(i)=H(keyi)-----等号右边就称之为hash函数.等号左边就是对应的存储位置;

2.哈希表的优缺点

这个就是散列表的特点:查找效率高,空间利用率低;（以空间换时间）

3.使用散列表要解决好两个问题:

(1) 构造好的散列函数:所选函数尽可能简单,以便提高转化速度;

    所选函数对关键码计算出的地址,应在散列地址中均匀分布,以减少空间浪费;

(2) 指定一个好的解决冲突的方案:查找时,如果从散列函数计算出的地址中查不到关键码,则应当依据解决冲突的规则,有规律地查询其他相关单元.

那么构造散列函数需要考虑的因素有哪些呢?(了解)

1.执行速度(即计算散列函数所需的时间); 2,关键字的长度; 3,散列表的大小

4,关键字的分布情况; 5查找频率;

4.构造散列函数的6个方法

1.直接地址法 2数字分析法 3平方取中法 4折叠法 5除留余数法 6随机数法

1.  直接地址法:

H(key)=a*key+b (a,b为常数),

例子:{100,300,500,700,800,900},哈希函数为Hash(key)=key/100,其实就是a=1/100,b=0;

那么以此函数建立的哈希表为:

优点:以关键码Key的某个线性函数值为散列地址,不会产生冲突;

为什么不会产生冲突?

y=ax+b 线性函数,x唯一,那么y唯一

缺点:要占用连续的地址空间,空间效率低.

直接定址法我们也比较常用,因为简单,同时优点是不会产生冲突,缺点是要占用连续的地址空间,空间效率低.

2.除留余数法

用关键字除以p得到的余数作为关键字的存储位置.

Hash(key)=key%p(p是一个整数)

那么关键是怎么取到合适的除数p?

技巧:设表长为m,取p<=m且为质数

例如{15,23,27,38,53,61,70},散列函数Hash(key)=key%7,那么哈希表为:

查找的时候同样用这个哈希函数,比如我们要查找70.用10除以7余数为0,直接去0号位置查找.

以上就是我们常用的散列表的构造方法:直接定址法和除留余数法.

5.处理冲突的方法

处理冲突的方法:

1.开放地址法(开地址法) 2.链地址法(拉链法) 3.再散列法(双散列函数法)

4.建立一个公共溢出区;

开地址法:

基本思想:有冲突时就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将元素存入.(开放地址法的常用方法:线性探测法,二次探测法,伪随机探测法)

Hi=(Hash(key)+di)%m (1<=i<m)

m为哈希表长度,di为增量序列1,2,……m-1,且di=i;

代码实现:

//这是配置好的模板文件
#include <iostream>
#include <string>
using namespace std; 
#define m 16 //哈希表长度
#define NONE -1//初始化哈希表为空
#define p 13 //p<=m,p为质数
//哈希表：除留余数、开地址法（线性探测）
 
typedef struct Hash
{
	int key;//关键字
	//其他项
}Hash ,HashTable[m];
 
//初始化
void init_HashTable(HashTable ht)
{
	for (int i = 0; i < m; i++)
	{
		ht[i].key = NONE;
	}
}
static int H(int key)
{
	return key % p;
}
bool Insert(int k, HashTable ht)
{
	int n1 = H(k);
	for (int i = 0; i < m; i++)
	{
		int n = (n1 + i)% m;
		if (ht[n].key == k)
		{
			return true;//此值已经在哈希表中存在，不允许重复
		}
		else if (ht[n].key == NONE)
		{
			ht[n ].key = k;
			return true;
		}
	}
	//满，失败
	return false;
}
void Show(HashTable ht)
{
	for (int i = 0; i < m; i++)
	{
		printf("%d   ", ht[i].key);
	}
}
int main()
{
	HashTable ht;
	init_HashTable(ht);
	int arr[16] = { 3,5,7,1,2,9,28,25,6,11,10,15,17,23,34,19 };
	for (int i = 0; i < m; i++)
	{
		Insert(arr[i], ht);
	}
 
	Show(ht);
	return 0;
}

二.拉链法

(第二种解决哈希冲突的方法,也更重要)

基本思想:相同散列地址的记录链成一单链表,m个散列地址就设m个单链表,然后用一个数组将m个单链表的表头指针存储起来,形成一个动态的结构.

例如:一组关键字为{19,14,23,1,68,20,84,27,55,11,10,79},散列函数为:Hash(key)=key%13,

就会发现有些元素是同义词,比如14%131,1%131,27%13==1,14,1,27是同义词

上图不好,我们最好能用头插法建立哈希表,头插法速度快，O(1)

最多有m个单链表,编号为0-m-1,用一个数组将m个单链表的表头指针存起来.

代码实现：

//这是配置好的模板文件
#include <iostream>
#include <string.h>
#include<assert.h>
using namespace std; 
#define m 13//哈希表长度
#define None -1
//哈希表：除留余数法+链地址法
typedef struct DateType
{
	int key;//关键字
	
}DateType;
typedef struct Node
{
	DateType date;
	struct Node* next;
}Node;
typedef struct
{
	Node* next;
}Hashtable[m];
//计算key 的哈希值，哈希函数为H(key)=key%m
static int H(int key)
{
	return key % m;
}
//初始化哈希表
void InitHashtable(Hashtable ht)
{
	assert(ht != NULL);
	if (!ht)
	return;
 
	for (int i = 0; i < m; i++)//将链表制空
	{
		ht[i].next = NULL;
	}
}
//查找关键key,返回节点地址
Node* Search(const Hashtable ht, int key)
{
	int n = H(key);
	for (Node* p = ht[n].next; p != NULL; p = p->next)
	{
		if (p->date.key == key)
			return p;
	}
	return NULL;
}
 
//插入
bool Insert(Hashtable ht,int key)//不存重复的值
{
	int n = H(key);
	if (Search(ht, key))//找到了相同的哈希值，则不允许存储重复数据，算法可用哈希表去重
	{
		return false;
	}
	Node* node = (Node*)malloc(sizeof(Node));
	assert( node!= NULL);
	
	//头插//时间复杂度O(1);尾插O(n)
	node->date.key = key;
	node->next = ht[n].next;
	ht[n].next = node;
	return true;
 
}
void Show(Hashtable ht)
{
	for (int i = 0; i < m; i++)
	{
		printf("哈希值为%d有：", i);
		for (Node* p = ht[i].next; p != NULL; p = p->next)
		{
			printf("%d ", p->date.key);
		}
		printf("\n");
	}
}
int main()
{
	Hashtable ht;
	InitHashtable(ht);
	int arr[16] = { 3,5,7,1,2,9,28,25,6,11,10,15,17,23,34,19 };
	//int arr[16] = { 15,19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79 };
	for (int i = 0; i < m; i++)
	{
		Insert(ht,arr[i] );
	}
	Show(ht);
	return 0;
}

总结

1.链地址法的优点:

• 非同义词不会冲突,无”聚集”现象;
• 链表上节点空间动态申请,更适合于表长不确定的情况.

开地址法非同义词也会产生冲突（比如原来需要存储的地址有元素,我们放入下一个地址,那么下一个地址需要存储的元素本来和这个不是同义词,但是也产生冲突了,这种就叫做聚集现象.）

而链地址法不会有这种问题,因为它的同义词都挂在各自的链表上,非同义词之间没有冲突,没有聚集现象;

2.思考:哈希表查找的时间复杂度?

不是O(1),如果完全没有冲突,是O(1),但是一般都会有冲突;

结论:哈希表的查找的时间复杂度不是O(1),但是逼近O(1);

3.影响时间复杂度的因素有散列函数和解决冲突的方法;

散列函数是不是能够让元素比较均匀的分布在散列表中.

解决冲突的方法是看看解决的冲突解决的是不是比较好,如果解决冲突解决的比较好,那么它的时间复杂度就会比较小.

4.几点结论:

• 散列表技术具有很好的平均性能,优于一些传统的技术;
• 链地址法优于开地址法

• • 是查找效率,一个是链地址它是动态的,表的长度是动态的,比较容易修改,而且如果做插入和删除的操作也比较方便.所以链地址法优于开地址法.

• 除留余数法作散列函数优于其他类型函数

• • 更均匀一些,通常我们的除数取一个质数,取一个小于等于表长的质数更好.这个就会获得一个比较好的散列效果.