C++进阶：（十一）深度解析——用哈希表封装 unordered_map 和 unordered_set

_OP_CHEN

发布于 2026-01-14 10:53:47

1630

文章被收录于专栏：C++C++

前言

在 C++ 的 STL 容器家族中，unordered_map 和 unordered_set 是高频使用的关联式容器。它们凭借哈希表的底层实现，实现了 O (1) 级别的平均查找、插入和删除效率，在处理大规模数据时展现出显著优势。但你是否好奇过，这两个容器是如何基于哈希表实现的？为什么 unordered_set 不支持修改元素，而 unordered_map 只能修改 value 不能修改 key？本文将带你从源码分析入手，一步步拆解哈希表封装 unordered_map 和 unordered_set 的完整实现过程，包含详细的代码实现和原理讲解，让你不仅知其然，更知其所以然。下面就让我我们正式开始吧！

一、前置知识：STL 中哈希表与 unordered 系列容器的渊源

在正式开始实现之前，我们先回顾一下 STL 中哈希表与 unordered_map、unordered_set 的历史渊源。这能帮助我们更好地理解设计思路的由来。

1.1 SGI-STL 的历史遗留问题

如果你翻阅过 SGI-STL 3.0 版本的源代码，会发现一个有趣的现象：这个版本中并没有 unordered_map 和 unordered_set 容器。因为 SGI-STL 3.0 是 C++11 标准之前的实现，而 unordered_map 和 unordered_set 是 C++11 才正式纳入标准的容器。

但这并不意味着 SGI-STL 没有提供哈希表相关的容器 —— 它实现了 hash_map 和 hash_set，只不过这两个容器属于非标准扩展（即 C++ 标准并未强制要求所有编译器实现）。它们的底层核心是一个名为 hashtable 的哈希表实现，相关源代码分散在 hash_map.h、hash_set.h、stl_hash_table.h 等文件中。

1.2 核心设计思路：复用哈希表底层

SGI-STL 中 hash_map 和 hash_set 的设计遵循了 "复用底层" 的原则，这也是 STL 容器设计的核心思想之一。从源码中可以看到：

hash_set 的底层是 hashtable，存储的是单一 key 值，传给 hashtable 的模板参数是 Value（实际为 key）；
hash_map 的底层同样是 hashtable，存储的是 pair<const Key, T> 键值对；
两者都通过 hashtable 提供的 insert_unique、find 等接口实现自身的核心功能。

这种设计的优势在于：只需要实现一个通用的哈希表，就能通过不同的模板参数和适配层，封装出两种不同用途的容器。我们后续的实现也将沿用这个思路，先实现一个通用的哈希表（HashTable），再基于它分别封装 unordered_map 和 unordered_set。

1.3 源码中的 "小瑕疵"：命名不规范

值得一提的是，即使是 STL 源码，也存在命名不规范的情况。比如 hash_set 的模板参数用 Value 命名（实际存储的是 key），而 hash_map 用 Key 和 T 命名（分别对应键和值）。这给阅读源码带来了一定的困扰。因此，在我们自己的实现中，会采用更清晰的命名规则：用 K 表示 key 类型，V 表示 value 类型，T 表示哈希表中存储的实际数据类型（可能是 K，也可能是 pair<K, V>）。

二、通用哈希表（HashTable）的实现

哈希表是 unordered_map 和 unordered_set 的底层核心，其实现质量直接决定了上层容器的性能。一个完整的哈希表需要支持节点存储、哈希计算、冲突解决、扩容、迭代器等核心功能。尽管在之前的博客中，我已经带大家实现过哈希表这一数据结构了，本期博客我还是再以STL中对于哈希表的实现，带大家复习一下通用哈希表的实现。下面我们一步步实现这个通用哈希表。

2.1 哈希表的核心结构设计

哈希表的经典实现是 "数组 + 链表" 的结合体（也称为链地址法）：

2.1.1 哈希节点（HashNode）的实现

