数据结构系列之哈希表

前言

哈希表是unordered系列的基础，比较重要。

一、什么是哈希以及哈希冲突问题

哈希

第一次接触哈希应该是字符串算法中学到的字符串哈希，for(auto e: ch) hash = hash * 131 + ch,可以快速实现一个字符串在另一个字符串中查找出现次数，O(n + m),他其实是将每一段字符串都映射成了一个值。

哈希是一种思想，我们在搜索树中要根据一定的规则来寻找元素，元素和位置没有关系，如果我们能不经过比较，直接O(1)拿到元素的位置，可以实现快速查找，哈希就是这样一种思想，通过哈希函数使元素存储的位置和他之间建立起一一映射的关系，这种思想就是哈希。其中使用的转化元素的函数称为哈希函数，搞出来的结构是哈希表。

哈希冲突

什么是哈希冲突？既然我们把一个元素映射成了一个值，那这个值不会重复吗？当然会，可能我算出来这个值，要存放进这个位置已经有元素放着了，这就是哈希冲突，发生哈希冲突就要解决，解决方式：
**1.尽量使用合理的哈希函数，比如上面写的那个字符串哈希，那个冲突的概率性很低。**设计原则：1.哈希函数算出来的值，要在地址中，比如地址是0 到 x，算出来的值应该在0 到 x-1
2.尽量均匀分布在地址中
3.尽量简单，因为要O(1)查找、插入、删除
2.使用开散列和闭散列

常用哈希函数

1.直接定址法
Hash(key) = A * Key + B; 类似一次函数
优点：简单，均匀
缺点：需要直到key如何分布。
比如可以映射A到Z26个字符
2.除留余数法
取小于地址的最近的那个质数prime，Hash(key) = key % prime;

二、闭散列

又叫做开放定址法，当发生哈希冲突时，如果哈希表没满，就放在下一个为空的位置，如何找到下一个空位置呢？

线性探测

依次往后探测，知道找到下一个位置为止，注意要走一圈，不是走到size处就停止，不然有可能浪费太多空间。
插入：先使用哈希函数，得到一个值，看那个位置是否冲突，那我问你，你怎么知道那个位置有元素？所以需要一个状态是存在和空
删除：还是先使用哈希函数，得到一个值，从那个位置一直往下找找到空为止，问题又来了

所以定义状态：表示存在、为空、或者删除
状态和结点，直接写成key-value了：

enum class STATUS {Empty,Delete,Exist};template<class K, class V>struct HashData {pair<K, V> _kv;STATUS _status = STATUS::Empty;};

内部就用顺序表就可以，vector是一个非常好的选择，还要记录一个有效数据n方便扩容问题。

template<class K, class V>class HashTable{public:HashTable(){_table.resize(10);}private: vector<HashData<K,V>> _table; int _n;}

插入

bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}size_t hashi = has(kv.first) % _table.size();while (_table[hashi]._status == STATUS::Exist){if (_table[hashi]._kv.first == kv.first){return false;}++hashi;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._status = STATUS::Exist;++n;return true;}

查找

