本文將介紹如何使用哈希表來實現(xiàn)C++ STL庫中的unordered_map和unordered_set容器。我們將會解釋哈希表的基本原理，并給出具體的代碼示例，幫助讀者更好地理解和應(yīng)用哈希表。
哈希原理講解–鏈接入口
set和map的實現(xiàn)的文章，與unordered_map實現(xiàn)類似
對HashTable的改造
#pragma once
template<class K>
struct Hashfunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//特化
template<>
struct Hashfunc<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto a : s)
{
hash += a;
hash *= 31;
}
return hash;
}
};
namespace hash_bucket
{
template <class T>
struct HashNode
{
HashNode<T>* _next;
T _data;
HashNode(const T& data)
:_next(nullptr),
_data(data)
{}
};
// 前置聲明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K, class T, class KeyOfT, class Hash>
struct _HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef _HTIterator<K, 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;
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
hashi++;
//循環(huán)找出存在的哈希桶位置；
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
hashi++;
}
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
return *this;
}
}
bool operator!=(const Self & s)
{
return _node != s._node;
}
bool operator ==(const Self& s)
{
return _node == s._node;
}
};
template<class K,class T,class KeyOfT, class Hash>
class HashTable
{
template<class K,class T,class KeyOfT,class Hash>
friend struct _HTIterator;
typedef HashNode<T> Node;
public:
typedef _HTIterator<K, T, KeyOfT, Hash> iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
// 找到第一個桶的第一個節(jié)點
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
HashTable()
{
_tables.resize(10, nullptr);
_n = 0;
}
~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;
}
}
iterator Find(const K& key)
{
KeyOfT kot;
Hash hs;
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);
}
pair<iterator,bool> Insert(const T& data)
{
KeyOfT kot;
Hash hs;
//查找是否有相同元素
iterator it = Find(kot(data));
if (it != end())
return make_pair(it,false);
//擴容
if (_n == _tables.size())
{
vector<Node*> 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);
it = iterator(newnode, this);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return make_pair(it,true);
}
bool Erase(const K& key)
{
KeyOfT kot;
Hash hs;
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;
}
private:
vector<Node*> _tables;
size_t _n;
};
}
對unordered_map和unordered_set的實現(xiàn)
unordered_set是一種集合存儲的容器，它存儲唯一的元素。我們同樣可以使用哈希表來實現(xiàn)unordered_set，將元素映射到數(shù)組的索引。
- 插入操作：通過哈希函數(shù)計算元素的索引，如果索引位置為空，則直接插入；否則，使用開放地址法尋找下一個可用的槽進行插入。
- 查找操作：通過哈希函數(shù)計算元素的索引，然后比較該索引位置的元素是否與目標(biāo)元素相等，如相等則返回存在；如不相等，則使用開放地址法依次查找下一個槽，直到找到相等的元素或者遇到空槽為止。
- 刪除操作：通過哈希函數(shù)計算元素的索引，然后通過循環(huán)找到對應(yīng)的元素，如果這個元素有前一個結(jié)點，那么就讓前一個結(jié)點鏈上當(dāng)前結(jié)點的下一個結(jié)點，然后刪除當(dāng)前結(jié)點；如果當(dāng)前元素沒有前一個結(jié)點，那么就表示刪除該節(jié)點后，哈希桶的頭結(jié)點將為空；
namespace fnc
{
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;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator,bool> insert(const K& k)
{
return _ht.Insert(k);
}
iterator find(const K& k)
{
return _ht.Find(k);
}
bool Erase(const K& k)
{
return _ht.Erase(k);
}
private:
hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
}
unordered_map是一種鍵值對存儲的容器，它允許通過鍵快速查找對應(yīng)的值。我們可以使用哈希表來實現(xiàn)unordered_map，將鍵映射到數(shù)組的索引，值存儲在對應(yīng)的槽中。
- 插入操作：通過哈希函數(shù)計算鍵的索引，如果索引位置為空，則直接插入；否則，使用開放地址法尋找下一個可用的槽進行插入。
- 查找操作：通過哈希函數(shù)計算鍵的索引，然后比較該索引位置的鍵是否與目標(biāo)鍵相等，如相等則返回對應(yīng)的值；如不相等，則使用開放地址法依次查找下一個槽，直到找到相等的鍵或者遇到空槽為止。
- 刪除操作：通過哈希函數(shù)計算元素的索引，然后通過循環(huán)找到對應(yīng)的元素，如果這個元素有前一個結(jié)點，那么就讓前一個結(jié)點鏈上當(dāng)前結(jié)點的下一個結(jié)點，然后刪除當(dāng)前結(jié)點；如果當(dāng)前元素沒有前一個結(jié)點，那么就表示刪除該節(jié)點后，哈希桶的頭結(jié)點將為空；
namespace fnc
{
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;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator,bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
iterator find(const K& k)
{
return _ht.Find(k);
}
bool Erase(const K& k)
{
return _ht.Erase(k);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
測試
insert
find和erase
//find和erase
void test_set2()
{
vector<int> v = { 3,1,5,15,45,7 };
unordered_set<int> us;
us.insert(3);
us.insert(1);
us.insert(5);
us.insert(15);
us.insert(45);
us.insert(7);
unordered_set<int>::iterator it = us.begin();
while (it != us.end())
{
cout << *it << " ";
++it;
}
cout << endl;
if (us.find(15) != us.end())
{
cout << "15:在" << endl;
}
else
{
cout << "15:不在" << endl;
}
if (us.find(16) != us.end())
{
cout << "16:在" << endl;
}
else
{
cout<<"16:不在" << endl;
}
cout << endl;
us.Erase(5);
us.Erase(7);
it = us.begin();
while (it != us.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}
void test_map2()
{
unordered_map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("left", "左"));
dict.insert(make_pair("right", "右"));
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
fnc::unordered_map<string, string>::iterator it = dict.find("sort");
if (it!=dict.end())
{
cout <<"找到了：" << (*it).first << ":" << (*it).second << endl;
}
cout << endl;
dict.Erase("left");
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
}
文章來源：http://www.zghlxwxcb.cn/news/detail-845495.html
operator[]
void test_map3()
{
vector<string> v = { "香蕉","蘋果","橙子","西瓜","香蕉",
"蘋果","橙子","西瓜","香蕉","蘋果","橙子" ,"香蕉","蘋果" };
unordered_map<string, int> dict;
for (auto a : v)
{
dict[a]++;
}
for (auto a : dict)
{
cout << a.first << ":" << a.second << endl;
}
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-845495.html
到了這里，關(guān)于C++進階--使用哈希表實現(xiàn)unordered_map和unordered_set的原理與實例的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![【C++入門到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入門 ]](https://imgs.yssmx.com/Uploads/2024/02/714971-1.jpeg)
