C++之unordered_xxx基于哈希表
由于上层unordered_xxx向哈希表传来的数据并不同，unordered_set是key而unordered_map是pair类型，所以在底层，哈希表处，我们统一用data来同时处理这两种数据。查找操作的目的是在哈希表中查找一个特定的键，并返回与该键关联的值。删除操作的目标是从哈希表中移除一个特定的键值对。代码语言：javascript。代码语言：javascript。代码语言：javasc
·
代码实现
代码语言：javascript
AI代码解释
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
Hash hs;
// 负载因子到1扩容
if (_n == _tables.size())
{
// 扩容
vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
// 遍历旧表，将旧表的数据全部重新映射到新表
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// cur头插到新表
size_t hashi = hs(cur->_kv.first) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(kv.first) % _tables.size();
// 头插
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}3. 注意事项
- 哈希函数的选择：哈希函数的质量直接影响到哈希表的性能。一个好的哈希函数应该能够将键均匀地分布到哈希表的不同槽位中，尽量减少冲突的发生。
- 扩容时机：在本实现中，当哈希表的负载因子达到 1 时进行扩容。负载因子是指哈希表中存储的有效数据个数与哈希表大小的比值。在实际应用中，可以根据具体需求调整扩容时机，例如将负载因子的阈值设置为 0.7 或 0.8 等，以平衡哈希表的空间利用率和操作性能。
4. 查找操作
1. 操作流程
查找操作的目的是在哈希表中查找一个特定的键，并返回与该键关联的值。以下是查找操作的详细步骤：
- 计算哈希值：使用哈希函数
Hash对待查找的键进行哈希运算，得到一个哈希值。然后，将该哈希值对哈希表的大小取模，得到该键在哈希表中的槽位索引。 - 遍历链表：从计算得到的槽位开始，沿着链表逐个节点进行比较，检查每个节点的键是否与待查找的键相等。如果找到匹配的键，则返回对应的节点指针；如果遍历完整个链表仍未找到匹配的键，则返回
nullptr，表示该键不存在于哈希表中。
2. 代码实现
代码语言：javascript
AI代码解释
Node* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
return cur;
cur = cur->_next;
}
return nullptr;
}3. 注意事项
- 查找效率：在拉链法哈希表中，查找操作的效率主要取决于哈希函数的质量和链表的长度。如果哈希函数能够将键均匀分布，且链表长度较短，则查找操作的效率较高。在最理想的情况下，每个槽位的链表长度为 1，查找操作的时间复杂度为 O(1)。
- 键的比较：在查找过程中，需要对键进行比较。因此，键的类型应该支持比较操作。如果键是自定义类型，需要确保重载了
==运算符，以便正确比较键的相等性。
5.删除操作
1. 操作流程
删除操作的目标是从哈希表中移除一个特定的键值对。以下是删除操作的详细步骤：
- 计算哈希值：使用哈希函数
Hash对待删除的键进行哈希运算，得到一个哈希值。然后，将该哈希值对哈希表的大小取模，得到该键在哈希表中的槽位索引。 - 遍历链表查找节点：从计算得到的槽位开始，沿着链表逐个节点进行比较，查找与待删除键匹配的节点。同时，需要记录当前节点的前驱节点，以便在删除操作中修改链表的指针。
- 删除节点：如果找到了匹配的节点，根据当前节点是否为链表的第一个节点，分别进行不同的处理：
- 如果当前节点是链表的第一个节点，将该槽位的头指针指向当前节点的下一个节点。
- 如果当前节点不是链表的第一个节点，将前驱节点的
_next指针指向当前节点的下一个节点。
- 释放内存：删除节点后，使用
delete释放该节点占用的内存。 - 更新数据量计数：将哈希表中存储的有效数据个数
_n减 1。 - 返回删除结果：删除成功返回
true，如果未找到匹配的键，则返回false。
2. 代码实现
代码语言：javascript
AI代码解释
bool Erase(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}3. 注意事项
- 链表的边界情况：在删除操作中，需要特别注意链表的边界情况，例如当前节点是链表的第一个节点或链表为空的情况。正确处理这些边界情况可以避免程序出现错误。
- 内存管理：在删除节点后，一定要记得释放该节点占用的内存，以防止内存泄漏。
总代码一览：
代码语言：javascript
AI代码解释
namespace hash_bucket
{
template<class K, class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K, V>& kv)
:_kv(kv)
, _next(nullptr)
{
}
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable(size_t n = __stl_next_prime(0))
:_tables(n, nullptr)
, _n(0)
{
}
~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;
}
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
Hash hs;
// 负载因子到1扩容
if (_n == _tables.size())
{
// 扩容
vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
// 遍历旧表，将旧表的数据全部重新映射到新表
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// cur头插到新表
size_t hashi = hs(cur->_kv.first) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(kv.first) % _tables.size();
// 头插
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
Node* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n; // 实际存储有效数据个数
};
}二.unordered_xxx自我实现部分
2.1unordered_xxx的结构
unordered_xxx底层都是哈希表，通过调用哈希表的接口，进而实现。在这部分，基本与map和set自我实现部分类似，这里直接给出结构。
1.unordered_set结构
代码语言：javascript
AI代码解释
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;
};2.unordered_map结构
代码语言：javascript
AI代码解释
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);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};2.2修改自我实现的哈希表
由于上层unordered_xxx向哈希表传来的数据并不同，unordered_set是key而unordered_map是pair类型，所以在底层，哈希表处，我们统一用data来同时处理这两种数据。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
11
0- 0
已为社区贡献111条内容
所有评论(0)