哈希节点需要存储数据和下一个节点的指针，设计成模板类以支持不同的数据类型：

// HashTable.h
namespace hash_bucket {
    // 哈希节点结构
    template<class T>
    struct HashNode {
        T _data;          // 存储的数据
        HashNode<T>* _next; // 指向下一个节点的指针

        // 构造函数
        HashNode(const T& data)
            : _data(data)
            , _next(nullptr) {}
    };
}

2.1.2 哈希函数的设计

哈希函数的作用是将 key 值映射为桶数组的索引（即哈希值）。由于 key 的类型可能是 int、string 等不同类型，我们需要设计一个通用的哈希函数接口，并针对不同类型进行特化。

首先实现默认的哈希函数模板（适用于整形类型）：

// HashTable.h
// 默认哈希函数模板（适用于整形类型）
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        // 直接将整形key转换为size_t作为哈希值
        return (size_t)key;
    }
};

对于 string 类型，不能直接转换为整形，需要设计专门的哈希算法。这里采用经典的字符串哈希算法：

// HashTable.h
// 字符串类型的哈希函数特化
template<>
struct HashFunc<string> {
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (char ch : key) {
            // 经典哈希算法：每次迭代累加字符ASCII值并乘以一个质数（131）
            hash = hash * 131 + ch;
        }
        return hash;
    }
};

2.1.3 键提取函数（KeyOfT）的设计

哈希表中存储的数据类型 T 可能有两种情况：

对于 unordered_set：T 就是 key 类型（K）
对于 unordered_map：T 是 pair<const K, V> 类型

哈希表在进行哈希计算和键比较时，只需要用到 key 值，因此需要一个 "键提取函数"，从 T 类型中提取出 K 类型的 key。这个函数不能硬编码，需要由上层容器（unordered_map/unordered_set）提供，因此我们将其设计为模板参数，由上层传入。

例如：

unordered_set 的键提取函数：直接返回 T（因为 T 就是 key）
unordered_map 的键提取函数：返回 pair 中的 first 成员（即 key）

2.2 哈希表的核心成员与构造、析构函数

2.2.1 核心成员变量

// HashTable.h
namespace hash_bucket {
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable {
    public:
        typedef HashNode<T> Node; // 哈希节点类型别名

    private:
        vector<Node*> _tables; // 桶数组：存储节点指针的vector
        size_t _n;             // 哈希表中存储的元素个数
        KeyOfT _kot;           // 键提取函数对象
        Hash _hash;            // 哈希函数对象
    };
}

2.2.2 构造函数：桶数组的初始化

桶数组的初始大小需要选择一个合适的质数（质数能减少哈希冲突）。STL 源码中提供了一个质数列表，我们可以直接复用这个列表，初始化时选择第一个质数（53）作为初始桶大小：

// HashTable.h
namespace hash_bucket {
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable {
        // 质数列表（来自SGI-STL源码）
        static const unsigned long __stl_prime_list[];
        static const int __stl_num_primes = 28;

        // 查找大于等于n的最小质数（用于扩容）
        inline unsigned long __stl_next_prime(unsigned long n) {
            const unsigned long* first = __stl_prime_list;
            const unsigned long* last = __stl_prime_list + __stl_num_primes;
            // 二分查找第一个大于等于n的质数
            const unsigned long* pos = lower_bound(first, last, n);
            return pos == last ? *(last - 1) : *pos;
        }

    public:
        // 构造函数：初始化桶数组
        HashTable() {
            // 初始桶大小为第一个质数53
            size_t initial_size = __stl_next_prime(0);
            _tables.resize(initial_size, nullptr);
            _n = 0;
        }
    };

    // 初始化质数列表
    template<class K, class T, class KeyOfT, class Hash>
    const unsigned long HashTable<K, T, KeyOfT, Hash>::__stl_prime_list[] = {
        53, 97, 193, 389, 769,
        1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433,
        1572869, 3145739, 6291469, 12582917, 25165843,
        50331653, 100663319, 201326611, 402653189, 805306457,
        1610612741, 3221225473, 4294967291
    };
}

