C++ 实现 unordered_set 与 unordered_map 详解

前言

在 C++ 标准库中，unordered_set 和 unordered_map 是常用的哈希容器，分别用于存储唯一元素集合和键值对关联表。它们的实现基于哈希表，因此能在平均 O(1) 时间内完成插入、查找和删除操作。理解它们的实现机制有助于我们更深入地掌握哈希表的核心原理和高效数据结构的设计。本篇文章将详细讲解如何使用 C++ 模板实现 HashTable 类，并基于该类构建 unordered_set 和 unordered_map，同时深入分析每个成员函数及其实现细节。

一、改造 HashTable

改造 HashTable 以适配 unordered_map 和 unordered_set 容器，主要涉及到如何根据这两种容器的特性来设计和实现 HashTable 节点的存储以及相应的操作。unordered_map 和 unordered_set 的主要区别在于它们存储的元素类型：map 存储键值对（key-value pairs），而 set 仅存储唯一的键值（通常是键本身作为值）。尽管如此，它们在底层数据结构（如 HashTable）的实现上有很多相似之处。

改造内容：

• K：key 的类型
• T：如果是 unordered_map，则为 pair<K, V>; 如果是 unordered_set，则为 K
• KeyOfT：通过 T 来获取 key 的一个仿函数类
• HashFunc: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将 Key 转换为整形数字才能取模

1.1 HashNode 类

HashNode 类用于构成链表，用于处理哈希表中冲突的元素。

template<class T>
class HashNode {
public:
    T _data; // 键值对
    HashNode<T>* _next; // 链表下一个节点的指针
    
    HashNode(const T& data) : _data(data), _next(nullptr) {}
};

【详细说明】：

• _data 存储键值对或元素本身。
• _next 指针用于形成链表，处理哈希冲突。
• const 用在构造函数参数 const T& data 中，确保插入时不会修改原始数据，保证了数据的安全传递。

1.2 HashTable 类框架

template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable {
    typedef HashNode<T> Node;
    // 友元声明
    template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
    friend struct HTIterator;

public:
    typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
    typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
    
private:
    vector<Node*> _table; // 指针数组
    size_t _n = 0; // 存储了多少有效数据
};

• 注意： HTIterator 迭代器结构声明为 HashTable 的友元，以便访问哈希表的私有成员变量 _table 和 _n。这种设计使得迭代器能够顺利地访问哈希表内部的桶和数据，实现无缝的遍历功能。

1.3 插入操作 Insert

pair<iterator, bool> Insert(const T& data) {
    HashFunc hf;
    KeyOfT kot;
    // 检查是否存在相同的元素
    iterator it = Find(kot(data));
    if (it != end()) {
        return make_pair(iterator(it), false);
    }
    
    // 扩容逻辑，当负载因子为 1 时扩容
    if (_n == _table.size()) {
        size_t newSize = _table.size() * 2;
        vector<Node*> newTable(newSize, nullptr);
        // 将旧表中的节点重新分配到新表
        for (size_t i = 0; i < _table.size(); ++i) {
            Node* cur = _table[i];
            while (cur) {
                Node* next = cur->_next;
                size_t hashi = hf(kot(cur->_data)) % newSize;
                cur->_next = newTable[hashi];
                newTable[hashi] = cur;
                cur = next;
            }
        }
        _table.swap(newTable);
    }
    
    // 插入新节点到表中
    size_t hashi = hf(kot(data)) % _table.size();
    Node* newnode = new Node(data);
    newnode->_next = _table[hashi];
    _table[hashi] = newnode;
    ++_n;
    return make_pair(iterator(newnode, this), true);
}

【详细说明】：

1. 查找重复元素：Find 函数被用来检查表中是否已经存在与 data 相同的元素。如果找到相同的元素，则返回一个指向该元素的迭代器以及 false 表示插入失败。
2. 扩容逻辑：如果哈希表中已存储的元素数量 _n 达到或超过当前桶数 _table.size()（即负载因子为 1），则执行扩容操作，将哈希表的大小增加一倍。
   • 重新计算旧表中每个节点的哈希值，并将节点重新插入到新表的适当位置。
   • 扩容后使用 swap 替换旧表，这种方式可以避免拷贝新表中的元素，提高效率。
