经典微网站,网站备案如何转移,如何开发电子商务网站,西安米德建站#x1f4dd;个人主页#x1f339;#xff1a;Eternity._ ⏩收录专栏⏪#xff1a;C “ 登神长阶 ” #x1f921;往期回顾#x1f921;#xff1a;哈希底层 #x1f339;#x1f339;期待您的关注 #x1f339;#x1f339; ❀哈希 #x1f4d2;1. 改造 HashTable… 个人主页Eternity._ ⏩收录专栏⏪C “ 登神长阶 ” 往期回顾哈希底层 期待您的关注 ❀哈希 1. 改造 HashTable2. HashTable的迭代器迭代器基本设计operator()begin()与end()⭐迭代器的构造 3. Unordered_Set的模拟实现Unordered_Set的基本设计Unordered_Set测试 4. Unordered_Map的模拟实现Unordered_Map的基本设计Unordered_Map测试 5. 总结 前言在C标准库中unordered_map和unordered_set作为高效的无序容器以其基于哈希表的实现方式为数据的快速查找、插入和删除提供了强有力的支持。这些容器通过哈希函数将元素映射到数组的索引上从而实现了接近O(1)的平均时间复杂度操作极大地提升了程序性能。然而尽管它们的使用极为便捷了解这些容器背后的工作原理和模拟实现过程对于深入理解数据结构、算法设计以及优化程序性能都至关重要 本文旨在带领读者踏上一场探索之旅从理论到实践逐步揭开unordered_map和unordered_set的神秘面纱。我们将不仅探讨这些容器的基本概念和特性详细阐述模拟实现的过程更重要的是通过模拟实现这两个容器深入理解其内部机制包括哈希表的构建、哈希函数的选择、冲突解决策略、动态扩容与再哈希等核心问题 本篇我们采用开散列的方式来模拟实现unordered帮助读者掌握哈希的构建与使用如果大家还不太了解哈希建议先去阅读我的上一篇文章
让我们一起踏上学习的旅程探索它带来的无尽可能 1. 改造 HashTable 改造HashTable以适配unordered_map和unordered_set容器主要涉及到如何根据这两种容器的特性来设计和实现HashTable节点的存储以及相应的操作。unordered_map和unordered_set的主要区别在于它们存储的元素类型map存储键值对key-value pairs而set仅存储唯一的键值通常是键本身作为值。尽管如此它们在底层数据结构如HashTable的实现上有很多相似之处 改造内容 Kkey的类型T如果是unordered_map则为pairK, V; 如果是unordered_set则为KKeyOfT通过T来获取key的一个仿函数类HF: 哈希函数仿函数对象类型哈希函数使用除留余数法需要将Key转换为整形数字才能 取模 // unordered_set 与 unordered_set
// unordered_set - HashTableK, K
// unordered_map - HashTableK, pairK, VHashTable的节点设计
templateclass T
struct HashNode
{HashNode* _next; // 存放数据T _data; // 指向节点的下一个元素HashNode(const T data):_data(data) ,_next(nullptr){}
};而在上一篇文章中我们有介绍了一个关于非整形求关键值的仿函数HashFunc在模拟实现是可以直接加在模拟实现的类上。
// hash_bucket是一个命名空间
// KeyOfT 和 Hash则是简化特定运算的仿函数
hash_bucket::HashTableK, K, SetKeyOfT, Hash _ht;
hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;适用于unordered的成员函数
代码示例(C)
// 修改了返回类型
pairiterator, bool Insert(const T data)
{Hash hf;KeyOfT kot;// 判断值是否存在iterator it Find(kot(data));if (it ! end()){// 插入失败返回已有节点的迭代器和false return make_pair(it, false);}// 负载因子if (_n _tables.size()){vectorNode* newTables;newTables.resize(_tables.size() * 2, nullptr);// 遍历旧表for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;// 挪动到新表size_t hashi hf(kot(cur-_data)) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi hf(kot(data)) % _tables.size();Node* newnode new Node(data);// 头插newnode-_next _tables[hashi];_tables[hashi] newnode;_n;// 插入成功返回新节点的迭代器和ture return make_pair(iterator(newnode, this, hashi), true);
}// 返回类型修改成了迭代器
iterator Find(const K key)
{Hash hf;KeyOfT kot;size_t hashi hf(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur, this, hashi);}cur cur-_next;}return end();
}2. HashTable的迭代器
迭代器基本设计
代码示例(C)
// 为了实现简单在哈希桶的迭代器类中需要用到hashBucket本身所以我们要进行一下前置声明并且我们在 HashTable 中也要设置一个友元(friend)//前置声明
templateclass K, class T, class KeyOfT, class Hash
class HashTable;// 通过模板来达到const的迭代器的复用
templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash
struct __HTIterator
{typedef HashNodeT Node;typedef __HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self;Node* _node;Ref operator*(){return _node-_data;}Ptr operator-(){return (_node-_data);}bool operator!(const Self s){return _node ! s._node;}
};templateclass K, class T, class KeyOfT, class Hash HashFuncK
class HashTable
{typedef HashNodeT Node;// 友元templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashfriend struct __HTIterator;...... // 其他待实现的函数
}operator() 因为哈希桶在底层是单链表结构所以哈希桶的迭代器不需要operator–()操作在operator()的设计上我们的问题是在走完这个桶之后如何找到下一个桶因此我们需要记录来方便寻找于是我们引入了两个变量 // HashTable
const HashTableK, T, KeyOfT, Hash* _pht;
// 当前桶的位置
size_t _hashi;代码示例(C) const HashTableK, T, KeyOfT, Hash* _pht;
size_t _hashi;Self operator()
{if (_node-_next){// 当前桶没走完移动到下一个节点_node _node-_next;}else{// 初步尝试方法// 当前桶走完了走下一个桶/*Hash hf;KeyOfT kot;size_t hashi hf(kot(_node-_data)) % _pht._tables.size();*/// 当前桶走完了走下一个桶_hashi;while (_hashi _pht-_tables.size()) // 判断当前桶的位置是否合法{// 判断当前桶是否存在数据if (_pht-_tables[_hashi]){_node _pht-_tables[_hashi];break;}_hashi;}// 走完了if (_hashi _pht-_tables.size()){_node nullptr;}}return *this;
}begin()与end() 关于构建迭代器的begin()与end()当我们模拟实现const版本时又会遇到新的问题const版本在调用构造时调不动因为我最开始实现的构造函数不是const版本当const版本想要调用构造函数时这时造成了权限的扩大因此为了解决这个问题我们重载了构造函数 代码示例(C)
// 普通版本
typedef __HTIteratorK, T, T, T*, KeyOfT, Hash iterator;
// const 版本
typedef __HTIteratorK, T, const T, const T*, KeyOfT, Hash const_iterator;iterator begin()
{for (size_t i 0; i _tables.size(); i){if (_tables[i]){return iterator(_tables[i], this, i);}}return end();
}iterator end()
{return iterator(nullptr, this, -1);
}const_iterator begin() const
{for (size_t i 0; i _tables.size(); i){if (_tables[i]){return const_iterator(_tables[i], this, i);}}return end();
}// this- const HashTableK, T, KeyOfT, Hash*
const_iterator end() const
{return const_iterator(nullptr, this, -1);
}⭐迭代器的构造
因为我们引入了两个新的变量所以此次构造与以往不同
代码示例(C)
// 非const版本
__HTIterator(Node* node, HashTableK, T, KeyOfT, Hash* pht, size_t hashi):_node(node), _pht(pht), _hashi(hashi)
{}// const版本
__HTIterator(Node* node, const HashTableK, T, KeyOfT, Hash* pht, size_t hashi):_node(node), _pht(pht), _hashi(hashi)
{}3. Unordered_Set的模拟实现
Unordered_Set的基本设计
代码示例(C)
templateclass K, class Hash HashFuncK
class unordered_set
{struct SetKeyOfT{const K operator()(const K key){return key;}};public:// 因为 unordered_set的特性K是不能够修改的// 所以我们在 const迭代器和非const迭代器上都用 const来修饰K来起到不能修改K的特点typedef typename hash_bucket::HashTableK, K, SetKeyOfT, Hash::const_iterator iterator;typedef typename hash_bucket::HashTableK, K, SetKeyOfT, Hash::const_iterator const_iterator;pairconst_iterator, bool insert(const K key){auto ret _ht.Insert(key);return pairconst_iterator, bool(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi),ret.second);}// 因为用到的都是const迭代器所以非const迭代器我们可以不写/*iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}*/const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}iterator find(const K key){return _ht.Find(key);}bool erase(const K key){return _ht.Erase(key);}private:hash_bucket::HashTableK, K, SetKeyOfT, Hash _ht;
};Unordered_Set测试
代码示例(C)
void TestSet()
{unordered_setint us;us.insert(1);us.insert(2);us.insert(6);us.insert(55);us.insert(3);unordered_setint::iterator it us.begin();while (it ! us.end()){// *it 5;cout *it ;it;}cout endl;
}4. Unordered_Map的模拟实现
Unordered_Map的基本设计
代码示例(C)
templateclass K, class V, class Hash HashFuncK
class unordered_map
{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};
public:// 在 unordered_map我们就只需要考虑 kv.first不能修改// 但是 kv.first-second是可以修改的因此我们需要将 K用 const修饰typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT::iterator iterator;pairiterator, bool insert(const pairK, V kv){return _ht.Insert(kv);}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}// 重载operator[]V operator[] (const K key){// 当_ht中没有就实现插入pairiterator, bool ret _ht.Insert(make_pair(key, V()));return ret.first-second;}const V operator[] (const K key) const{pairiterator, bool ret _ht.Insert(make_pair(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::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;
};Unordered_Map测试
代码示例(C)
void TestMap()
{unordered_mapstring, string dict;dict.insert(make_pair(sort, 排序));dict.insert(make_pair(left, 左边));dict.insert(make_pair(right, 右边));for (auto kv : dict){// kv.first x;kv.second x;cout kv.first : kv.second endl;}cout endl;
}5. 总结
在本文的探索之旅中我们深入剖析了unordered_map与unordered_set的内部机制并通过模拟实现这两个容器不仅加深了对哈希表这一重要数据结构的理解还锻炼了编程能力和问题解决能力 通过模拟实现我们亲手构建了哈希表从简单的数组加链表结构到动态扩容、再哈希等高级特性的实现每一步都充满了挑战与收获。这个过程中我们深刻体会到了数据结构设计的精妙之处也学会了如何在实践中不断优化和调整我们的设计 unordered_map与unordered_set等无序容器将在更多领域发挥重要作用。随着技术的不断发展我们也期待看到更多高效、稳定、易用的容器实现出现。
同时我们也希望读者能够保持对新技术、新知识的好奇心和求知欲不断探索、不断学习、不断进步 希望本文能够为你提供有益的参考和启示让我们一起在编程的道路上不断前行 谢谢大家支持本篇到这里就结束了祝大家天天开心
