哈希 模拟实现 unordered_set，unordered_map

什么是哈希

你可能会觉得这个名字很奇怪，或者你可能以为这是某个外国大佬的名字，实际上不是，哈希来自音译Hash，意为散列，就是将一堆比较分散的数据通过某种映射关系集中起来。

一、哈希函数

上面我们所说的某种映射关系实际上还有一种别的名称，就是哈希函数。而不同的哈希函数通常拥有自己的名字。

1.直接法

如果我想存储一些不重复的数字，而这些数字的范围不太大，所有的数字都是1~99之内的，那么我就可以使用直接法。这个名字就很直接，我直接开一个100个int大小的数组，然后从1到99，只要有数字出现，那么我就标记那个位置，这样我们只要去找它对应位置的值是否存在，就能够找到key。

2.余数法

但是，直接法的缺陷也很致命——如果这些数字的范围太大，那么就会导致空间的严重浪费。比如前几个数字都是10以内的，突然来了一个100000，那么我难道要开辟100000个空间吗？所以我们常使用的哈希函数还是余数法。给定一定范围的空间，将key值取余然后映射到这个范围。

上面的图就是一个余数法的栗子，整个空间大小为10，然后key通过取余映射到对应位置，只不过上面的数字都在0 - 9内，所以取不取余数无所谓。那么，接下来我要问的是，如果我再插入一个11呢？好，你可能会说，取余映射不就好了？11 % 10 == 1，但是你发现1的位置已经被占了。这也是我们接下来要讨论的问题，哈希冲突。

哈希冲突

哈希冲突是哈希表逃不过的问题。这个问题来自哈希表本身的定义，将大范围的value通过key值映射到一小块空间。这种化大为小的妙诀自然要付出一定的代价，比如哈希冲突。这也与我们人类社会一样，如果太过拥挤，就一定会有磕磕碰碰。所谓哈希冲突，简言之就是不同的value映射到同一位置，这是可能的，虽然它们的key值不同，但是取余之后就可能相同。接下来为大家介绍两种解决哈希冲突的方法。

1， 闭散列表

这第一种方法的思想就是，你既然知道有人把位置占用了，你用顺延一位，去占用你后面的位置。化成图就是这样的，

这种方法有好处，那自然是解决了哈希冲突，但是缺陷也很明显——那万一key取余后为2的value来了，就又得顺延。最后不妨设想最坏的情况（我认为这种情况会经常发生），所有的位置都错乱了，然后自然地查找效率就会损失，这与我们研究哈希表的意愿背道而驰。总而言之，这种符合我们最初想法的做法应该实现一下。但是，实现闭散列之前，有一个问题，这个问题最终会导致闭散列的结构。如何在一个闭散列哈希表中查找数据呢？ 你可能会说，这还不简单，找到key取余之后位置，然后将值取出来不久可以了。如果不是，那就顺着往后找，直到找到不久ok？问题就出现在这，我们遇到空值会停止查找，万一中间有某个值被删除了呢？

33映射到3的位置，21顺延映射到8的位置。然后删除33，现在我想找到21，我先找到1的位置，然后往后找，找到3，发现位置是空，查找结束。很明显，这不是我们想要的，因为3的位置以前有数据，只是被删除了，而非一开始就是空的。所以我们需要将这两种状态区分开来，这也是闭散列哈希表的巧妙结构。还有就是，如果表满了怎么办呢？我们的做法保证了表不会满，引入了负载因子来衡量表满的程度，负载因子就是表中的数据 / 表的大小，如果负载因子过大，就扩大表的容量。

