C++ 哈希表原理与 unordered_map/set 封装实现

这有两种方法，第一种方法是弄一个 newtable，newtable resize 一下到当前 2 倍，下一步依旧遍历旧表，重新映射到新表。但是取出旧表的值映射到信表是很麻烦的，因为要重新算位置，并且可能冲突时可能还要把冲突逻辑走一遍。

那怎么解决呢？我不定义一个 vector 的 newtable，而是定义一个哈希表的 newHT，newHT 里面有一个 vector，把这个 vector resize 一下。然后遍历旧表的数据插入到新表即可，如果状态是存在，插入到新表里面，最后旧表不要了，旧表和新表变换。

这里的亮点是再次复用了 insert 函数，进而复用了线性探测逻辑，空间开好后不走 if 的逻辑。下面测试一下。

下面写一下查找：来一个 key 取模算出一个位置，找到空时还没有找到就结束了，否则继续。值为存在状态且如果第一个值等于 key 就找到了，返回该位置对象，没找到就返回空指针。

再来写一下删除，可以复用 find 找到要删除的值，如果找到了改为删除即可，--n 并返回 true；没有找到返回 false。

这还是有个小问题，Find 这里返回的是 HashData 类型的指针，他人拿上后改状态就比较麻烦了。可以选择 Find 那里返回一个 pair，但是 Erase 那的 ret 又不可以了。所以还是这样改。

这里也不可以直接在 HashData 中把 pair 的 k 改成 const key，若改了都没有办法赋值。

还有一个问题是 key 可能不能取模，整型才能取模，key 可能是 string 或 double 等。此时就要走两层映射，哈希表里把存的值和位置建立出映射关系。用除留余数法必须是整型，若不是整型想办法让它变为整型，如字符串先和整型建立映射，然后再和存储位置建立映射。这里用仿函数解决问题。

需要写两个，一个是默认的 HashFunc，能取模的转化为整型就可以。哈希中传一个默认的哈希 func，里面所有取模的地方多走一层，定义个 Hashfunc 的对象，调它的 ()。

但是 string 不能转整型，再写个 StringFunc，返回 string 的第 0 个字符。然后 HashFunc 默认传 DefaultHashFunc，若自己传了就用自己的。

再看一个方法：平时用 unordered_map/set 也要取模，但用的时候也没有写仿函数，所以这里可用模板特化解决。

这样就可以做到不传仿函数，当 K 是 string 时走特化的，其余走正常的。但是 string 第一个字母 ASCII 值再这取模也不好，第一个字母相同的都冲突了，可以考虑把所有 ASCII 值加起来，这样就会好很多。

但可能还会有换顺序的场景：这样还是会引发很多冲突，所以有人专门对这做了研究叫字符串哈希算法。我们可以把大佬的方法用一下，每次加之前乘一个 131，这样冲突就可以大大减少了。

4. 二次探测及拉链法

以上说的方式叫闭散列的开放定址法，特点是从当前空间里去找下一个位置，但它有很强的局限性。以上说的核心方法是线性探测，它的特征是当前位置已有值，就去后面依次找其它位置。缺陷是会导致互相堵，此时有人想能不能冲突时让它们往外分散一些，所以有人提出了二次探测。二次探测不是说探测两次，是按二次方的角度探测。比如线性探测是模一个值算出一个位置，若该位置有值不断向后找；二次探测就是每次走 i^2 探测。

这样多值冲突时会相对分散开。

下面再来说一个方法，能不能不要说你的空间被占了就去占别人的空间，想个办法别互相影响，于是有人提出了拉链法，也叫哈希桶。它是把数组弄成指针数组，数组中不存值了，位置冲突了内部消化。

比如来了 1，开一个结点把 1 挂起来；来了 111，继续开一个结点挂起来。也就是冲突的值不是用探测的方式解决，而是用一个链表把它挂起来。下面先来搭个框架 (为了防止命名冲突，前面的方法用 open_address 括起来，下面的方法叫 hash_backet)：现在的重点是，HashTable 第一层基础结构是个指针数组，原来按照原生写法要定义二级指针之类的，现在可以用 vector，同时也要给 n 记录存储了多少个有效数据。顺便写一下构造。

下面实现一下 insert，先算一下位置，然后头插：这里让 newnode 的 next 指向第一个结点，第一个结点的地址在 hashi 的位置，newnode 此时要成为第一个，把 hashi 位置的地址改为 newnode 的就完成头插了。