3. 插入新节点：通过计算哈希值来确定新元素的插入位置 hashi，并将新节点 newnode 插入到对应桶的链表头部（使用头插法）。
4. const 的使用：
   • 函数参数 const T& data 保证传入的数据在插入过程中不会被修改。
   • const 确保了数据传递的安全性，避免数据在插入时发生意外更改。

1.4 查找操作 Find

iterator Find(const K& key) {
    HashFunc hf;
    KeyOfT kot;
    size_t hashi = hf(key) % _table.size();
    Node* cur = _table[hashi];
    while (cur) {
        if (kot(cur->_data) == key) {
            return iterator(cur, this);
        }
        cur = cur->_next;
    }
    return iterator(nullptr, this);
}

【详细说明】：

1. 定位桶：通过哈希函数计算 key 的哈希值，找到对应的桶位置 hashi。在此位置上可以通过链表查找目标元素。
2. 遍历链表：从桶的链表头开始，逐一检查每个节点的键值。如果找到与 key 匹配的节点，则返回指向该节点的迭代器。
3. 返回空迭代器：如果遍历完链表后仍未找到匹配的键，则返回一个空迭代器（nullptr）。
4. const 的使用：
   • 参数 const K& key 保证在查找过程中不会修改传入的键值，确保了查找操作的安全性和一致性。
   • const 修饰 key 可以避免传递过程中被无意改变，从而保证数据的一致性。

1.5 删除操作 Erase

