7.哈希表

7.1 哈希表引入

        哈希表的出现依旧是为了查找方便而设计的。在顺序结构中，查询一个值需要一一比较，复杂度为O(N)；在平衡树中，查询变为了二分查找，复杂度为O(logN)；而对于哈希表，我们可以通过特殊的映射关系，将其查询的复杂度变为O(1)。

        因此，哈希（散列）的主要思想是用于查找，希望可以不通过比较，一次性拿到要搜索的元素。为了实现这个目的，可以考虑将带存储的元素按照某种哈希方法（散列方法）映射到指定位置，这样就在存储元素和存储位置之间产生了一一映射关系。通过这种关系，我们可以根据待搜索的元素通过哈希函数直接计算出存储位置。类比于数学中一种特殊的映射关系——函数：给定一个自变量x（给一个带存储的元素的key），通过函数关系f（通过哈希函数Hash），得到一个因变量y（得到key对应的值，作为存储位置的标识）。

        通过以上的方法构建出来的结构即为哈希表（散列表）

        哈希函数用于计算不同的元素应该存储的位置。常见的哈希函数 Hash(key) ：

①直接定址法：即线性关系确定位置 Hash(key) = A*key+B

②除留余数法：即对哈希表的长度取模 Hash(key) = key%m

        如同函数一样，一个多个自变量可能映射到同一个因变量。哈希函数虽然决定了映射关系，但问题也很明显，即无法避免位置的冲突，我们一般将不同关键码而具有相同哈希地址的现象称为哈希冲突。为了解决哈希冲突，可以采取闭散列或者开散列两种方法。

7.2 闭散列（开放地址法）

        闭散列规定，当发生哈希冲突时，可以把当前的key存储到冲突位置的“下一个”位置。

7.2.1 结构设计

        对于开放地址法，哈希表采用数组的方式进行哈希表的组织，即数组的每个位置存放一个元素。当发生冲突时就按照既定的规则，找寻数组合适的空位。

        当存在这样“寻找”的操作时，因为单纯依靠数组中的值没有办法判断当前位置是否可用，因此需要通过一个标记来指明对应位置的状态。哈希表中的元素包括：空、占用、删除三种状态。空——位置没有元素，可以存放新元素；占用——当前位置已存在有效元素；删除——当前位置元素无效。给定这三种状态将使得我们的插入、删除、查找操作变得容易起来。

        给出如下基本结构，使用结构体将值和状态组织起来，存在数组中构成哈希表，_num成员记录存入的元素数量。

	//因为哈希冲突的存在，我们在占用对应位置时需要先对哈希表中对应位置的数据进行性质判断//哈希表中的元素包括 有效、已删除、空 三种状态，通过枚举常量来定义出这三种状态enum state{EMPTY,DELETE,EXIST};//哈希表元素既要包含key-value，还需要包含状态，因此使用结构体template <class K, class V>struct HashData{pair<K, V> _kv;state _state = EMPTY;};template<class K, class V, class HashFunc = HashFunc<K>>class HashTable {public://构造函数HashTable(){_table.resize(10);}private:vector<HashData<K, V>> _table;size_t _num = 0;};

7.2.2 哈希表模板

    template<class K, class V, class HashFunc = HashFunc<K>>

         对于这个模板参数，重点解释一下其中的HashFunc的作用。我们的哈希表采用除留取余的方法计算映射位置，采取这个哈希方法就表明我们的key必须要是可以取模的值，也就是整型。但是key不一定都是整型，例如string类型的key也是完全可以的。所以设定了HashFunc这个模板参数，用于接受一个仿函数，这个仿函数可以将key转化为可以进行取模运算的形式。

	//需要注意，当前哈希表的哈希函数是直接对key取模//但是当哈希表元素的key是其他类型，如string时，很明显这种取模运算就会产生错误，因此我们需要想办法将string对象转化为可以取模运算的数值//我们通过模板参数HashFunc来处理，这是一个仿函数类，通过这个仿函数我们可以得到到对应对象的可进行模运算的数字//这是哈希表缺省仿函数类，当key类型可以转换成size_t时即可不传参采取默认的仿函数template<class K>struct HashFunc {size_t operator()(const K& key){return (size_t)key;}};//类模板的特化，这样string类型也可以采取默认的仿函数了template<>struct HashFunc<string> {size_t operator()(const string& s){size_t ret = 0;for (const auto& e : s){ret = ret * 31 + e;	//string对象采取每次乘31再加下一个字符的策略}return ret;}};

        上述代码给出了HashFunc的模板类，对于一般的key直接尝试强制类型转换。另外可以对一些特殊情况，如string写出其模板特化，人为的将其转化为可计算的形式。

        使用了特化的形式就可以在哈希表的模板参数处给定缺省值，这样可以在实例化模板时不需要考虑string的HashFunc问题，自动使用缺省值的特化。

