【数据结构篇C++实现】- 哈希表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构篇C++实现】- 哈希表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

友情链接：C/C++系列系统学习目录

🚀一、哈希表的原理精讲

🚢（一）概念

哈希表：也叫做散列表。是根据关键字和值（Key-Value）直接进行访问的数据结构。也就是说，它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的一个存储位置，然后把键值对映射到哈希表上的对应位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数（散列函数），用于存放记录的数组叫做哈希表（散列表）。

哈希表是基于快速存取的角度设计的，也是一种典型的“空间换时间”的做法，本质上是由数组衍生而来，其核心就是哈希函数

几个核心概念：

键(key)：组员的编号如， 1 、 5 、 19 。。。
值(value)：组员的其它信息（包含性别、年龄和战斗力等）
索引：数组的下标(0,1,2,3,4) ，用以快速定位和检索数据，同时可以把该数组称为索引数组
哈希函数：将组员编号映射到索引上，一般采用求余法

c++哈希表,数据结构与算法,数据结构,散列表,c++,哈希表

图中，Key为28，通过哈希函数计算存放在哈希表中的位置，得到索引为：28 % 5 = 3，但是如此的话就会造成一个问题：如果还有个学生的学号为33，通过哈希函数计算后得到的数组存放位置下标也为3，这种情况就是待会要讲的哈希冲突

🚢（二）常见哈希函数的构造方法

⛳1.直接定址法

如果我们现在要对0～100岁的人口数字统计表，如表所示，那么我们对年龄这个关键字就可以直接用年龄的数字作为地址。此时f (key) =key。

c++哈希表,数据结构与算法,数据结构,散列表,c++,哈希表

如果我们现在要统计的是80后出生年份的人口数，如表所示，那么我们对出生年份这个关键字可以用年份减去1980来作为地址。此时f (key)=key-1980。

c++哈希表,数据结构与算法,数据结构,散列表,c++,哈希表

也就是说，我们可以取关键字的某个线性函数值为散列地址，即f (key) =axkey+b (a、b为常数)
这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。

⛳2.数字分析法

例如当手机号码为关键字时，其11位数字是有规则的，此时是无需把11位数值全部当做散列地址，这时我们给关键词抽取，抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数中是常常用到的手段。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

⛳3.平方取中法

这个方法计算很简单，假设关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227，用做散列地址。再比如关键字是4321，那么它的平方就是18671041，抽取中间的3位就可以是671，也可以是710，用做散列地址。平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。

⛳4.除留余数法

这是一种最简单、最常用的方法，假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为H ( k e y ) = k e y % p ( p < = m ) 事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。
除留余数法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。

⛳5.随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。也就是H ( k e y ) = random ( k e y ) 这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

🚢（三）哈希冲突与处理方法

哈希函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计的好的哈希函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

⛳1.开放地址法

所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

举例：就是当我们去教室上课，发现该位置已经存在人了，所以我们应该寻找新的位子坐下，这就是开放定址法的思路。如何寻找新的位置就通过以下几种方法实现。

（1）线性探测法

当我们的所需要存放值的位置被占了，我们就往后面一直加1并对m取模直到存在一个空余的地址供我们存放值，取模是为了保证找到的位置在0~m-1的有效空间之中。

它的公式是:
$f_{i}(key)=(f(key)+d_{i})MODm(d_{i}=1,2,3,......,m-1)$

c++哈希表,数据结构与算法,数据结构,散列表,c++,哈希表

存在问题：出现非同义词冲突（两个不相同的哈希值，抢占同一个后续的哈希地址）被称为堆积或聚集现象。

（2）平方探测法

当我们的所需要存放值的位置被占了，会前后寻找而不是单独方向的寻找。

公式：
$h(x)=(Hash(x) +i)mod (Hashtable.length);（i依次为+(i^2)和-(i^2)）$
c++哈希表,数据结构与算法,数据结构,散列表,c++,哈希表

（3）再哈希法

同时构造多个不同的哈希函数，等发生哈希冲突时就使用第二个、第三个……等其他的哈希函数计算地址，直到不发生冲突为止。虽然不易发生聚集，但是增加了计算时间。

总结：

c++哈希表,数据结构与算法,数据结构,散列表,c++,哈希表

⛳2.链地址法

将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。

