C++进阶：unordered_set 和 unordered_map 详解及哈希表模拟实现 | 极客日志

C++算法

C++进阶：unordered_set 和 unordered_map 详解及哈希表模拟实现

哈希表原理及 STL 容器 unordered_set 和 unordered_map 的模拟实现。涵盖哈希函数设计、冲突解决策略（开放定址法与哈希桶）、负载因子控制、扩容机制以及迭代器封装。通过 C++ 代码演示底层数据结构构建过程，解析 key-value 模型与去重逻辑，提供完整的头文件源码及测试用例。

SecGuard发布于 2025/10/13更新于 2026/6/419 浏览

C++ 进阶：unordered_set 和 unordered_map 详解及哈希表模拟实现

引入

在正式讲解 STL 的 unordered_map 以及 unordered_set 这两个容器之前，我们先来回顾一下目前接触到能够高效查找数据的数据结构。首先想到的是数组，但这里的数组不是简单的将元素直接存放到任意位置，而是先将存储在数组中的元素进行一次排序，然后借助二分算法来进行查找。由于这里数组的排序只需要一次，那么排序付出的代价可以均摊到每一次的查找操作中，所以这里排序的代价可以忽略不计，而二分查找的时间复杂度则是 O(logN)，这种方式能够实现高效的数据查找。但是如果涉及到插入以及删除操作的话，如果插入以及删除元素不在数组末尾，那么必然就要移动大量的元素，意味着插入和删除的时间复杂度最坏情况下会达到 O(N)，效率相比于查找就不那么高效。

接着就是在二叉搜索树的基础上优化，压缩其高度的 AVL 树和红黑树这两个数据结构。这两种数据结构则是会将整个二叉搜索树的高度压缩到 logN，所以对于 AVL 树以及红黑树来说，其查找和插入都是在 logN 这个量级。那么相比于刚才所说的排序 + 二分的数组，其综合效率上又要更进一步。

而目前我们接触到的数据结构中，综合效率最为高效的数据结构便是 AVL 树以及红黑树，而本文要登场的数据结构：哈希表。该数据结构核心功能也是高效查找数据，而更关键的是，哈希表的综合效率还能够在 AVL 树以及红黑树的基础上更进一步。而本文着重要讲的 STL 的两个容器：unordered_map 和 unordered_set，其底层采取的数据结构便是哈希表。所以要掌握 unordered_map 以及 unordered_set，首先我们就得先掌握哈希表。后文的内容，我会首先讲解哈希表的原理，理解了哈希表之后，那么我们便可以用代码模拟实现 STL 中的 unordered_set 和 unordered_map 这两个容器。

哈希表

由上文可知，哈希表也是高效查找数据的数据结构。而 AVL 以及红黑树之所以能够高效查找数据，核心就是借助二叉搜索树的左小右大的性质，也就是左子树中的所有节点小于根节点，右子树中的所有节点大于根节点，来实现数据的查找。而这里的哈希表是如何来实现数据的查找呢？

哈希表实现数据的查找则是通过建立键与存储位置的映射来实现数据的查找。而哈希表本质上就是一个动态数组，所以这里的存储位置其实就是数组的索引，哈希表就是建立键与数组索引的一个映射。

而这里所谓的映射，有一个专业术语来称呼，便是哈希函数。

哈希函数

所谓的哈希函数可能仅仅就是一个简单的算术表达式，比如 Ax-C，也许可能对应的是一个有很多步骤的复杂算法。总之，我们可以用一个函数来代表这里的哈希函数：

y = hash(x)

那么在认识以及了解哈希函数具备哪些性质之前，我们可以先来看一下哈希函数长什么样：

// 乘法哈希
uint32_t knuth_hash(uint32_t key) {
    return key * 2654435761;
}

// 字符串哈希
uint32_t djb2_hash(const char* str) {
    uint32_t hash = 5381; // 魔术种子（Magic Number）
    int c;
    while ((c = *str++)) {
        // hash * 33 + c
        hash = ((hash << ) + hash) + c;
    }
     hash;
}

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。在线工具，Gemini 图片去水印在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online

H(string) -> int

enum state { EMPTY, DELETE, OCCUPY };
template<typename T>
struct HashNode {
    T data;
    state _state;
};

Hash(Key) = Key % N

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 HashFuc>
class HashTable {
private:
    typedef HashNode<T> Node;
    std::vector<Node*> HT;
    size_t _n;
};

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

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

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

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 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 key, typename T, typename keyofT, typename HashFun = _HashFun<key>>
class HashTable {
    // ...
};

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