7.2.3 insert插入

        插入元素的操作有多个注意点，我们一一列举。

        ①哈希冲突处理方式

        在插入元素的过程中，势必会出现哈希冲突，而闭散列规定，当发生哈希冲突时，把当前的值存储到冲突位置的“下一个”位置。所以问题就转化为了如何去找这“下一个位置”。

        处理的方案有很多，此处只介绍两种方法。一般常用的方法是线性探测，即当发现当前位置冲突时，就+1尝试存在后一个位置，如果仍然冲突就继续向后+1寻找，本文采用的即为这种方法。另一种是很相似的二次探测，其冲突后所加的值为二次序列，即1 4 9 16...。

        当状态是EXIST的时候就说明被占用发生冲突，需要持续寻找直到找到非EXIST的位置。

        ②扩容

        如此向哈希表中存储肯定有容量满的时刻，因此我们还需要处理扩容逻辑。规定负载因子（实际就是数组占用率）大于等于0.7的时候就进行扩容。

        因为我们使用的是除留余数法，是根据哈希表的长度来进行取模映射的，所以当哈希表长度变化时，也就代表我们需要重新映射元素位置了。重新映射实际上也就是将原来的元素依次插入新扩容的表，于是我们可以复用Insert函数，代替我们完成插入操作。虽然效率没有变化，但是少写了部分代码，还是很棒的。

        ③不允许重复元素

        哈希表和set、map一样不允许重复元素的出现，因此需要通过Find来排除重复元素的情况。

		//插入bool Insert(const pair<K,V>& kv){//使用find函数排除重复的情况if (Find(kv.first)){return false;}//处理扩容的情况//当负载因子（已存储元素/哈希表总长度）>= 0.7时就进行扩容//已存储元素由成员_num记录，每次成功insert后_num++if (_num * 10 / _table.size() >= 7){//因为哈希函数计算中参考了哈希表长度，所以在扩容后会使得映射关系发生变化，所以需要一个一个重新调整//扩容方法：定义一个原先size大小二倍的数组，遍历原来的哈希表，将值一一映射到新的哈希表中，最后将这个局部变量与旧表交换，出函数作用域销毁旧表留下新表//我们发现上述方法中，将原值重新映射到新的哈希表中实际上就是对新表的insert，于是我们可以复用insert逻辑//由于在此阶段，新表不会涉及到重复或扩容问题，所以实际复用的是之后正常的插入逻辑HashTable<K, V> newtable;newtable._table.resize(2 * _table.size());for (int i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newtable.Insert(_table[i]._kv);}}_table.swap(newtable._table);}HashFunc hfs;size_t hashi = hfs(kv.first) % _table.size();//当发生哈希冲突时，采取线性探测的方法找寻下一个空位置//线性探测：从发生冲突的位置开始，依次向后逐个检查是否有空位置//与之相似的探测方法还有二次探测：从发生冲突的位置开始，按二次方的规律找后1、4、9、16…的位置是否有空位置while (_table[hashi]._state == EXIST){hashi = (hashi + 1) % _table.size();}//找到空位（DELETE、EMPTY），修改对应地址下的数据_table[hashi]._kv = kv;_table[hashi]._state = EXIST;_num++;return true;}

7.2.4 Find查找

        查找逻辑需要依照哈希函数找到开始查找的位置，也需要安装哈希冲突的处理方法既定的逻辑，按图索骥寻找可能的位置。在此过程中只有碰到了EMPTY才说明查找完毕，因为DELETE是被删除位置，它的“下一个位置”仍可能是通过哈希冲突占用的元素。

		//查找HashData<K, V>* Find(const K& key){HashFunc hsf;size_t hashi = hsf(key) % _table.size();while (_table[hashi]._state != EMPTY)	//注意DELETE不能作为判断查找完毕的标志{if (_table[hashi]._kv.first == key){return &_table[hashi];}hashi = (hashi + 1) % _table.size();}return nullptr;}

 7.2.5 Erase删除

        删除操作只需要找到位置后，将状态置为DELETE即可。

		//删除//删除只需要将对应位置的状态置为删除即可bool Erase(const K& key){if (HashData<K, V>* dst = Find(key)){dst->_state = DELETE;_num--;return true;}else{return false;}}