例如，关键字序列为{ 12 , 67 , 56 , 16 , 25 , 37 , 22 , 29 , 15 , 47 , 48 , 34 }，我们用除留余数法构造散列函数H ( k e y ) = k e y % 12 ，用拉链法处理冲突，建立的表如下图所示。

我们将每一条链表称为哈希桶，数组成员为每一个索引值相同的多个元素

c++哈希表,数据结构与算法,数据结构,散列表,c++,哈希表

⛳3.公共溢出区法

这个方法其实就更加好理解，就是把凡是冲突的家伙额外找个公共场所待着。我们为所有冲突的关键字建立了一个公共的溢出区来存放。

就前面的例子而言，我们共有三个关键字37 , 48 , 34与之前的关键字位置有冲突，那么就将它们存储到溢出表中，如下图所示。

c++哈希表,数据结构与算法,数据结构,散列表,c++,哈希表

如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

🚀二、哈希表的算法实现

为了减少哈希冲突的现象出现，这里我们就讲解一下链地址这种处理方法的实现，一般我们称为哈希链表

c++哈希表,数据结构与算法,数据结构,散列表,c++,哈希表文章来源地址https://www.toymoban.com/news/detail-782267.html

1.哈希链表的结构体定义

#define DEFAULT_SIZE 3 //默认哈希表大小是3
 
typedef struct _ListNode
{
	int key;
	int data;
	struct _ListNode *next;
}ListNode,*List,*Element;//List作为每个哈希桶的头结点，不保存元素
 
typedef struct _HashTable
{
	List *Lists;//保存所有哈希桶头结点的数组，是个二级指针
	int tableSize;//数组大小 也即哈希桶的个数
}HashTable;

2.哈希函数

//求余数法 根据key 定为桶的位置
int Hash(int key, int tableSize)
{
	return (key%tableSize);
}

3.初始化哈希链表

//初始化哈希表
HashTable * InitHashTable(int tableSize)
{
	HashTable *ht=new HashTable;
	if (!ht) return NULL;
 
	tableSize <= 0 ? DEFAULT_SIZE : tableSize;//如果哈希表数组大小小于等于0 则取默认大小
	ht->tableSize = tableSize;
 
	ht->Lists = new List[tableSize];
	if (!ht->Lists)
	{
		delete ht;
		return NULL;
	}
 
	//为数组中每一个哈希桶的头结点初始化
	for (int i=0;i<tableSize;i++)
	{
		ht->Lists[i] = new ListNode;
		if (!ht->Lists[i])
		{
			delete ht->Lists;
			delete ht;
			return NULL;
		}
		
		//并将头结点置空
		memset(ht->Lists[i], 0, sizeof(ListNode));
	}
 
	return ht;
	
}

4.哈希表查找元素

//根据key值查找哈希表中元素
Element Find(HashTable *ht,int key)
{
 
	int i = Hash(key, ht->tableSize);
	Element tmp = NULL;
    tmp = ht->Lists[i]->next; //取出key所在数据桶的第一个元素
 
	while (tmp!=NULL)
	{
		if (tmp->key == key) return tmp;//找到相同元素则将元素返回
		else tmp = tmp->next;//没有找到则继续找下一个
	}
 
	return tmp;
}

5.哈希表插入元素

//插入元素
bool InsertHashTable(HashTable* &ht, int key, int value)
{
	
	if (Find(ht, key) != NULL)//如果找到了相对应的key的元素 则证明插入元素已经因为存在 因为键值key是惟一的
	{
		printf("Element has existed !");
		return false;
	}
	
	Element L = ht->Lists[Hash(key,ht->tableSize)];//找出 key所对应哈希桶的头结点
    
	//采用头插法插入元素
	Element q = new ListNode;
	if (!q) return false;
 
	q->data = value;
	q->key = key;
	q->next = L->next;
	L->next = q;
 
	return true;
 
}

6.哈希表删除元素

bool DeleteHashNode(HashTable* &ht, int key)
{
	int i = Hash(key, ht->tableSize);
 
	List L = ht->Lists[i];//找到key所在哈希桶的头结点
	Element e = L->next;//找到第一个元素
 
	while (e != NULL && e->key!=key)
	{
		L = e;
		e = e->next;
	}
 
	if (e == NULL)
		return false; //如果没有找到key所对应的元素 返回false
 
	//从桶链表中删除元素e
	L->next = e->next;
	delete e;
	return true;	
}

7.程序清单