void insert(const T& _data) {
    HashFun returnHash;
    keyofT returnKey;
    if (find(returnKey(_data))) { return; }
    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;
}

template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun>
class Hash_iterator {
private:
    typedef HashNode<T> Node;
    Node* _Node;
    HashTable<key, T, keyofT, HashFun>* HTptr;
    // ...
};

template<typename key, typename T, typename keyofT, typename HashFuc>
class HashTable {
public:
    template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun>
    friend class Hash_iterator;
    // ...
};

self& operator++() {
    if (_Node == nullptr) { 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] == nullptr) {
        nextnum++;
    }
    if (nextnum < HTptr->HT.size()) {
        _Node = HTptr->HT[nextnum];
    } else {
        _Node = nullptr;
    }
    return *this;
}

typedef Hash_iterator<key, T, ptr, ref, keyofT, HashFun> self;

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

template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFuc>
class Hash_iterator {
public:
    // ...
    ref operator*() { return _Node->data; }
    ptr operator->() { return &_Node->data; }
    // ...
};

template<typename key, typename T, typename keyofT, typename HashFun>
class HashTable {
    // ...
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 keyofT, typename HashFuc = _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;
    Node* _Node;
    HashTable<key, T, keyofT, HashFuc>* HTptr;
    // ...
};

template<typename key, typename T, typename keyofT, typename HashFuc>
class HashTable {
    // ...
};

Hash_iterator(Node* ptr, const HashTable<key, T, keyofT, HashFun>* _HTptr) : _Node(ptr), HTptr(_HTptr) { }

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

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

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

template<typename key, typename val>
class unordered_map {
    // ...
public:
    iterator find(const key& k) { return _HT.find(k); }
    const_iterator find(const key& k) const { return _HT.find(k); }
    // ...
};
template<typename key>
class unordered_set {
public:
    iterator find(const key& k) { return _HT.find(k); }
};

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

template<typename key, typename val>
class unordered_map {
    // ...
public:
    std::pair<iterator, bool> insert(const std::pair<key, val>& data) { return _HT.insert(data); }
    // ...
};

template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun = _HashFun<key>>
class Hash_iterator {
private:
    // ...
    typedef Hash_iterator<key, T, T*, T&, keyofT, HashFun> iterator;
public:
    // ...
};

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

template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun = _HashFun<key>>
class Hash_iterator {
private:
    // ...
    Node* _Node;
    const HashTable<key, T, keyofT, HashFun>* HTptr;
public:
    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; }
    // ...
};

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

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

#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 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 HashFuc = _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 == nullptr) { 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] == nullptr) {
            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;
    
    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;
        }
    }
    
    template<typename key, typename T, typename ptr, typename ref, typename keyofT, typename HashFun>
    friend class Hash_iterator;
    
    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

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

} // namespace wz

#pragma once
#include "hashbucket.h"

namespace wz {

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

#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_HashTable_basic() {
    cout << "Testing HashTable basic operations..." << endl;
    HashTable<int, int, _HashFun<int>> ht;
    cout << "HashTable construction test passed." << endl;
    auto result = ht.insert(42);
    assert(result.second == true);
    assert(*result.first == 42);
    cout << "Insert unique value test passed." << endl;
    auto result2 = ht.insert(42);
    assert(result2.second == false);
    cout << "Insert duplicate value test passed." << endl;
    auto found = ht.find(42);
    assert(found != ht.end());
    assert(*found == 42);
    cout << "Find existing value test passed." << endl;
    auto notFound = ht.find(100);
    assert(notFound == ht.end());
    cout << "Find non-existing value test passed." << endl;
    cout << "All basic HashTable tests passed!" << endl << endl;
}

void test_HashTable_iterator() {
    cout << "Testing HashTable iterators..." << endl;
    HashTable<int, int, _HashFun<int>> ht;
    assert(ht.begin() == ht.end());
    cout << "Empty container iterator test passed." << endl;
    ht.insert(1);
    ht.insert(2);
    ht.insert(3);
    int sum = 0;
    for (auto it = ht.begin(); it != ht.end(); ++it) {
        sum += *it;
    }
    assert(sum == 6); // 1+2+3
    cout << "Forward iteration test passed." << endl;
    assert(ht.begin() != ht.end());
    cout << "Non-empty container iterator test passed." << endl;
    cout << "All iterator tests passed!" << endl << endl;
}

