数据结构（14）——哈希表（1）

欢迎来到博主的专栏：数据结构
博主ID：代码小豪

哈希表的思想

在以往的线性表中，查找速度取决于线性表是否有序，如果是无序的线性表，我们就要从表头开始匹配key值是否相同，因此时间复杂度取决于线性表的元素个数，为O（N）。

如果线性表有序，则可以通过二分查找法大大的减少查找时间，时间复杂度为O（logN），这个时间复杂度看起来让人满意，但是我们要考虑到一点，那就是保持线性表的有序性是要付出代价的，使用排序算法也有O（N*logN）的时间复杂度。

即使是使用关联式容器，它的查找速度也是O（logN），但是好处在于插入和删除元素并不会破坏查找速度。但是查找的速度就局限于此了吗？

已现实为例，如果我们想要在城里找到大舅妈，肯定不会遍历整个城的街道，从街道口走到街道尾去找大舅妈的家，我们会先知道大舅妈的住址，直接去这个住址就能找到大舅妈。

这就是哈希表的查找的方式了，将key值放在映射的地址处，这样查找key值就不用从头开始遍历了。举个例子，假设现在有一个能容纳十个元素的哈希表。我们规定key值的个位数就是映射的地址值，即让1位于1号，2位于2号。以此类推，而10则放在0号。

假设我们要查找13，那么去3号处就能找到对应值，查找速度为O（1）。这就是哈希表查找的优势。

映射方法（哈希函数）

哈希表中的映射方法叫做哈希函数，以上表为例，其哈希函数为F(key)=key%10。于是F(13)=3，F(25)=5。一个好的哈希函数很重要。这将决定哈希表的查找，插入，删除的速率（最主要还是查找）。哈希函数需要能将key值的数据转换成整形的能力。

但是并非所有类型都可以和整形转换。比如string就不能通过F(key)=key%10的方式获得映射值，此时我们就需要设计一个使用于string的哈希函数，比如可以设计让string的所有元素相加为映射值的哈希函数，即F(string)={a1+a2+……+an}。实际上字符串的哈希函数设计绝没这么简单，感兴趣可以在网上搜索。

那么自定义类型当然也要依靠自定义的哈希函数才能获得其映射值，通常哈希函数的设计需要考虑一下几点：
（1）选取的key值的独特性，比如我们在数据库中查找一个人，如果选择“姓名”作为映射值，那么肯定效率不佳，因为全国同名同性的人是在太多了，如果我们选择“生日+姓名”作为映射值就会好很多。

（2）哈希函数的结果要尽可能的分散，假设现在有N个元素要插入到哈希表，那么它们的映射值越分散在哈希表就越好，如果N个元素经过哈希函数的运算结果的映射值都是1，那么肯定是毫无效率可言的。

（3）哈希函数的计算结果要包含在哈希表的域中，如果一个哈希表能容纳100个元素（即可容纳映射值0-99的元素），那么如果一个key值计算出映射值为101，那么肯定是没法插入的。

在c++标准库中的unordered_map，就是用哈希表为底层的容器，其允许我们传入自定义的哈希函数，已适配那些自定义的类型的映射值计算。

template < class Key,                                    // unordered_map::key_typeclass T,                                      // unordered_map::mapped_typeclass Hash = hash<Key>, //可以传入自定义的哈希函数// unordered_map::hasherclass Pred = equal_to<Key>,                   // unordered_map::key_equalclass Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type> class unordered_map;

除留余数法

除留余数法是一个比较通用，而且简单的哈希函数。其主要方法为：

设哈希表可容纳最大地址数为m，取一个不超过m的值p作为除数，其哈希函数为：hash(key)=key%p。

比如当前哈希表的最大地址数为50，待插入的key的哈希值为313，则其映射值为313%50=13。

在后续哈希表的底层设计中，博主将采用这个方法。

哈希表

hash表的底层可以用序列式容器vector，或者deque，因为哈希表的映射值与下标很适配。

template<class key,class value>
class hash_tab
{
public:hash_tab(){_tab.resize(10);_n = 0;}typedef pair<key, value> value_type;private:vector<hash_data<value_type>> _tab;size_t _n;//当前有效数据
};

而哈希表每个元素都要存储两个数据，分别是data，以及状态state。由于vector一次性开了十个元素的空间，因此有些空间是没有有效数据的。这些没有有效数据的元素的状态记为空（empty），如果元素具有有效数据则记为有（exist），如果元素的有效数据被删除，则记为删除（delete）。

enum state
{EXIST,//存在映射DELETE,//删除映射EMPTY//空的映射
};template<class T>
struct hash_data
{hash_data(){_state = EMPTY;}hash_data(const T& data,state state){_data = data;_state = state;}const hash_data& operator=(const hash_data& hashdata){_data = hashdata._data;_state = hashdata._state;return *this;}T _data;state _state;
};

insert

insert的方式如下：
（1）先通过hash函数计算出key值的映射地址处。博主采用除留余数法。
（2）将元素插入到映射值对应的地方。