// 哈希表Hash.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//Author：See QQ3492625357 
//代码为手写，程序通过简单测试，其中可能有误或不当之处欢迎指正
 
#include <iostream>
 
#define DEFAULT_SIZE 3 //默认哈希表大小是3
 
typedef struct _ListNode
{
	int key;
	int data;
	struct _ListNode *next;
}ListNode,*List,*Element;//List作为每个哈希桶的头结点，不保存元素
 
typedef struct _HashTable
{
	List *Lists;//保存所有哈希桶头结点的数组
	int tableSize;//数组大小 也即哈希桶的个数
}HashTable;
 
//求余数法 根据key 定为桶的位置
int Hash(int key, int tableSize)
{
	return (key%tableSize);
}
 
//初始化哈希表
HashTable * InitHashTable(int tableSize)
{
	HashTable *ht=new HashTable;
	if (!ht) return NULL;
 
	tableSize <= 0 ? DEFAULT_SIZE : tableSize;//如果哈希表数组大小小于等于0 则取默认大小
	ht->tableSize = tableSize;
 
	ht->Lists = new List[tableSize];
	if (!ht->Lists)
	{
		delete ht;
		return NULL;
	}
 
	//为数组中每一个哈希桶的头结点初始化
	for (int i=0;i<tableSize;i++)
	{
		ht->Lists[i] = new ListNode;
		if (!ht->Lists[i])
		{
			delete ht->Lists;
			delete ht;
			return NULL;
		}
		
		//并将头结点置空
		memset(ht->Lists[i], 0, sizeof(ListNode));
	}
 
	return ht;
	
}
 
//根据key值查找哈希表中元素
Element Find(HashTable *ht,int key)
{
 
	int i = Hash(key, ht->tableSize);
	Element tmp = NULL;
    tmp = ht->Lists[i]->next; //取出key所在数据桶的第一个元素
 
	while (tmp!=NULL)
	{
		if (tmp->key == key) return tmp;//找到相同元素则将元素返回
		else tmp = tmp->next;//没有找到则继续找下一个
	}
 
	return tmp;
}
 
//插入元素
bool InsertHashTable(HashTable* &ht, int key, int value)
{
	
	if (Find(ht, key) != NULL)//如果找到了相对应的key的元素 则证明插入元素已经因为存在 因为键值key是惟一的
	{
		printf("Element has existed !");
		return false;
	}
	
	Element L = ht->Lists[Hash(key,ht->tableSize)];//找出 key所对应哈希桶的头结点
    
	//采用头插法插入元素
	Element q = new ListNode;
	if (!q) return false;
 
	q->data = value;
	q->key = key;
	q->next = L->next;
	L->next = q;
 
	return true;
 
}
//删除元素
bool DeleteHashNode(HashTable* &ht, int key)
{
	int i = Hash(key, ht->tableSize);
 
	List L = ht->Lists[i];//找到key所在哈希桶的头结点
	Element e = L->next;//找到第一个元素
 
	while (e != NULL && e->key!=key)
	{
		L = e;
		e = e->next;
	}
 
	if (e == NULL)
		return false; //如果没有找到key所对应的元素 返回false
 
	//从桶链表中删除元素e
	L->next = e->next;
	delete e;
	return true;	
}
int main()
{
	int elem[] = { 100,200,300,400,500,600,700,800,900 };
 
	HashTable *HT = NULL;
	HT = InitHashTable(DEFAULT_SIZE);
	if (!HT) return -1; 
 
	for (int i=0;i< sizeof(elem) / sizeof(elem[0]);i++)
	{
		InsertHashTable(HT, i, elem[i]);
	}
	
	//输出测试
	for (int i = 0; i < sizeof(elem) / sizeof(elem[0]); i++)
	{
		Element tmp = Find(HT, i);
		if (tmp!=NULL)
		{
			std::cout << tmp->data << " ";
		}
		
	}
	std::cout << std::endl;
 
	//把key=3删除 测试输出结果
	DeleteHashNode(HT, 3);
	std::cout << "删除key=3 value=400 后 输出哈希表" << std::endl;
	for (int i = 0; i < sizeof(elem) / sizeof(elem[0]); i++)
	{
		Element tmp = Find(HT, i);
		if (tmp != NULL)
		{
			std::cout << tmp->data << " ";
		}
 
	}
	std::cout << std::endl;
 
	system("pause");
}