数据结构与算法C++实现（10）之哈希表

一、概念

散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f，是的每个关键字key对应一个存储位置f(key)。查找时，根据这个对应的关系找到给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上。我们把这种对应关系f成为散列函数，又称为哈希(Hash)函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续空间称为散列表或哈希表(Hash-Table)。

二、散列表的构造方法

2.1 直接定址法
直接定址法使用下面的公式

f(key)=a×key+b,b为常数
 

比如统计出生年份，那么就可以使用f(key)=key−1990 f(key) = key-1990f(key)=key−1990来计算散列地址。

2.2 除留取余法
这种方法是最常用的散列函数构造方法，对于表长为m的散列公式为
 

这里的mod是取余的意思

2.3 数字分析法
分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址这里使用一个手机号码作为例子，手机号码是一个字符串，一般的说，后面4位是真正的用户号。

2.4 折叠法
把关键词分割成位数相同的几个部分，然后叠加。

2.5 平方取中法

三、冲突解决方法

常用处理冲突的思路：

• 换个位置: 开放地址法
• 同一位置的冲突对象组织在一起: 链地址法

开放地址其实是一种治标不治本的方法，因此我们这里只介绍链地址法。

从图中可以看出，哈希表的每个地址中存的是一个链表的地址，地址冲突的元素，都放在这个链表中，这样就不用担心地址冲突啦！

代码：

#include<iostream>
#include<list>
#include<vector>
using namespace std;

template<class T>
class Hash
{
	public:
		Hash(int num = 53) : tables(num, nullptr){ }
		unsigned int HashFunction(const T& item) // 产生哈希数 
		{
			unsigned result = 0;
			char* new_ptr = (char*)(&item);//强行转换为字符指针，为了下面的for循环中 
			for(int i = 0; i < sizeof(item); ++i)//一个字节一个字节的产生独有的哈希数 
			{
				result += new_ptr[i] * 3 + 5;//可以设计成自己喜欢的方程，来产生哈系数 
			}
			return result;
		}
		void Push(const T& item)
		{
			unsigned int hash_num = HashFunction(item);
			hash_num = hash_num % tables.size();//取余，将哈系数控制在我们的索引之内 
			if(tables[hash_num] == nullptr)
			{
				tables[hash_num] = new list<T>;
				(*tables[hash_num]).push_back(item);
			}
			else
			{
				(*tables[hash_num]).push_back(item);
			}
		}
		void Delete(const T& item)
		{
			unsigned int hash_num = HashFunction(item);
			hash_num = hash_num % tables.size();
			if(tables[hash_num] == nullptr)
			{
				return;
			}
			else
			{
				(*tables[hash_num]).remove(item);
			}
			
			if((*tables[hash_num]).size() == 0)//如果链表为空，就将这个链表delete 
			{
				delete tables[hash_num];
				tables[hash_num] = nullptr;
			}
		} 
	private:
		vector<list<T>*> tables; 	
};


int main()
{
	Hash<int> my_hash_table;
	for(int i = 0; i < 10; ++i)
	{
		my_hash_table.Push(i*6);
	} 
	
	my_hash_table.Delete(6);
	
	
	return 0;
}