![由[哈希/散列]模擬實現[unordered_map/unordered_set] (手撕迭代器),遣返回家的C家家,哈希算法,算法,C語言,c++,數據結構](https://imgs.yssmx.com/Uploads/2023/10/728543-1.png)
1.迭代器分析
![由[哈希/散列]模擬實現[unordered_map/unordered_set] (手撕迭代器),遣返回家的C家家,哈希算法,算法,C語言,c++,數據結構](https://imgs.yssmx.com/Uploads/2023/10/728543-2.png)
2.細節(jié)處理
| 以下兩篇文章均為筆者的嘔心瀝血 |
|---|
| 想要搞懂本篇文章的uu請自行查閱 |
哈希/散列的細節(jié)實現
哈希/散列–哈希表[思想到結構][==修訂版==]
手撕迭代器的細節(jié)處理文章來源：http://www.zghlxwxcb.cn/news/detail-728543.html
模擬實現map/set[改編紅黑樹實現map/set容器底層]文章來源地址http://www.zghlxwxcb.cn/news/detail-728543.html
3.完整代碼
3.1HashTable.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <array>
#include <time.h>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <assert.h>
using namespace std;
//轉換函數
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t value = 0;
for (auto ch : s)
{
value = value * 131 + ch;
}
return value;
}
};
//開散列/鏈地址法
namespace ChainAddressing
{
//STL庫中unordered_map/unordered_set的定義
/* template
<
class Key,
class T,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Alloc = allocator< pair<const Key,T> >
>
class unordered_map;
class unordered_set;
*/
//結點類
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_next(nullptr)
, _data(data)
{
}
};
/// 迭代器
//哈希表前置聲明
template<class K, class T, class GetKey, class Hash>
class HashTable;
//迭代器類
template<class K, class T, class Ref, class Ptr, class GetKey, class Hash>
struct HashIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, GetKey, Hash> HT;
typedef HashIterator<K, T, Ref, Ptr, GetKey, Hash> Self;
typedef HashIterator<K, T, T&, T*, GetKey, Hash> Iterator;
//成員屬性
Node* _node;
const HT* _ht;
//構造函數
HashIterator(Node* node, const HT* ht)
:_node(node)
, _ht(ht)
{
}
//特殊構造函數
HashIterator(const Iterator& it)
:_node(it._node)
, _ht(it._ht)
{
}
//解引用運算符
Ref operator*()
{
return _node->_data;
}
//成員訪問運算符
Ptr operator->()
{
return &_node->_data;
}
//關系運算符
bool operator!=(const Self& s)
{
return _node != s._node;
}
//前置++
Self& operator++()
{
//下個結點不空 向下++即可
if (_node->_next != nullptr)
{
_node = _node->_next;
}
//下個結點為空
else
{
GetKey get;
Hash hash;
//當前數據的哈希下標
size_t hashi = hash(get(_node->_data)) % _ht->_tables.size();
//下個結點為空 說明當前桶已空 找下一個非空桶
++hashi;
//找非空桶時 肯定不能越過哈希表
while (hashi < _ht->_tables.size())
{
//_ht->_tables[hashi] :
// 取出的是表中的ptr 指向桶中首結點指針[如果存在的話]
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
else
++hashi;
}
//while循環(huán)結束情況:
//1.不滿足循環(huán)條件 hashi == _ht->_tables.size()
// 即找完整個表 都沒有找到非空桶 即當前桶之后的桶全為空
//2._ht->_tables[hashi]不為空 找到了 break出來了
//面對上述情況 只需對第一種情況操作 即桶均空 ++失敗 表中已無數據 返回空指針
if (hashi == _ht->_tables.size())
_node = nullptr;
}
return *this;
}
};
///
//哈希表類
template< class K, class T, class GetKey, class Hash >
class HashTable
{
template<class K, class T, class Ref, class Ptr, class GetKey, class Hash>
friend struct HashIterator;
typedef HashNode<T> Node;
public:
typedef HashIterator<K, T, T&, T*, GetKey, Hash> iterator;
typedef HashIterator<K, T, const T&, const T*, GetKey, Hash> const_iterator;
//迭代器
iterator begin()
{
Node* ptr = nullptr;
for (size_t i = 0; i < _tables.size(); ++i)
{
ptr = _tables[i];
if (ptr)
break;
}
return iterator(ptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin() const
{
Node* ptr = nullptr;
for (size_t i = 0; i < _tables.size(); ++i)
{
ptr = _tables[i];
if (ptr)
break;
}
return const_iterator(ptr, this);
}
const_iterator end() const
{
return const_iterator(nullptr, this);
}
//析構函數
~HashTable()
{
for (auto& ptr : _tables)
{
while (ptr)
{
//記錄下一個結點
Node* next = ptr->_next;
//釋放當前結點
delete ptr;
//更新ptr
ptr = next;
}
ptr = nullptr;
}
}
//查找函數
iterator Find(const K& key)
{
if (_tables.size() == 0)
return end();
GetKey get;
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* ptr = _tables[hashi];
while (ptr)
{
if (get(ptr->_data) == key)
return iterator(ptr, this);
ptr = ptr->_next;
}
return end();
}
//刪除函數
bool Erase(const K& key)
{
Hash hash;
GetKey get;
size_t hashi = hash(key) % _tables.size();
Node* prv = nullptr;
Node* ptr = _tables[hashi];
while (ptr)
{
if (get(ptr->_data) == key)
{
if (prv == nullptr)
_tables[hashi] = ptr->_next;
else
prv->_next = ptr->_next;
delete ptr;
return true;
}
else
{
prv = ptr;
ptr = ptr->_next;
}
}
return false;
}
//C++SGI版本STL庫:獲得下一個素數
//在SGI下 設定哈希表的容量為素數
//[可能效率更高 有興趣的可以自行查閱]
/*
size_t GetNextPrime(size_t index)
{
static const int num = 28;
static const unsigned long prime[num] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
size_t i = 0;
for (i = 0; i < num; ++i)
{
if (prime[i] > index)
return prime[i];
}
return prime[i];
}
*/
//插入函數
pair<iterator, bool> Insert(const T& data)
{
GetKey get;
iterator it = Find(get(data));
if (it != end())
return make_pair(it, false);
Hash hash;
//負載因子/荷載系數 -- Load_Factor = _n / _tables.size();
//負載因子 == 1時擴容
if (_n == _tables.size())
{
/// 高級代碼1.0 /
/*
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
HashTable<K, V> newht;
newht.resize(newsize);
for (auto& ptr : _tables)
{
while (ptr)
{
newht.Insert(ptr->_pair);
ptr = ptr->_next;
}
}
_tables.swap(newht._tables);
*/
//初代擴容
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
//引進stl庫素數思想
//size_t newsize = GetNextPrime(_tables.size());
vector<Node*> newtables(newsize, nullptr);
//遍歷舊表 取出舊表里每一個指針
for (auto& ptr : _tables)
{
//ptr是舊表里存儲的每一個指針
//它指向當前哈希桶的首結點 即他存儲的是首結點的地址
while (ptr)
{
//算出 當前結點根據新哈希函數計算的新下標
size_t hashi = hash(get(ptr->_data)) % newtables.size();
//ptr是首結點的地址 ptr->_next為第二個結點的地址
Node* next = ptr->_next;
// 頭插到新表
ptr->_next = newtables[hashi];
newtables[hashi] = ptr;
//更新ptr 即向下遍歷
ptr = next;
}
}
_tables.swap(newtables);
}
//哈希函數計算出的下標
size_t hashi = hash(get(data)) % _tables.size();
//鏈表頭插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return make_pair(iterator(newnode, this), false);
}
//最大桶數據個數
size_t MaxBucketSize()
{
size_t max = 0;
for (size_t i = 0; i < _tables.size(); ++i)
{
auto ptr = _tables[i];
size_t size = 0;
while (ptr)
{
++size;
ptr = ptr->_next;
}
//每個桶數據個數
//printf("[%d] -> %d\n", i, size);
if (size > max)
max = size;
}
return max;
}
private:
vector<Node*> _tables; // 指針數組
size_t _n = 0; // 存儲有效數據個數
};
}
3.2unordered_set.h
#pragma once
#include "HashTable.h"
namespace ape
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
public:
//獲得key
struct SetGetKey
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename ChainAddressing::HashTable<K, K, SetGetKey, Hash>::const_iterator iterator;
typedef typename ChainAddressing::HashTable<K, K, SetGetKey, 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:
ChainAddressing::HashTable<K, K, SetGetKey, Hash> _ht;
};
//打印函數
void print(const unordered_set<int>& s)
{
unordered_set<int>::const_iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
//測試函數
void test_unordered_set()
{
int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
unordered_set<int> s;
for (auto e : a)
s.insert(e);
s.insert(54);
s.insert(107);
unordered_set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s)
cout << e << " ";
cout << endl;
print(s);
}
}
3.3unordered_map.h
#pragma once
#include "HashTable.h"
namespace ape
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
public:
//獲得key
struct MapGetKey
{
const K& operator()(const pair<K, V>& pair)
{
return pair.first;
}
};
public:
typedef typename ChainAddressing::HashTable<K, pair<const K, V>, MapGetKey, Hash>::iterator iterator;
typedef typename ChainAddressing::HashTable<K, pair<const K, V>, MapGetKey, 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>& pair)
{
return _ht.Insert(pair);
}
//下標運算符
V& operator[](const K& key)
{
pair<iterator, bool> pair = insert(make_pair(key, V()));
return pair.first->second;
}
//查找
iterator find(const K& key)
{
return _ht.Find(key);
}
//刪除
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
ChainAddressing::HashTable<K, pair<const K, V>, MapGetKey, Hash> _ht;
};
void test_unordered_map1()
{
unordered_map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(2, 2));
unordered_map<int, int>::iterator it = m.begin();
while (it != m.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
void test_unordered_map2()
{
string s[] = { "西瓜", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉", "梨" };
unordered_map<string, int> um;
for (auto& e : s)
{
um[e]++;
}
for (auto& pair : um)
{
cout << pair.first << ":" << pair.second << endl;
}
}
class Date
{
friend struct HashDate;
friend ostream& operator<<(ostream& _cout, const Date& d);
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{
}
bool operator<(const Date& d) const
{
return (_year < d._year)
|| (_year == d._year && _month < d._month)
|| (_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d) const
{
return (_year > d._year)
|| (_year == d._year && _month > d._month)
|| (_year == d._year && _month == d._month && _day > d._day);
}
bool operator==(const Date& d) const
{
return _year == d._year
&& _month == d._month
&& _day == d._day;
}
private:
int _year;
int _month;
int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
struct HashDate
{
size_t operator()(const Date& d)
{
size_t value = 0;
value += d._year;
value *= 131;
value += d._month;
value *= 131;
value += d._day;
value *= 131;
return value;
}
};
void test_unordered_map4()
{
Date d1(2023, 10, 1);
Date d2(2023, 10, 5);
Date d3(2023, 10, 2);
Date d4(2023, 10, 2);
Date d5(2023, 10, 2);
Date d6(2023, 10, 1);
Date a[] = { d1, d2, d3, d4, d5, d6 };
unordered_map<Date, int, HashDate> um;
for (auto e : a)
{
um[e]++;
}
for (auto& pair : um)
{
cout << pair.first << ":" << pair.second << endl;
}
}
}
3.4Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <array>
#include <time.h>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <assert.h>
using namespace std;
#include "HashTable.h"
#include "Unordered_Map.h"
#include "Unordered_Set.h"
int main()
{
//ape::test_unordered_set();
ape::test_unordered_map4();
return 0;
}
到了這里，關于由[哈希/散列]模擬實現[unordered_map/unordered_set] (手撕迭代器)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
