手写 C++ 哈希表：unordered_set/unordered_map 用法、模拟实现与性能对比

unordered_map

#include <iostream>
#include <unordered_map>
using namespace std;

void test1() {
    unordered_map<int, int> mp;
    mp.insert(make_pair(1, 1));
    mp.insert(make_pair(5, 5));
    mp.insert(make_pair(2, 2));
    mp.insert(make_pair(4, 4));
    mp.insert(make_pair(3, 3));
    unordered_map<int, int>::iterator it = mp.begin();
    while (it != mp.end()) {
        cout << it->first << ":" << it->second << endl;
        it++;
    }
    it = mp.find(3);
    if (it != mp.end()) {
        cout << "找到了 " << it->first << ":" << it->second << endl;
    }
    mp.erase(it);
    if (!mp.count(3)) {
        cout << "没有找到 3" << endl;
    }
    mp[3] = 5;
    cout << mp[3] << endl;
}

void test2() {
    string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    unordered_map<string, int> mp;
    for (auto& e : arr) {
        unordered_map<string, int>::iterator ret = mp.find(e);
        if (ret != mp.end()) {
            ret->second++;
        } else {
            mp.insert(make_pair(e, 1));
        }
    }
    for (auto& e : mp) {
        cout << e.first << " " << e.second << endl;
    }
}

int main() {
    test1();
    test2();
    return 0;
}

以上代码展示了插入、查找、删除、遍历以及桶状态的查询。留意 max_load_factor() 默认是 1，所以 load_factor() 到达 1 时触发 rehash。test3 里还演示了安全访问桶元素的方式——先确认桶存在再查看大小。

模拟实现

看过标准库怎么用，现在动手写一套自己的 unordered_set 和 unordered_map，底层都用同一个哈希桶。整体框架和 set/map 的红黑树封装很像，所以重复的部分就不展开了。

哈希节点

节点只存数据 T，不区分 key 和 value——谁知道封装自己的是 unordered_set 还是 unordered_map。

template<class T> class HashNode {
public:
    T _data;
    HashNode<T>* _next;
    HashNode(const T& data) :_data(data), _next(nullptr) {}
};

封装逻辑

设计上有几个点提前想好：

• 底层哈希表的 Hash 模版参数作为上层的缺省值更合理。
• 查找或删除时需要用 key 值，所以上层容器必须保留第一个模版参数 K。
• 从节点 T 中提取 key 需要 KeyOfT 仿函数。

迭代器

迭代器里封装节点指针，模拟原生指针行为。不过真正的难点是 operator++：当前节点 _next 不为空时直接走下一个；为空则说明当前桶已遍历完，得找到下一个非空桶。这需要访问哈希表的 _tables 数组，所以迭代器里还得存上哈希表的指针。

于是迭代器模版参数几乎得和哈希表对齐：

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> struct __HTIterator {
    typedef HashNode<T> Node;
    Node* _node;
    const HashTable<K, T, KeyOfT, Hash>* _pht;
    size_t _hashi; //当前节点所在桶的编号
};

这里需要哈希表的前置声明，因为迭代器定义在哈希表之前。

template<class K, class T, class KeyOfT, class Hash> class HashTable;

另外迭代器内部要用到 _tables 这个私有成员，所以迭代器类得被声明为友元：

template<class K, class T, class KeyOfT, class Hash> class HashTable {
    template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator;
    // ...
};

operator++ 的实现就把上面两种分支写清楚：

typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
self& operator++() {
    if (_node->_next) {
        _node = _node->_next;
    } else {
        _hashi++;
        while (_hashi < _pht->_tables.size()) {
            if (_pht->_tables[_hashi]) {
                _node = _pht->_tables[_hashi];
                break;
            }
            _hashi++;
        }
        if (_hashi == _pht->_tables.size()) {
            _node = nullptr;
        }
    }
    return *this;
}

我们把当前桶的编号 _hashi 直接存在迭代器里，省得每次用哈希计算，虽然多占点内存但逻辑更直白。

