哈希表的实现（上）

前言

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，分别unordered_map、unordered_set和unordered_multimap、unordered_multiset。他们的底层便用到了哈希表。本文将从哈希表的基本实现、封装、迭代器的实现、const迭代器的实现顺序进行介绍。

哈希

引入

在介绍前，我们先来做一道简单的题目，这种思想就用到了哈希。

387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

 此题可以用暴力查找，一遍一遍的统计每个字母的个数，但这种方法时间复杂度太大了。直接说优化方法，我们可以把每个字母和数组的下标进行映射，我们知道每个字符都可以通过assic转换为一个数，比如'a'这个字母，只要将他在减去一个'a'，那么得到的就是0，我们开一个int数组，大小为26，这样刚好存入26个英文字母。这样只需要遍历一遍字符串，便可以把所有的字母都统计一遍，然后在遍历一遍，就能得到哪个出现了一次。代码如下:

class Solution {
public:int firstUniqChar(string s) {vector<int> arr(26);for(int i = 0;i<s.size();i++){arr[s[i]-'a']++;}for(int i = 0;i<s.size();i++){if(arr[s[i]-'a']==1)return i;}return -1;}
};

 通过assic的转换与数组下标取得映射关系，这种思想就用到了哈希，接下来我们就详细介绍一下哈希。

哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素
时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即
O()，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

插入元素

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

搜索元素

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

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

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

为哈希表 (Hash Table)( 或者称散列表 )。

这就是哈希的概念，可能看着有些复杂，但我给大家举一个例子，就清楚了。

例如：数据集合{1，7，6，4，5，9}；

哈希函数设置为： hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

 用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快。

但这样就会有一个问题，当我们插入11或者14时就会出现多个数值映射一个位置的情况。就是哈希冲突

哈希冲突

原因

出现上面的情况有以下几种原因：

 

1. 哈希函数设计不合理：如果哈希函数不能将键均匀地分布到哈希表的各个位置，就会导致某些位置被频繁访问，从而增加冲突的概率。
2. 哈希表大小有限：哈希表的大小是有限的，而键的数量可能是无限的。当键的数量超过哈希表的大小时，冲突就不可避免。
3. 键的分布不均匀：如果键的分布本身就不均匀，那么即使哈希函数设计得再好，也无法完全避免冲突。

 解决方法

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

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有

空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。如果被装满，则进行扩容。

下面介绍闭散列中的一种解决方法，就是线性探索。

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

插入：

通过哈希函数获取待插入元素在哈希表中的位置

如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，

使用线性探测找到下一个空位置，插入新元素

如果装满则进行扩容处理

删除

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素

会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影

响。因此 线性探测采用标记的伪删除法来删除一个元素。

下面我们来进行实现。

首先我们需要三个状态来表示该位置的情况。

	enum Status{EMPTY,EXIST,DELETE};

 接下来我们在实现一个节点

	template<class K, class V>struct HashData{pair<K, V> _kv;Status _s;          //状态};

暂时先实现为KV结构，后面会更改。

 接下来是最基本的哈希表结构。

class HashTable{public:HashTable(){_tables.resize(10);}private:vector<HashData> _tables;size_t _n = 0; // 存储的关键字的个数};
}

 定义一个vector<HashData>类型的数组，在定义一个_n表示存储关键字的数量，构造函数中先给vector开十个大小的空间。之后我们来进行插入操作。

Insert

插入操作时，我们需要规定一个负载因子，它表示的是该空间中非空所占空间的比例，如果超出这个值就需要扩容，通常设置为0.7比较合适。（设计太大，那么产生冲突的可能性就越大，但相对于来说节省点空间，设计太小，产生冲突可能性小，但浪费了大量空间）代码如下：

	bool Insert(const pair<K, V>& kv){// 负载因子0.7就扩容if (_n*10 / _tables.size() == 7){size_t newSize = _tables.size() * 2;HashTable<K, V> newHT;newHT._tables.resize(newSize);// 遍历旧表for (size_t i = 0; i < _table.size(); i++){if (_tables[i]._s == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}size_t hashi = kv.first % _tables.size();while (_tables[hashi]._s == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._s = EXIST;++_n;return true;}

 首先先判断负载因子的大小，若超过则进行扩容处理，扩容的大小为之前的二倍，然后构建一个新的哈希表，在新的哈希表中重新插入原表中的值，之后再用swap进行交换，这样我们就完成了扩容。不用担心新建的哈希表无法释放，他会自动调用vector的析构函数。

扩完容或者不需要扩容时，进行下一步操作，通过哈希函数找到位置，进行插入，如果该位置已经存在，就接着向下查找，直到出现空或者删除状态时再进行插入。插入成功后把该位置的状态改为EXIST,并++n。这就是insert的实现。

Find

比如我们查找44，首先算出他的关键值4，那么在他的位置进行查找时，不为空，但他里面存放的并不是44，这时我将就继续向下寻找，在下表为8处找到了他。

如果我们查找34，关键值还是4，但当我们一直查找直到下表为0时，状态为空，此时结束，就说明没有34这个数。

还有一种情况，当我们把6删除时，应该为伪删除，也就是 不是真的把6去掉，而是将6位置的状态设置为删除，删除后当我们在查找6时，发现它的状态为删除，那么我们也无法找到。

代码如下：

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

Erase

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

删除时我们要先确定这个值在不在，若不存在直接返回false，若存在进行删除操作。

将该位置的状态改为删除，并且--n遍完成了操作。