7.3 开散列（链地址法/拉链法）

        开散列在哈希表的每个位置定义一个哈希桶（也就是链表），在发生冲突时将后来的结点链接在当前位置的链表后，即一个位置可以有多个由链表链接起来的元素。

7.3.1 结构设计

        拉链法的哈希表每个位置由一个哈希桶组成，因此按照单链表的方法定义链表节点即可。由于每个元素均是new的结点，因此需要一个析构函数遍历整个哈希表的所有哈希桶来析构结点。

	template <class K, class V>struct HashNode{//结点的构造函数HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}pair<K, V> _kv;HashNode<K, V>* _next;};template<class K, class V, class HashFunc = HashFunc<K>>class HashTable {public:typedef HashNode<K, V> Node;//构造函数HashTable(){_table.resize(10, nullptr);}//析构函数~HashTable(){for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* tmp = cur;cur = cur->_next;delete tmp;}_table[i] = nullptr;}}private:vector<Node*> _table;size_t _num = 0;};

        拉链法的哈希表模板参数与开放地址法相同，不再解释。

7.3.2 Insert插入 

        和开放地址法相似的逻辑，也不允许重复元素，除此之外还有一些值得注意的问题。

        ①扩容

        首先是负载因子，拉链法由于采取链表的方式，因此不会存在存不进去的问题。哈希表短，元素多只会导致链表过长效率变低，因此仍然使用负载因子，当其大于1时就扩容。

        如果扩容逻辑参照开放地址法，创建新表再复用Insert函数，看似方便，但实际存在效率问题。因为拉链法采取的是链表形式，所以Insert操作需要new结点，而在全部插入后又将原来的所有节点都释放了，相当于把旧有结点全部释放然后又重新申请。

        为了避免这个问题，可以考虑直接转移结点，即根据结点的值直接更改结点的链接_next，这样就避免了重复的new和delete。

        ②插入方法

        对于一个哈希桶，当做一个单链表即可，最方便的插入元素方式即为头插。

		//插入bool Insert(const pair<K, V>& kv){//使用find函数排除重复的情况if (Find(kv.first)){return false;}HashFunc hfs;size_t hashi = hfs(kv.first) % _table.size();//处理扩容的情况//当负载因子（已存储元素/哈希桶总数量（也即哈希表长度））>= 1时就进行扩容,//已存储元素由成员_num记录，每次成功insert后_num++if (_num  / _table.size() >= 1){//同样的，在扩容后会使得映射关系发生变化，需要一个一个重新调整//扩容方法：定义一个原先size大小二倍的数组，遍历原来的哈希表，将值一一映射到新的哈希表中，最后将这个局部变量与旧表交换，出函数作用域销毁旧表留下新表//我们采取老方法，将这个过程看作向新表插入数据，复用insert//但是这种方法需要将原哈希表的结点全部释放后再new一遍，效率低/*HashTable<K, V> newtable;newtable._table.resize(2 * _table.size(), nullptr);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){newtable.Insert(cur->_kv);cur = cur->_next;}}_table.swap(newtable._table);*///我们可以采取直接转移结点的方法，遍历原哈希表，将其中的结点直接链在新哈希表中,实际上就是把Insert的复用部分再写一遍vector<Node*> newtable;	//新建一个vector作为新的tablenewtable.resize(2 * _table.size(), nullptr);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* tmp = cur->_next;//记录cur的nextsize_t hashi = hfs(cur->_kv.first) % newtable.size();//根据新表计算地址//头插cur->_next = newtable[hashi];newtable[hashi] = cur;cur = tmp;}_table[i] = nullptr;//原表置空是好习惯，此处换出去的是vector，析构时析构的也是vector<Node*>不会调用到哈希表的析构函数，所以不会释放结点，不置空也不会有问题}_table.swap(newtable);}//找到了对应位置后直接头插即可Node* newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;_num++;return true;}

7.3.3 Find查找

        在拉链法下查找，只需要根据哈希函数找到对应位置，然后遍历哈希桶即可。

		//查找//哈希函数定位到位置，遍历哈希桶寻找Node* Find(const K& key){HashFunc hsf;size_t hashi = hsf(key) % _table.size();Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}

7.3.4 Erase删除

        删除操作实际就只是单链表的删除操作，根据哈希函数确定单链表，然后进行删除即可，这是单链表的基操。

		//删除//因为是单链表的删除，需要遍历桶找到前驱节点,并且考虑头删的问题bool Erase(const K& key){HashFunc hsf;size_t hashi = hsf(key) % _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev == nullptr){_table[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;_num--;return true;}else{prev = cur;cur = cur->_next;}}return false;}