2.2.3 析构函数：释放节点资源

析构函数需要遍历所有桶，释放每个桶中的链表节点，避免内存泄漏：

// HashTable.h
namespace hash_bucket {
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable {
    public:
        // 析构函数
        ~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; // 置空桶指针
            }
        }
    };
}

2.3 哈希表的核心操作：插入（Insert）

插入操作是哈希表最核心的操作之一，需要处理哈希计算、冲突解决、扩容等关键逻辑。插入的核心流程如下：

检查插入的 key 是否已存在（存在则返回失败）；
计算 key 的哈希值，确定对应的桶索引；
检查负载因子（_n / 桶数组大小），若达到 1 则进行扩容；
将新节点以头插法插入到对应的桶中；
更新元素个数_n，返回插入成功的迭代器和成功标志。

2.3.1 扩容逻辑

当负载因子（元素个数 / 桶数组大小）达到 1 时，哈希冲突的概率会显著增加，此时需要扩容。扩容的核心步骤：

计算新的桶大小（选择大于当前桶大小的最小质数）
创建新的桶数组（大小为新的桶大小，初始化为 nullptr）
遍历旧桶数组中的所有节点，重新计算每个节点在新桶数组中的索引
将节点插入到新桶数组对应的位置（头插法）
释放旧桶数组的资源，将新桶数组与旧桶数组交换

2.3.2 插入函数的实现

// HashTable.h
namespace hash_bucket {
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable {
    public:
        // 插入元素，返回pair<迭代器, bool>：迭代器指向插入的元素，bool表示是否插入成功
        pair<Iterator, bool> Insert(const T& data) {
            // 1. 检查key是否已存在
            K key = _kot(data);
            Iterator it = Find(key);
            if (it != End()) {
                // key已存在，插入失败
                return make_pair(it, false);
            }

            // 2. 检查负载因子，达到1则扩容
            if (_n == _tables.size()) {
                // 计算新的桶大小
                size_t new_size = __stl_next_prime(_tables.size() + 1);
                // 创建新的桶数组
                vector<Node*> new_tables(new_size, nullptr);

                // 遍历旧桶数组，将所有节点重新映射到新桶
                for (size_t i = 0; i < _tables.size(); ++i) {
                    Node* cur = _tables[i];
                    while (cur) {
                        // 保存下一个节点
                        Node* next = cur->_next;
                        // 重新计算当前节点在新桶中的索引
                        K node_key = _kot(cur->_data);
                        size_t hashi = _hash(node_key) % new_tables.size();
                        // 头插法插入新桶
                        cur->_next = new_tables[hashi];
                        new_tables[hashi] = cur;
                        // 处理下一个节点
                        cur = next;
                    }
                    // 旧桶置空
                    _tables[i] = nullptr;
                }

                // 交换新旧桶数组
                _tables.swap(new_tables);
            }

            // 3. 计算插入位置的哈希索引
            size_t hashi = _hash(key) % _tables.size();
            // 4. 头插法插入新节点
            Node* new_node = new Node(data);
            new_node->_next = _tables[hashi];
            _tables[hashi] = new_node;
            // 5. 更新元素个数
            ++_n;

            // 返回插入成功的迭代器和true
            return make_pair(Iterator(new_node, this), true);
        }
    };
}

2.4 哈希表的核心操作：查找（Find）和删除（Erase）

2.4.1 查找函数（Find）

查找的核心逻辑：

计算 key 的哈希值，确定对应的桶索引；
遍历该桶中的链表节点，比较节点的 key 与目标 key；
找到则返回对应的迭代器，未找到则返回 End ()。

