C++哈希表以及unordered_set与unordered_map的封装

2401_87151858

1080人浏览 · 2025-11-23 22:27:41

2401_87151858 · 2025-11-23 22:27:41 发布

引入

平衡树的不足：每次查找元素时，要不断地进行比较，其时复杂的为O(logN)。有没有这样一种方式，可以不用比较，直接就能知道它的位置呢？
如果让元素跟其存储位置建立映射的的关系，那我们就能很快的找到该元素了，插入元素就可以直接找到该元素的存储位置进行存放，删除元素也是类似
如何建立映射关系呢？这就用到了哈希函数

1. 直接定址法

关键字为key的元素直接被映射到下标为key的位置。 $f (k ey) = k ey$
在这里插入图片描述
即学号为i的学生，其信息存储在a[i]（这里的学号即为每个元素的关键字key）。该方法适用于数据范围较集中的情况。（如果关键字分别为{1, 2, 3, 4, 9, 10, 1000000}，直接定址法就要开长度为1000000的数组，空间利用率极低）

2. 除留余数法

关键字为key的元素会被映射到下标为key % n的位置，n是数组的长度 (因为key % n < n，这样就能保证映射的位置不会越界)。 $\ \% \ n$
在这里插入图片描述
这样可以把数据映射到一段集中的区域。
但是如果再插入一个key为10数据呢？由于10 % 7 == 3，而下标为3的位置已经放了key为31数据，这就出现了冲突，即关键字不同的数据映射到了同一个位置。如何解决？方法有很多，这里只介绍最常用的。

3. 拉链法

把映射到同一位置的元素用链表给串起来
在这里插入图片描述
上图的数据结构就是个哈希表（其实就是个链表数组），数组长度称为表长。若要查找10，则直接找到其存储位置10 % 7 = 3，即在下标为3的链表中查找即可。

哈希表查找的时间复杂度与链表的长度有关，如何减少链表长度？

减少冲突。有数学研究表明：数组长度取成质数时，发生冲突的概率会更小。
哈希表开大一点。如果表长只有7，而要插入70000个不同的数据，那平均下来链表长度大概为10000，查找效率也会偏低。这种情况其实就是哈希表太小了！如何解决？这里我们引入一个负载因子的概念：
$\frac{表中的元素数量}{表长}$
负载因子一般在0.7 ~ 0.8以下，否则就需要对表进行扩容。

理论部分讲解完毕，接下来上代码！

4. 基础操作

1). 节点定义

// 哈希表的节点（单链表）
template<class T>
struct hash_table_node
{
    T _val;
    hash_table_node* _next;

    hash_table_node(const T& x = T(), hash_table_node* next = nullptr)
        :_val(x)
        ,_next(next)
    {}
};

// 哈希表
template<class T>
class HashTable
{
    typedef hash_table_node<T> node;
    vector<node*> _h;   // 链表数组
    size_t _size = 0;   // 表中的元素个数
    
public:
    HashTable(int n = 17)
        :_h(n)		// 初始时，表长设为17
    {}
};

2). 查找

    node* find(const T& x)
    {
        int pos = x % _h.size();	// 找到x应当存储的下标
        for(node* i = _h[pos]; i; i = i->_next)
            if(i->_val == x)
                return i;
        return nullptr; // 未找到返回空
    }

3). 插入

    bool insert(const T& x)
    {
        // 表中已经有x了，无需重复插入
        if(find(x)) return false;

        int pos = x % _h.size(); // 找到x应当存储的下标
        // 头插
        node* cur = new node(x);
        cur->_next = _h[pos];
        _h[pos] = cur;
        _size++;
        return true;
    }

再引入负载因子判断是否扩容

    bool insert(const T& x)
    {
        // 表中已经有x了，无需重复插入
        if(find(x)) return false;

        // 引入负载因子，适当扩容
        if(_size >= 0.7 * _h.size())
            reserve(_h.size() + 1);	// 扩容：新容量变为 >= _h.size() + 1的最小质数

        int pos = x % _h.size(); // 找到x应当存储的下标
        // 头插
        node* cur = new node(x);
        cur->_next = _h[pos];
        _h[pos] = cur;
        _size++;
        return true;
    }

    // 扩容：新容量变为 >= n的最小质数
    void reserve(size_t n)
    {
        if(_h.size() >= n) return;

        n = get_next_prime(n); // 找 >= n的最小质数
        vector<node*> new_h(n);
        for(int i = 0; i < _h.size(); i++)
        {
            if(_h[i])
            {
                // 为了提高效率，直接把原哈希表的节点移动到新表中
                node* j = _h[i];
                while(j)
                {
                    int pos = j->_val % new_h.size();
                    node* next = j->_next;
                    j->_next = new_h[pos];
                    new_h[pos] = j;
                    j = next;
                }
            }
        }
        _h.swap(new_h);
    }

    // 返回 >= n的最小质数
    size_t get_next_prime(size_t n)
    {
        static size_t p[29] =
        {   17,
            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
        };
        if(n > p[28]) return p[28];
        return *lower_bound(p, p + 29, n); // 二分查找，返回p数组中>=n的最小数的迭代器。#include<algorithm>
    }

