【C++】深入哈希表核心：从改造到封装，解锁 unordered_set 与 unordered_map 的终极奥义！

embedded/2024/11/26 17:24:43/

文章目录

  • 修改哈希表
    • 模板参数
    • 迭代器
    • ``HashTable`` 的默认成员函数
    • ``HashTable`` 迭代器相关函数
    • ``HashTable`` 的 ``Insert`` 函数
    • ``HashTable`` 的 ``Find``函数
    • ``HashTable`` 的 ``Erase``函数
  • 封装 unordered_set
  • 封装 unordered_map
  • 测试 unordered_set 和 unordered_map

修改哈希表

我们基于链地址法实现的哈希表来封装实现 unordered_set 和 unordered_map ，但是由于实现的哈希表是 Key-Value 结构的并且我们的实现的哈希表缺少了迭代器，所以我们需要对之前实现的哈希表进行改造。

模板参数

HashNode
节点里不再存储确定的 pair<K, V> ，而是类型 T ，代表代表存储的数据可能是 key 或者 key-Value 。

template<class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}
};

HashTable

template<class K, class T, class KeyOfT, class hash = HashFunc<K>>
class HashTable
  • K ：代表的是 key
  • T ：代表是存的可能是 key 或者 key-value
  • KeyOfT ：仿函数，目的是拿到 T 里面的 key

迭代器

哈希表的迭代器其实就是对节点指针进行封装，而且是单向迭代器，只需实现 ++ 即可。

//哈希表与迭代器相互依赖，需要前置声明
template<class K, class T, class KeyOfT, class hash>
class HashTable;template<class K, class T, class KeyOfT, class Hash, class Ref, class Ptr>
struct HTIterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef HTIterator<K, T, KeyOfT, Hash, Ref, Ptr> Self;Node* _node;//需要用到哈希表里的数组大小，故需要指向哈希表的指针const HT* _pht;HTIterator(Node* node, const HT* pht):_node(node),_pht(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){//...} 
};

由于哈希表的特殊性，其迭代器的 ++ 较为复杂，也是实现哈希表迭代器的重点。
重载 ++
迭代器的++分为两种情况：

  • 当前迭代器不是哈希桶的最后一个节点，直接走到下一个节点。
  • 当前迭代器是哈希桶的最后一个节点，需要找下一个不为空的哈希桶的头节点。
    在这里插入图片描述
    在这里插入图片描述
Self& operator++()
{//当前哈希桶还有数据，直接到下一个节点if (_node->_next){_node = _node->_next;}//当前哈希桶走完了，寻找下一个不为空的哈希桶else if (_node->_next == nullptr){KeyOfT kot;Hash hashfunc;size_t hashi = hashfunc(kot(_node->_data)) % _pht->_tables.size();++hashi;while (hashi < _pht->_tables.size()){_node = _pht->_tables[hashi];//找到了下一个桶if (_node)break;else++hashi;}//处理迭代器在最后一个不为空的哈希桶的最后一个节点的情况if (hashi == _pht->_tables.size()){_node = nullptr;}}return *this;
}Self& operator++(int)
{Self tmp = *this;++(*this);return tmp;
}

HashTable 的默认成员函数

//构造函数
HashTable(): _tables(__stl_next_prime(0)), _n(0)
{}//拷贝构造函数
HashTable(const HashTable<K, T, KeyOfT, hash>& ht)
{_tables.resize(ht._tables.size());for (auto& data : ht){Insert(data);}
}//赋值重载
HashTable<K, T, KeyOfT, hash>& operator=(const HashTable<K, T, KeyOfT, hash>& ht)
{vector<Node*> newtables(ht._tables.size());for (size_t i = 0; i < ht._tables.size(); ++i){Node* cur = ht._tables[i];while (cur){Node* newnode = new Node(cur->_data);newnode->_next = newtables[i];newtables[i] = newnode;cur = cur->_next;}}_tables.swap(newtables);return *this;
}
//析构函数
~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;}
}

HashTable 迭代器相关函数

typedef HTIterator<K, T, KeyOfT, hash, T&, T*> Iterator;
typedef HTIterator<K, T, KeyOfT, hash, const T&, const T*> Const_Iterator;Iterator begin()
{if (_n == 0)return end();for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];if (cur){return Iterator(cur, this);}}return end();
}Iterator end()
{return Iterator(nullptr, this);
}Const_Iterator begin() const
{if (_n == 0)return end();for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];if (cur){return Const_Iterator(cur, this);}}}Const_Iterator end() const
{return Const_Iterator(nullptr, this);
}

begin() 对应的迭代器应该是哈希表中第一个非空的哈希桶的头节点，需要特别处理。
end() 直接返回空指针对应的迭代器即可。

HashTable 的 Insert 函数

对于 Insert 函数，只需将其返回值改成迭代器与布尔值的 pair ，再将原本关于使用到 key 的地方套一层 KeyOfT 实例化出来的对象即可。