// HashTable.h
namespace hash_bucket {
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable {
    public:
        // 查找key对应的元素，返回迭代器
        Iterator Find(const K& key) {
            // 空表直接返回End()
            if (_tables.empty()) {
                return End();
            }
            // 计算哈希索引
            size_t hashi = _hash(key) % _tables.size();
            // 遍历对应桶的链表
            Node* cur = _tables[hashi];
            while (cur) {
                if (_kot(cur->_data) == key) {
                    // 找到key，返回对应的迭代器
                    return Iterator(cur, this);
                }
                cur = cur->_next;
            }
            // 未找到，返回End()
            return End();
        }
    };
}

2.4.2 删除函数（Erase）

删除的核心逻辑：

计算 key 的哈希值，确定对应的桶索引
遍历该桶中的链表节点，找到 key 对应的节点
处理节点的前驱指针（若为头节点则更新桶指针，否则更新前驱节点的 next 指针）
释放该节点的内存，更新元素个数_n，返回删除成功标志

// HashTable.h
namespace hash_bucket {
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable {
    public:
        // 删除key对应的元素，返回是否删除成功
        bool Erase(const K& key) {
            // 空表直接返回false
            if (_tables.empty()) {
                return false;
            }
            // 计算哈希索引
            size_t hashi = _hash(key) % _tables.size();
            Node* cur = _tables[hashi];
            Node* prev = nullptr; // 前驱节点指针

            // 遍历对应桶的链表
            while (cur) {
                if (_kot(cur->_data) == key) {
                    // 找到要删除的节点
                    if (prev == nullptr) {
                        // 头节点：更新桶指针
                        _tables[hashi] = cur->_next;
                    } else {
                        // 非头节点：更新前驱节点的next指针
                        prev->_next = cur->_next;
                    }
                    // 释放节点内存
                    delete cur;
                    // 更新元素个数
                    --_n;
                    return true;
                }
                // 移动指针
                prev = cur;
                cur = cur->_next;
            }

            // 未找到key，返回false
            return false;
        }
    };
}

2.5.2 迭代器的实现

为了同时支持普通迭代器和 const 迭代器，我们设计一个模板化的迭代器结构 HTIterator，通过模板参数区分普通和 const 类型：

// HashTable.h
namespace hash_bucket {
    // 前置声明HashTable，因为迭代器需要访问HashTable的成员
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable;

    // 哈希表迭代器：模板参数Ptr为数据指针类型，Ref为数据引用类型
    template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
    struct HTIterator {
        typedef HashNode<T> Node;
        typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;

        Node* _node;                  // 当前指向的节点
        const HashTable<K, T, KeyOfT, Hash>* _pht; // 指向哈希表的指针（用于查找下一个桶）

        // 构造函数
        HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
            : _node(node)
            , _pht(pht) {}

        // 解引用运算符：返回数据的引用
        Ref operator*() {
            return _node->_data;
        }

        // 箭头运算符：返回数据的指针（支持->访问成员）
        Ptr operator->() {
            return &_node->_data;
        }

        // 不等运算符：用于判断迭代器是否到达末尾
        bool operator!=(const Self& s) const {
            return _node != s._node;
        }

        // 相等运算符
        bool operator==(const Self& s) const {
            return _node == s._node;
        }

        // 前置++运算符：核心实现
        Self& operator++() {
            // 1. 如果当前节点有下一个节点，直接移动到下一个节点
            if (_node->_next != nullptr) {
                _node = _node->_next;
            } else {
                // 2. 当前桶遍历完，查找下一个非空桶
                KeyOfT kot;
                Hash hash;
                // 计算当前节点所在的桶索引
                size_t hashi = hash(kot(_node->_data)) % _pht->_tables.size();
                // 从当前桶的下一个桶开始查找
                ++hashi;
                while (hashi < _pht->_tables.size()) {
                    if (_pht->_tables[hashi] != nullptr) {
                        // 找到非空桶，指向该桶的第一个节点
                        _node = _pht->_tables[hashi];
                        return *this;
                    }
                    ++hashi;
                }
                // 3. 所有桶都遍历完，迭代器指向nullptr（End()）
                _node = nullptr;
            }
            return *this;
        }