4). 删除

    bool erase(const T& x)
    {
        int pos = x % _h.size();
        for(node* i = _h[pos], *pre = nullptr; i; pre = i, i = i->_next)
        {
            if(i->_val == x)
            {
                if(!pre)    // 这里说明被删除的元素是头节点
                    _h[pos] = _h[pos]->_next;
                else
                    pre->_next = i->_next;
                delete i;
                _size--;
                return true;
            }
        }
        return false;
    }

5). 测试

void test01()
{
    HashTable<int> h;
    int a[] = { 19,30,5,36,13,20,21,12,24,25,96 };
    for(auto e : a)
        h.insert(e);
    for(auto e : a)
        cout << h.find(e)->_val << ' ';
    cout << endl;
    cout << h.insert(19) << endl;
    cout << h.erase(19) << endl;
    cout << h.erase(30) << endl;
    for(auto e : a)
    {
        if(h.find(e))
            cout << h.find(e)->_val << ' ';
    }
}

运行结果
在这里插入图片描述

好了哈希表的基础操作已经搞定，下面开始进一步封装

5. 迭代器

封装节点指针，然后通过运算符重载修改其解引用、++等行为
在这里插入图片描述

// 普通迭代器：封装node*
template<class T>
struct HashTable_iterator
{
    typedef hash_table_node<T> node;
    node* _pnode;               // 哈希表节点指针
    const vector<node*>* _ph;   // 哈希表指针
    size_t _pos;                // 该节点在哈希表的位置

    HashTable_iterator(node* pn = nullptr, const vector<node*>* ph = nullptr, size_t pos = 0)
        :_pnode(pn)
        ,_ph(ph)
        ,_pos(pos)
    {}

    typedef HashTable_iterator Self;
    // 前置++
    Self& operator++()
    {
        assert(_pnode);
        if(_pnode->_next)
            _pnode = _pnode->_next;
        else{
            _pos++;
            while(_pos < _ph->size() && !(*_ph)[_pos])
                _pos++;
            if(_pos < _ph->size())
                _pnode = (*_ph)[_pos];
            else
                _pnode = nullptr;
        }
        return *this;
    }
    // 后置++
    Self operator++(int)
    {
        Self tmp(*this);
        ++(*this);
        return tmp;
    }
    
	// 注意：unordered_set与unordered_map的迭代器都为单向迭代器，不支持--
	
    T& operator*() { return _pnode->_val; }
    T* operator->() { return &_pnode->_val; }
    bool operator!= (const Self& it) const
    { return _pnode != it._pnode; }
    bool operator== (const Self& it) const
    { return _pnode == it._pnode; }
};

// const迭代器：封装const node*
template<class T>
struct HashTable_const_iterator
{
    typedef hash_table_node<T> node;
    const node* _pnode;       // 哈希表节点指针
    const vector<node*>* _ph; // 哈希表指针
    size_t _pos;              // 该节点在哈希表的位置

    HashTable_const_iterator(const node* pn = nullptr, const vector<node*>* ph = nullptr, size_t pos = 0)
        :_pnode(pn)
        ,_ph(ph)
        ,_pos(pos)
    {}

    // 可能会用普通迭代器构造constdiedaiq
    HashTable_const_iterator(const HashTable_iterator<T>& it)
        :_pnode(it._pnode)
        ,_ph(it._ph)
        ,_pos(it._pos)
    {}

    typedef HashTable_const_iterator Self;
    // 前置++
    Self& operator++()
    {
        assert(_pnode);
        if(_pnode->_next)
            _pnode = _pnode->_next;
        else{
            _pos++;
            while(_pos < _ph->size() && !(*_ph)[_pos])
                _pos++;
            if(_pos < _ph->size())
                _pnode = (*_ph)[_pos];
            else
                _pnode = nullptr;
        }
        return *this;
    }
    // 后置++
    Self operator++(int)
    {
        Self tmp(*this);
        ++(*this);
        return tmp;
    }
    const T& operator*() { return _pnode->_val; }
    const T* operator->() { return &_pnode->_val; }
    bool operator!= (const Self& it) const
    { return _pnode != it._pnode; }
    bool operator== (const Self& it) const
    { return _pnode == it._pnode; }
};

