C++进阶：深入理解 unordered_set 与 unordered_map（含哈希表模拟实现）

Hash(Key) = key % N

其中 N 为数组长度。当发生冲突时，采用线性探测，即从当前位置 i 往后遍历 i+1, i+2... 直到找到空闲位置。遍历过程中需注意模运算，防止越界。

对于删除操作，不能直接标记为 EMPTY，否则会影响后续查找。需引入 DELETE 状态标记，表示该位置曾被占用但已删除。

随着数据量增加，负载因子变大，冲突概率升高，性能下降。此时需要扩容。扩容时机通常由负载因子决定，一般设定为 0.7 或 0.75 时触发。

二次探测

线性探测容易导致有效数据分布集中（聚簇现象）。二次探测则使用 i+0^2, i+1^2, i+2^2... 作为探测序列，使数据分布更离散，减少冲突概率。

哈希桶

哈希桶本质上是一个指针数组，每个位置指向一个链表。哈希函数计算出的下标即为链表头节点位置。插入时直接头插，无需处理冲突，因为链表天然支持多对一映射。

查找时间复杂度取决于最长链表的长度。理想情况下，每个桶的平均长度为 N/m（N 为元素个数，m 为桶数），查找接近 O(1)。若所有键都映射到同一桶，则退化为 O(N)，但概率极低。

STL 的 unordered_set 和 unordered_map 底层均采用哈希桶结构。Java 的 HashMap 在此基础上进一步优化，当链表长度超过阈值时转换为红黑树。

模拟实现 unordered_set 和 unordered_map

unordered_set 和 unordered_map 底层封装了哈希表。为了复用代码，我们可以设计一个通用的哈希表模板类，上层容器仅负责特定逻辑（如去重或键值对存储）。

节点定义

每个桶对应一个单链表节点：

template<typename T>
class HashNode {
public:
    T data;
    HashNode<T>* next;
    HashNode(const T& val) : data(val), next(nullptr) {}
};

哈希表核心类

哈希表本质是动态指针数组，可用 vector 封装。需维护节点总数 _n 以计算负载因子。

template<typename key, typename T, typename keyofT, typename HashFun = _HashFun<key>>
class HashTable {
private:
    typedef HashNode<T> Node;
    std::vector<Node*> HT;
    size_t _n;
    // ... 其他成员函数
};

构造函数

初始化时开辟一定长度的指针数组，注意使用 resize 而非 reserve，确保有效长度正确。

HashTable() : _n(0) { HT.resize(10, nullptr); }

Insert 函数

插入前需检查键是否存在（去重）。若存在则不插入；若不存在，先判断是否需扩容（负载因子 >= 1）。扩容时重新映射所有节点到新数组，采用头插法并交换 vector 以提高效率。

获取键值需借助仿函数（KeyOfT），处理浮点型或自定义类型时需二次映射为整形。对于字符串，推荐使用 BKDR 哈希等成熟算法以减少碰撞。

std::pair<iterator, bool> insert(const T& _data) {
    HashFun returnHash;
    keyofT returnKey;
    iterator exit = find(returnKey(_data));
    if (exit != end()) return std::make_pair(exit, false);

    if (_n == HT.size()) {
        // 扩容逻辑：创建新数组，重新映射节点
        std::vector<Node*> newve;
        size_t newsize = 2 * HT.size();
        newve.resize(newsize);
        for (int i = 0; i < HT.size(); i++) {
            Node* cur = HT[i];
            while (cur) {
                Node* prev = cur->next;
                size_t num = returnHash(returnKey(cur->data)) % newve.size();
                Node* next = newve[num];
                cur->next = next;
                newve[num] = cur;
                cur = prev;
            }
        }
        HT.swap(newve);
    }

    size_t num = returnHash(returnKey(_data)) % HT.size();
    Node* newnode = new Node(_data);
    newnode->next = HT[num];
    HT[num] = newnode;
    _n++;
    return std::make_pair(iterator(newnode, this), true);
}