完成后 ++n，返回 true，最基本的插入逻辑就完成了。

思考一下这里需要扩容吗？需要扩容，假如不扩容有大量数据时单个桶的拉链会特别长，这样查找数据时效率大大下降，和链表没什么差异了。因此还是要控制负载因子，只不过负载因子可控制的大一些，一般负载因子控制在 1，意味着平均下来每个桶一个数据 (理想状况)。下面实现扩容，如果_n 等于_table 的 size 就扩容。还是用原来的思想，newsize 是原表的两倍，再弄个新表，把旧表数据变换到新表。

但是这种思路这里不太推荐，因为这里复用 insert 时会不断的新开结点，最后还要把结点一个个释放了。相当于把这些结点新开了一遍，旧节点又释放了一遍，太浪费了。因此把结点挪下去就可以了：可以定义 newTable，resize 一下，然后遍历旧链表，把结点迁下来到新表，当前位置迁走后置空一下。都迁走后新表是想要的，变换一下 (底层是 finish，start，endofstor 等的交换)。

下面测试一下 (顺便写个 print 函数方面查看)。

还有个问题，最后新表结束要去调用析构函数，先调 delete[] 数组，delete[] 中先针对每个数组中的对象调用析构函数，但表上每个对象是内置类型，没有析构函数，因此 HashTable 是要单独写析构的 (后面来说)。

下面来写 find，find 就是链表的查找，查找到位置以后再遍历链表就行。

实现完 find 后再补充一下 Insert，如果值已经有了就别插入了，返回 false(同时补充之前的 insert)。

下面来实现删除，这里删除不好复用 find，因为要找前一个和后一个，所以还是找到要删除的位置，再找到前一个。

但是有个坑：当 cur 删除 1 位置时，此时 prev 是空，表示头删，所以分两种情况写。

再看下一个问题：之前写的开放定址法的哈希不用写析构，vector 调用自己的析构时全都干了。哈希桶这里要写析构，因为这只会释放 vector 的空间，不会把桶释放了，桶是内置类型，所以自己实现。

还有像 string 这样的类型也要解决，可以把前面写的 DefaultHashFunc 写到全局，这样大家都可以用，然后再改一下 (所有取模的地方用仿函数转化一下)。

5. 完整代码

//HashTable.h
#pragma once
#include <vector>
#include <string>
#include <stdio.h>

template<class K>
struct DefaultHashFunc {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};

