哈希表（Hash Table）是一种常用的数据结构，它能够以接近常数时间复杂度的效率完成插入、删除和查找操作。在现代编程中，标准模板库（STL）提供了 unordered_map 和 unordered_set，它们都是基于哈希表实现的。在这篇博客中，我们将从零开始，使用 C++ 实现一个通用的哈希表，并基于此实现 unordered_map 和 unordered_set，同时完成迭代器的设计。
1. 哈希表的基本原理
2. 开放地址法（闭散列）哈希表的实现
1. 线性探测
具体实现如下：
C-/unordered_map_set at c0fcac61b3e7110c8e5f3a360eca0d920acf3ccb · hqxnb666/C- · GitHub
首先，我们定义哈希表的状态枚举和数据节点结构
enum State
{EMPTY, // 空状态EXIST, // 已存在DELETE // 被删除
};template<class K, class V>
struct HashData
{std::pair<K, V> _kv; // 键值对State _state; // 当前节点状态HashData() : _state(EMPTY) {}
};
接下来，定义哈希函数模板：
template<class K>
struct HashFunc
{size_t operator()(const K& key){return static_cast<size_t>(key);}
};// 针对 std::string 的特化
template<>
struct HashFunc<std::string>
{size_t operator()(const std::string& key){size_t hash = 0;for (char ch : key){hash = hash * 131 + ch; // 使用 BKDR 哈希算法}return hash;}
};
这个模板是用来干什么的呢？，当我们传递参数时，能只传递整数吗？传递字符串又该如何处理？
因此我们采用了仿函数的方式，重载对应的()，当传递的是字符串时，编译器按需实例化，通过这个BKDR函数来将字符串进行处理后再进行我们的去留余数法，而这个算法的作用是什么呢，我们当前代码影响效率的因素是什么？最大程度上的影响因素是如果处理后的数字一旦发生冲突，就要挨家挨户往后找空，这样很浪费时间，于是我们采取了目前最优秀的字符串处理算法，这样经过处理后的数字很少会发生冲突，最大程度上提高了我们的效率！
以下是哈希表的类定义：
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:HashTable(size_t size = 10) : _tables(size), _n(0) {}bool Insert(const std::pair<K, V>& kv){// 检查装载因子，决定是否需要扩容if (_n * 10 / _tables.size() >= 7){// 扩容并重新哈希Rehash();}Hash hs;size_t idx = hs(kv.first) % _tables.size();// 线性探测寻找空位while (_tables[idx]._state == EXIST){// 如果键已存在，更新值if (_tables[idx]._kv.first == kv.first){_tables[idx]._kv.second = kv.second;return true;}idx = (idx + 1) % _tables.size();}_tables[idx]._kv = kv;_tables[idx]._state = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){Hash hs;size_t idx = hs(key) % _tables.size();size_t origin = idx; // 记录初始位置while (_tables[idx]._state != EMPTY){if (_tables[idx]._state == EXIST && _tables[idx]._kv.first == key){return &_tables[idx];}idx = (idx + 1) % _tables.size();if (idx == origin) break; // 回到起点，查找结束}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr) {return false;}else{ret->_state = DELETE;--_n;return true;}}private:void Rehash(){size_t newSize = _tables.size() * 2;std::vector<HashData<K, V>> newTables(newSize);for (auto& data : _tables){if (data._state == EXIST){Hash hs;size_t idx = hs(data._kv.first) % newSize;while (newTables[idx]._state == EXIST){idx = (idx + 1) % newSize;}newTables[idx] = data;}}_tables.swap(newTables);}std::vector<HashData<K, V>> _tables;size_t _n; // 有效元素个数
};
这里涉及到一个概念，我们一开始假设的是十个空间大小对应余数，随着数字越来越多，十个一旦不够用了我们就需要对其进行扩容操作，那么什么时候选择扩容比较好呢？太小了浪费空间，太大了效率不够，因此，通过测试目前最适用的负载因子是0.7，
3. 拉链法（开散列）哈希表的实现
拉链法通过数组加链表的方式处理哈希冲突。每个数组元素（桶）存储一个链表，所有映射到同一桶的元素都链接在这个链表中。
定义哈希节点：
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
{
public:typedef __HTIterator<K, T, KeyOfT, Hash> iterator;typedef HashNode<T> Node;HashTable(size_t size = 10): _tables(size, nullptr), _n(0){}~HashTable(){Clear();}std::pair<iterator, bool> Insert(const T& data){KeyOfT kot;Hash hs;size_t idx = hs(kot(data)) % _tables.size();Node* cur = _tables[idx];while (cur){if (kot(cur->_data) == kot(data)){return { iterator(cur, this), false }; // 元素已存在}cur = cur->_next;}// 插入新节点Node* newNode = new Node(data);newNode->_next = _tables[idx];_tables[idx] = newNode;++_n;// 检查装载因子，决定是否需要扩容if (_n > _tables.size()){Rehash();}return { iterator(newNode, this), true };}bool Erase(const K& key){KeyOfT kot;Hash hs;size_t idx = hs(key) % _tables.size();Node* cur = _tables[idx];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){if (prev){prev->_next = cur->_next;}else{_tables[idx] = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}iterator Find(const K& key){KeyOfT kot;Hash hs;size_t idx = hs(key) % _tables.size();Node* cur = _tables[idx];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return end();}iterator begin(){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);}private:void Rehash(){size_t newSize = _tables.size() * 2;std::vector<Node*> newTables(newSize, nullptr);KeyOfT kot;Hash hs;for (auto& head : _tables){Node* cur = head;while (cur){Node* next = cur->_next;size_t idx = hs(kot(cur->_data)) % newSize;cur->_next = newTables[idx];newTables[idx] = cur;cur = next;}}_tables.swap(newTables);}void Clear(){for (auto& head : _tables){Node* cur = head;while (cur){Node* next = cur->_next;delete cur;cur = next;}head = nullptr;}_n = 0;}std::vector<Node*> _tables;size_t _n; // 有效元素个数
};
void _CheckCapacity()
{size_t bucketCount = BucketCount();if(_size == bucketCount){HashBucket<V, HF> newHt(bucketCount);for(size_t bucketIdx = 0; bucketIdx < bucketCount; ++bucketIdx){PNode pCur = _ht[bucketIdx];while(pCur){// 将该节点从原哈希表中拆出来_ht[bucketIdx] = pCur->_pNext;// 将该节点插入到新哈希表中size_t bucketNo = newHt.HashFunc(pCur->_data);pCur->_pNext = newHt._ht[bucketNo];newHt._ht[bucketNo] = pCur;pCur = _ht[bucketIdx];}}newHt._size = _size;this->Swap(newHt);}
}4. 基于哈希表实现 unordered_map 和 unordered_set
unordered_map 是一种以键值对（key-value）形式存储数据的关联容器，其中每个键都是唯一的。由于哈希表天然支持根据键快速查找对应的值，因此我们可以使用哈希表作为 unordered_map 的底层数据结构。
- 键值对的存储：需要存储键和值的关联关系，通常使用
std::pair<const K, V>。 - 哈希函数：需要一个能够将键映射到哈希表索引的哈希函数。
- 键的提取器（Key Extractor）：在哈希表中，我们需要从存储的元素中提取键，以进行哈希计算和比较。
- 迭代器的支持：为了使容器的使用更加方便，我们需要实现迭代器，支持遍历所有元素。
首先，我们定义一个提取键的仿函数 MapKeyOfT，用于从键值对中提取键：
template<class K, class V>
struct MapKeyOfT
{const K& operator()(const std::pair<const K, V>& data) const{return data.first;}
};
接下来，定义 unordered_map 类模板：
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
public:typedef std::pair<const K, V> ValueType;typedef HashTable<K, ValueType, MapKeyOfT<K, V>, Hash> HashTableType;typedef typename HashTableType::iterator iterator;unordered_map() : _ht() {}// 插入元素std::pair<iterator, bool> insert(const ValueType& kv){return _ht.Insert(kv);}// 查找元素iterator find(const K& key){return _ht.Find(key);}// 访问元素，如果键不存在，则插入默认值V& operator[](const K& key){auto it = _ht.Find(key);if (it == _ht.end()){auto ret = _ht.Insert({ key, V() });return ret.first->second;}else{return it->second;}}// 删除元素bool erase(const K& key){return _ht.Erase(key);}// 迭代器支持iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}private:HashTableType _ht;
};
-
ValueType定义：ValueType是存储在哈希表中的数据类型，即键值对std::pair<const K, V>。 -
HashTableType定义：HashTableType是我们之前实现的哈希表类型，模板参数包括键类型、存储的数据类型、键提取器和哈希函数。 -
insert函数：调用底层哈希表的Insert方法，将键值对插入哈希表。返回值是一个包含迭代器和布尔值的std::pair，表示插入操作的结果。 -
find函数：调用底层哈希表的Find方法，根据键查找元素，返回迭代器。 -
operator[]：提供数组下标操作符，方便用户访问或修改元素。如果键不存在，则插入一个默认值（值的默认构造），并返回其引用。 -
erase函数：调用哈希表的Erase方法，根据键删除元素。 -
迭代器支持：通过底层哈希表的迭代器，提供
begin()和end()方法，支持遍历。
unordered_set 的实现
unordered_set 是一种存储唯一元素的无序容器，不存储键值对。由于只需要存储键，因此可以直接使用哈希表，将键作为存储的元素。
在设计 unordered_set 时，需要考虑：
- 元素的存储：直接存储键，类型为
K。 - 哈希函数：用于将键映射到哈希表索引。
- 键的提取器：由于存储的就是键本身，因此键提取器可以直接返回元素本身。
- 迭代器的支持：需要提供迭代器，支持遍历所有元素。
定义键提取器 SetKeyOfT：
template<class K>
struct SetKeyOfT
{const K& operator()(const K& key) const{return key;}
};
定义 unordered_set 类模板：
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
public:typedef K ValueType;typedef HashTable<K, ValueType, SetKeyOfT<K>, Hash> HashTableType;typedef typename HashTableType::iterator iterator;unordered_set() : _ht() {}// 插入元素std::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);}// 迭代器支持iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}private:HashTableType _ht;
};
-
ValueType定义：存储的元素类型就是键类型K。 -
HashTableType定义：使用哈希表，模板参数包括键类型、存储的数据类型（也是K）、键提取器和哈希函数。 -
insert函数：调用哈希表的Insert方法，将键插入哈希表。 -
find函数：根据键查找元素，返回迭代器。 -
erase函数：根据键删除元素。 -
迭代器支持：提供
begin()和end()方法，支持遍历。
为了使 unordered_map 和 unordered_set 能够像标准容器一样使用迭代器遍历，我们需要实现符合 STL 标准的迭代器。在哈希表的实现中，我们已经定义了迭代器 __HTIterator，它能够遍历哈希表中的所有元素。unordered_map 和 unordered_set 的迭代器可以直接使用哈希表的迭代器。
typedef typename HashTableType::iterator iterator;
通过以上的实现，我们成功地基于哈希表构建了 unordered_map 和 unordered_set，并提供了迭代器支持，使其用法与标准库中的容器类似。在这个过程中，我们深入理解了哈希表的工作原理，以及如何利用模板和仿函数实现通用的、可扩展的容器。