哈希表提供迭代器接口

template<class K, class T, class KeyOfT, class Hash> class HashTable {
    typedef HashNode<T> Node;
    template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator;
public:
    typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
    typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
public:
    iterator begin() {
        for (size_t i = 0; i < _tables.size(); i++) {
            if (_tables[i]) {
                return iterator(_tables[i], this, i);
            }
        }
        return end();
    }
    iterator end() {
        return iterator(nullptr, this, -1);
    }
    const_iterator begin() const {
        for (size_t i = 0; i < _tables.size(); i++) {
            if (_tables[i]) {
                return const_iterator(_tables[i], this, i);
            }
        }
        return end();
    }
    const_iterator end() const {
        return const_iterator(nullptr, this, -1);
    }
    // ...
};

const 版本的 begin() / end() 在返回迭代器时，如果构造函数参数不是 const HashTable*，会出现权限放大问题，所以迭代器的 _pht 成员和构造函数参数都加了 const。

unordered_set / unordered_map 的迭代器类型

unordered_set 内元素不可修改，所以普通迭代器和 const 迭代器其实都是底层哈希表的 const_iterator。

namespace dck {
    template<class K, class Hash = HashFunc<K>> class unordered_set {
        struct SetKeyOfT {
            const K& operator()(const K& key) { return key; }
        };
    public:
        typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
        typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;
        const_iterator begin() const { return _ht.begin(); }
        const_iterator end() const { return _ht.end(); }
    private:
        hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
    };
}

unordered_map 稍微复杂点：普通迭代器的 key 不能改，value 可以改；const 迭代器什么都不能改。所以普通迭代器是底层普通迭代器，const 迭代器是底层 const 迭代器，并且 pair 的 key 带 const。

namespace dck {
    template<class K, class V, class Hash = HashFunc<K>> class unordered_map {
        struct MapKeyOfT {
            const K& operator()(const pair<K, V>& kv) { return kv.first; }
        };
    public:
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_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(); }
    private:
        hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
    };
}

插入、查找、删除

这三个接口的核心是把原来的 bool 改成迭代器或 pair<iterator,bool>，并且在需要 key 的地方一律使用仿函数。

查找：返回找到的迭代器或者 end()。

iterator Find(const K& key) {
    Hash hf;
    KeyOfT kot;
    size_t hashi = hf(key) % _tables.size();
    Node* cur = _tables[hashi];
    while (cur) {
        if (kot(cur->_data) == key) return iterator(cur, this, hashi);
        cur = cur->_next;
    }
    return end();
}

插入：负载因子设为 1，超过就扩容两倍，重新映射节点。返回 pair<iterator,bool> 表示插入位置和是否成功。

pair<iterator, bool> Insert(const T& data) {
    KeyOfT kot;
    iterator it = Find(kot(data));
    if (it != end()) return make_pair(it, false);
    Hash hf;
    if (_n == _tables.size()) {
        size_t newSize = _tables.size() * 2;
        vector<Node*> newTables;
        newTables.resize(newSize);
        for (size_t i = 0; i < _tables.size(); i++) {
            Node* cur = _tables[i];
            while (cur) {
                Node* next = cur->_next;
                size_t hashi = hf(kot(cur->_data)) % newSize;
                cur->_next = newTables[hashi];
                newTables[hashi] = cur;
                cur = next;
            }
            _tables[i] = nullptr;
        }
        _tables.swap(newTables);
    }
    size_t hashi = hf(kot(data)) % _tables.size();
    Node* newNode = new Node(data);
    newNode->_next = _tables[hashi];
    _tables[hashi] = newNode;
    ++_n;
    return make_pair(iterator(newNode, this, hashi), true);
}

上层封装时，unordered_map 直接调用 Insert 即可；unordered_set 需要把返回的普通迭代器转换成 const_iterator，否则类型不匹配。