        // 后置++运算符（复用前置++）
        Self operator++(int) {
            Self tmp = *this;
            ++(*this);
            return tmp;
        }
    };
}

2.5.3 哈希表的 begin () 和 end () 接口

在 HashTable 类中提供 begin () 和 end () 接口，分别返回指向第一个元素的迭代器和指向末尾的迭代器（_node 为 nullptr）：

// HashTable.h
namespace hash_bucket {
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable {
    public:
        // 普通迭代器类型别名
        typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;
        // const迭代器类型别名
        typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;

        // 普通迭代器begin()：返回第一个非空桶的第一个节点
        Iterator Begin() {
            if (_n == 0) {
                return End();
            }
            // 遍历桶数组，找到第一个非空桶
            for (size_t i = 0; i < _tables.size(); ++i) {
                if (_tables[i] != nullptr) {
                    return Iterator(_tables[i], this);
                }
            }
            return End();
        }

        // 普通迭代器end()：返回指向nullptr的迭代器
        Iterator End() {
            return Iterator(nullptr, this);
        }

        // const迭代器begin()
        ConstIterator Begin() const {
            if (_n == 0) {
                return End();
            }
            for (size_t i = 0; i < _tables.size(); ++i) {
                if (_tables[i] != nullptr) {
                    return ConstIterator(_tables[i], this);
                }
            }
            return End();
        }

        // const迭代器end()
        ConstIterator End() const {
            return ConstIterator(nullptr, this);
        }

        // 友元声明：让迭代器可以访问哈希表的私有成员（_tables）
        template<class K1, class T1, class Ptr, class Ref, class KeyOfT1, class Hash1>
        friend struct HTIterator;
    };
}

三、基于哈希表封装 unordered_set

unordered_set 是存储唯一 key 的容器，其底层复用我们实现的 HashTable。由于 unordered_set 存储的是单一 key，因此需要设计对应的键提取函数，并限制元素的修改（不允许修改 key）。

3.1 unordered_set 的类结构设计

// MyUnorderedSet.h
#include "HashTable.h"

namespace bit {
    template<class K, class Hash = HashFunc<K>>
    class unordered_set {
        // 键提取函数：unordered_set存储的是K，直接返回key
        struct SetKeyOfT {
            const K& operator()(const K& key) {
                return key;
            }
        };

    public:
        // 迭代器类型别名（复用HashTable的迭代器）
        typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
        typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator 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>
        pair<iterator, bool> insert(const K& key) {
            return _ht.Insert(key);
        }

        // 查找元素
        iterator find(const K& key) {
            return _ht.Find(key);
        }

        const_iterator find(const K& key) const {
            return _ht.Find(key);
        }

        // 删除元素
        bool erase(const K& key) {
            return _ht.Erase(key);
        }

    private:
        // 底层哈希表：存储的类型是const K（不允许修改）
        hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
    };
}

3.2 关键设计说明

键提取函数 SetKeyOfT：由于 unordered_set 存储的是 K 类型的 key，键提取函数直接返回传入的 key 即可。
元素不可修改：哈希表存储的类型是 const K，因此迭代器解引用后返回的是 const K&，不允许修改元素（符合 unordered_set 的特性）。
接口复用：insert、find、erase 等接口直接复用哈希表的对应接口，上层只需要进行简单的封装。

3.3 unordered_set 的测试用例

// MyUnorderedSet.h
namespace bit {
    void test_unordered_set() {
        // 测试插入和遍历
        unordered_set<int> s;
        int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3, 3, 15};
        for (auto e : a) {
            auto ret = s.insert(e);
            if (ret.second) {
                cout << "插入成功：" << e << endl;
            } else {
                cout << "插入失败（已存在）：" << e << endl;
            }
        }
        cout << endl;

        // 遍历输出（无序）
        cout << "unordered_set遍历结果：";
        for (auto e : s) {
            cout << e << " ";
        }
        cout << endl << endl;

