当前位置： 代码网 > it编程>编程语言>C/C++ > C++中 unordered_map 与unordered_set的实现

C++中 unordered_map 与unordered_set的实现

2026年09月07日 • C/C++ •我要评论
一、 容器简介在 c++98 中，stl 提供了底层为红黑树结构的关联式容器，查询效率为 o ( log ⁡ 2 n ) o(\log_2 n) o(log2​n)。为了在海量数据下实现 o (

一、 容器简介

在 c++98 中，stl 提供了底层为红黑树结构的关联式容器，查询效率为 o ( log ⁡ 2 n ) o(\log_2 n) o(log2​n)。为了在海量数据下实现 o ( 1 ) o(1) o(1) 的常数级查找效率，c++11 引入了 4 个 unordered 系列关联式容器。

1. unordered_map

  • 它是存储 <key, value> 键值对的关联式容器，允许通过 keys 快速索引到对应的 value。
  • 在内部，容器没有对键值对按照任何特定的顺序排序。
  • 容器将相同哈希值的键值对放在相同的桶中，以此实现极致的查找速度。
  • 由于底层单链表结构限制，它的迭代器至少是前向迭代器（不支持反向遍历）。

2. unordered_set

  • 它是仅存储唯一关键码（key）的关联式容器，是处理海量数据去重与极速存在性校验的绝佳利器。
  • 与 unordered_map 机制相同，其内部元素同样无序，依靠哈希函数将关键码映射并存储到对应的哈希桶中。
  • 为了防止底层哈希映射位置被破坏，容器中的元素不能被修改（其迭代器本质上是 const 迭代器）。
  • 同样仅支持单向迭代，其插入、查找、删除的平均时间复杂度均能达到常数级别 o ( 1 ) o(1) o(1)。

二、 核心接口与使用示例

1. 容量与基础查询

  • empty()：检测容器是否为空。
  • size()：获取容器的有效元素个数。
unordered_map<string, int> dict;
dict.insert({"apple", 1});
bool isempty = dict.empty(); // 返回 false
size_t count = dict.size();  // 返回 1

2. 元素查找

  • find(const k& key)：返回 key 在哈希桶中的位置迭代器，若未找到则返回 end()。
  • count(const k& key)：返回关键码为 key 的键值对个数。因容器中 key 不可重复，故返回值最大为 1，常用于快速判断元素是否存在。
unordered_set<int> us = {1, 2, 3};

// 使用 find 查找
auto it = us.find(2);
if (it != us.end()) {
    cout << "找到了: " << *it << endl;
}

// 使用 count 判断存在性
if (us.count(4) == 0) {
    cout << "元素 4 不存在" << endl;
}

3. operator[] 的特殊机制

unordered_map 提供了 operator[]，其实际调用了底层的插入操作。用参数 key 与默认值构造键值对进行插入：

  • 若 key 不在容器中，插入成功并返回默认值的引用。
  • 若 key 已存在，插入失败，但会返回原来 key 对应的 value 引用。
unordered_map<string, string> dict;
dict["insert"] = "插入"; // key不存在，插入 {"insert", ""}，随后将其 value 修改为 "插入"
dict["insert"] = "覆盖"; // key已存在，直接返回 value 引用并修改为 "覆盖"

三、 面试题实战

实战 1：

重复 n 次的元素

给定一个数组，找出一个出现了特定次数的元素。利用 unordered_map 统计频次。

class solution {
public:
    int repeatedntimes(vector<int>& a) {
        size_t n = a.size() / 2;
        unordered_map<int, int> m;
        for (auto e : a) {
            m[e]++; // 元素不存在则初始化为0后加1，存在则直接加1
        }
        for (auto& e : m) {
            if (e.second == n) return e.first;
        }
        return -1;
    }
};

实战 2：

两个数组的交集

求两个数组的交集并去重。利用 unordered_set 实现去重与快速匹配。

class solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s1;
        for (auto e : nums1) s1.insert(e);
            
        unordered_set<int> s2;
        for (auto e : nums2) s2.insert(e);
            
        vector<int> vret;
        for (auto e : s1) {
            if (s2.find(e) != s2.end()) {
                vret.push_back(e);
            }
        }
        return vret;
    }
};

四、 哈希表底层原理

哈希表通过哈希函数将元素的关键码映射为存储位置。常见的哈希函数有除留余数法：hash(key) = key % capacity。

当不同关键字计算出相同的哈希地址时，即发生哈希冲突。解决冲突的方法有两种：

  1. 闭散列（开放定址法）：寻找下一个空位置存放冲突元素（如线性探测）。其载荷因子必须严格限制在 0.7 - 0.8 以下，容易产生数据堆积，空间利用率低。
  2. 开散列（链地址法 / 哈希桶）：将哈希地址相同的元素归于同一个桶，通过单链表链接。stl 主要采用开散列，其载荷因子可以达到 1.0，空间利用率和查找效率更优。

五、 底层完整实现

以下为基于开散列（哈希桶）完整封装 unordered_map 和 unordered_set 的核心代码。

1. 基础组件与哈希函数

#pragma once
#include <iostream>
#include <vector>
#include <string>
using namespace std;