迭代器封装

原生指针无法跨桶遍历，需封装迭代器类 Hash_iterator。它需指向当前节点及所属哈希表对象，以便访问桶数组。重载 ++, *, ->, ==, != 运算符。

template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun>
class Hash_iterator {
private:
    typedef HashNode<T> Node;
    Node* _Node;
    const HashTable<key, T, keyofT, HashFun>* HTptr;
    // ... 构造函数及运算符重载
};

注意 const 版本与非 const 版本的区别在于返回值是否允许修改数据。unordered_set 的迭代器通常为 const 版本，而 unordered_map 允许修改 value。

其他关键函数

• Find: 遍历对应桶的链表查找键。
• Erase: 删除节点需处理前驱指针，释放内存。
• Begin/End: 返回首尾迭代器。
• 析构: 遍历所有链表释放节点内存。

完整源码示例

以下是核心模块的实现代码，包含哈希表、迭代器及上层容器封装。

hashbucket.h

#pragma once
#include <string>
#include <vector>

namespace my_std {

template<typename T>
class _HashFun {
public:
    size_t operator()(const T& val) { return val; }
};

template<>
class _HashFun<int> {
public:
    size_t operator()(const int& val) { return static_cast<size_t>(val); }
};

template<>
class _HashFun<std::string> {
public:
    size_t operator()(const std::string& val) {
        size_t hash = 0;
        for (int i = 0; i < val.size(); i++) {
            hash = hash * 131 + val[i];
        }
        return hash;
    }
};

template<typename T>
class HashNode {
public:
    T data;
    HashNode<T>* next;
    HashNode(const T& val) : data(val), next(nullptr) {}
};

template<typename key, typename T, typename keyofT, typename HashFun = _HashFun<key>>
class HashTable;

template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun = _HashFun<key>>
class Hash_iterator {
private:
    typedef HashNode<T> Node;
    typedef Hash_iterator<key, T, ptr, ref, keyofT, HashFun> self;
    typedef Hash_iterator<key, T, T*, T&, keyofT, HashFun> iterator;
    Node* _Node;
    const HashTable<key, T, keyofT, HashFun>* HTptr;

public:
    Hash_iterator(Node* ptr, const HashTable<key, T, keyofT, HashFun>* _HTptr) : _Node(ptr), HTptr(_HTptr) {}
    Hash_iterator(const iterator& it) : _Node(it.getNode()), HTptr(it.getHTptr()) {}

    Node* getNode() const { return _Node; }
    const HashTable<key, T, keyofT, HashFun>* getHTptr() const { return HTptr; }

    self& operator++() {
        if (!_Node) return *this;
        if (_Node->next) {
            _Node = _Node->next;
            return *this;
        }
        keyofT returnKey;
        HashFun returnHash;
        size_t currentnum = returnHash(returnKey(_Node->data)) % HTptr->HT.size();
        size_t nextnum = currentnum + 1;
        while (nextnum < HTptr->HT.size() && !HTptr->HT[nextnum]) {
            nextnum++;
        }
        if (nextnum < HTptr->HT.size()) {
            _Node = HTptr->HT[nextnum];
        } else {
            _Node = nullptr;
        }
        return *this;
    }

    ref operator*() { return _Node->data; }
    ptr operator->() { return &_Node->data; }

    bool operator==(const self& p) { return _Node == p._Node; }
    bool operator!=(const self& p) { return _Node != p._Node; }
};

template<typename key, typename T, typename keyofT, typename HashFun>
class HashTable {
private:
    typedef HashNode<T> Node;
    std::vector<Node*> HT;
    size_t _n;

public:
    typedef Hash_iterator<key, T, T*, T&, keyofT, HashFun> iterator;
    typedef Hash_iterator<key, T, const T*, const T&, keyofT, HashFun> const_iterator;

    template<typename key_, typename T_, typename ptr_, typename ref_, typename keyofT_, typename HashFun_>
    friend class Hash_iterator;

