C++ unordered系列容器的深度解析与模拟实现

一、unordered系列容器的核心认识

在C++标准库中， unordered系列容器（ unordered_map、 unordered_set及其 multi版本）是基于哈希表实现的关联式容器，与基于红黑树的 map/ set系列形成互补。其核心特性体现在"无序"与"高效"两大维度：

1.1 核心特性与适用场景

无序性：元素的存储顺序由键的哈希值决定，与插入顺序无关，无法通过迭代器实现"按键排序"的遍历。时间复杂度：插入、删除、查找的平均时间复杂度为O(1)，最坏情况为O(n)（取决于哈希冲突的严重程度）。适用场景：适用于对查找效率要求极高，且无需元素有序的场景（如缓存实现、高频查询系统）；若需范围查询或有序遍历，则应选择 map/ set。

1.2 与map/set的关键差异

特性	unordered系列（哈希表）	map/set系列（红黑树）
底层结构	哈希表（桶+链表/红黑树）	红黑树（自平衡二叉搜索树）
元素顺序	无序	按键有序
查找效率	平均O(1)，最坏O(n)	O(logn)
迭代器类型	单向迭代器（forward_iterator）	双向迭代器（bidirectional_iterator）
键的要求	需提供哈希函数+相等比较器	需提供小于比较器（operator<）

1.3 核心接口速览

unordered系列容器的接口与 map/ set类似，但因无序性缺少 lower_bound/ upper_bound等范围查询接口：

插入： insert(key)（ unordered_set）、 insert({key, value})（ unordered_map）查找： find(key)（返回迭代器，未找到则为 end()）删除： erase(key)（删除所有匹配键的元素）容量： size()（元素个数）、 bucket_count()（桶数量）、 load_factor()（负载因子=size/bucket_count）

二、底层哈希表的工作原理

unordered系列的高效性依赖于哈希表的设计，其核心是"将键通过哈希函数映射到连续地址空间（桶），并通过冲突解决机制处理哈希碰撞"。

2.1 哈希表的基本结构

哈希表由三部分组成：

桶数组（Bucket Array）：连续的内存空间，每个元素（桶）是指向链表/红黑树的指针，用于存储哈希值相同的元素。节点（Node）：存储键、值（或仅键）及指向下一节点的指针，构成链表/红黑树。哈希函数（Hash Function）：将键映射为桶数组索引（ index = hash(key) % bucket_count）。

2.2 哈希冲突的解决：链地址法

当不同的键通过哈希函数映射到同一桶索引时，产生哈希冲突。 unordered系列采用链地址法解决冲突：将哈希值相同的元素存储在同一桶对应的链表（或红黑树）中。

现代实现（如libstdc++）会对长链表进行优化：当链表长度超过阈值（通常为8）时，自动转为红黑树，将最坏情况下的查找时间从O(n)优化为O(logn)。

2.3 负载因子与扩容机制

负载因子：衡量哈希表拥挤程度的指标（ load_factor = size / bucket_count）。负载因子过高会导致冲突加剧，降低效率。扩容触发：当负载因子超过阈值（默认1.0）时，哈希表会扩容（通常将桶数量翻倍为下一个质数），并将所有元素重新哈希（rehash）到新桶中。质数桶数量：桶数量通常为质数（如17、37、79），可减少哈希值对桶数量取模时的冲突概率。

三、模拟实现unordered_map

以下基于哈希表原理，模拟实现一个简化版 unordered_map（支持基本插入、查找、删除操作）。

3.1 核心结构设计

3.1.1 节点结构

每个节点存储键、值及下一节点指针：

template <class Key, class Value>
struct HashNode {
    pair<Key, Value> _kv;       // 键值对
    HashNode<Key, Value>* _next; // 下一个节点

    HashNode(const pair<Key, Value>& kv)
        : _kv(kv)
        , _next(nullptr)
    {}
};

3.1.2 哈希表主体

哈希表需包含：桶数组、元素个数、哈希函数、键比较器等核心成员：