HashData<const K, V>* Find(const K& key){size_t hashi = key % _table.size();while (_table[hashi]._status != STATUS::Empty){//考虑状态问题，有可能是删除if (_table[hashi]._status == STATUS::Exist && _table[hashi]._kv.first == key){return reinterpret_cast<HashData<const K, V>*>(&_table[hashi]);}++hashi;hashi %= _table.size();}return nullptr;}

删除

这么多数据结构，哈希表的删除相对简单一点，复用一下find，这也是find使用返回结点指针的原因

bool Erase(const K& key){auto it = Find(key);if (it != nullptr){it->_status = STATUS::Delete;--n;return true;}return false;}

下面还有两个问题：

扩容问题

1.扩容怎么搞，如何扩容，什么时候扩容？

扩容逻辑：

if (n * 1.0 / _table.size() >= 0.7){//扩容size_t newSize = _table.size() * 2;HashTable<K, V> _newtable;_newtable._table.resize(newSize);for (int i = 0; i < _table.size(); ++i){if (_table[i]._status == STATUS::Exist){_newtable.insert(_table[i]._kv);}}_table.swap(_newtable._table);}

这里复用insert非常巧，因为你如果搞一个vector还需要重新写一遍插入的逻辑，这样调用insert直接走到下面了。

字符串问题

传进来是个数字可以跑，那字符串呢？所以还需要一个参数来控制字符串，又因为unordered系列中并不需要手动传第三个参数，所以得是默认参数，这里可以玩特化，是int类型就直接返回，是string类型就用下面的

struct DefaultHashFunc {size_t operator()(const K& key)const{return (size_t)key;}};template<>class DefaultHashFunc<string>{public:size_t operator()(const string& key)const{unsigned long long hash = 0;for (auto ch : key){hash = hash * 131 + ch;}return hash;}};

模板参数

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

之后用key的地方套一层hashfunc就可以了。

缺点

如果冲突太多，效率会下降很多，甚至到O(N),那怎么办呢？来看二次探测

二次探测

二次探测指的不是探测两次，而是二次方探测，找下一个位置的方法是HashFunc hs;size_t hashi = (hs(key) + i * i ) % _table,size(),第一次在原位置，然后是1，4，9等等
研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

三、开散列

unordered系列的底层的哈希表用的就是开散列方式
开散列又称为拉链法，就是还是正常使用哈希函数计算，但是此时冲突的就挂在结点上，相当于每个位置都是一个链表一样，那结点就要存放next指针了，每个位置挂了个桶，又可以称为哈希桶。

结点

template<class K,class V>struct HashData {HashData* _next;pair<K, V> _kv;HashData(const pair<K,V>& p):_kv(p),_next(nullptr){}};

hashtable

template<class K,class V,class HashFunc = DefaultHashFunc<K>>class HashTable {typedef HashData<K, V> Node;public:HashTable(){_table.resize(10,nullptr);}private:vector<Node*> _table;int _n;//存储有效数据};

由于有链表和上面的经验，这里简单提一下怎么搞就上代码了，当然还是要用默认DefaultHashFunc

insert

先不考虑扩容逻辑，先得到位置，进行悬挂，这里来个头插就可以，主要的逻辑newnode->_next = _table[hashi];_table[hashi] = newnode; 理解成单链表的头插就可以，_table[hashi]相当于_head

erase

这里不太方便复用find，单链表删除要找前一个，把握住前一个连到要删结点的后一个就行。

Find

简单的遍历链表，没啥说的

析构问题

上面的闭散列的开放定址法需要析构吗？不需要vector自己的析构够用了，这个呢？需要，因为下面挂的结点不会自己析构。

上述代码：

HashTable(){_table.resize(10,nullptr);}bool insert(const pair<K, V>& p){if (Find(p.first) != nullptr){return false;}HashFunc h;size_t hashi = h(p.first) % _table.size();Node* newnode = new Node(p);newnode->_next = _table[hashi];_table[hashi] = newnode;_n++;return true;}Node* Find(const K& key){HashFunc h;size_t hashi = h(key) % _table.size();Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key) {return cur;}cur = cur->_next;}return nullptr;}bool erase(const K& key){HashFunc h;size_t hashi = h(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;cur = nullptr;return true;}prev = cur;cur = cur->_next;}return false;}~HashTable(){for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;delete cur;cur = nullptr;cur = next;}}}

扩容问题：

理想情况下，每个桶挂一个结点，再插入一个就会冲突，所以当有效数据等于_size的时候就扩容

如何扩容？还像上面一样搞一个新的哈希表吗？可以但是及其不推荐，搞一个新的哈希表调用插入还会再new结点，然后还需要析构原来的，所以怎么搞呢？搞一个新的vector，遍历旧表，把结点头插过来不就完了，最后直接交换旧表。

if (_n == _table.size()){//扩容size_t newsize = _table.size() * 2;vector<Node*> newtable;newtable.resize(newsize, nullptr);for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t newhashi = h(cur->_kv.first) % newsize;cur->_next = newtable[newhashi];newtable[newhashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}

优缺点

开散列比闭散列的优势其实就是空间问题，闭散列线性探测要求0.7，二次探测要求0.5，空间浪费太多，而拉链法对负载因子容忍度比较高，拉链法的问题就是可能会导致一条链太长，这个GCC也有处理方式将他转化为了红黑树，还有桶的长度最好取质数来减少冲突，这个模拟unordered系列都会提到。

四、完整代码

个人gitee

总结

哈希表整体不难，需要掌握拉链法，封装unordered系列就有点难度了。