    HashTable() : _n(0) { HT.resize(10, nullptr); }

    ~HashTable() {
        for (int i = 0; i < HT.size(); i++) {
            Node* cur = HT[i];
            while (cur) {
                Node* next = cur->next;
                delete cur;
                cur = next;
            }
            HT[i] = nullptr;
        }
    }

    iterator find(const key& k) {
        keyofT returnKey;
        HashFun returnHash;
        size_t num = returnHash(k) % HT.size();
        Node* cur = HT[num];
        while (cur) {
            if (returnKey(cur->data) == k) return iterator(cur, this);
            cur = cur->next;
        }
        return iterator(nullptr, this);
    }

    const_iterator find(const key& k) const {
        HashFun returnHash;
        keyofT returnKey;
        size_t num = returnHash(k) % HT.size();
        Node* cur = HT[num];
        while (cur) {
            if (returnKey(cur->data) == k) return const_iterator(cur, this);
            cur = cur->next;
        }
        return const_iterator(nullptr, this);
    }

    std::pair<iterator, bool> insert(const T& _data) {
        HashFun returnHash;
        keyofT returnKey;
        iterator exit = find(returnKey(_data));
        if (exit != end()) return std::make_pair(exit, false);

        if (_n == HT.size()) {
            std::vector<Node*> newve;
            size_t newsize = 2 * HT.size();
            newve.resize(newsize);
            for (int i = 0; i < HT.size(); i++) {
                Node* cur = HT[i];
                while (cur) {
                    Node* prev = cur->next;
                    size_t num = returnHash(returnKey(cur->data)) % newve.size();
                    Node* next = newve[num];
                    cur->next = next;
                    newve[num] = cur;
                    cur = prev;
                }
            }
            HT.swap(newve);
        }

        size_t num = returnHash(returnKey(_data)) % HT.size();
        Node* newnode = new Node(_data);
        newnode->next = HT[num];
        HT[num] = newnode;
        _n++;
        return std::make_pair(iterator(newnode, this), true);
    }

    void erase(const key& k) {
        HashFun returnHash;
        keyofT returnKey;
        size_t num = returnHash(k) % HT.size();
        Node* cur = HT[num];
        Node* prev = nullptr;
        while (cur) {
            if (returnKey(cur->data) == k) {
                if (prev) {
                    prev->next = cur->next;
                } else {
                    HT[num] = cur->next;
                }
                delete cur;
                _n--;
                return;
            }
            prev = cur;
            cur = cur->next;
        }
    }

    iterator begin() {
        for (int i = 0; i < HT.size(); i++) {
            if (HT[i]) return iterator(HT[i], this);
        }
        return iterator(nullptr, this);
    }

    const_iterator begin() const {
        for (int i = 0; i < HT.size(); i++) {
            if (HT[i]) return const_iterator(HT[i], this);
        }
        return const_iterator(nullptr, this);
    }

    iterator end() { return iterator(nullptr, this); }
    const_iterator end() const { return const_iterator(nullptr, this); }
};

} // namespace my_std

myunordered_map.h & myunordered_set.h

#pragma once
#include "hashbucket.h"

namespace wz {

template<typename key, typename val>
class unordered_map {
private:
    class keyofMapT {
    public:
        const key& operator()(const std::pair<key, val>& _kv) { return _kv.first; }
    };
    my_std::HashTable<const key, std::pair<key, val>, keyofMapT> _HT;

public:
    typedef typename my_std::HashTable<const key, std::pair<key, val>, keyofMapT>::iterator iterator;
    typedef typename my_std::HashTable<const key, std::pair<key, val>, keyofMapT>::const_iterator const_iterator;

    std::pair<iterator, bool> insert(const std::pair<key, val>& data) {
        return _HT.insert(data);
    }

    iterator find(const key& k) { return _HT.find(k); }
    const_iterator find(const key& k) const { return _HT.find(k); }

    void erase(const key& k) { _HT.erase(k); }

