C++ STL 进阶：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));
    
    // 遍历
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        cout << it->first << ":" << it->second << endl;
    }
    
    // [] 接口特性：若 key 不存在会自动创建
    mp[3] = 5;
    cout << mp[3] << endl;
}

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

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

模拟实现思路

模拟实现的核心在于构建一个通用的哈希表（HashTable），然后基于它封装 unordered_set 和 unordered_map。

1. 哈希桶节点改造

底层哈希桶需要通用化，因为 unordered_map 存储的是 pair，而 unordered_set 存储的是 K。因此节点模板参数设为 T。

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

2. 迭代器的实现难点

迭代器++的本质是找下一个节点。在哈希桶结构中，这分为两种情况：

1. 当前节点的 next 不为空，直接向后移动。
2. 当前桶遍历完了，需要寻找下一个有元素的桶。

这意味着迭代器内部必须持有哈希表的引用以及当前所在桶的编号。

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; }
};

注意： 这里我们提供的迭代器访问顺序是按照桶的编号顺序，而标准库中通常按照元素插入顺序实现，这需要额外维护链表结构。

3. 哈希表核心逻辑

查找与插入

查找时需要通过 KeyOfT 仿函数提取 key。插入时如果发生冲突，采用头插法。

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);
    
    // 扩容逻辑：当元素个数等于桶数时扩容
    if (_n == _tables.size()) {
        size_t newSize = _tables.size() * 2;
        vector<Node*> newTables(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;
    KeyOfT kot;
    size_t hashi = hf(key) % _tables.size();
    Node* prev = nullptr;
    Node* cur = _tables[hashi];
    while (cur) {
        if (kot(cur->_data) == key) {
            if (prev == nullptr)
                _tables[hashi] = cur->_next;
            else
                prev->_next = cur->_next;
            delete cur;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

4. 封装 unordered_set 与 unordered_map

unordered_set

内部元素不可修改，因此迭代器统一为 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;

    pair<iterator, bool> insert(const K& key) {
        auto ret = _ht.Insert(key);
        // 构造 const_iterator
        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;
};
}

unordered_map

普通迭代器允许修改 value，const 迭代器不允许修改任何内容。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;

    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;
};
}

性能测试对比

通过对比 set 与 unordered_set 的插入、查找、删除耗时，可以直观看到哈希表的优势。

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() + 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 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;

    cout << "插入数据个数：" << us.size() << endl;
    ht.Some(); // 打印桶使用情况
}

测试结果通常显示，在大数据量下，unordered_set 的各项性能均高于 set。最长的桶挂的元素很少，平均桶长度接近 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;

    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); }

    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(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; KeyOfT kot;
        size_t hashi = hf(key) % _tables.size();
        Node* prev = nullptr;
        Node* cur = _tables[hashi];
        while (cur) {
            if (kot(cur->_data) == key) {
                if (prev == nullptr)
                    _tables[hashi] = cur->_next;
                else
                    prev->_next = cur->_next;
                delete cur;
                return true;
            }
            prev = cur;
            cur = cur->_next;
        }
        return false;
    }

    void Some() {
        size_t bucketSize = 0, maxBucketLen = 0, sum = 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;
        }
        double averageBucketLen = bucketSize ? (double)sum / bucketSize : 0;
        printf("all bucketSize:%d\n", _tables.size());
        printf("bucketSize:%d\n", bucketSize);
        printf("maxBucketLen:%d\n", maxBucketLen);
        printf("averageBucketLen:%lf\n\n", averageBucketLen);
    }

private:
    vector<Node*> _tables;
    size_t _n = 0;
};
}

MyUnorderedSet.h & MyUnorderedMap.h

结构如上文所示，主要区别在于 KeyOfT 的实现和模板参数的传递。

通过以上实现，我们不仅掌握了 unordered_set 和 unordered_map 的使用技巧，还深入理解了其背后的哈希表机制。在实际开发中，根据数据特点选择合适的容器，能显著提升程序效率。