然后把哈希表的begin与end实现一下

template<class T>
class HashTable
{
	// ...省略前面的代码
public:
    typedef HashTable_iterator<T> iterator;
    typedef HashTable_const_iterator<T> const_iterator;
    iterator begin()
    {
        if(!_size) return end();   
        for(int i = 0; i < _h.size(); i++)
            if(_h[i])
                return iterator(_h[i], &_h, i);
        return end();   // 按理说不会走到这里，但有些编译器会强制要求有返回值
    }
    iterator end() 
    { 
        return iterator(nullptr, &_h, -1); 
        //注意不要写成：{nullptr, &_h, -1}; C++11开始，对列表初始化，禁止窄化转换（有符号负数→无符号）
    }

    const_iterator begin() const
    {
        if(!_size) return end();
        for(int i = 0; i < _h.size(); i++)
            if(_h[i])
                return const_iterator(_h[i], &_h, i);
        return end();
    }
    const_iterator end() const 
    { 
        return const_iterator(nullptr, &_h, 0); 
    }
};

测试一下

void test02()
{
	HashTable<int> h;
    int a[] = { 19,30,5,36,13,20,21,12,24,25,96 };
    for(auto e : a)
        h.insert(e);
    for(auto e : h)	// 提供迭代器后就可以用范围for了
    	cout << e << ' ';
}

运行结果
在这里插入图片描述

然后把find与insert的返回值修改一下

    // 找到了返回值为x的迭代器，否则返回end()
    iterator find(const T& x)
    {
        int pos = x % _h.size();	// 找到x应当存储的下标
        for(node* i = _h[pos]; i; i = i->_next)
            if(i->_val == x)
                return iterator(i, &_h, pos);
        return end(); // 未找到返回空
    }
    
    // 顺便提供const版本的find
    const_iterator find(const T& x) const
    {
        int pos = x % _h.size();
        for(const node* i = _h[pos]; i; i = i->_next)
            if(i->_val == x)
                return const_iterator(i, &_h, pos);
        return end();
    }
    
    // 成功插入返回：<值为x的迭代器, true>; 否则返回<值为x的迭代器, false>
    pair<iterator, bool> insert(const T& x)
    {
        // 表中已经有x了，无需重复插入
        iterator it = find(x);
        if(it != end()) return {it, false};

        // 引入负载因子，适当扩容
        if(_size >= 0.7 * _h.size())
            reserve(_h.size() + 1);

        int pos = x % _h.size(); // 找到x应当存储的下标
        // 头插
        node* cur = new node(x);
        cur->_next = _h[pos];
        _h[pos] = cur;
        _size++;
        return {iterator(cur, &_h, pos), true};
    }

6. 构造、析构、拷贝构造、赋值重载等

	// 默认构造
    HashTable(int n = 17)
        :_h(get_next_prime(n))	// 这里重新修正一下
    {}

    // 列表构造
    HashTable(initializer_list<T> il)
    {
        reserve(ceil(il.size() / 0.7)); // 尽量不要超过负载因子. ceil是向上取整。#include<cmath>
        for(const auto& e : il)
            insert(e);
    }
    // 析构
    ~HashTable() { clear(); }
    void clear()
    {
        for(const node* i : _h)
            while(i)
            {
                node* next = i->_next;
                delete i;
                i = next;
            }
        _size = 0;
    }
    // 拷贝构造
    HashTable(const HashTable& ht)
    {
        _h.resize(ht._h.size());
        for(auto& e : ht)
            insert(e);
    }

    void swap(HashTable& ht)
    {
        _h.swap(ht._h);
        std::swap(_size, ht._size);
    }

    // 赋值重载
    HashTable& operator= (const HashTable& ht)
    {
        if(this != &ht)
        {
            HashTable tmp(ht);
            swap(tmp);
        }
        return *this;
    }
	// 求哈希表中元素个数
    size_t size() const { return  _size; }
    // 判断是否为空
    bool empty() const { return !_size; }

好了，哈希表的核心操作框架已经介绍完毕。接下来引入泛型：封装unordered_set与unordered_map（这两个容器的用法与set、map类似，参考上篇 set与map的用法。不过unordered_set与unordered_map不支持lower_bound与upper_bound操作）

7. 泛型

上述代码有几个的问题：

问题1

元素x的映射的位置为x % _h.size()，如果x为负数呢？这就越界了啊！如果x为浮点数或者字符串呢？会编译错误啊！为此我们需要把x处理成非负整数。

// 将元素x处理成非负整数
template<class T>
struct HashFunc
{
    size_t operator() (const T& x) const
    {
        return (size_t)x;
    }
};