//状态，用来标记当前位置是存在数据，还是从前存在但是被删除了，还是一开始就没有数据。
enum state {
     EMPTY,EXIST,DELETE,
};
//哈希表的数据类型
template<typename T>
struct __hash_data {
    T     _data; //数据域state _state; //状态__hash_data() :_state(EMPTY) {
    } //默认的构造函数需要给空，必须给空。__hash_data(const T& data) :_data(data) {
    }
};
// 4个模板参数，K就是key的type，T就是value的type，KeyOfT取出value中的key值，Hash是哈希算法
template<typename K, typename T, typename KeyOfT, typename Hash>
class HashTable {
    
public:using HashType = __hash_data<T>;void insert(const T& d) {
     KeyOfT koft;//调整负载因子,如果表为空或者负载因子大于等于0.7，那么需要扩容if (_tables.size() == 0 || _nums * 10 / _tables.size() > 7) {
    size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, T, KeyOfT, Hash> _HT; //这里创建再一个哈希表，复用insert，现代写法_HT._tables.resize(newSize); //细节，开好空间for (size_t i = 0; i < _tables.size(); ++i) {
    if (_tables[i]._state == EXIST) {
    _HT.insert(_tables[i]._data);}}_tables.swap(_HT._tables);}//找到映射位置size_t index = HashFunc(koft(d)) % _tables.size();while (_tables[index]._state == EXIST) {
     //直到某个位置的状态是删除或者是空++index;if (index == _tables.size()) //如果走到表尾，转到表头index = 0;}_tables[index] = d;_tables[index]._state = EXIST;++_nums;}HashType* find(const K& key) {
    KeyOfT koft;size_t index = HashFunc(key) % _tables.size();while (_tables[index]._state != EMPTY) {
     //状态为存在或者删除都要继续找if (koft(_tables[index]._data) == key) {
     //找到key值if (_tables[index]._state == EXIST) {
     //如果状态为存在，直接返回return &_tables[index];}else {
     //如果状态为删除，继续向后找++index;if (index == _tables.size())index = 0;}}}return nullptr; //没有找到}void erase(const K& key) {
    HashType* ret = find(key);if (ret) {
    ret->_state = DELETE;--_nums;}else {
    return;}}
private:vector<HashType> _tables;size_t           _nums = 0; //表中存入的数据个数size_t HashFunc(const K& key) {
     //哈希算法，具体介绍在后面。return Hash()(key);}
};

2 ，开散列表

考虑到闭散列的缺陷，后面如我们所愿的出现了一种新的哈希表，开散列。闭散列的冲突是去占用别人的位置，这样于情于理都不太合适。而开散列则是利用链表，如果冲突，那么将冲突的数据挂起来，形成一条一条的链子。

像上面那样。这种方法保证了哈希冲突的解决不去占用别人的资源，而且理应如此。