比如现在插入的元素key值为60，由于当前哈希表的最大空间为10（默认构造函数），因此除留余数法为hash（60）=60%10=0。插入在0下标处。

ok，现在我们来面临第一个问题，如果我们现在插入30，那么它该插入在什么位置呢？根据哈希函数hash（30）=30%10=0。那么它应该插入在映射值为0的下标处，但是0下标处已经存在60这个数据了，那么该如何处理呢？

这种情况被称为“哈希冲突”，即不同的key值（30与60），但是经过哈希函数计算后，得到了相同的映射值（0）。如果想要减少哈希冲突，优化哈希函数是一个不错的选择，但是这并不能解决哈希冲突，通常我们会用两种方法解决哈希冲突，闭散列和开散列。这篇文章我们先来了解闭散列的哈希表，在下一篇中博主再谈谈开散列的哈希表如何实现。

闭散列

闭散列：也称开放地址法，当发生哈希冲突时。探测哈希表的空位置，将key值插入在冲突位置的下一个空位置处。探测方法也分为多种

方法（1）线性探测

线性探测：从冲突位置开始，依次往后探测，直到找到下一个新位置为止。以上例为例，由于30插入的位置与60发生了哈希冲突，那么30从0下标开始线性探测后续位置，直到遇到第一个空位置（EMPTY）,DELETE也算作空位置。

如果此时在插入一个20，与60依然发生了哈希冲突，根据线性探测的方法，20应该插入在下标2的位置。

假如这个哈希表满了，那么再次插入一个key值会发生什么事呢？

根据线性探测的规则，插入2的位置会陷入一个死循环，因为在这个哈希表中已经不存在空位置了，在这个哈希表中无论探测多少次都找不到位置。

实际上，当哈希表中的元素占比整个空间越来越多时，哈希冲突发生的几率会越来越高，而每次发生哈希冲突时，都会带来额外的时间开销（线性探测）。因此，最好的解决方法是控制元素与空间之间的占比。

负载因子

我们将哈希表中元素与空间之间的占比成为负载因子。即：

负载因子=元素个数÷哈希表的总容量

负载因子与元素个数成正比，与哈希表的总容量成反比，当负载因子小时，发生哈希冲突的几率低，插入效率高，但是空间利用率也低。当负载因子大时，发生哈希冲突的几率大，插入效率低，但是空间利用率高。因此控制负载因子在一定的数值内也是很重要的。

通常来说，采取线性探测的哈希表，其负载因子应该控制到0.7~0.8。如果负载因子超过这个区间，就要对哈希表进行扩容。以降低哈希表的负载因子。

扩容

哈希表的扩容策略是异地扩容，即先构造一个新的哈希表，这个新的哈希表是原哈希表的二倍，然后再讲原哈希表的元素重新插入在新哈希表当中。最后交换新旧两个哈希表。那么为什么要这样做呢？与其说异地扩容的好处，不如讲讲原地扩容的坏处。

假如我们将上例中的哈希表扩容两倍，即新哈希表的容量为20.

由于哈希表的最大容量发生了变化，那么哈希函数也会随之变化，因为我们设定的哈希函数为

hash（key）=key%size

由于size从10变成了20，那么哈希函数就变成了key%20。那么哈希表中17的映射值为
hash（17）=17%20=17，这个插入位置就不对。因此更好的方式是新建一个新哈希表。将旧表的内容插入至新表当中。

	bool insert(const value_type& kv){//负载因子过多，需要扩容 负载因子等于size%_nif (double(_n) / _tab.size() >= 0.7){hash_tab new_tab;new_tab._tab.resize(_tab.size() * 2);//建立新表for (auto& e : _tab){if (e._state == EXIST)//只插入有效值{new_tab.insert(e._data);//将旧表的值插入到新表当中}}_tab.swap(new_tab._tab);//交换新旧两表}size_t hashnum = kv.first % _tab.size();//哈希函数——除留余数法while (_tab[hashnum]._state ==EXIST )//线性探测{hashnum++;hashnum %= _tab.size();}_tab[hashnum] = hash_data<value_type>(kv, EXIST);//插入新值_n++;return true;}

find和erase

find函数的方法如下：

通过哈希函数计算出映射值，找到映射的位置，然后线性检测找到正确的key值，然后返回节点，如果线性检测到空节点（DELETE不算空节点，仅EMPTY）。就说明哈希表中不存在对应key值，返回nullptr。

	hash_data<value_type>* find(const key& key){size_t hashnum = key % _tab.size();while (_tab[hashnum]._state != EMPTY){if (key == _tab[hashnum]._data.first&&_tab[hashnum]._state!=DELETE){return &_tab[hashnum];}hashnum++;hashnum %= _tab.size();}return nullptr;}

erase的实现就更简单，我们先通过find查找到待删除的元素，然后将该元素的状态调整成DELETE就可以了，因为对这个元素的data进行修改不是一个明智的选择。这会影响到映射关系。

bool erase(const key& key)
{size_t hashnum = key % _tab.size();hash_data<value_type>* ptr=find(key);if (ptr == nullptr)return false;ptr->_state = DELETE;_n--;return true;
}