template <class Key, class Value, class Hash = hash<Key>, class KeyEqual = equal_to<Key>>
class UnorderedMap {
public:
    using Node = HashNode<Key, Value>;

    // 迭代器类（单向迭代器）
    struct iterator {
        Node* _node;               // 当前节点
        const UnorderedMap* _ht;   // 指向哈希表（用于遍历下一个桶）

        iterator(Node* node, const UnorderedMap* ht)
            : _node(node)
            , _ht(ht)
        {}

        // 解引用
        pair<Key, Value>& operator*() { return _node->_kv; }
        pair<Key, Value>* operator->() { return &_node->_kv; }

        // 迭代器++（关键：遍历完当前桶后找下一个非空桶）
        iterator& operator++() {
            if (_node->_next) {
                _node = _node->_next; // 同一桶内的下一个节点
            } else {
                // 找下一个非空桶
                size_t index = _ht->HashFunc(_node->_kv.first);
                index++; // 从当前桶的下一个开始
                while (index < _ht->_buckets.size()) {
                    if (_ht->_buckets[index]) {
                        _node = _ht->_buckets[index];
                        return *this;
                    }
                    index++;
                }
                // 所有桶遍历完毕
                _node = nullptr;
            }
            return *this;
        }

        bool operator!=(const iterator& it) const {
            return _node != it._node;
        }
    };

private:
    vector<Node*> _buckets;    // 桶数组
    size_t _size = 0;          // 元素个数
    Hash _hash;                // 哈希函数对象
    KeyEqual _keyEqual;        // 键比较对象（判断键是否相等）
};

3.2 核心操作实现

3.2.1 哈希函数与桶索引计算

哈希函数将键映射为桶索引，需处理哈希值可能为负数的情况（如对整数取模）：

private:
    // 计算哈希值并映射到桶索引
    size_t HashFunc(const Key& key) const {
        // 对哈希值取模，确保索引为非负数（处理负数哈希值）
        return _hash(key) % _buckets.size();
    }

3.2.2 插入操作

插入流程：

检查负载因子，若超过阈值则扩容；计算键的哈希值，定位到目标桶；遍历桶内链表，若键已存在则插入失败（ unordered_map不允许重复键）；否则在链表头部插入新节点，更新元素个数。

public:
    pair<iterator, bool> insert(const pair<Key, Value>& kv) {
        // 1. 检查扩容（负载因子>1.0时扩容）
        if (_size > _buckets.size()) {
            Reserve(_buckets.size() == 0 ? 10 : _buckets.size() * 2);
        }

        // 2. 计算桶索引
        size_t index = HashFunc(kv.first);

        // 3. 检查键是否已存在
        Node* cur = _buckets[index];
        while (cur) {
            if (_keyEqual(cur->_kv.first, kv.first)) {
                return {iterator(cur, this), false}; // 键已存在，插入失败
            }
            cur = cur->_next;
        }

        // 4. 插入新节点（头插法）
        Node* newNode = new Node(kv);
        newNode->_next = _buckets[index];
        _buckets[index] = newNode;
        _size++;

        return {iterator(newNode, this), true};
    }

3.2.3 扩容与重新哈希（Reserve）

扩容需重新分配桶数组，并将旧桶中所有元素重新哈希到新桶：

public:
    void Reserve(size_t n) {
        if (n <= _buckets.size()) return;

        // 1. 创建新桶数组（大小为n，取最近的质数更佳）
        vector<Node*> newBuckets(n, nullptr);

        // 2. 将旧桶元素重新哈希到新桶
        for (size_t i = 0; i < _buckets.size(); i++) {
            Node* cur = _buckets[i];
            while (cur) {
                Node* next = cur->_next; // 保存下一个节点

                // 计算在新桶中的索引
                size_t newIndex = _hash(cur->_kv.first) % newBuckets.size();
                // 插入新桶（头插）
                cur->_next = newBuckets[newIndex];
                newBuckets[newIndex] = cur;

                cur = next;
            }
            _buckets[i] = nullptr; // 旧桶清空
        }

        // 3. 替换桶数组
        _buckets.swap(newBuckets);
    }

