C++ 实现 unordered_set 与 unordered_map 详解

• 注意： 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 的实现原理，并在日常开发中设计出高效、可复用的数据结构。希望本文能够对您深入理解哈希表和无序容器的实现有所帮助！