        // 测试迭代器遍历
        cout << "迭代器遍历结果：";
        unordered_set<int>::iterator it = s.begin();
        while (it != s.end()) {
            // *it += 1; // 编译报错：不允许修改const K
            cout << *it << " ";
            ++it;
        }
        cout << endl << endl;

        // 测试find和erase
        auto find_it = s.find(5);
        if (find_it != s.end()) {
            cout << "找到元素：" << *find_it << endl;
            s.erase(5);
            cout << "删除元素5后，遍历结果：";
            for (auto e : s) {
                cout << e << " ";
            }
            cout << endl;
        } else {
            cout << "未找到元素5" << endl;
        }
    }
}

测试结果说明：

插入重复元素（如 3、15）会返回插入失败。
遍历结果是无序的，因为哈希表的存储是无序的。
尝试修改迭代器指向的元素会编译报错，保证了元素的不可修改性。

四、基于哈希表封装 unordered_map

unordered_map 是存储键值对（key-value）的容器，key 唯一，value 可修改。其底层同样复用 HashTable，需要设计对应的键提取函数（从 pair 中提取 key），并限制 key 的修改（value 可修改）。

4.1 unordered_map 的类结构设计

// MyUnorderedMap.h
#include "HashTable.h"

namespace bit {
    template<class K, class V, class Hash = HashFunc<K>>
    class unordered_map {
        // 键提取函数：从pair<const K, V>中提取key（first成员）
        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, Hash>::Iterator iterator;
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator 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);
        }

        // 查找元素
        iterator find(const K& key) {
            return _ht.Find(key);
        }

        const_iterator find(const K& key) const {
            return _ht.Find(key);
        }

        // 删除元素
        bool erase(const K& key) {
            return _ht.Erase(key);
        }

        // 重载[]运算符：支持插入和访问value
        V& operator[](const K& key) {
            // 插入键值对（若key不存在则插入，value为默认构造）
            pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
            // 返回value的引用
            return ret.first->second;
        }

    private:
        // 底层哈希表：存储的是pair<const K, V>（key不可修改，value可修改）
        hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
    };
}

4.2 关键设计说明

键提取函数 MapKeyOfT：unordered_map 存储的是 pair<const K, V>，键提取函数返回 pair 的 first 成员（即 key）。
key 不可修改，value 可修改：哈希表存储的是 pair<const K, V>，因此 key 是 const 类型（不可修改），而 value 是普通类型（可修改）。
operator [] 的实现：这是 unordered_map 的常用接口，其核心是复用 insert 函数。当 key 不存在时，insert 会插入一个默认构造的 value；当 key 存在时，直接返回已存在的 value 的引用。这样就实现了 "访问 + 插入" 的双重功能。

4.3 unordered_map 的测试用例

// MyUnorderedMap.h
namespace bit {
    void test_unordered_map() {
        // 测试插入和遍历
        unordered_map<string, string> dict;
        dict.insert({"sort", "排序"});
        dict.insert({"left", "左边"});
        dict.insert({"right", "右边"});
        // 插入重复key
        auto ret = dict.insert({"sort", "排序（重复）"});
        if (ret.second) {
            cout << "插入成功：sort -> " << ret.first->second << endl;
        } else {
            cout << "插入失败（key已存在）：sort -> " << ret.first->second << endl;
        }
        cout << endl;

        // 测试[]运算符
        dict["insert"] = "插入"; // 插入新键值对
        dict["left"] = "左边（修改后）"; // 修改已有value
        cout << "dict[\"insert\"] = " << dict["insert"] << endl;
        cout << "dict[\"left\"] = " << dict["left"] << endl;
        cout << endl;

        // 遍历输出
        cout << "unordered_map遍历结果：" << endl;
        unordered_map<string, string>::iterator it = dict.begin();
        while (it != dict.end()) {
            // it->first += "x"; // 编译报错：key是const类型，不可修改
            it->second += "（已遍历）"; // value可修改
            cout << it->first << " : " << it->second << endl;
            ++it;
        }
        cout << endl;

        // 测试find和erase
        auto find_it = dict.find("right");
        if (find_it != dict.end()) {
            cout << "找到元素：" << find_it->first << " : " << find_it->second << endl;
            dict.erase("right");
            cout << "删除元素right后，遍历结果：" << endl;
            for (auto& kv : dict) {
                cout << kv.first << " : " << kv.second << endl;
            }
        } else {
            cout << "未找到元素right" << endl;
        }
    }
}

