📝个人主页🌹：Eternity._

⏩收录专栏⏪：C++ “ 登神长阶 ”

🤡往期回顾🤡：哈希底层

🌹🌹期待您的关注 🌹🌹

❀哈希

📒1. 改造 HashTable📜2. 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的神秘面纱。我们将不仅探讨这些容器的基本概念和特性，详细阐述模拟实现的过程，更重要的是，通过模拟实现这两个容器，深入理解其内部机制，包括哈希表的构建、哈希函数的选择、冲突解决策略、动态扩容与再哈希等核心问题

本篇我们采用<code>开散列的方式来模拟实现unordered，帮助读者掌握哈希的构建与使用，如果大家还不太了解哈希，建议先去阅读我的上一篇文章

让我们一起踏上学习的旅程，探索它带来的无尽可能！

📒1. 改造 HashTable

改造HashTable以适配unordered_map和unordered_set容器，主要涉及到如何根据这两种容器的特性来设计和实现HashTable节点的存储以及相应的操作。unordered_map和unordered_set的主要区别在于它们存储的元素类型：map存储键值对（key-value pairs），而set仅存储唯一的键值（通常是键本身作为值）。尽管如此，它们在底层数据结构（如HashTable）的实现上有很多相似之处

改造内容：

K：key的类型T：如果是unordered_map，则为pair<K, V>; 如果是unordered_set，则为KKeyOfT：通过T来获取key的一个仿函数类HF: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能

取模

// unordered_set 与 unordered_set

// unordered_set -> HashTable<K, K>

// unordered_map -> HashTable<K, pair<K, V>>

HashTable的节点设计：

template<class T>

struct HashNode

{

HashNode* _next; // 存放数据

T _data; // 指向节点的下一个元素

HashNode(const T& data)

:_data(data)

,_next(nullptr)

{ }

};

而在上一篇文章中，我们有介绍了一个关于非整形求关键值的仿函数HashFunc，在模拟实现是可以直接加在模拟实现的类上。

// hash_bucket是一个命名空间

// KeyOfT 和 Hash则是简化特定运算的仿函数

hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;

hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;

适用于unordered的成员函数

代码示例(C++)：

// 修改了返回类型

pair<iterator, 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())

{

vector<Node*> 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)

//前置声明

template<class K, class T, class KeyOfT, class Hash>

class HashTable;

// 通过模板来达到const的迭代器的复用

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>

struct __HTIterator

{

typedef HashNode<T> Node;

typedef __HTIterator<K, 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;

}

};

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>

class HashTable

{

typedef HashNode<T> Node;

// 友元

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>

friend struct __HTIterator;

...... // 其他待实现的函数

}

🌈operator++()

因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要operator–()操作，在operator++()的设计上，我们的问题是在走完这个桶之后，如何找到下一个桶，因此我们需要记录来方便寻找，于是我们引入了两个变量

// HashTable

const HashTable<K, T, KeyOfT, Hash>* _pht;

// 当前桶的位置

size_t _hashi;

代码示例(C++)：

const HashTable<K, 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 __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;

// const 版本

typedef __HTIterator<K, 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 HashTable<K, T, KeyOfT, Hash>*

const_iterator end() const

{

return const_iterator(nullptr, this, -1);

}

⭐迭代器的构造

因为我们引入了两个新的变量，所以此次构造与以往不同

代码示例(C++)：

// 非const版本

__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)

:_node(node)

, _pht(pht)

, _hashi(hashi)

{ }

// const版本

__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)

:_node(node)

, _pht(pht)

, _hashi(hashi)

{ }

📚3. Unordered_Set的模拟实现

🧩Unordered_Set的基本设计

代码示例(C++)：

template<class K, class Hash = HashFunc<K>>

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::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;

typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;

pair<const_iterator, bool> insert(const K& key)

{

auto ret = _ht.Insert(key);

return pair<const_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::HashTable<K, K, SetKeyOfT, Hash> _ht;

};

🌸Unordered_Set测试

代码示例(C++)：

void TestSet()

{

unordered_set<int> us;

us.insert(1);

us.insert(2);

us.insert(6);

us.insert(55);

us.insert(3);

unordered_set<int>::iterator it = us.begin();

while (it != us.end())

{

// *it += 5;

cout << *it << " ";

++it;

}

cout << endl;

}

📝4. Unordered_Map的模拟实现

🧩Unordered_Map的基本设计

代码示例(C++)：

<code>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:

// 在 unordered_map我们就只需要考虑 kv.first不能修改

// 但是 kv.first->second是可以修改的，因此我们需要将 K用 const修饰

typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;

pair<iterator, bool> insert(const pair<K, V>& kv)

{

return _ht.Insert(kv);

}

iterator begin()

{

return _ht.begin();

}

iterator end()

{

return _ht.end();

}

// 重载operator[]

V& operator[] (const K& key)

{

// 当_ht中没有就实现插入

pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));

return ret.first->second;

}

const V& operator[] (const K& key) const

{

pair<iterator, 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::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;

};

🌸Unordered_Map测试

代码示例(C++)：

void TestMap()

{

unordered_map<string, 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的内部机制，并通过模拟实现这两个容器，不仅加深了对哈希表这一重要数据结构的理解，还锻炼了编程能力和问题解决能力

通过模拟实现，我们亲手构建了哈希表，从简单的数组加链表结构，到动态扩容、再哈希等高级特性的实现，每一步都充满了挑战与收获。这个过程中，我们深刻体会到了数据结构设计的精妙之处，也学会了如何在实践中不断优化和调整我们的设计

<code>unordered_map与unordered_set等无序容器将在更多领域发挥重要作用。随着技术的不断发展，我们也期待看到更多高效、稳定、易用的容器实现出现。

同时，我们也希望读者能够保持对新技术、新知识的好奇心和求知欲，不断探索、不断学习、不断进步

希望本文能够为你提供有益的参考和启示，让我们一起在编程的道路上不断前行！

谢谢大家支持本篇到这里就结束了，祝大家天天开心！