// 特化string版本
template<>
struct HashFunc<string>
{
    size_t operator() (const string& x) const
    {
    	// 把string类型看作131进制的数（有相关研究表明，这样哈希冲突较少）
    	// 例如x = "abc"
    	// 则其key = 'a'*131^2 + 'b'*131^1 + 'c'*131^0
        size_t res = 0;
        for(auto& c : x)
            res = res * 131 + c;
        return res;
    }
};

然后再把哈希表的涉及求x的存储下标的地方再修改一下

// 新增模板参数Hash，用于把元素转换为非负整数
template<class T, class Hash = HashFunc<T>>
class HashTable
{
    typedef hash_table_node<T> node;
    vector<node*> _h;
    size_t _size = 0;
    
    // 求x的哈希值（将x转换为非负整数）
    size_t get_hash(const T& x) const
    {
        static Hash f;
        return f(x);
    }
public:
	// ... 省略其他代码
	
    iterator find(const T& x)
    {
        // 先把x转化成非负整数，再找到其存储的下标
        int pos = get_hash(x) % _h.size();	
        for(node* i = _h[pos]; i; i = i->_next)
            if(i->_val == x)
                return iterator(i, &_h, pos);
        return end();
    }
    
    // const版本的find也是类似

    // 成功插入返回：<值为x的迭代器, true>; 否则返回<值为x的迭代器, false>
    pair<iterator, bool> insert(const T& x)
    {
        iterator it = find(x);
        if(it != end()) return {it, false};

        if(_size >= 0.7 * _h.size())
            reserve(_h.size() + 1);

        // 先把x转化成非负整数，再找到其存储的下标
        int pos = get_hash(x) % _h.size();
        node* cur = new node(x);
        cur->_next = _h[pos];
        _h[pos] = cur;
        _size++;
        return {iterator(cur, &_h, pos), true};
    }

    // 让新容量变为 >= n的最小质数
    void reserve(size_t n)
    {
        if(_h.size() >= n) return;
        n = get_next_prime(n);
        vector<node*> new_h(n);
        for(int i = 0; i < _h.size(); i++)
        {
            if(_h[i])
            {
                node* j = _h[i];
                while(j)
                {
                    // 先把j->_val转化成非负整数，再找到其存储的下标
                    int pos = get_hash(j->_val) % new_h.size();
                    node* next = j->_next;
                    j->_next = new_h[pos];
                    new_h[pos] = j;
                    j = next;
                }
            }
        }
        _h.swap(new_h);
    }
    
    bool erase(const T& x)
    {
        // 先把x转化成非负整数，再找到其存储的下标
        int pos = get_hash(x) % _h.size();
        for(node* i = _h[pos], *pre = nullptr; i; pre = i, i = i->_next)
        {
            if(i->_val == x)
            {
                if(!pre)
                    _h[pos] = _h[pos]->_next;
                else
                    pre->_next = i->_next;
                delete i;
                _size--;
                return true;
            }
        }
        return false;
    }

测试一下

void test03()
{
	HashTable<string> h;
	string s[] = { "left", "right", "sort", "aa", "a", "bb", "aaa", "a" };
	for(auto& e : s) h.insert(e);
	for(auto& e : h)
		cout << e << ' ';
	cout << endl;
	if(h.find("yyyyyy") != h.end()) cout << *h.find("yyyyyy") << endl;
	else cout << "找不到" << endl;
	
	h.erase("sort");
	h.erase("aaa");
	for(auto& e : h)
		cout << e << ' ';
}

运行结果
在这里插入图片描述

问题2

先看一段代码

void test04()
{
	HashTable<int> h = { 1,2,3,4,5 };
	for(auto& e : h)
	{
		cout << e << ' ';
		e += 10;	// 竟然可以修改哈希表里面的数据！！！ 
	}
	cout << endl;
	
	int a[] = { 1,2,3,4,5 };
	for(auto e : a)
	{
		if(h.find(e) != h.end())
			cout << *h.find(e) << ' ';
		else
			cout << "未找到" << ' ';
	}
}

运行结果
在这里插入图片描述

竟然能通过迭代器修改数据！这会破坏元素与其存储位置的映射关系！为此需要把哈希表进一步封装为unordered_set与unordered_map。
但是修改后的上述代码只能封装unordered_set（key模型），由于unordered_map在unordered_set之上又对每个key绑定了数据value，即unordered_map存储pair<key, value>，且查找元素是按key而非pair<key, value>，所以我们还需引入额外模板参数

template<class K,		    // 元素的关键字key的类型
		 class T,		    // 实际存储的元素类型
		 class ExtractKey,	// 提取元素的关键字
		 class Hash>	    // 将key处理成非负整数
class HashTable
{
    typedef hash_table_node<T> node;
    vector<node*> _h;   // 链表数组
    size_t _size = 0;   // 表中的元素个数
    