void test_HashTable_erase() {
    cout << "Testing HashTable erase..." << endl;
    HashTable<int, int, _HashFun<int>> ht;
    ht.insert(42);
    assert(ht.find(42) != ht.end());
    ht.erase(42);
    assert(ht.find(42) == ht.end());
    cout << "Erase existing value test passed." << endl;
    ht.erase(100); // Should not crash
    cout << "Erase non-existing value test passed." << endl;
    for (int i = 0; i < 10; i++) {
        ht.insert(i);
    }
    for (int i = 0; i < 10; i += 2) {
        ht.erase(i);
    }
    for (int i = 0; i < 10; i++) {
        auto it = ht.find(i);
        if (i % 2 == 0) {
            assert(it == ht.end());
        } else {
            assert(it != ht.end());
        }
    }
    cout << "Multiple erase test passed." << endl;
    cout << "All erase 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);
    auto notFound = uset.find(100);
    assert(notFound == uset.end());
    cout << "Set find test passed." << endl;
    uset.erase(42);
    assert(uset.find(42) == uset.end());
    cout << "Set erase test passed." << endl;
    uset.insert(1);
    uset.insert(2);
    uset.insert(3);
    int count = 0;
    for (auto it = uset.begin(); it != uset.end(); ++it) {
        count++;
        assert(*it >= 1 && *it <= 3);
    }
    assert(count == 3);
    cout << "Set iteration 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");
    auto notFound = umap.find(100);
    assert(notFound == umap.end());
    cout << "Map find test passed." << endl;
    umap.erase(42);
    assert(umap.find(42) == umap.end());
    cout << "Map erase test passed." << endl;
    // operator[]
    umap[1] = "one";
    assert(umap.find(1) != umap.end());
    assert(umap[1] == "one");
    umap[1] = "modified";
    assert(umap[1] == "modified");
    assert(umap.find(2) == umap.end());
    umap[2] = "two";
    assert(umap.find(2) != umap.end());
    assert(umap[2] == "two");
    cout << "Map operator[] test passed." << endl;
    umap[1] = "one";
    umap[2] = "two";
    umap[3] = "three";
    int count = 0;
    for (auto it = umap.begin(); it != umap.end(); ++it) {
        count++;
        assert(it->first >= 1 && it->first <= 3);
        assert(!it->second.empty());
    }
    assert(count == 3);
    cout << "Map iteration test passed." << endl;
    cout << "All unordered_map tests passed!" << endl << endl;
}

void test_collision_handling() {
    cout << "Testing collision handling..." << endl;
    HashTable<int, int, _HashFun<int>> ht;
    ht.insert(2); // 2 % 2 = 0
    ht.insert(4); // 4 % 2 = 0
    ht.insert(6); // 6 % 2 = 0
    assert(ht.find(2) != ht.end());
    assert(ht.find(4) != ht.end());
    assert(ht.find(6) != ht.end());
    cout << "Collision handling test passed." << endl;
    cout << "All collision handling tests passed!" << endl << endl;
}

void test_rehashing() {
    cout << "Testing rehashing..." << endl;
    HashTable<int, int, _HashFun<int>> ht;
    const int COUNT = 20; // Resize from 10 to 20
    for (int i = 0; i < COUNT; i++) {
        ht.insert(i);
    }
    for (int i = 0; i < COUNT; i++) {
        assert(ht.find(i) != ht.end());
    }
    cout << "Rehashing test passed." << endl;
    cout << "All rehashing tests passed!" << endl << endl;
}

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

C++进阶：unordered_set 和 unordered_map 详解及哈希表模拟实现

C++ 进阶：unordered_set 和 unordered_map 详解及哈希表模拟实现

引入

哈希表

哈希函数

更多推荐文章

相关免费在线工具

开放定址法 + 线性探测

负载因子

二次探测

哈希桶

unordered_set 和 unordered_map 的封装

构造函数

insert 函数

迭代器 Hash_iterator

begin/end 函数

find 函数

完善 insert 函数

erase 函数

析构函数

源码

hashbucket.h

myunordered_map.h

myunordered_set.h

main.cpp

更多推荐文章

相关免费在线工具

C++进阶：unordered_set 和 unordered_map 详解及哈希表模拟实现

C++ 进阶：unordered_set 和 unordered_map 详解及哈希表模拟实现

引入

哈希表

哈希函数

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

开放定址法 + 线性探测

负载因子

二次探测

哈希桶

unordered_set 和 unordered_map 的封装

构造函数

insert 函数

迭代器 Hash_iterator

begin/end 函数

find 函数

完善 insert 函数

erase 函数

析构函数

源码

hashbucket.h

myunordered_map.h

myunordered_set.h

main.cpp

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具