[C++][数据结构]哈希1：哈希函数的介绍与线性探测的实现

前言

学完了二叉树，我们要学当前阶段数据结构的最后一个内容了：哈希！！

引入

先来介绍两个用哈希封装的两个容器：unordered_map unordered_set

与map和set的不同：

map/set是双向迭代器，而另外两个是单向的
map/set有序，另外两个没有顺序

unordered_map

unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
它的迭代器至少是前向迭代器。

哈希

哈希就是散列，
就是这些值key和存储位置之间存在着映射的关联关系

哈希函数

哈希函数的内容也就是一个哈希是如何设计的

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

直接定址法–(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
- 优点：简单、均匀
- 缺点：需要事先知道关键字的分布情况
- 使用场景：适合查找比较小且连续的情况
除留余数法–(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
平方取中法–(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
折叠法–(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
随机数法–(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。
通常应用于关键字长度不等时采用此法
数学分析法–(了解)
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

说明

对于第一种方法的弊端很明显：
比如存两个值：1和1000，那我是不是要开1001个空间，空间太浪费了

我们用第二种方法，就能大大的节省空间

哈希碰撞

但还是有问题：
如果取余之后，有了同样的余数怎么办？？

对于两个数据元素的关键字 $k_i$ 和 $k_j$ (i != j)，有 $k_i$ != $k_j$ ，但有：Hash( $k_i$ ) == Hash( $k_j$ )，
即：**不同关键字通过相同哈希哈数计算出相同的哈希地址，**该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
发生哈希冲突该如何处理呢？

解决哈希冲突

补充：
哈希不会填满，到超过自己设定的负载因子的时候，会按照一定倍数扩容
负载因子/载荷因子 = 存进去的数据个数/表的大小
闭散列一般是0.7

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
那如何寻找下一个空位置呢？

基本结构

enum State
{EMPTY,//空EXIST,//存在DELETE//删除
};template<class K, class V>
struct HashData
{pair<K, V>_kv;		//键值对State _state = EMPTY;	//初始为空
};

线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入
1. 先找到对应的位置
2. 找到空位置或者遍历完停止查找（要注意循环到尾部的时候，下一个是头部）

	bool Insert(const pair<K, V>& kv)				//线性探测版本{if (Find(kv.first) == nullptr){return false;}if (_n*10 / _tables.size() >= 7){//方法2:比较神奇的写法HashTable<K, V>newHT(_tables.size() * 2);for (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);//把新的交换给旧的//旧的还能自动释放}size_t hashi = kv.first % _tables.size();while (_tables[hashi]._state == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}

查找

	HashData<const k, V>* Find(const K& key){size_t hashi = key % _tables.size();while (_tables[hashi]._state != EMPTY){if (key == _tables[hashi]._kv.first&& _tables[hashi]._state == EXIST){return &_tables[hashi];}hashi++;hashi %= _tables.size();}return nullptr;}

这里的返回值给指针是为了方便删除

删除
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影
响。
因此线性探测采用标记的伪删除法来删除一个元素。

// 哈希表每个空间给个标记
// EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};

	bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;return true;}return false;}

扩容
当超过负载因子的时候，我们就要扩容，
但是，扩容之后，可能原来不冲突的冲突了。
所以建议是：开一个新的空间来重新一一映射
在此提供两种思路：
开一个新空间，遍历旧表，将值给新表

			//方法1size_t newSize = _tables.size() * 2;vector<HashData>newTables(newSize);_tables.swap(newTables);

这种方法比较普通

这种方法更巧妙，每次插入新的值都去调用一次Insert，但是，是用扩容后的新表调用，所以不用再扩容，直接找到合适的位置存入即可，
并且交换新表和旧表

			//方法2:比较神奇的写法HashTable<K, V>newHT(_tables.size() * 2);for (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);//把新的交换给旧的//旧的还能自动释放

优化1

我们要想一想：如果参数是string这种无法进行%运算的类型怎么办？
所以我们要增加一个模板参数，来讲他们转化成可以运算的整形

那么我们可以将每一位的ASCII码值分别乘以131，来作为关键码去取余，这个131来自BKDRHash函数，我们可以看这篇文章的分析

字符串哈希算法

	struct HashFuncString{size_t operator()(const string& s){size_t hash = 0;for (auto e : s){hash += e;hash *= 131;}return hash;}};

优化2

因为string经常作为key，所以我们可以进行特化

	// 特化template<>struct HashFunc<string>{size_t operator()(const string& s){size_t hash = 0;for (auto e : s){hash += e;hash *= 131;}return hash;}};

这样就不用再单独去写一个HashFuncString函数了

二次探测

找下一个空位置的方法为：
$H_i$ = ( $H_0$ + $i^2$ )% m, 或者： $H_i$ = ( $H_0$ - $i^2$ )% m。其中：i = 1,2,3…， $H_0$ 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
也就是说，先对关键码进行加减运算，然后再取余