    // 提取元素的 key
    const K& get_key(const T& x) const
    {
        static ExtractKey f;
        return f(x);
    }
    // 将key转化成非负整数（计算key的哈希值）
    size_t get_hash(const K& key) const
    {
        static Hash f;
        return f(key);
    }
    
    // ... 省略其他代码
};

然后再把求元素的存储下标相关的代码修改一下

    // 参数应当是K类型。找到了关键字为key的迭代器，否则返回end()
    iterator find(const K& key)
    {
        // 先把key转化成非负整数，再找到其存储的下标
        int pos = get_hash(key) % _h.size();	
        for(node* i = _h[pos]; i; i = i->_next)
            if(get_key(i->_val) == key) // 提取_val的key再进行比较
                return iterator(i, &_h, pos);
        return end();
    }
    
    // const版本的find也是类似。参数应当为K类型
    
    // insert的参数应当是T类型。成功插入返回：<值为x的迭代器, true>; 否则返回<值为x的迭代器, false>
    pair<iterator, bool> insert(const T& x)
    {
        iterator it = find(get_key(x));
        if(it != end()) return {it, false};

        if(_size >= 0.7 * _h.size())
            reserve(_h.size() + 1);

        // 先提取val的key，然后转化成非负整数，再找到其存储的下标
        int pos = get_hash(get_key(x)) % _h.size();
        node* cur = new node(x);
        cur->_next = _h[pos];
        _h[pos] = cur;
        _size++;
        return {iterator(cur, &_h, pos), true};
    }
    
    void reserve(size_t n)
    {
        if(_h.size() >= n) return;

        n = get_next_prime(n);
        vector<node*> new_h(n);
        for(int i = 0; i < _h.size(); i++)
        {
            if(_h[i])
            {
                node* j = _h[i];
                while(j)
                {
                    // 先提取j->_val的key，然后转化成非负整数，再找到其存储的下标
                    int pos = get_hash(get_key(j->_val)) % new_h.size();
                    node* next = j->_next;
                    j->_next = new_h[pos];
                    new_h[pos] = j;
                    j = next;
                }
            }
        }
        _h.swap(new_h);
    }

    // erase的参数应当也是K类型
    bool erase(const K& key)
    {
        // 先把key转化成非负整数，再找到其存储的下标
        int pos = get_hash(key) % _h.size();
        for(node* i = _h[pos], *pre = nullptr; i; pre = i, i = i->_next)
        {
        	// 应当按K类型数据比较
            if(get_key(i->_val) == key)
            {
                if(!pre)    // 这里说明被删除的元素是头节点
                    _h[pos] = _h[pos]->_next;
                else
                    pre->_next = i->_next;
                delete i;
                _size--;
                return true;
            }
        }
        return false;
    }

8. 封装unordered_set

成员变量

template<class K, class Hash = HashFunc<K>>
class unordered_set
{
    typedef const K T;  // 为了防止数据，这里加上const
    struct ExtractK
    {
        const K& operator() (const T& x) const
        {
            return x;
        }
        // 补充小知识：
        // 函数参数 const T& 展开就是 const const K&
        // const重复修饰同一个类型时，编译器会将其视为冗余，最终类型不变
        // const const K&等价于 const K&
    };
    typedef HashTable<K, T, ExtractK, Hash> hash_table;
    hash_table _ht;
};

迭代器

	// 直接用哈希表的即可
    typedef typename hash_table::iterator       iterator;
    typedef typename hash_table::const_iterator 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(); }

查找、插入、删除

    iterator find(const K& key) { return _ht.find(key); }
    const_iterator find(const K& key) const { return _ht.find(key); }
    pair<iterator, bool> insert(const T& x) { return _ht.insert(x); }
    int erase(const K& key) { return _ht.erase(key); }

其他

    unordered_set() {}
    // 列表构造
    unordered_set(initializer_list<T> il)
    {
        _ht.reserve(ceil(il.size() / 0.7)); // 尽量不要超过负载因子. ceil是向上取整
        for(const auto& e : il)
            _ht.insert(e);
    }
    
    size_t size() const { return _ht.size(); }
    bool empty() const { return _ht.empty(); }
    void reserve(size_t n) {_ht.reserve(n); }
    void clear() { _ht.clear(); }
    void swap(unordered_set& s) { _ht.swap(s._ht); }

9. 封装unordered_map

成员变量

template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
    typedef pair<const K, V> T;  // 为了防止数据，给K加上const
    struct ExtractK
    {
        const K& operator() (const T& x) const
        {
            return x.first;	// 关键字为 K类型
        }
    };
    typedef HashTable<K, T, ExtractK, Hash> hash_table;
    hash_table _ht;
};

