全自动建站系统源码,wordpress吧,做公众号app 网站 app,做设计_素材网站有哪文章目录 一、引言二、C unordered系列的无序关联式容器概览三、基于哈希桶的C unordered系列数据结构模拟实现1、unordered_map的模拟实现2、unordered_set的模拟实现3、哈希桶及其迭代器实现的代码 四、扩展与应用1. 自定义哈希函数2. 其他unordered数据结构unordered_multim… 文章目录 一、引言二、C unordered系列的无序关联式容器概览三、基于哈希桶的C unordered系列数据结构模拟实现1、unordered_map的模拟实现2、unordered_set的模拟实现3、哈希桶及其迭代器实现的代码 四、扩展与应用1. 自定义哈希函数2. 其他unordered数据结构unordered_multimap与unordered_mapunordered_multiset与unordered_set 3. 实际应用案例分析 一、引言
哈希函数与哈希桶是计算机科学中用于实现高效数据检索的重要工具。在之前的博客中我们已经详细探讨了哈希的基本概念、哈希函数的构造方法以及哈希桶的工作原理等内容。在本篇博客中我们将进一步深入探索C中的unordered系列数据结构并利用之前介绍的哈希桶原理进行模拟实现。
C11提供的unordered系列数据结构如unordered_map、unordered_set等是STLStandard Template Library中提供的一组非常重要的容器。它们以哈希表为基础通过哈希函数将键映射到存储位置从而实现了快速的插入、删除和查找操作。这些数据结构在处理大规模数据时能够展现出比有序容器如map、set更高的性能。在C11中提供了的4个unordered系列的关联式容器。这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同。
本文将使用哈希桶对C unordered系列数据结构进行模拟实现。文本前置内容请点击此处 哈希技术解析从哈希函数到哈希桶迭代器的全面指南 二、C unordered系列的无序关联式容器概览
1. unordered_map与unordered_multimap简介
数据结构特性
unordered_mapC STL中的一个无序关联容器它存储的元素是键值对并且每个键在容器中唯一。其内部实现通常基于哈希表通过哈希函数将键映射到存储位置从而提供了常数时间复杂度的插入、删除和查找操作。unordered_multimap与unordered_map类似但它允许键在容器中出现多次即可以存储多个具有相同键的键值对。
应用场景
unordered_map当需要快速根据键查找对应的值时或者当键的唯一性很重要时unordered_map是一个很好的选择。例如在缓存系统、词频统计等场景中unordered_map可以高效地存储和检索键值对。unordered_multimap当需要存储多个具有相同键的键值对时可以使用unordered_multimap。这在某些特定的应用场景中很有用比如记录一个单词在文本中出现的所有位置。
2. unordered_set与unordered_multiset简介
数据结构特性
unordered_set是一个无序集合它存储的元素是唯一的不包含重复的元素。其内部实现也基于哈希表通过哈希函数将元素映射到存储位置从而实现了常数时间复杂度的插入、删除和查找操作。unordered_multiset与unordered_set类似但它允许集合中包含重复的元素。
应用场景
unordered_set当需要快速检查一个元素是否存在于集合中或者需要维护一个不包含重复元素的集合时unordered_set是一个合适的选择。例如在算法中去除重复元素、实现并集和交集运算等场景unordered_set都能提供高效的解决方案。unordered_multiset当需要统计元素的出现次数或者需要维护一个包含重复元素的集合时可以使用unordered_multiset。这在某些特定的数据处理和分析任务中可能会很有用。
总的来说C的unordered系列数据结构提供了高效的无序存储和检索机制适用于各种需要快速处理大量数据的场景。通过合理地选择和使用这些数据结构可以显著提高程序的性能和效率。
非unordered系列数据结构点击此处深入解析C树形关联式容器map、set及其衍生容器的使用与原理-CSDN博客 三、基于哈希桶的C unordered系列数据结构模拟实现
1、unordered_map的模拟实现 使用自定义哈希桶存储键值对 unordered_map的简化模板类定义注hash_bucket是我实现的哈希桶所在的命名空间 templateclass K, class V, class Hash HashFuncK
class unordered_map
{struct MapKeyOfT {const K operator()(const pairK, V kv) { return kv.first; }};
public:typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::iterator iterator;// ....
private:hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;
};模板参数K键Key的类型。V值Value的类型。Hash哈希函数Hash Function的类型默认为HashFuncK即默认以K来计算哈希位置。该参数也在哈希桶部分有介绍。 内部结构体 MapKeyOfT这个结构体定义了一个调用运算符用于从pairK, V中提取键。这是哈希表内部可能需要的以便能够根据键来定位存储的元素。 迭代器类型定义typedef语句定义了一个迭代器类型表示指向hash_bucket::HashTable中元素的迭代器。这个迭代器类型用于公开unordered_map的接口以便用户可以遍历集合中的元素。 私有成员_ht是unordered_map的私有成员其类型为hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash 。这个哈希表用于存储键值对并根据键的哈希值来定位元素。 实现插入、查找、删除等基本操作 operator[]用于访问或插入一个键值对。如果键k已经存在于unordered_map中则该函数返回该键对应的值的引用如果键k不存在则该函数插入一个新的键值对键为k值为V()的默认构造实例并返回新插入值的引用 V operator[](const K k) {pairiterator, bool it insert({ k,V() });return (*it.first).second;//return (*((this-insert(make_pair(k, V()))).first)).second;
}在这段代码中insert成员函数被调用它尝试插入一个键值对到unordered_map中。insert返回一个pairiterator, bool其中迭代器指向新插入的元素或已存在的元素布尔值表示是否实际插入了新元素。由于unordered_map不允许重复的键所以对于operator[]来说这个布尔值总是true除非在插入过程中发生了异常。然后通过解引用迭代器it.first来获取键值对的引用并返回其second成员即值的引用。 pairiterator,bool insert(const pairK, V kv) { return _ht.Insert(kv); }
bool erase(const K k) { return _ht.Erase(k); }
iterator find(const K k) { return _ht.Find(k); }insert函数接收一个pairK, V类型的参数并调用_ht.Insert方法尝试将其插入哈希表中。它返回一个pairiterator, bool其中迭代器指向新插入的元素或已存在的元素布尔值表示是否成功插入了新元素。erase函数接收一个键类型的参数并调用_ht.Erase方法尝试从哈希表中删除具有该键的键值对。它返回一个布尔值表示删除操作是否成功。find函数接收一个键类型的参数并调用_ht.Find方法查找具有该键的键值对。如果找到它返回一个指向该键值对的迭代器否则返回end()迭代器。 封装哈希桶迭代器 我们的哈希桶已实现了绝大部分的功能因此我们此处仅仅调用其函数即可。 typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::iterator iterator;
iterator begin() { return _ht.begin(); }
iterator end() { return _ht.end(); }2、unordered_set的模拟实现 利用哈希桶存储唯一元素 unordered_set的简化模板类定义注hash_bucket是我实现的哈希桶所在的命名空间 templateclass K, class Hash HashFuncK
class unordered_set{struct SetKeyOfT{const K operator()(const K key) { return key; }};
public:typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::iterator iterator;//...
private:hash_bucket::HashTableK, const K, SetKeyOfT, Hash _ht;
};模板参数unordered_set模板接受两个类型参数K和Hash。K是集合中元素的键类型Hash是哈希函数类型用于计算键的哈希值。默认情况下如果没有提供Hash它将使用HashFuncK作为哈希函数。 内部结构体SetKeyOfT这是一个简单的函数对象或称为仿函数它重载了operator()以返回其输入的引用。在unordered_set的上下文中它用于从键中提取键本身在这种情况下键就是元素本身。这是为了与hash_bucket::HashTable的接口保持一致该接口可能期望一个可以从某种类型中提取键的函数对象。 迭代器类型定义使用typedef语句定义了一个名为iterator的类型别名它表示指向hash_bucket::HashTable中元素的迭代器。这个迭代器类型用于公开unordered_set的接口以便用户可以遍历集合中的元素。 私有成员变量_ht是unordered_set的一个私有成员变量其类型为hash_bucket::HashTableK, const K, SetKeyOfT, Hash。这表示它是一个哈希表用于存储unordered_set中的元素。键类型是const K因为集合中的元素不应被修改在unordered_set中元素是唯一的并且一旦插入就不能被修改。SetKeyOfT用于从键中提取键而Hash是用于计算哈希值的函数。 实现集合的基本操作 pairiterator,bool insert(const K k) { return _ht.Insert(k); }
bool erase(const K k) { return _ht.Erase(k); }
iterator find(const K k) { return _ht.Find(k); }insert函数尝试在集合中插入一个元素并返回一个pairiterator, bool其中迭代器指向新插入的元素或已存在的元素布尔值表示是否实际插入了新元素。由于unordered_set不允许重复元素所以如果尝试插入一个已经存在的元素该函数不会插入新元素而是返回指向已存在元素的迭代器并将布尔值设置为false。 封装哈希桶迭代器 此处与unordered_map相同。 typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::iterator iterator;
iterator begin() { return _ht.begin(); }
iterator end() { return _ht.end(); }3、哈希桶及其迭代器实现的代码
该文已详细叙述哈希桶相关内容 -深入解析C树形关联式容器map、set及其衍生容器的使用与原理-CSDN博客
templateclass K
struct HashFunc {size_t operator()(const K key) { return (size_t)key; }
};
template
struct HashFuncstring {size_t operator()(const string s) {size_t hashi 0;for (auto e : s) {hashi e;hashi * 31;}return hashi;}
};
namespace hash_bucket
{templateclass Tstruct HashNode {HashNodeT* _next;T _data;HashNode(const T data) :_next(nullptr), _data(data) {}};templateclass K, class T, class KeyOfT, class Hash class HashTable;templateclass K, class T, class KeyOfT, class Hashstruct __HTIterator {typedef HashNodeT Node;typedef HashTableK, T, KeyOfT, Hash HT;typedef __HTIteratorK, T, KeyOfT, Hash Self;Node* _node;HT* _ht;__HTIterator(Node* node, HT* ht) :_node(node), _ht(ht) {}T operator*() { return _node-_data; }T* operator-() { return _node-_data; }bool operator!(const Self s)const { return _node ! s._node; }bool operator(const Self s) const { return _node s._node; }Self operator() {if (_node-_next) {_node _node-_next;}else {KeyOfT kot;Hash hs;size_t hashi hs(kot(_node-_data)) % _ht-_tables.size();hashi;while (hashi _ht-_tables.size()) {if (_ht-_tables[hashi]) {_node _ht-_tables[hashi];break;}hashi;}if (hashi _ht-_tables.size()) {_node nullptr;}}return *this;}};templateclass K, class T, class KeyOfT, class Hash class HashTable {typedef HashNodeT Node;templateclass K, class T, class KeyOfT, class Hashfriend struct __HTIterator;public:typedef __HTIteratorK, T, KeyOfT, Hash iterator;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); }HashTable()//:kot(KeyOfT()),hs(Hash()){_tables.resize(10, nullptr);_n 0;kot KeyOfT();hs Hash();} ~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;}}pairiterator,bool Insert(const T data) {iterator it Find(kot(data));if (it ! end())return { it,false};if (_n _tables.size()) {vectorNode* newTables(_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 hs(kot(cur-_data)) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi hs(kot(data)) % _tables.size();Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return { iterator(newnode, this),true };}bool Erase(const K key) {size_t hashi hs(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur) {if (kot(cur-_data) key) {// 删除if (prev)prev-_next cur-_next;else_tables[hashi] cur-_next;delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;}iterator Find(const K key) {size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];while (cur) {if (kot(cur-_data) key)return iterator(cur, this);cur cur-_next;}return iterator(nullptr, this);}private:vectorNode* _tables;size_t _n;KeyOfT kot; Hash hs;};
}四、扩展与应用
1. 自定义哈希函数
在C中当使用std::unordered_set、std::unordered_map等无序容器时哈希函数起着至关重要的作用。默认的哈希函数对于许多类型都工作得很好但有时对于自定义类型或特殊需求默认的哈希函数可能不是最优的甚至可能导致性能下降或哈希冲突过多。
为特定类型设计哈希函数
对于自定义类型需要提供一个哈希函数该函数接受自定义类型的对象作为参数并返回一个足够大的整数值。设计哈希函数时需要确保
不同的对象尽可能映射到不同的哈希值。相同的对象总是映射到相同的哈希值。哈希函数的计算应该尽可能快。
例如对于一个包含字符串和整数的自定义类型可以使用字符串的哈希值和整数的哈希值的组合作为整体的哈希值。
2. 其他unordered数据结构
除了unordered_set和unordered_map之外标准库还提供了unordered_multimap和unordered_multiset。这两个数据结构分别允许存储具有相同键的多个值对和多个值。
unordered_multimap与unordered_map
unordered_multixxx与unordered_xxx的主要区别在于前者允许键重复而后者不允许。具体来说
键的重复性unordered_map中的每个键都是唯一的每个键只能映射到一个值。而unordered_multimap允许键的重复这意味着同一个键可以映射到多个值。使用场景当你需要存储键值对并且每个键只对应一个值时unordered_map是合适的选择。而如果你需要存储的键值对中有多个键是相同的并且每个键对应多个值那么unordered_multimap更为合适。内部实现两者都使用哈希表作为底层数据结构以实现快速的插入、删除和查找操作。但由于unordered_multimap允许键重复因此在处理冲突和存储键值对时可能需要更复杂的逻辑。
unordered_multiset与unordered_set
元素的重复性unordered_set中的每个元素都是唯一的不允许有重复元素。而unordered_multiset则允许元素重复即集合中可以包含多个相同的元素。使用场景当你需要存储一个不包含重复元素的集合时unordered_set是合适的选择。而如果你需要存储的集合中可能包含重复的元素那么unordered_multiset更为合适。内部实现两者都使用哈希表作为底层数据结构以实现快速的插入、删除和查找操作。但由于unordered_multiset允许元素重复因此在处理冲突和存储元素时可能需要更复杂的逻辑。
在实际应用中根据具体的需求和数据特性选择合适的数据结构是非常重要的。例如在需要统计词频的场景中由于一个单词可能在文本中出现多次因此使用unordered_multiset来存储单词和它们的出现次数会更合适。而在某些需要唯一标识的场景中如用户ID的存储使用unordered_set来确保ID的唯一性则更为合适。
3. 实际应用案例分析
unordered系列数据结构在实际项目中有着广泛的应用特别是在需要快速查找和插入的场景中。
案例一词频统计
在处理大量文本数据时词频统计是一个常见的任务。可以使用unordered_map来存储每个单词及其出现的次数。由于哈希表提供了平均常数时间的查找和插入操作因此这种方法在处理大规模文本时非常高效。
案例二缓存系统
在缓存系统中通常需要快速查找和插入键值对。unordered_map或unordered_set可以用作缓存的底层数据结构提供快速的访问速度。当缓存达到最大容量时还可以使用这些数据结构来高效地执行替换策略如LRU缓存替换。
本文完整代码 unordered_map与unordered_set · 比奇堡的Zyb/每日学习 - 码云 - 开源中国 (gitee.com)