template<class T>
class _hash {
    
public:size_t operator()(const T& data) {
    return data;}
};// BKDR哈希
template<>
class _hash<string> {
    
public:size_t operator()(const string& str) {
    size_t hashCode = 0;for (auto& e : str) {
    hashCode = e * 131 + hashCode;}return hashCode;}
};
template<class T>
struct __open_hash_data {
     //开散列数据类型T _data;__open_hash_data* _next;__open_hash_data():_next(nullptr) {
    }__open_hash_data(const T& data):_data(data) {
    }
};
template<class K, class T, class KeyOfT, class Hash>
class oHashTable {
    
public:using HashData = __open_hash_data<T>;bool insert(const T& d) {
    KeyOfT koft;//调整负载因子,负载因子大于等于1if (_tables.size() == 0 || _nums * 10 / _tables.size() >= 10) {
    size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<HashData*> newTables;newTables.resize(newSize);for (size_t i = 0; i < _tables.size(); ++i) {
     //遍历整张表HashData* cur = _tables[i];HashData* next = nullptr;while (cur) {
     //完成一条链子上的节点转移next = cur->_next;size_t index = HashFunc(koft(cur->_data)) % newTables.size(); //找到映射位置cur->_next = newTables[index]; //链接到新表上newTables[index] = cur;cur = next;}_tables[i] = nullptr; //旧表变空}_tables.swap(newTables);}size_t index = HashFunc(koft(d)) % _tables.size();HashData* cur = _tables[index];while (cur) {
    if (cur->_data == d) {
    return false;}else {
    cur = cur->_next;}}HashData* newData = new HashData(d);newData->_next = _tables[index];_tables[index] = newData;++_nums;return true;}HashData* find(const K& key) {
    KeyOfT koft;size_t index = HashFunc(key) % _tables.size();HashData* cur = _tables[index];while (cur && koft(cur->_data) != key) {
    cur = cur->_next;}return cur;}bool erase(const K& key) {
    KeyOfT koft;size_t index = HashFunc(key) % _tables.size();HashData* cur = _tables[index], prev = nullptr;while (cur) {
    if (koft(cur->_data) == key) {
     //找到要删除的valueif (prev == nullptr) {
     //如果头节点要删除_tables[index] = cur->_next;delete cur;}else {
    prev->_next = cur->_next;delete cur;}--_nums;return true;}else {
     //没有找到prev = cur;cur = cur->_next;}}//如果运行到这，说明没有找到return false;}
private:vector<HashData*> _tables;size_t            _nums = 0;size_t HashFunc(const K& key) {
    return Hash()(key);}
};

字符串哈希算法

字符串哈希算法就是将字符串转换成可以取余的整形的函数，给大家贴上一个网站，自行参考。
字符串哈希算法

iterator

哈希表的iterator有点意思。iterator其实封装的是哈希节点的指针。我就operator++说一说，如果当前节点的next指针非空，那么直接返回next构造的迭代器就行。如果next为空，那么重点来了。我们要找到下一个位置，我们需要哈希表的信息，所以哈希表迭代器还应该封装一个哈希表的成员。

template<class K, class T, class KeyOfT, class Hash> //前置声明
class oHashTable;template<class T>
struct __open_hash_data;template<class K, class T, class KeyOfT, class Hash>
struct _HashTableIterator {
    using HashData = __open_hash_data<T>;using HT       = oHashTable<K, T, KeyOfT, Hash>; //哈希表using Self     = _HashTableIterator<K, T, KeyOfT, Hash>;HashData* _node;HT*       _ht;_HashTableIterator(HashData* node, HT* ht):_node(node),_ht(ht) {
    }T& operator*() {
    return _node->_data;}T* operator->() {
    return &operator*();}Self operator++() {
    if (_node->_next) {
     //这条链子上非空_node = _node->_next;return *this;}else {
     //此条链子后面已经没有节点了size_t index = _ht->HashFunc(KeyOfT()(_node->_data)) % _ht->_tables.size();++index;for (; index < _ht->_tables.size(); ++index) {
    if (_ht->_tables[index]) {
    _node = _ht->_tables[index];return *this;}}}//后面没有节点了_node = nullptr;return *this;}

unordered_set

所谓unordered系列，其实就是封装了哈希表，所用的方法与set和map封装红黑树大抵相同，实现起来也相当简单。

template<class K>
class SetKOfT {
    
public:const K& operator()(const K& key) {
    return key;}
};
template<class K, class Hash = _hash<K>>
class Myunordered_set {
    
public:using HT = oHashTable<K, K, SetKOfT<K>, Hash>;using  iterator = typename HT::iterator;iterator begin() {
    return _ht.begin();}iterator end() {
    return _ht.end();}pair<iterator, bool> insert(const K& key) {
    return _ht.insert(key);}void erase(const K& key) {
    return _ht.erase(key);}
private:HT _ht;
};

unordered_map

template<class K, class V>
class MapKeyOfT {
    
public:const K& operator()(const pair<K, V>& kv) {
    return kv.first;}
};template<class K, class V, class Hash = _hash<K>>
class Myunordered_map {
    
public:using HT = oHashTable<K, pair<K, V>, MapKeyOfT<K, V>, Hash>;using iterator = typename HT::iterator;iterator begin() {
    return _ht.begin();}iterator end() {
    return _ht.end();}pair<iterator, bool> insert(const pair<K, V>& kv) {
    return _ht.insert(kv);}V& operator[](const K& key) {
    iterator ret = _ht.insert(make_pair(key, V())).first;return (*ret).second;}
private:HT _ht;
};