迭代器

	// 直接用哈希表的即可
    typedef typename hash_table::iterator       iterator;
    typedef typename hash_table::const_iterator 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(); }

查找、插入、删除

    iterator find(const K& key) { return _ht.find(key); }
    const_iterator find(const K& key) const { return _ht.find(key); }
    pair<iterator, bool> insert(const T& x) { return _ht.insert(x); }
    int erase(const K& key) { return _ht.erase(key); }

    // 通过key找对应的值。
    V& operator[] (const K& key)
    {
        return insert({key, V()}).first->second;
    }

其他

    unordered_map() {}
    unordered_map(initializer_list<T> il) 
    {
        _ht.reserve(ceil(il.size() / 0.7));
        for(const auto& e : il)
            _ht.insert(e);
    }
    
    size_t size() const { return _ht.size(); }
    bool empty() const  { return _ht.empty(); }
    void reserve(size_t n) { _ht.reserve(n); }
    void clear()    { _ht.clear(); }
    void swap(unordered_map& s) { _ht.swap(s._ht); }

10. 完整代码

HashTable.h

#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
#include<assert.h>
#include<cmath>
using namespace std;

// 哈希表的节点（单链表）
template<class T>
struct hash_table_node
{
    T _val;
    hash_table_node* _next;

    hash_table_node(const T& x = T(), hash_table_node* next = nullptr)
        :_val(x)
        ,_next(next)
    {}
};

// 普通迭代器：封装node*
template<class T>
struct HashTable_iterator
{
    typedef hash_table_node<T> node;
    node* _pnode;               // 哈希表节点指针
    const vector<node*>* _ph;   // 哈希表指针
    size_t _pos;                // 该节点在哈希表的位置

    HashTable_iterator(node* pn = nullptr, const vector<node*>* ph = nullptr, size_t pos = 0)
        :_pnode(pn)
        ,_ph(ph)
        ,_pos(pos)
    {}

    typedef HashTable_iterator Self;
    // 前置++
    Self& operator++()
    {
        assert(_pnode);
        if(_pnode->_next)
            _pnode = _pnode->_next;
        else{
            _pos++;
            while(_pos < _ph->size() && !(*_ph)[_pos])
                _pos++;
            if(_pos < _ph->size())
                _pnode = (*_ph)[_pos];
            else
                _pnode = nullptr;
        }
        return *this;
    }
    // 后置++
    Self operator++(int)
    {
        Self tmp(*this);
        ++(*this);
        return tmp;
    }

    T& operator*() { return _pnode->_val; }
    T* operator->() { return &_pnode->_val; }
    bool operator!= (const Self& it) const
    { return _pnode != it._pnode; }
    bool operator== (const Self& it) const
    { return _pnode == it._pnode; }
};

// const迭代器：封装const node*
template<class T>
struct HashTable_const_iterator
{
    typedef hash_table_node<T> node;
    const node* _pnode;       // 哈希表节点指针
    const vector<node*>* _ph; // 哈希表指针
    size_t _pos;              // 该节点在哈希表的位置

    HashTable_const_iterator(const node* pn = nullptr, const vector<node*>* ph = nullptr, size_t pos = 0)
        :_pnode(pn)
        ,_ph(ph)
        ,_pos(pos)
    {}

    // 可能会用普通迭代器构造constdiedaiq
    HashTable_const_iterator(const HashTable_iterator<T>& it)
        :_pnode(it._pnode)
        ,_ph(it._ph)
        ,_pos(it._pos)
    {}

    typedef HashTable_const_iterator Self;
    // 前置++
    Self& operator++()
    {
        assert(_pnode);
        if(_pnode->_next)
            _pnode = _pnode->_next;
        else{
            _pos++;
            while(_pos < _ph->size() && !(*_ph)[_pos])
                _pos++;
            if(_pos < _ph->size())
                _pnode = (*_ph)[_pos];
            else
                _pnode = nullptr;
        }
        return *this;
    }
    // 后置++
    Self operator++(int)
    {
        Self tmp(*this);
        ++(*this);
        return tmp;
    }
    const T& operator*() { return _pnode->_val; }
    const T* operator->() { return &_pnode->_val; }
    bool operator!= (const Self& it) const
    { return _pnode != it._pnode; }
    bool operator== (const Self& it) const
    { return _pnode == it._pnode; }
};

// 将元素x处理成非负整数
template<class T>
struct HashFunc
{
    size_t operator() (const T& x) const
    {
        return (size_t)x;
    }
};