测试结果说明：

插入重复 key 会返回失败，保留原有 value。
[ ] 运算符既可以插入新键值对，也可以修改已有 value。
尝试修改 key 会编译报错，保证了 key 的不可修改性；value 可以自由修改。
遍历结果是无序的，符合 unordered_map 的特性。

五、常见问题与优化方向

5.1 常见问题解答

5.1.1 为什么 unordered_set 的元素不可修改？

因为 unordered_set 的元素是 key，而 key 是哈希表组织数据的基础。如果修改了 key，会导致其哈希值发生变化，该元素在哈希表中的位置就会失效，进而导致后续的查找、删除等操作出错。因此，unordered_set 的元素被设计为不可修改（存储为 const K）。

5.1.2 为什么 unordered_map 的 key 不可修改，而 value 可以修改？

原因与 unordered_set 类似：key 是哈希表组织数据的基础，修改 key 会导致哈希值变化，破坏哈希表的结构。而 value 只是附加数据，修改 value 不会影响 key 的哈希值和在哈希表中的位置，因此可以自由修改。

5.1.3 哈希冲突的影响及解决方式？

哈希冲突是指不同的 key 通过哈希函数计算得到相同的桶索引。我们的实现采用链地址法（链表）解决冲突：同一个桶中的多个节点通过链表连接。

哈希冲突过多会导致链表过长，使查找效率从 O (1) 退化到 O (n)。解决这个问题的关键是：

选择合适的哈希函数（减少冲突概率）
合理的扩容机制（负载因子达到 1 时扩容，减少每个桶的平均节点数）

5.1.4 为什么桶大小要选择质数？

质数能减少哈希冲突的概率。因为如果桶大小是合数，某些 key 的哈希值可能会集中在某些桶中（例如桶大小为 4，哈希值为 0、4、8 的 key 都会映射到同一个桶）。而质数的因子较少，能让 key 更均匀地分布在各个桶中，减少冲突。

5.2 优化方向

5.2.1 支持更多 key 类型

目前我们的哈希函数只支持 int 和 string 类型。可以通过模板特化，为更多类型（如 double、自定义类）提供哈希函数。

例如，为 double 类型提供哈希函数特化：

template<>
struct HashFunc<double> {
    size_t operator()(const double& key) {
        // 将double转换为整数后计算哈希值（注意精度问题）
        return (size_t)(key * 1000000000);
    }
};

5.2.2 优化哈希函数

对于 string 类型的哈希函数，我们目前采用的是简单的累加算法。可以使用更高效的哈希算法（如 MurmurHash、FNV 哈希），进一步减少冲突概率。

5.2.3 支持迭代器的 const 修饰

目前我们的迭代器已经支持 const_iterator，但可以进一步完善接口，例如提供 cbegin () 和 cend () 接口，与 STL 标准容器保持一致。

5.2.4 支持批量插入和范围构造

可以为 unordered_map 和 unordered_set 添加范围构造函数和批量插入接口，支持从其他容器（如 vector、list）批量插入元素，提升使用便利性。

总结

通过本文的实现，相信大家不仅掌握了 unordered_map 和 unordered_set 的底层原理，还学会了模板编程、泛型设计、迭代器设计等 C++ 核心技术。这些技术在实际开发中具有广泛的应用，希望能为大家提供帮助。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-17，如有侵权请联系 cloudcommunity@tencent.com 删除

map

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度