    iterator begin() { return _HT.begin(); }
    const_iterator begin() const { return _HT.begin(); }
    iterator end() { return _HT.end(); }
    const_iterator end() const { return _HT.end(); }

    val& operator[](const key& k) {
        std::pair<iterator, bool> _pair = insert(std::make_pair(k, val()));
        return _pair.first->second;
    }
};

template<typename key>
class unordered_set {
private:
    class keyofSetT {
    public:
        const key& operator()(const key& k) { return k; }
    };
    my_std::HashTable<key, key, keyofSetT> _HT;

public:
    typedef typename my_std::HashTable<key, key, keyofSetT>::const_iterator iterator;
    typedef typename my_std::HashTable<key, key, keyofSetT>::const_iterator const_iterator;

    std::pair<iterator, bool> insert(const key& k) {
        std::pair<iterator, bool> p = _HT.insert(k);
        return std::pair<iterator, bool>(p.first, p.second);
    }

    iterator find(const key& k) { return _HT.find(k); }
    void erase(const key& k) { _HT.erase(k); }
    iterator begin() const { return _HT.begin(); }
    iterator end() const { return _HT.end(); }
};

} // namespace wz

main.cpp

#include <iostream>
#include <cassert>
#include <string>
#include <vector>
#include "hashbucket.h"
#include "myunordered_map.h"
#include "myunordered_set.h"

using namespace std;
using namespace my_std;
using namespace wz;

void test_HashFun() {
    cout << "Testing _HashFun..." << endl;
    _HashFun<int> intHash;
    assert(intHash(42) == 42);
    cout << "Int hash function test passed." << endl;
    _HashFun<std::string> stringHash;
    size_t hash1 = stringHash("hello");
    size_t hash2 = stringHash("world");
    assert(hash1 != hash2);
    cout << "String hash function test passed." << endl;
    cout << "All _HashFun tests passed!" << endl << endl;
}

void test_unordered_set() {
    cout << "Testing unordered_set..." << endl;
    unordered_set<int> uset;
    auto result = uset.insert(42);
    assert(result.second == true);
    assert(*result.first == 42);
    cout << "Set insert test passed." << endl;
    auto result2 = uset.insert(42);
    assert(result2.second == false);
    cout << "Set duplicate insert test passed." << endl;
    auto found = uset.find(42);
    assert(found != uset.end());
    assert(*found == 42);
    cout << "Set find test passed." << endl;
    uset.erase(42);
    assert(uset.find(42) == uset.end());
    cout << "Set erase test passed." << endl;
    cout << "All unordered_set tests passed!" << endl << endl;
}

void test_unordered_map() {
    cout << "Testing unordered_map..." << endl;
    unordered_map<int, std::string> umap;
    auto result = umap.insert({42, "forty-two"});
    assert(result.second == true);
    assert(result.first->first == 42);
    assert(result.first->second == "forty-two");
    cout << "Map insert test passed." << endl;
    auto result2 = umap.insert({42, "another value"});
    assert(result2.second == false);
    assert(result2.first->second == "forty-two");
    cout << "Map duplicate insert test passed." << endl;
    auto found = umap.find(42);
    assert(found != umap.end());
    assert(found->first == 42);
    assert(found->second == "forty-two");
    cout << "Map find test passed." << endl;
    umap.erase(42);
    assert(umap.find(42) == umap.end());
    cout << "Map erase test passed." << endl;
    cout << "All unordered_map tests passed!" << endl << endl;
}

int main() {
    cout << "Starting comprehensive tests for hash table implementation..." << endl << endl;
    test_HashFun();
    test_unordered_set();
    test_unordered_map();
    cout << "All tests passed! Hash table implementation is working correctly." << endl;
    return 0;
}

结语

至此，关于哈希表原理及 unordered_set、unordered_map 的模拟实现已全部讲解完毕。掌握这些底层机制，有助于在开发中更好地利用 STL 容器，并在遇到性能瓶颈时进行针对性优化。