// 特化string版本
template<>
struct HashFunc<string>
{
    size_t operator() (const string& x) const
    {
    	// 把string类型看作131进制的数（有相关研究表明，这样哈希冲突较少）
    	// 例如x = "abc"
    	// 则其key = 'a'*131^2 + 'b'*131^1 + 'c'*131^0
        size_t res = 0;
        for(auto& c : x)
            res = res * 131 + c;
        return res;
    }
};

// 哈希表
template<class K,		    // 元素的关键字key的类型
		 class T,		    // 实际存储的元素类型
		 class ExtractKey,	// 提取元素的关键字
		 class Hash>	    // 将key处理成非负整数
class HashTable
{
    typedef hash_table_node<T> node;
    vector<node*> _h;   // 链表数组
    size_t _size = 0;   // 表中的元素个数
    
    // 提取元素的 key
    const K& get_key(const T& x) const
    {
        static ExtractKey f;
        return f(x);
    }
    // 将key转化成非负整数（计算key的哈希值）
    size_t get_hash(const K& key) const
    {
        static Hash f;
        return f(key);
    }
    // 找 >= n的最小质数
    size_t get_next_prime(size_t n)
    {
        static size_t p[29] =
        {   17,
            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
        };
        if(n > p[28]) return p[28];
        return *lower_bound(p, p + 29, n);
    }

public:
    typedef HashTable_iterator<T> iterator;
    typedef HashTable_const_iterator<T> const_iterator;
    iterator begin()
    {
        if(!_size) return end();   
        for(int i = 0; i < _h.size(); i++)
            if(_h[i])
                return iterator(_h[i], &_h, i);
        return end();   // 按理说不会走到这里，但有些编译器会强制要求有返回值
    }
    iterator end() 
    { 
        return iterator(nullptr, &_h, -1); 
        //注意不要写成：{nullptr, &_h, -1}; C++11开始，对列表初始化，禁止窄化转换（有符号负数→无符号）
    }

    const_iterator begin() const
    {
        if(!_size) return end();
        for(int i = 0; i < _h.size(); i++)
            if(_h[i])
                return const_iterator(_h[i], &_h, i);
        return end();
    }
    const_iterator end() const 
    { 
        return const_iterator(nullptr, &_h, 0); 
    }

    HashTable(int n = 17)
        :_h(get_next_prime(n))		// 初始时，表长设为17
    {}
    
    // 列表构造
    HashTable(initializer_list<T> il)
    {
        reserve(ceil(il.size() / 0.7)); // 尽量不要超过负载因子. ceil是向上取整
        for(const auto& e : il)
            insert(e);
    }

    // 析构
    ~HashTable() { clear(); }
    void clear()
    {
        for(const node* i : _h)
            while(i)
            {
                node* next = i->_next;
                delete i;
                i = next;
            }
        _size = 0;
    }

    // 拷贝构造
    HashTable(const HashTable& ht)
    {
        _h.resize(ht._h.size());
        for(auto& e : ht)
            insert(e);
    }

    void swap(HashTable& ht)
    {
        _h.swap(ht._h);
        std::swap(_size, ht._size);
    }

    // 赋值重载
    HashTable& operator= (const HashTable& ht)
    {
        if(this != &ht)
        {
            HashTable tmp(ht);
            swap(tmp);
        }
        return *this;
    }

    size_t size() const { return  _size; }
    bool empty() const { return !_size; }

    // find的参数应当是K类型。找到了关键字为key的迭代器，否则返回end()
    iterator find(const K& key)
    {
        // 先把key转化成非负整数，再找到其存储的下标
        int pos = get_hash(key) % _h.size();	
        for(node* i = _h[pos]; i; i = i->_next)
            if(get_key(i->_val) == key) // 提取_val的key再进行比较
                return iterator(i, &_h, pos);
        return end(); // 未找到返回空
    }

    // 顺便提供const版本的find
    const_iterator find(const K& key) const
    {
        // 先把key转化成非负整数，再找到其存储的下标
        int pos = get_hash(key) % _h.size();	
        for(const node* i = _h[pos]; i; i = i->_next)
            if(get_key(i->_val) == key) // 提取_val的key再进行比较
                return const_iterator(i, &_h, pos);
        return end(); // 未找到返回空
    }

    // insert的参数应当是T类型。成功插入返回：<值为x的迭代器, true>; 否则返回<值为x的迭代器, false>
    pair<iterator, bool> insert(const T& x)
    {
        iterator it = find(get_key(x));
        if(it != end()) return {it, false};

        if(_size >= 0.7 * _h.size())
            reserve(_h.size() + 1);

        // 先提取val的key，然后转化成非负整数，再找到其存储的下标
        int pos = get_hash(get_key(x)) % _h.size();
        node* cur = new node(x);
        cur->_next = _h[pos];
        _h[pos] = cur;
        _size++;
        return {iterator(cur, &_h, pos), true};
    }