template<class k>
struct hashfunc {
    size_t operator()(const k& key) { return (size_t)key; }
};

// 针对 string 的哈希特化 (bkdr hash)
template<>
struct hashfunc<string> {
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto e : key) {
            hash *= 31;
            hash += e;
        }
        return hash;
    }
};

2. 哈希桶与迭代器实现

namespace hash_bucket
{
    template<class t>
    struct hashnode {
        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 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) { return _node != s._node; }

        self& operator++() {
            if (_node->_next) {
                _node = _node->_next;
            } else {
                keyoft kot;
                hash hs;
                size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
                ++hashi;
                while (hashi < _pht->_tables.size()) {
                    if (_pht->_tables[hashi]) break;
                    ++hashi;
                }
                if (hashi == _pht->_tables.size()) _node = nullptr;
                else _node = _pht->_tables[hashi];
            }
            return *this;
        }
    };

    // 哈希表主体
    template<class k, class t, class keyoft, class hash>
    class hashtable {
        template<class k, class t, class ptr, class ref, class keyoft, class hash>
        friend struct htiterator;

        typedef hashnode<t> node;
    public:
        typedef htiterator<k, t, t*, t&, keyoft, hash> iterator;
        typedef htiterator<k, t, const t*, const t&, keyoft, hash> constiterator;

        hashtable() { _tables.resize(10, nullptr); }
        
        ~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 begin() {
            if (_n == 0) return end();
            for (size_t i = 0; i < _tables.size(); i++) {
                if (_tables[i]) return iterator(_tables[i], this);
            }
            return end();
        }
        iterator end() { return iterator(nullptr, this); }

        pair<iterator, bool> insert(const t& data) {
            keyoft kot;
            iterator it = find(kot(data));
            if (it != end()) return make_pair(it, false);

            hash hs;
            if (_n == _tables.size()) {
                vector<node*> newtables(_tables.size() * 2, nullptr);
                for (size_t i = 0; i < _tables.size(); i++) {
                    node* cur = _tables[i];
                    while (cur) {
                        node* next = cur->_next;
                        size_t hashi = hs(kot(cur->_data)) % newtables.size();
                        cur->_next = newtables[hashi];
                        newtables[hashi] = cur;
                        cur = next;
                    }
                    _tables[i] = nullptr;
                }
                _tables.swap(newtables);
            }

            size_t hashi = hs(kot(data)) % _tables.size();
            node* newnode = new node(data);
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;
            ++_n;
            return make_pair(iterator(newnode, this), true);
        }

        iterator find(const k& key) {
            keyoft kot;
            hash hs;
            size_t hashi = hs(key) % _tables.size();
            node* cur = _tables[hashi];
            while (cur) {
                if (kot(cur->_data) == key) return iterator(cur, this);
                cur = cur->_next;
            }
            return end();
        }

        bool erase(const k& key) {
            keyoft kot;
            hash hs;
            size_t hashi = hs(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;
                    --_n;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            return false;
        }

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

3. 封装 unordered_set

namespace bit
{
    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, 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> insert(const k& key) { return _ht.insert(key); }
        iterator find(const k& key) { return _ht.find(key); }
        bool erase(const k& key) { return _ht.erase(key); }

    private:
        hash_bucket::hashtable<k, const k, setkeyoft, hash> _ht;
    };
}

4. 封装 unordered_map

namespace bit
{
    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>::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); }

        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); }
        bool erase(const k& key) { return _ht.erase(key); }

    private:
        hash_bucket::hashtable<k, pair<const k, v>, mapkeyoft, hash> _ht;
    };
}

六、 扩展应用

在海量数据处理场景下，常规哈希表会面临内存不足的问题。此时可以使用哈希思想的延伸结构：

  1. 位图 (bitmap)：使用二进制比特位代表数据是否存在，适用于海量整型数据的快速查找与去重。
  2. 布隆过滤器 (bloom filter)：将哈希函数与位图结合，通过多个哈希函数将一个数据映射到位图中。适用于容忍一定误判率的海量字符串查重过滤场景，空间优势极大。

七、 总结

  • 若业务场景需要数据保持特定顺序输出，应选择基于红黑树的 map/set。
  • 若核心需求为极限速度的增删查改，优先选用 unordered_map/unordered_set。
  • stl 的底层通过仿函数提取器（keyoft）实现了 hashtable 泛型代码的复用，理解这一点有助于掌握 c++ 的泛型编程逻辑。
  • 在使用 operator[] 时需明确其底层包含插入逻辑，仅查询判断时应优先使用 find() 或 count()。

到此这篇关于c++中 unordered_map 与unordered_set的实现的文章就介绍到这了,更多相关c++中 unordered_map 与unordered_set内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！

赞 (0)

相关文章:

版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站仅提供信息存储服务，不拥有所有权，不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 2386932994@qq.com 举报，一经查实将立刻删除。

发表评论

验证码：
最近更新的文章
推荐阅读
大家感兴趣的文章
Copyright © 2017-2026  代码网 保留所有权利. 粤ICP备2024248653号
站长QQ:2386932994 | 联系邮箱：2386932994@qq.com