pair<iterator, bool> insert(const K& key) {
    auto ret = _ht.Insert(key);
    return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
}

删除：遍历桶内链表，找到后删除并连接前后节点。

bool Erase(const K& key) {
    Hash hf;
    size_t hashi = hf(key) % _tables.size();
    Node* prev = nullptr;
    Node* cur = _tables[hashi];
    while (cur) {
        if (cur->_kv.first == key) {
            if (prev == nullptr) {
                _tables[hashi] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            delete cur;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

unordered_map 的 operator[] 就靠 Insert 实现：

V& operator[](const K& key) {
    pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
    return ret.first->second;
}

桶统计与效率测试

为了方便观察哈希表的健康状况，加一个 Some() 函数输出桶使用数、最大链长、平均链长等信息。

void Some() {
    size_t bucketSize = 0;
    size_t maxBucketLen = 0;
    size_t sum = 0;
    double averageBucketLen = 0;
    for (size_t i = 0; i < _tables.size(); i++) {
        Node* cur = _tables[i];
        if (cur) ++bucketSize;
        size_t bucketLen = 0;
        while (cur) {
            ++bucketLen;
            cur = cur->_next;
        }
        sum += bucketLen;
        if (bucketLen > maxBucketLen) maxBucketLen = bucketLen;
    }
    averageBucketLen = (double)sum / (double)bucketSize;
    printf("all bucketSize:%d\n", _tables.size());
    printf("bucketSize:%d\n", bucketSize);
    printf("maxBucketLen:%d\n", maxBucketLen);
    printf("averageBucketLen:%lf\n\n", averageBucketLen);
}

下面用 100 万个随机数比较 set、unordered_set 和我们自己的 HashTable 的插入、查找、删除耗时。

#include <set>
#include <unordered_set>
#include "HashTable.h"

void test() {
    const size_t N = 1000000;
    unordered_set<int> us;
    set<int> s;
    hash_bucket::HashTable<int, int> ht;
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; ++i) {
        //v.push_back(rand()); // 重复多
        v.push_back(rand() + i); // 重复少
        //v.push_back(i); // 无重复，有序
    }
    size_t begin1 = clock();
    for (auto e : v) s.insert(e);
    size_t end1 = clock();
    cout << "set insert:" << end1 - begin1 << endl;
    size_t begin2 = clock();
    for (auto e : v) us.insert(e);
    size_t end2 = clock();
    cout << "unordered_set insert:" << end2 - begin2 << endl;
    size_t begin10 = clock();
    for (auto e : v) ht.Insert(make_pair(e, e));
    size_t end10 = clock();
    cout << "HashTbale insert:" << end10 - begin10 << endl << endl;
    size_t begin3 = clock();
    for (auto e : v) s.find(e);
    size_t end3 = clock();
    cout << "set find:" << end3 - begin3 << endl;
    size_t begin4 = clock();
    for (auto e : v) us.find(e);
    size_t end4 = clock();
    cout << "unordered_set find:" << end4 - begin4 << endl;
    size_t begin11 = clock();
    for (auto e : v) ht.Find(e);
    size_t end11 = clock();
    cout << "HashTable find:" << end11 - begin11 << endl << endl;
    cout << "插入数据个数：" << us.size() << endl << endl;
    ht.Some();
    size_t begin5 = clock();
    for (auto e : v) s.erase(e);
    size_t end5 = clock();
    cout << "set erase:" << end5 - begin5 << endl;
    size_t begin6 = clock();
    for (auto e : v) us.erase(e);
    size_t end6 = clock();
    cout << "unordered_set erase:" << end6 - begin6 << endl;
    size_t begin12 = clock();
    for (auto e : v) ht.Erase(e);
    size_t end12 = clock();
    cout << "HashTable Erase:" << end12 - begin6 << endl << endl;
}

int main() {
    test();
    return 0;
}

在数据量较大时，unordered_set 的插入、查找、删除都比 set 快很多。我们自己实现的哈希表甚至比标准库的 unordered_set 还快一点，主要原因是标准库为了保持迭代器按插入顺序遍历，需要额外维护链表等结构，而我们的迭代器只按桶顺序走，实现更轻量。从统计上看，最大桶长度只有 2，平均桶长度约 1.28，时间复杂度接近 O(1)。

完整代码

HashTable.h

#pragma once
#include <iostream>
#include <vector>
using namespace std;

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

template<> struct HashFunc<string> {
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto& e : key) {
            hash *= 31;
            hash += e;
        }
        return hash;
    }
};

namespace hash_bucket {
    template<class T> class HashNode {
    public:
        T _data;
        HashNode<T>* _next;
        HashNode(const T& data) :_data(data), _next(nullptr) {}
    };

    template<class K, class T, class KeyOfT, class Hash> class HashTable;

    template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> struct __HTIterator {
        typedef HashNode<T> Node;
        typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
        Node* _node;
        const HashTable<K, T, KeyOfT, Hash>* _pht;
        size_t _hashi;
        __HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi) :_node(node), _pht(pht), _hashi(hashi) { }
        self& operator++() {
            if (_node->_next) {
                _node = _node->_next;
            } else {
                _hashi++;
                while (_hashi < _pht->_tables.size()) {
                    if (_pht->_tables[_hashi]) {
                        _node = _pht->_tables[_hashi];
                        break;
                    }
                    _hashi++;
                }
                if (_hashi == _pht->_tables.size()) {
                    _node = nullptr;
                }
            }
            return *this;
        }
        Ref operator*() { return _node->_data; }
        Ptr operator->() { return &_node->_data; }
        bool operator!=(const self& s) { return _node != s._node; }
    };

    template<class K, class T, class KeyOfT, class Hash> class HashTable {
        typedef HashNode<T> Node;
        template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator;
    public:
        typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
        typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
    public:
        iterator begin() {
            for (size_t i = 0; i < _tables.size(); i++) {
                if (_tables[i]) {
                    return iterator(_tables[i], this, i);
                }
            }
            return end();
        }
        iterator end() {
            return iterator(nullptr, this, -1);
        }
        const_iterator begin() const {
            for (size_t i = 0; i < _tables.size(); i++) {
                if (_tables[i]) {
                    return const_iterator(_tables[i], this, i);
                }
            }
            return end();
        }
        const_iterator end() const {
            return const_iterator(nullptr, this, -1);
        }
    public:
        HashTable() { _tables.resize(10); }
        ~HashTable() {
            for (size_t i = 0; i < _tables.size(); i++) {
                Node* cur = _tables[i];
                while (cur) {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
        }
        iterator Find(const K& key) {
            Hash hf;
            KeyOfT kot;
            size_t hashi = hf(key) % _tables.size();
            Node* cur = _tables[hashi];
            while (cur) {
                if (kot(cur->_data) == key) return iterator(cur, this, hashi);
                cur = cur->_next;
            }
            return end();
        }
        pair<iterator, bool> Insert(const T& data) {
            KeyOfT kot;
            iterator it = Find(kot(data));
            if (it != end()) return make_pair(it, false);
            Hash hf;
            if (_n == _tables.size()) {
                size_t newSize = _tables.size() * 2;
                vector<Node*> newTables;
                newTables.resize(newSize);
                for (size_t i = 0; i < _tables.size(); i++) {
                    Node* cur = _tables[i];
                    while (cur) {
                        Node* next = cur->_next;
                        size_t hashi = hf(kot(cur->_data)) % newSize;
                        cur->_next = newTables[hashi];
                        newTables[hashi] = cur;
                        cur = next;
                    }
                    _tables[i] = nullptr;
                }
                _tables.swap(newTables);
            }
            size_t hashi = hf(kot(data)) % _tables.size();
            Node* newNode = new Node(data);
            newNode->_next = _tables[hashi];
            _tables[hashi] = newNode;
            ++_n;
            return make_pair(iterator(newNode, this, hashi), true);
        }
        bool Erase(const K& key) {
            Hash hf;
            size_t hashi = hf(key) % _tables.size();
            Node* prev = nullptr;
            Node* cur = _tables[hashi];
            while (cur) {
                if (cur->_kv.first == key) {
                    if (prev == nullptr) {
                        _tables[hashi] = cur->_next;
                    } else {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            return false;
        }
    private:
        vector<Node*> _tables;
        size_t _n;
    };
}

MyUnorderedSet.h

#pragma once
#include "HashTable.h"

namespace dck {
    template<class K, class Hash = HashFunc<K>> class unordered_set {
        struct SetKeyOfT {
            const K& operator()(const K& key) { return key; }
        };
    public:
        typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
        typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;
        pair<iterator, bool> insert(const K& key) {
            auto ret = _ht.Insert(key);
            return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
        }
        iterator find(const K& key) { return _ht.Find(key); }
        iterator erase(const K& key) { return _ht.Erase(key); }
        const_iterator begin() const { return _ht.begin(); }
        const_iterator end() const { return _ht.end(); }
    private:
        hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
    };
}

MyUnorderedMap.h

#pragma once
#include "HashTable.h"

namespace dck {
    template<class K, class V, class Hash = HashFunc<K>> class unordered_map {
        struct MapKeyOfT {
            const K& operator()(const pair<K, V>& kv) { return kv.first; }
        };
    public:
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;
        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;
        }
        iterator find(const K& key) { return _ht.Find(key); }
        iterator erase(const K& key) { return _ht.Erase(key); }
        iterator begin() { return _ht.begin(); }
        iterator end() { return _ht.end(); }
        const_iterator begin() const { return _ht.begin(); }
        const_iterator end() const { return _ht.end(); }
    private:
        hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
    };
}

最后是一个简单的功能测试，可以看看自定义容器和标准库在迭代顺序上的差异。

#include <unordered_set>
#include "MyUnorderedSet.h"
#include "MyUnorderedMap.h"

void test_unordered_set() {
    dck::unordered_set<int> st;
    st.insert(4);
    st.insert(1);
    st.insert(2);
    st.insert(3);
    dck::unordered_set<int>::iterator it = st.begin();
    while (it != st.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;  // 桶顺序：1 2 3 4
    unordered_set<int> st1;
    st1.insert(4);
    st1.insert(1);
    st1.insert(2);
    st1.insert(3);
    unordered_set<int>::iterator it1 = st1.begin();
    while (it1 != st1.end()) {
        cout << *it1 << " ";  // 插入顺序：4 1 2 3
        ++it1;
    }
    cout << endl;
}

void print(const dck::unordered_map<int, int>& mp) {
    dck::unordered_map<int, int>::const_iterator it = mp.begin();
    while (it != mp.end()) {
        cout << it->first << " " << it->second << endl;
        ++it;
    }
    cout << endl;
}

void test_unordered_map() {
    dck::unordered_map<int, int> mp;
    mp.insert(make_pair(4, 4));
    mp.insert(make_pair(1, 1));
    mp.insert(make_pair(2, 2));
    mp.insert(make_pair(3, 3));
    print(mp);
    dck::unordered_map<int, int>::iterator it = mp.begin();
    while (it != mp.end()) {
        // it->first++; // 编译错误，key 不可改
        it->second++;
        cout << it->first << " " << it->second << endl;
        ++it;
    }
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    dck::unordered_map<string, int> countMap;
    for (auto x : arr) countMap[x]++;
    for (auto t : countMap) {
        cout << t.first << " " << t.second << endl;
    }
    cout << endl;
}

int main() {
    test_unordered_set();
    test_unordered_map();
    return 0;
}

整个实现里，迭代器顺序选择了桶优先，省掉了维护插入顺序的额外开销，换来更直接的结构和略优的性能。这种取舍在实际项目里按场景权衡就好。