    // 让新容量变为 >= n的最小质数
    void reserve(size_t n)
    {
        if(_h.size() >= n) return;

        n = get_next_prime(n); // 找 >= n的最小质数
        vector<node*> new_h(n);
        for(int i = 0; i < _h.size(); i++)
        {
            if(_h[i])
            {
                // 为了提高效率，直接把原哈希表的节点移动到新表中
                node* j = _h[i];
                while(j)
                {
                    // 先提取j->_val的key，然后转化成非负整数，再找到其存储的下标
                    int pos = get_hash(get_key(j->_val)) % new_h.size();
                    node* next = j->_next;
                    j->_next = new_h[pos];
                    new_h[pos] = j;
                    j = next;
                }
            }
        }
        _h.swap(new_h);
    }

    // erase的参数应当也是K类型
    bool erase(const K& key)
    {
        // 先把key转化成非负整数，再找到其存储的下标
        int pos = get_hash(key) % _h.size();
        for(node* i = _h[pos], *pre = nullptr; i; pre = i, i = i->_next)
        {
            if(get_key(i->_val) == key)
            {
                if(!pre)    // 这里说明被删除的元素是头节点
                    _h[pos] = _h[pos]->_next;
                else
                    pre->_next = i->_next;
                delete i;
                _size--;
                return true;
            }
        }
        return false;
    }
};

unordered_set_map.h

#include"HashTable.h"

template<class K, class Hash = HashFunc<K>>
class unordered_set
{
    typedef const K T;  // 为了防止数据，这里加上const
    struct ExtractK
    {
        // 参数 const T& 展开就是 const const K&
        // const重复修饰同一个类型时，编译器会将其视为冗余，最终类型不变
        // const const K&等价于 const K&
        const K& operator() (const T& x) const
        {
            return x;
        }
    };
    typedef HashTable<K, T, ExtractK, Hash> hash_table;
    hash_table _ht;
public:
    unordered_set() {}
    unordered_set(initializer_list<T> il)
    {
        _ht.reserve(ceil(il.size() / 0.7));
        for(const auto& e : il)
            _ht.insert(e);
    }

    typedef typename hash_table::iterator       iterator;
    typedef typename hash_table::const_iterator 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(); }

    iterator find(const K& key) { return _ht.find(key); }
    const_iterator find(const K& key) const { return _ht.find(key); }
    pair<iterator, bool> insert(const T& x) { return _ht.insert(x); }
    int erase(const K& key) { return _ht.erase(key); }
    
    size_t size() const { return _ht.size(); }
    bool empty() const { return _ht.empty(); }
    void reserve(size_t n) {_ht.reserve(n); }
    void clear() { _ht.clear(); }
    void swap(unordered_set& s) { _ht.swap(s._ht); }
};

template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
    typedef pair<const K, V> T;  // 为了防止数据，键值加上const
    struct ExtractK
    {
        const K& operator() (const T& x) const
        {
            return x.first;
        }
    };
    typedef HashTable<K, T, ExtractK, Hash> hash_table;
    hash_table _ht;

public:
    unordered_map() {}
    unordered_map(initializer_list<T> il) 
    {
        _ht.reserve(ceil(il.size() / 0.7));
        for(const auto& e : il)
            _ht.insert(e);
    }
    typedef typename hash_table::iterator       iterator;
    typedef typename hash_table::const_iterator 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(); }

    iterator find(const K& key) { return _ht.find(key); }
    const_iterator find(const K& key) const { return _ht.find(key); }
    pair<iterator, bool> insert(const T& x) { return _ht.insert(x); }
    int erase(const K& key) { return _ht.erase(key); }

    // 通过key找对应的值。
    V& operator[] (const K& key)
    {
        return insert({key, V()}).first->second;
    }

    size_t size() const { return _ht.size(); }
    bool empty() const  { return _ht.empty(); }
    void reserve(size_t n) { _ht.reserve(n); }
    void clear()    { _ht.clear(); }
    void swap(unordered_map& s) { _ht.swap(s._ht); }
};

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

2026企业微信AI Agent实测：7款技术方案对比

会话审计、敏感词管理、聊天质检、敏感行为识别、舆情、属性、词频及竞品分析覆盖服务风险；线索公海、客户、产品、商机、订单、回款、发票和业绩目标则连接销售全过程。快创助手负责快速建运营任务，策略生成把目标拆成方案，智能客服回答系统使用咨询，数据报表处理自然语言查数，AI洞察联合标签、订单和会话分析客户。我们设计了客户筛选、订单关联、销售交接、会话质检和异常恢复任务，配合技术访谈与行业公开资料复核。准备