bool Erase(const K& key) {
    HashFunc hf;
    KeyOfT kot;
    size_t hashi = hf(key) % _table.size();
    Node* prev = nullptr;
    Node* cur = _table[hashi];
    while (cur) {
        if (kot(cur->_data) == key) {
            if (prev == nullptr) {
                _table[hashi] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            --_n;
            delete cur;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

【详细说明】：

1. 定位桶并遍历链表：通过哈希值定位 key 对应的桶 hashi，然后遍历该桶的链表查找目标节点。
2. 删除目标节点：
   • 如果目标节点在链表的头部，则将桶的头指针指向目标节点的下一个节点。
   • 如果目标节点在链表的中间或尾部，则通过 prev->_next = cur->_next 跳过目标节点，将其从链表中移除。
3. 更新元素数量：删除目标节点后，减少元素计数 _n，并释放节点内存。
4. 返回删除结果：若删除成功则返回 true，否则返回 false。
5. const 的使用：
   • const K& key 参数修饰确保在删除过程中不会修改 key。
   • const 在这里保证了删除过程的安全性，不会意外更改 key，确保查找与删除逻辑的一致性。

1.6 析构函数 ~HashTable()

~HashTable() {
    for (size_t i = 0; i < _table.size(); ++i) {
        Node* cur = _table[i];
        while (cur) {
            Node* next = cur->_next;
            delete cur;
            cur = next;
        }
        _table[i] = nullptr;
    }
}

【详细说明】：

1. 遍历哈希表的每个桶：
   • for (size_t i = 0; i < _table.size(); ++i) 循环用于访问哈希表中的每一个桶。_table.size() 是桶的数量。
2. 遍历每个桶的链表：
   • Node* cur = _table[i]; 获取桶的链表头指针 cur。
   • while (cur) 表示当 cur 不为空时，继续删除链表的节点。
3. 逐节点释放链表：
   • Node* next = cur->_next; 在删除 cur 之前，先保存当前节点的下一个节点 next。
   • delete cur; 删除当前节点以释放其内存。
   • cur = next; 更新 cur 指针为 next，即指向下一个节点，重复此过程直至链表尾部。
4. 清空桶指针：
   • _table[i] = nullptr; 将当前桶指针置为 nullptr，确保析构后哈希表的所有桶均为空指针。

二、HTIterator 迭代器简介

HTIterator 是 HashTable 的自定义迭代器结构，支持遍历哈希表中的每一个元素。它通过遍历链表节点 _node 和跳转到非空桶位置，实现无序遍历。通过重载操作符，它具备了和标准迭代器类似的操作功能。

2.1 前置声明

template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;

由于 HTIterator 中引用了 HashTable，而 HashTable 中也可能引用 HTIterator，因此需要在声明 HashTable 前先进行前置声明，以避免编译时出现未定义的行为。

2.2 成员变量

Node* _node;
const HashTable<K, T, KeyOfT, HashFunc>* _pht;

• _node：指向当前遍历的链表节点。
• _pht：指向迭代器所属的哈希表实例，允许迭代器在链表结束后跳转到下一个非空桶，继续遍历。

const 修饰哈希表指针 _pht，确保迭代器在遍历过程中不会修改哈希表结构，提高了安全性。

2.3 构造函数

HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht) : _node(node), _pht(pht) {}

• 构造函数初始化 _node 和 _pht，使得迭代器具备遍历链表和桶的能力。
• 这里的 const 确保哈希表指针 _pht 不会被修改。

2.4 拷贝构造函数

HTIterator(const Iterator& it) : _node(it._node), _pht(it._pht) {}

• 允许从另一个普通迭代器 Iterator 进行构造，用于将普通迭代器转换为 const_iterator。

2.5 operator* 和 operator->

Ref operator*() {
    return _node->_data;
}

• 解引用运算符，返回当前 _node 所指向节点的值 _data。
• 返回类型 Ref 允许返回 T& 或 const T&，实现灵活的访问。

Ptr operator->() {
    return &_node->_data;
}

• 提供成员访问功能，返回当前节点的数据地址（指针）。
• 返回类型 Ptr 允许返回 T* 或 const T*。

2.6 自增操作符 operator++

Self& operator++() {
    if (!_node || !_pht) return *this; // 边界检查
    
    if (_node->_next) {
        _node = _node->_next;
    } else {
        KeyOfT kot;
        HashFunc hf;
        size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
        
        // 查找下一个非空桶
        ++hashi;
        while (hashi < _pht->_table.size() && _pht->_table[hashi] == nullptr) {
            ++hashi;
        }
        
        // 若找到下一个非空桶，更新 _node；否则置为 nullptr
        _node = (hashi < _pht->_table.size()) ? _pht->_table[hashi] : nullptr;
    }
    return *this;
}

【详细说明】：

1. 边界检查：如果 _node 或 _pht 为 nullptr，直接返回当前迭代器，不进行操作。
2. 遍历链表节点：如果当前节点有下一个节点 _next，则直接将 _node 移动到 _next，继续链表的遍历。
3. 跳转到下一个非空桶：
   • 若当前链表遍历完毕，通过哈希函数定位到当前元素所在的桶 hashi。
   • 自增 hashi，开始查找下一个非空桶的位置。
   • 若找到下一个非空桶，则将 _node 指向该桶的第一个节点；若无更多桶，则将 _node 置为 nullptr，表示迭代结束。
4. 返回迭代器引用：返回 *this 使得该操作符支持前置自增的链式调用。

2.7 operator!= 和 operator==

bool operator!=(const Self& s) {
    return _node != s._node;
}

• 比较两个迭代器是否指向不同的节点。
• 用于迭代结束检查，若 _node 指针不同则返回 true，表示未到达结束。

bool operator==(const Self& s) {
    return _node == s._node;
}

• 比较两个迭代器是否指向相同的节点。
• 若 _node 指针相同，则返回 true，用于判断两个迭代器是否相等。

三、Unordered_Set 的实现

unordered_set 是一个无序集合，包含唯一的元素，不支持重复插入。为了实现 unordered_set，我们使用了前面定义的 HashTable。unordered_set 通过 HashTable 来完成元素的存储和冲突解决。

3.1 unordered_set 的基本设计

unordered_set 通过哈希表 HashTable 存储集合中的元素。为了从 HashTable 中获取键，unordered_set 中定义了一个 SetKeyOfT 仿函数类：

namespace xny {
template<class K>
class unordered_set {
    struct SetKeyOfT {
        const K& operator()(const K& key) {
            return key;
        }
    };

public:
    typedef typename HashTable<K, K, SetKeyOfT>::const_iterator iterator;
    typedef typename HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;
    
    pair<iterator, bool> insert(const K& key) {
        pair<typename HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
        return pair<const_iterator, bool>(ret.first, ret.second);
    }
    
    iterator begin() {
        return _ht.begin();
    }
    iterator end() {
        return _ht.end();
    }
    const_iterator begin() const {
        return _ht.begin();
    }
    const_iterator end() const {
        return _ht.end();
    }

private:
    HashTable<K, K, SetKeyOfT> _ht;
};
}

3.2 详细分析每个函数

• const 修饰符确保传入的 key 不会在插入过程中被修改。
• pair<const_iterator, bool> 确保返回类型的安全性，使得外部代码无法修改集合中的元素。

begin 和 end: begin 和 end 返回集合的起始和结束迭代器，以支持集合的遍历。它们调用哈希表的 begin 和 end 方法。

iterator begin() { return _ht.begin(); }
iterator end() { return _ht.end(); }

这两个函数还分别提供了 const 版本，允许在常量上下文中进行集合遍历操作。

insert: insert 函数用于向集合中插入一个元素。它调用 _ht.Insert(key) 方法将元素插入到哈希表中，并返回一个 pair，包含一个指向新插入元素的迭代器和一个布尔值，表示插入是否成功。

pair<iterator, bool> insert(const K& key) {
    pair<typename HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
    return pair<const_iterator, bool>(ret.first, ret.second);
}

3.3 Unordered_Set 测试

以下代码展示了 unordered_set 的基本操作：

xny::unordered_set<int> uset;
uset.insert(10);
uset.insert(20);
uset.insert(30);
for (auto it = uset.begin(); it != uset.end(); ++it) {
    cout << *it << " ";
}

此测试代码向集合插入几个整数，并使用迭代器遍历集合，输出结果不保证顺序，但每个元素唯一。

四、Unordered_Map 的实现

unordered_map 是一种无序的关联容器，存储键值对（key-value），通过键来快速访问对应的值。与 unordered_set 类似，unordered_map 也依赖 HashTable 实现底层存储。

4.1 unordered_map 的基本设计

unordered_map 通过哈希表 HashTable 存储键值对。为了支持键值对的存储，它定义了一个 MapKeyOfT 仿函数，用于从键值对中提取键：

namespace xny {
template<class K, class V>
class unordered_map {
    struct MapKeyOfT {
        const K& operator()(const pair<const K, V>& kv) {
            return kv.first;
        }
    };

public:
    typedef typename HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
    typedef typename HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
    
    pair<const_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 begin() {
        return _ht.begin();
    }
    iterator end() {
        return _ht.end();
    }
    const_iterator begin() const {
        return _ht.begin();
    }
    const_iterator end() const {
        return _ht.end();
    }

private:
    HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}

4.2 详细分析每个函数

• 这里的 pair<const_iterator, bool> 确保返回的键值对不可被外部代码修改，保证了数据安全性。
• const 修饰符用于 insert 函数的参数 kv，以确保键值对在插入时不被修改。
• const 确保传入的 key 不会在操作过程中被修改。
• 若键不存在，通过 make_pair 创建一个默认值，并插入哈希表。

begin 和 end: begin 和 end 返回容器的起始和结束迭代器，用于遍历 unordered_map 的所有键值对。

iterator begin() { return _ht.begin(); }
iterator end() { return _ht.end(); }

同样，提供了 const 版本的 begin 和 end，使得可以在 const 上下文中遍历容器。

operator[]: operator[] 提供通过键访问对应值的方式，若键不存在则插入一个默认值，若存在则直接返回对应的值。

V& operator[](const K& key) {
    pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
    return ret.first->second;
}

insert: insert 函数用于插入键值对。它调用哈希表的 _ht.Insert(kv) 方法，并返回一个 pair，包含一个指向新插入键值对的迭代器和一个布尔值，表示是否成功插入。

pair<const_iterator, bool> insert(const pair<K, V>& kv) {
    return _ht.Insert(kv);
}

4.3 Unordered_Map 测试

以下代码展示了 unordered_map 的基本操作：

xny::unordered_map<string, int> umap;
umap["apple"] = 3;
umap["banana"] = 5;
umap["orange"] = 8;
for (auto it = umap.begin(); it != umap.end(); ++it) {
    cout << it->first << " : " << it->second << endl;
}

此代码演示了通过 operator[] 插入键值对以及使用迭代器遍历容器的方式。它展示了 unordered_map 的键值对存储和查找功能。

结语

通过实现 HashTable 以及基于它构建 unordered_set 和 unordered_map，我们不仅深入了解了哈希表的基本操作和冲突解决方法，还学习了如何使用 C++ 模板和仿函数来设计通用数据结构。此外，本文还讨论了 const 的使用技巧，以确保在数据访问时增强安全性和可读性。掌握这些实现细节，可以帮助我们更好地理解 STL 的实现原理，并在日常开发中设计出高效、可复用的数据结构。希望本文能够对您深入理解哈希表和无序容器的实现有所帮助！