【数据结构】哈希表

前言

哈希概念

哈希函数

常见的哈希函数

解决哈希冲突

闭散列

线性探测

插入

删除

线性探测的模拟实现

整体框架

查找

插入

删除

前言

C++98中，STL提供了底层为红黑树结构的一系列关联式容器，查询时效率可达到O(logN)，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。

最好的查询是进行很少的比较次数就能够将元素找到，因此C++11中，STL提供了4个unordered系列的关联式容器，其所采用的底层结构为哈希结构，查询的效率达到O(1)，所采用的方法是通过某种函数使得元素的存储位置与存储的值key建立一一映射关系，查找时通过该函数快速查找到元素key达到O(1)的查找效率。

官方文档：unordered_map - C++ Reference

官方文档：unordered_set - C++ Reference

哈希概念

理想的查找方法是可以不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储结构，通过某种函数(HashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置

取元素比较，若关键码相等，则搜索成功。

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。但是按照上述哈希方式，向集合中插入元素44，会出现不同的数据通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

哈希函数

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的所有数值，而如果哈希表允许有m个地址时，其值域必须在0到m-1之间；
哈希函数计算出来的地址能均匀分布在整个空间中；

常见的哈希函数

直接定址法

取关键码的某个线性函数为哈希地址：Hash（Key）= A*Key + B

直接定址法适用于数据相对集中的场景，若数据集合为{8,9,12,14,18,10000}即数据相对分散时，易造成浪费空间；

除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p (p<=m)，将关键码转换成哈希地址；

解决哈希冲突

解决哈希冲突两种常见的方法是：闭散列和开散列

闭散列

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

线性探测

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

插入

删除

线性探测采用状态标记的方式解决上述问题即哈希表中每个空间存放状态标记，EMPTY表示此位置为空，EXIST表示此位置已经存放元素，DELETE表示此位置元素已经删除；线性探测采用标记的伪删除法来删除一个元素即设置该位置的状态为DELETE;

线性探测的模拟实现

整体框架

enum State
{EMPTY,//此位置为空EXIST,//此位置已经存放元素DELETE//此位置元素已经删除
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;
};template<class K,class V>
class HashTable
{
public://...
private:vector<HashData<K,V>> _tables;
//(vector中虽然提供size()函数，但由于vector底层为连续存储结构,哈希为映射关系即哈希表并不是依次存储所以实际存储的数据需要记录)size_t _n=0;//记录实际存储的数据个数
};

查找

哈希表控制负载因子在0.7以下，当插入的数据增多时，哈希表便进行扩容操作，所以哈希表一定存在空位置；

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

插入

哈希表中插入数据步骤如下：

查看哈希表中是否存在该键值的键值对，若已存在则插入失败；
判断是否需要调整哈希表的大小，若哈希表的大小为0，会发生%0错误，因此哈希表初始化设置哈希表长度为10，若哈希表的负载因子大于0.7，则首先创建一个新的哈希表，该哈希表的大小为原哈希表的两倍，然后遍历原哈希表，将原哈希表中的数据插入到新哈希表，最后将原哈希表与新哈希表交换即可；
将键值对插入哈希表；
哈希表中的记录实际存储的数据个数自增1；

注意：在将原哈希表的数据插入到新哈希表的过程中，由于哈希表长度的变化，需要重新根据哈希函数计算哈希值，哈希值确定每个数据在新哈希表中的插入位置；

将键值对插入哈希表的具体步骤如下：

通过哈希函数计算出对应的哈希地址；
若产生哈希冲突，则从哈希地址处开始，采用线性探测向后寻找一个状态为EMPTY或DELETE的位置；
将键值对插入到该位置，并将该位置的状态设置为EXIST；

//哈希表最初长度为0,线性探测出现%0错误
//resize()所开辟的空间实现size()与capacity()相等
//利用构造函数,将最初长度设置为10
HashTable(size_t size = 10)
{_tables.resize(size);
}

//插入逻辑
//插入的哈希数据键值key若在哈希表中已经存在,则插入失败返回false;
//控制负载因子在0.7以下,即插入的数据量增多,需要进行扩容
//线性探测合适的插入位置,插入数据,哈希表中存放数据的个数自增1并返回true;
bool Insert(const pair<K, V>& kv)
{//哈希表中查找插入的数据的键值key是否存在,存在则插入失败HashData<K, V>* ret = Find(kv.first);if (ret != nullptr){return false;}//控制负载因子小于0.7if ((_n * 10) / _tables.size() >= 7){//异地扩容://思路1://size_t newsize=_tables.size()*2;//开辟哈希表长度为newsize的新表//vector<HashData<K,V>> newtables(newsize);//遍历旧表,映射到新表(插入新表时所有数据重新映射,继续在新表中线性探测查找插入位置)//...//交换旧表与新表//_tables.swap(newtables);//思路2:(本质:复用哈希表中insert()中的线性探测)//创建<key,value>的哈希表,利用构造函数解决容量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();//由于哈希表底层结构采用vector,vector连续存储数据,有效数据的个数为_tables.size()//size_t hashi = kv._first%_tables.capacity();//数据集合虽然可以映射到[_tables.size(),_tables.capacity()]区间范围内,但无法插入到此段区间内,因为vector连续存储while (_tables[hashi]._state == EXIST){++hashi;hashi = hashi%_tables.size();//走到哈希表末尾位置,返回起始位置查找}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;
}

删除

哈希表中删除数据的步骤如下：

查看哈希表中是否存在该键值的键值对，若不存在则删除失败；
若键值存在，则将该键值对所在位置的状态改为DELETE即可；
哈希表中的实际存储元素个数自减1；

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

当哈希表中的HashData存储string时，string类型的数据不支持取模运算，若采用运算符重载，需要更改库中的string，除留余数法如何建立string类型数据与存储位置的映射关系吗?

解决方案：

首先将string类型转换为整型，建立string类型与整型的映射关系（采用仿函数实现）；
其次转换后的整型值与存储位置建立映射关系（模版参数增加1个接收仿函数）；

思考：任意类型的值如何转换为整型值？

     1. 本身为整型家族的成员，则可以通过强制类型转换可以转化为整型；

     2. 对于string类型，可以取每个字符的ASCII码值，逐个相加且每相加一次乘以权重31；

     3. 对于其他类型，按数据类型各自的特征自定义仿函数实现转换为整型；

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto e : key){hash += e;hash *= 31;//BKDR字符串哈希算法,累乘因子为31}return hash;}
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public://...
private:vector<HashData<K, V>> _tables;size_t _n = 0;//记录哈希表中实际存放的数据个数
};