3.2.4 查找操作

查找流程：计算键的哈希值定位到桶，遍历桶内链表匹配键：

public:
    iterator find(const Key& key) {
        if (_buckets.empty()) return end();

        size_t index = HashFunc(key);
        Node* cur = _buckets[index];
        while (cur) {
            if (_keyEqual(cur->_kv.first, key)) {
                return iterator(cur, this);
            }
            cur = cur->_next;
        }
        return end();
    }

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

3.2.5 删除操作

删除流程：定位到桶，遍历链表找到目标节点，调整指针并释放内存：

public:
    size_t erase(const Key& key) {
        if (_buckets.empty()) return 0;

        size_t index = HashFunc(key);
        Node* cur = _buckets[index];
        Node* prev = nullptr;

        while (cur) {
            if (_keyEqual(cur->_kv.first, key)) {
                // 找到节点，删除
                if (prev == nullptr) {
                    // 头节点
                    _buckets[index] = cur->_next;
                } else {
                    prev->_next = cur->_next;
                }
                delete cur;
                _size--;
                return 1;
            }
            prev = cur;
            cur = cur->_next;
        }
        return 0; // 未找到
    }

3.3 构造与析构函数

需确保资源正确释放：

public:
    // 构造函数（初始化桶数组）
    UnorderedMap() {
        _buckets.resize(10, nullptr); // 初始桶数量为10
    }

    // 析构函数（释放所有节点和桶）
    ~UnorderedMap() {
        for (size_t i = 0; i < _buckets.size(); i++) {
            Node* cur = _buckets[i];
            while (cur) {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _buckets[i] = nullptr;
        }
    }

四、unordered_set的模拟实现

unordered_set与 unordered_map的核心差异在于： unordered_set的"值"即为"键"，且不允许重复。因此可复用哈希表逻辑，仅需调整节点存储内容（仅存键）。

简化实现框架：

template <class Key, class Hash = hash<Key>, class KeyEqual = equal_to<Key>>
class UnorderedSet {
private:
    // 节点仅存储键
    struct Node {
        Key _key;
        Node* _next;
        Node(const Key& key) : _key(key), _next(nullptr) {}
    };

    // 哈希表主体（逻辑与UnorderedMap类似，仅操作键而非键值对）
    vector<Node*> _buckets;
    size_t _size = 0;
    Hash _hash;
    KeyEqual _keyEqual;

public:
    // 插入（仅插入键，不允许重复）
    pair<iterator, bool> insert(const Key& key) {
        // 逻辑与UnorderedMap::insert类似，仅处理键
    }

    // 查找、删除等接口（略，与map类似）
};

五、自定义类型的哈希支持

标准库的 hash模板仅支持内置类型（如 int、 string），对于自定义类型，需手动提供哈希函数：

5.1 方法一：特化hash模板

struct Person {
    string name;
    int age;
};

// 特化hash<Person>
namespace std {
    template <>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            // 组合name和age的哈希值（简单实现）
            return hash<string>()(p.name) ^ hash<int>()(p.age);
        }
    };
}

5.2 方法二：自定义哈希函数类

struct PersonHash {
    size_t operator()(const Person& p) const {
        return hash<string>()(p.name) + hash<int>()(p.age);
    }
};

// 使用时指定哈希函数
UnorderedMap<Person, int, PersonHash> map;

六、总结与扩展

unordered系列容器的高效性源于哈希表的O(1)平均复杂度，但需关注哈希函数设计与冲突处理。模拟实现过程中，核心难点在于：

迭代器的正确遍历（跨桶跳转逻辑）；扩容时的重新哈希（确保元素正确映射到新桶）；哈希冲突的优化（链表转红黑树等高级策略）。

实际开发中，需根据场景选择容器：追求无序高效查询用 unordered系列，需有序或范围查询用 map/ set系列。深入理解底层原理，不仅能提升容器使用效率，更能为自定义数据结构设计提供思路。