void CheckCapacity()
{if (_n == _tables.size()){//把哈od希桶里的链表每个节点拆下来插入newht效率太低了/*HashTable<K, V> newht;newht._tables.resize(__stl_next_prime(_tables.size() + 1));for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){newht.Insert(cur->_kv);cur = cur->_next;}}_tables.swap(newht._tables);*/KeyOfT kot;hash hashfunc;vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hashfunc(kot(cur->_data)) % newtables.size();//头插cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}
}pair<Iterator, bool> Insert(const T& data)
{KeyOfT kot;Iterator it = Find(kot(data));//不等于end()说明哈希表里有重复元素if (it != end())return { it, false };//检查是否需要扩容CheckCapacity();hash hashfunc;size_t hashi = hashfunc(kot(data)) % _tables.size();Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return { Iterator(newnode, this), false };
}

HashTable 的 Find函数

将返回值改为迭代器，原本用到 key 的地方套一层 KeyOfT 实例化出来的对象即可。

Iterator Find(const K& key)
{KeyOfT kot;hash hashfunc;size_t hashi = hashfunc(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return Iterator(cur, this);}cur = cur->_next;}//没找到就返回return end();
}

HashTable 的 Erase函数

跟 Insert 函数的处理基本一样，不多叙述了。

bool Erase(const K& key)
{KeyOfT kot;hash hashfunc;size_t hashi = hashfunc(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){//删除头节点的情况if (prev == nullptr){_tables[hashi] = cur->_next;}//非头节点的情况else{prev->_next = cur->_next;}delete cur;--_n;return true;}else {prev = cur;cur = cur->_next;}}return false;
}

unordered_setfont_358">封装 unordered_set

对 HashTable 的迭代器和函数进行封装即可，灰常简单。

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>::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();}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;
};

unordered_mapfont_415">封装 unordered_map

也是对 HashTable 的迭代器和函数进行封装，但有所不同的是，还需要多重载 [] ，也比较简单。

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>::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();}pair<iterator, bool> Insert(const pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = Insert({ key, V() });return ret.first->second;}iterator Find(const K& key){return _ht.Find(key);}bool Erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, hash> _ht;
};

unordered_set__unordered_mapfont_479">测试 unordered_set 和 unordered_map

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

拜拜，下期再见😏

摸鱼ing😴✨🎞
请添加图片描述
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=3kzw99ffumyoo


http://www.ppmy.cn/embedded/140669.html

相关文章

虚拟浏览器可以应对哪些浏览器安全威胁？

虚拟浏览器可以应对哪些浏览器安全威胁？

众所周知&#xff0c;互联网安全对企业和个人都至关重要。 因此&#xff0c;在有害的网络内容和终端用户之间必须有一道屏障。浏览器隐私是浏览器安全的一个重要组成部分。不用说也知道&#xff0c;大多数常用的浏览器&#xff0c;都会把最终用户的数据出售给第三方&#xff0c…
阅读更多...
git教程

git教程

文章目录 简介&#xff1a;使用教程&#xff1a;&#xff08;1&#xff09;安装git&#xff1a;&#xff08;2&#xff09;设置用户名和邮箱作为标识符&#xff1a;&#xff08;3&#xff09;建立本地仓库&#xff1a;本地仓库作用&#xff1a;&#xff08;1&#xff09;将文件…
阅读更多...
springboot获取配置文件中的值

springboot获取配置文件中的值

概括 在开发过程中&#xff0c;对于一些通用的配置&#xff0c;通常会定在一个配置文件中。通常为application.properties或者application.yml文件中。我们只需要在需要使用的地方通过注解直接获取即可。 使用 在springboot中可以通过使用value注解来读取配置文件中的属性。…
阅读更多...
随手记：鼠标触顶方法

随手记：鼠标触顶方法

// 鼠标触顶方法 scrollMethod() { window.onscroll () > { let t document.documentElement.scrollTop || document.body.scrollTop; if(t > 10) { this.positionStyle.top 0px; }else{ this.positionStyle.top 128px; } } },
阅读更多...
Spring Boot OA：企业办公自动化的高效路径

Spring Boot OA：企业办公自动化的高效路径

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了企业OA管理系统的开发全过程。通过分析企业OA管理系统管理的不足&#xff0c;创建了一个计算机管理企业OA管理系统的方案。文章介绍了企业OA管理系统的系统分析部…
阅读更多...
英伟达推出了全新的小型语言模型家族——Hymba 1.5B

英伟达推出了全新的小型语言模型家族——Hymba 1.5B

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
高性能存储SIG月度动态：重构和优化fuse，推动containerd社区支持erofs

高性能存储SIG月度动态：重构和优化fuse，推动containerd社区支持erofs

本次月报综合了 SIG 在 9、10 两个月的工作进展&#xff0c;包含多项新特性、优化、Bugfix 等。 一、SIG 整体进展 重构和优化 fuse 代码&#xff0c;为接下来的 writeback 性能优化特性做准备。 containerd erofs snapshotter PR 已提交&#xff0c;社区 review 讨论中。 …
阅读更多...
介绍一下strcat(c基础)

介绍一下strcat(c基础)

hi , I am 36 适合对象c语言初学者 strcat(arr1,arr2); 是使arr2的内容接到arr1 格式 #include<string.h> strcat(arr1,arr2) arr2首元素会从arr1中的‘\0’开始替换。 返回值为arr1.(即arr1数组的首地址)链接分享一下arr的意义(c基础)-CSDN博客​​​​​​ …
阅读更多...
最新文章

Copyright @ 2022~2023