template<>
struct DefaultHashFunc<string> {
    size_t operator()(const string& str) {
        size_t hash = 0;
        for (auto ch : str) {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

namespace open_address {
    enum STATE { EXIST, EMPTY, DELETE };
    
    template<class K, class V>
    struct HashData {
        pair<K, V> _kv;
        STATE _state = EMPTY;
    };
    
    template<class K, class V, class HashFunc = DefaultHashFunc<K>>
    class HashTable {
    public:
        HashTable() {
            _table.resize(10);
        }
        
        bool Insert(const pair<K, V>& kv) {
            if (Find(kv.first)) {
                return false;
            }
            //扩容
            if (_n * 10 / _table.size() >= 7) {
                size_t newSize = _table.size() * 2;
                //遍历旧表，重新映射到新表
                HashTable<K, V, HashFunc> newHT;
                newHT._table.resize(newSize);
                //遍历旧表的数据插入到新表即可
                for (size_t i = 0; i < _table.size(); i++) {
                    if (_table[i]._state == EXIST) {
                        newHT.Insert(_table[i]._kv);
                    }
                }
                _table.swap(newHT._table);
            }
            //线性探测
            HashFunc hf;
            size_t hashi = hf(kv.first) % _table.size();
            while (_table[hashi]._state == EXIST) {
                ++hashi;
                hashi %= _table.size();
            }
            _table[hashi]._kv = kv;
            _table[hashi]._state = EXIST;
            ++_n;
            return true;
        }
        
        HashData<const K, V>* Find(const K& key) {
            //线性探测
            HashFunc hf;
            size_t hashi = hf(key) % _table.size();
            while (_table[hashi]._state != EMPTY) {
                if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) {
                    return (HashData<const K, V>*) & _table[hashi];
                }
                ++hashi;
                hashi %= _table.size();
            }
            return nullptr;
        }
        
        bool Erase(const K& key) {
            HashData<const K, V>* ret = Find(key);
            if (ret) {
                ret->_state = DELETE;
                --_n;
                return true;
            }
            return false;
        }
        
    private:
        vector<HashData<K, V>> _table;
        size_t _n = 0; //存储有效数据的个数
    };
}

namespace hash_backet {
    template<class T>
    struct HashNode {
        pair<K, V> _kv;
        HashNode<K, V>* _next;
        HashNode(const pair<K, V>& kv) :_kv(kv), _next(nullptr) {}
    };
    
    template<class K, class V, class HashFunc = DefaultHashFunc<K>>
    class HashTable {
        typedef HashNode<K, V> Node;
    public:
        HashTable() {
            _table.resize(10, nullptr);
        }
        
        ~HashTable() {
            for (size_t i = 0; i < _table.size(); i++) {
                Node* cur = _table[i];
                while (cur) {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _table[i] = nullptr;
            }
        }
        
        bool Insert(const pair<K, V>& kv) {
            if (Find(kv.first)) {
                return false;
            }
            HashFunc hf;
            //负载因子到 1 就扩容
            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 hashi = hf(cur->_kv.first) % newSize;
                        cur->_next = newTable[hashi];
                        newTable[hashi] = cur;
                        cur = next;
                    }
                    _table[i] = nullptr;
                }
                _table.swap(newTable);
            }
            size_t hashi = hf(kv.first) % _table.size();
            //头插
            Node* newnode = new Node(kv);
            newnode->_next = _table[hashi];
            _table[hashi] = newnode;
            ++_n;
            return true;
        }
        
        Node* Find(const K& key) {
            HashFunc hf;
            size_t hashi = hf(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 hf;
            size_t hashi = hf(key) % _table.size();
            Node* prev = nullptr;
            Node* cur = _table[hashi];
            while (cur) {
                if (cur->_kv.first == key) {
                    if (prev == nullptr) {
                        _table[hashi] = cur->_next;
                    } else {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            return false;
        }
        
        void Print() {
            for (size_t i = 0; i < _table.size(); i++) {
                printf("[%d]->", i);
                Node* cur = _table[i];
                while (cur) {
                    cout << cur->_kv.first << "->";
                    cur = cur->_next;
                }
                printf("NULL\n");
            }
        }
        
    private:
        vector<Node*> _table; //指针数组
        size_t _n; //存储了多少个有效数据
    };
}

6. 封装

下面开始进行封装，先来搭一下 set 架子，它里面是个哈希表，用桶的方法。因为现在不确定是 K 还是 KV 的，是要用第二个模板参数来确定是 K 还是 KV 的。对于 set 而言是 K，对于 map 而言是个 pair。

再回顾一下为啥需要第一个模板参数呢：因为若没有 K find 和 erase 都不好写，假如写成 T：对 set 可以，对于 map 不可以，难道要传个 pair？显然不合适。然后都跟着改一下，插入的是一个 data。

find 这里还要补充 keyofT：补完后都跟着改了。

改正个错误。

下面实现 set 和 map 的插入。

下面来实现迭代器，对哈希表而言要把迭代器封装一下。begin 后找到第一个桶的位置，++找 node 的 next 就可往下走。那当前桶走完了怎么走到下一个桶？需要用表帮我们找下一个桶。先实现起来走着看，里面需要一个结点指针，迭代器需要用结点指针来构造。

下面看 operator++，简单实现是如果_node 的 next 不为空，就继续往下走；若为空，就相当于一个桶走完了，那就要找后一个桶。找后一个桶时先算一下自己当前在几号桶，可提前存一个下标以便知道在几号桶。

除了下标在哪知道外，还需要哈希表对象，因为光有下标也没法往后走，因此最好都传过来，定义一个 HashTable 的指针。

有了上述后来看下图：这样可算出当桶的位置，算完后 ++hashi，从下一个位置查找下一个不为空的桶。如果桶不为空就 break 找到了，为空就 ++。

循环出来要么找到了，要么找到了结尾也没有找到，所以这样写：这样不用外面再判断了，循环出来说明所有桶都走完了。若走完了找不到让空充当结束位置。

下面进一步完善一下。

现在有了++和构造，再来补充一下!=和==。

下面实现 begin，找第一个桶就行，遍历找，找到第一个桶后就构造一个迭代器返回，第一个是个结点指针，第二个可传 this，this 就是哈希表指针，没找到就返回空。

再来实现 end，构造一个空的返回去。

下面先从 set 中套一层，再从 map 中套一层。

但这里还是有相互依赖的问题：HashTable 里用迭代器没事，因为迭代器的实现在前面，HTIterator 里面会用 HashTable。这样谁在前面都会有问题，因此可以做一个前置声明，就是告诉你 HashTable 是定义了的。

最后再实现一下 operator*和 operator->。

测试时会遇到这样的问题：说是类外面不能访问私有，可以弄一个友元，类模板这友元带模板参数。

可以测试看一下 (erase 最后补一下--_n)。

下面来解决 const 迭代器的问题：可以被修改是一个问题，我们的目标是 key 不能被修改。还是老方法，弄个 const 迭代器，控制返回值 T 就可以了，所以多加参数改一下。

现在把 const 迭代器外层壳套上了，开始套里面的：现在先完成 set，set 这 K 不允许修改，可以这样：这样普通和 const 对象都可以调用。下面编译一下：报错说构造有问题，const 修饰*this，因为 const 修饰后传的时候是这样：权限放大传不过去。可以考虑重载一下，把成员遍量也改成 const 的。

下面来看 map 的，还是老样子，pair 的位置改为 const K。

再改一下返回值问题。

再完善 insert 这里，插入失败返回 false；若是新插入的返回新结点和 true。

改完 insert 后其余位置就要变了：编译后 set 出现了老问题：set 调用的是哈希表中的 insert：set 这里看起来没有问题，我调用你的，你返回 pair 类型，类型看起来是完全匹配的。实际上上框的代码是 unordered_set 里面的，下框的代码是 hashtable 里面的。hashtable 里面的就是个普通迭代器，set 里看起来是普通，实际上是 const 迭代器。也就是这两个 pair 是不一样的 pair 类型，所以它报错了。这里再把 map 中的 const 迭代器加一下。

map 不报错是因为 map 这的 iterator 就是 iterator。那怎么让一个类型转化为另一个类型呢？可以模仿之前的思路，我们需要 pair 中的普通迭代器可转化为 const 迭代器，因此就支持一个相关的构造函数。

当你是 const 迭代器时这是一个构造，当你是普通迭代器时是拷贝构造。改一下错误。

再看个问题，这的写法和上次的不一样：上次的写是先接收 pair，再用 pair 参数构造，相当于把两个参数提取出来，单独调用 pair 构造。这里相当于编译器不严格的检查，因为毕竟是不同类型的 iterator，显然中间支持了转化，保险起见这样写肯定没有问题。

为什么要大费力气的把 insert 返回一个 pair 呢？因为要实现 operator[]。

7. 完整代码

//unordered_map.h
#pragma once
#include "HashTable.h"

namespace yxx {
    template<class K, class V>
    class unordered_map {
        struct MapKeyOfT {
            const K& operator()(const pair<const K, V>& kv) {
                return kv.first;
            }
        };
    public:
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator const_iterator;
        
        iterator begin() {
            return _ht.begin();
        }
        iterator end() {
            return _ht.end();
        }
        const_iterator begin() const {
            return _ht.begin();
        }
        const_iterator end() const {
            return _ht.end();
        }
        
        pair<iterator, bool> insert(const pair<K, V>& kv) {
            return _ht.Insert(kv);
        }
        
        V& operator[](const K& key) {
            pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
            return ret.first->second;
        }
        
    private:
        hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
    };
}

//unordered_set.h
#pragma once
#include "HashTable.h"

namespace yxx {
    template<class K>
    class unordered_set {
        struct SetKeyOfT {
            const K& operator()(const K& key) {
                return key;
            }
        };
    public:
        typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
        typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;
        
        iterator begin() const {
            return _ht.begin();
        }
        iterator end() const {
            return _ht.end();
        }
        
        pair<iterator, bool> insert(const K& key) {
            pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
            return pair<const_iterator, bool>(ret.first, ret.second);
        }
        
    private:
        hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
    };
}

//HashTable.h
#pragma once
#include <vector>
#include <string>
#include <stdio.h>
#include <iostream>

template<class K>
struct DefaultHashFunc {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};

template<>
struct DefaultHashFunc<string> {
    size_t operator()(const string& str) {
        size_t hash = 0;
        for (auto ch : str) {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

namespace hash_bucket {
    template<class T>
    struct HashNode {
        T _data;
        HashNode<T>* _next;
        HashNode(const T& data) :_data(data), _next(nullptr) {}
    };
    
    //前置声明
    template<class K, class T, class KeyOfT, class HashFunc>
    class HashTable;
    
    template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
    struct HTIterator {
        typedef HashNode<T> Node;
        typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
        typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
        
        Node* _node;
        const HashTable<K, T, KeyOfT, HashFunc>* _pht;
        
        HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht) :_node(node), _pht(pht) {}
        HTIterator(const Iterator& it) :_node(it._node), _pht(it._pht) {}
        
        Ref operator*() {
            return _node->_data;
        }
        
        Ptr operator->() {
            return &_node->_data;
        }
        
        Self& operator++() {
            if (_node->_next) {
                _node = _node->_next;
            } else {
                KeyOfT kot;
                HashFunc hf;
                size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
                //从下一个位置查找查找下一个不为空的桶
                ++hashi;
                while (hashi < _pht->_table.size()) {
                    if (_pht->_table[hashi]) {
                        _node = _pht->_table[hashi];
                        return *this;
                    } else {
                        ++hashi;
                    }
                }
                _node = nullptr;
            }
            return *this;
        }
        
        bool operator!=(const Self& s) {
            return _node != s._node;
        }
        
        bool operator==(const Self& s) {
            return _node == s._node;
        }
    };
    
    template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
    class HashTable {
        typedef HashNode<T> Node;
        //友元声明
        template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
        friend struct HTIterator;
        
    public:
        typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
        typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
        
        iterator begin() {
            //找第一个桶
            for (size_t i = 0; i < _table.size(); i++) {
                Node* cur = _table[i];
                if (cur) {
                    return iterator(cur, this);
                }
            }
            return iterator(nullptr, this);
        }
        
        iterator end() {
            return iterator(nullptr, this);
        }
        
        const_iterator begin() const {
            //找第一个桶
            for (size_t i = 0; i < _table.size(); i++) {
                Node* cur = _table[i];
                if (cur) {
                    return const_iterator(cur, this);
                }
            }
            return const_iterator(nullptr, this);
        }
        
        const_iterator end() const {
            return const_iterator(nullptr, this);
        }
        
        HashTable() {
            _table.resize(10, nullptr);
        }
        
        ~HashTable() {
            for (size_t i = 0; i < _table.size(); i++) {
                Node* cur = _table[i];
                while (cur) {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _table[i] = nullptr;
            }
        }
        
        pair<iterator, bool> Insert(const T& data) {
            KeyOfT kot;
            iterator it = Find(kot(data));
            if (it != end()) {
                return make_pair(it, false);
            }
            HashFunc hf;
            //负载因子到 1 就扩容
            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 hashi = hf(kot(cur->_data)) % newSize;
                        cur->_next = newTable[hashi];
                        newTable[hashi] = cur;
                        cur = next;
                    }
                    _table[i] = nullptr;
                }
                _table.swap(newTable);
            }
            size_t hashi = hf(kot(data)) % _table.size();
            //头插
            Node* newnode = new Node(data);
            newnode->_next = _table[hashi];
            _table[hashi] = newnode;
            ++_n;
            return make_pair(iterator(newnode, this), true);
        }
        
        iterator Find(const K& key) {
            HashFunc hf;
            KeyOfT kot;
            size_t hashi = hf(key) % _table.size();
            Node* cur = _table[hashi];
            while (cur) {
                if (kot(cur->_data) == key) {
                    return iterator(cur, this);
                }
                cur = cur->_next;
            }
            return end();
        }
        
        bool Erase(const K& key) {
            HashFunc hf;
            KeyOfT kot;
            size_t hashi = hf(key) % _table.size();
            Node* prev = nullptr;
            Node* cur = _table[hashi];
            while (cur) {
                if (kot(cur->_data) == key) {
                    if (prev == nullptr) {
                        _table[hashi] = cur->_next;
                    } else {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            --_n;
            return false;
        }
        
        void Print() {
            for (size_t i = 0; i < _table.size(); i++) {
                printf("[%d]->", i);
                Node* cur = _table[i];
                while (cur) {
                    cout << cur->_data << "->";
                    cur = cur->_next;
                }
                printf("NULL\n");
            }
        }
        
    private:
        vector<Node*> _table; //指针数组
        size_t _n; //存储了多少个有效数据
    };
}