C++中用哈希表封裝myunordered_set和myunordered_map方法詳解
更新時(shí)間：2026年05月05日 09:23:34 作者：進(jìn)擊的荊棘
這篇文章主要介紹了C++中用哈希表封裝myunordered_set和myunordered_map方法,封裝通用哈希表底層,快速實(shí)現(xiàn)myunordered_set和myunordered_map,掌握STL無序容器核心設(shè)計(jì),需要的朋友可以參考下
1.源碼及框架分析
SGI-STL30版本源代碼中沒有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL版本，這兩個容器是C++11之后才更新的。但是SGI-STL30實(shí)現(xiàn)了哈希表，只是容器的名字是hash_map和hash_set，它是作為非標(biāo)準(zhǔn)容器出現(xiàn)的，非標(biāo)準(zhǔn)是指非C++標(biāo)準(zhǔn)規(guī)定必須實(shí)現(xiàn)的，源代碼在hash_map/hash_set/set_hash_map/stl_hash_set/stl_hashtable.h中
hash_map和hash_set的實(shí)現(xiàn)結(jié)構(gòu)框架核心部分截?。?/p>
//stl_hash_set
template<class Value,class HashFcn=hash<Value>,
class EqualKey=equal_to<Value>,
class Alloc=alloc>
class hash_set{
private:
typedef hashtable<Value,Value,HashFcn,identity<Value>,
EqualKey,Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::const_iterator iterator;
typedef typename ht::const_iterator const_iterator;
hasher hash_funct() const {return rep.hash_funct();}
key_equal key_eq() const {return rep.key_eq();}
};
//stl_hash_map
template<class Key,class T,class HashFcn=hash<Key>,
class EqualKey=equal_to<Key>,
class Alloc=alloc>
class hash_map{
private:
typedef hashtable<pair<const Key,T>,Key,HashFcn,
selectlst<pair<const Key,T>>,EqualKey,Alloc> ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef T data_type;
typedef T mapped_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::iterator iterator;
typedef typename ht::const_iterator const_iterator;
};
//stl_hashtable.h
template<class Value,class Key,class HashFcn,
class ExtractKey,class EqualKey,
class Alloc>
class hashtable{
public:
typedef Key key_type;
typedef Value value_type;
typedef HashFcn hasher;
typedef EqualKey key_equal;
private:
hasher hash;
key_equal equals;
ExtractKey get_key;
typedef __hashtable_node<Value> node;
vector<node*,Alloc> buckets;
size_type num_elements;
public:
typedef __hashtable_iterator<Value,Key,HashFcn,ExtractKey,EqualKey,
Alloc> itertor;
pair<iterator,bool> insert_unique(const value_type& obj);
const_iterator find(const key_type& key) const;
};
template<class Value>
struct __hashtable_node{
__hahstable_node* next;
Value val;
};●通過源碼可以看到，結(jié)構(gòu)上hash_map和hash_set跟map和set的完全類似，復(fù)用同一個hashtable實(shí)現(xiàn)key和key/value結(jié)構(gòu)，hash_set傳給hash_ table的是兩個key，hash_map傳給hash_table的是pair<const key,value>
●需要注意源碼里面跟map/set源碼類似，命名風(fēng)格比較亂，這里比map和set還亂，hash_set模板參數(shù)居然用的Value命名，hash_map用的是Key和T命名。
2.模擬實(shí)現(xiàn)
2.1實(shí)現(xiàn)出復(fù)用哈希表的框架并支持insert
●unordered_map和unordered_set復(fù)用之前實(shí)現(xiàn)的哈希表。
●key參數(shù)用K，value參數(shù)用V，哈希表中數(shù)據(jù)類型，使用T。
●其次跟map和set相比而言unordered_map和unordered_set的模擬實(shí)現(xiàn)類結(jié)構(gòu)更復(fù)雜一點(diǎn)，但是大框架和思路完全類似。一i那位HashTable實(shí)現(xiàn)了泛型不知道T參數(shù)到底是K，還是pair<K,V>，那么insert內(nèi)部進(jìn)行插入時(shí)要用K對象轉(zhuǎn)換成整型取模和K比較相等，因?yàn)閜air的value不參與計(jì)數(shù)取模，且默認(rèn)支持的key和value一起比較相等，需要時(shí)的任何時(shí)候只需要比較K對象，所以在unordered_map和unordered_set層分別實(shí)現(xiàn)一個MapKeyOfT和SetKeyOfT的仿函數(shù)傳給HashTable的KeyOfT，然后HashTable中通過KEyOfT仿函數(shù)取出T類型對象中的K對象，再轉(zhuǎn)換成整型取模和K比較相等。
namespace Achieve{
template<class K,class Hash=HashFunc<K>>
class unordered_set{
struct SetKeyOfT{
const K& operator()(const K& kv){
return key;
}
};
public:
bool insert(const K& key){
return _ht.Insert(key);
}
private:
hash_buckte::HashTable<K,K,SetKeyOfT,Hash> _ht;
};
}
namespace Achieve{
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:
bool insert(const pair<K,V>& kv){
return _ht.Insert(kv);
}
private:
hash_buckte::HashTable<K,pair<K,V>,MapKeyOfT,Hash> _ht;
};
}
inline unsigned long __stl_next_prime(unsigned long n){
//Note:assumes long is at least 32 bits
static const int __stl_num_primes=28;
static const unsigned long __stl_prime_list[__stl_num_primes]={
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
};
const unsigned long* first=__stl_prime_list;
const unsigned long* last=__stl_prime_list+__stl_num_primes;
const unsigned long* pos=lower_bound(first,last,n);
return pos==last?*(last-1):*pos;
}
namespace hash_buckte{
template<class T>
struct HashNode{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
};
template<class K,class T,class KeyOfT,class Hash>
class HashTable{
typedef HashNode<T> Node;
public:
HashTable()
:_tables(__stl_next_prime(0))
,_n(0)
{}
~HashTable(){
for(int i=0;i<_tables.size();i++){
Node* cur=_tables[i];
while(cur){
Node* next=cur->_next;
delete cur;
cur=next;
}
_tables[i]=nullptr;
}
}
bool Insert(const T& data){
KeyOfT kot;
Hash hash;
Iterator it=Find(kot(data));
if(it!=End()) return false;
//當(dāng)負(fù)載因子為1時(shí)，擴(kuò)容
if(_n==_tables.size()){
//直接復(fù)用Insert，不好
/*HashTable<K,V> newht;
newht._tables.resize(_tables.size()*2);
for(int i=0;i<_tables.size();i++){
Node* cur=_tables[i];
while(cur){
newht.Insert(cur);
cur=cur->_next;
}
}
_tables.swap(newht);*/
vector<Node*> newTable(__stl_next_prime(_tables.size()+1));
//newht._tables.resize(_tables.size()*2);
//newht._tables.resize(__stl_next_prime(_tables.size()+1));
for(int i=0;i<_tables.size();i++){
Node* cur=_tables[i];
while(cur){
Node* next=cur->_next;
size_t hash1=hash(kot(cur->_data))%newTable.size();
//頭插
cur->_next=newTable[hash1];
newTable[hash1]=cur;
cur=next;
}
_tables[i]=nullptr;
}
_tables.swap(newTable);
}
//頭插
size_t hash1=hash(kot(data))%_tables.size();
Node* newNode=new Node(data);
newNode->_next=_tables[hash1];
_tables[hash1]=newNode;
++_n;
return true;
}
private:
vector<Node*> _tables;
size_t _n;
};
}2.2支持iterator的實(shí)現(xiàn)
iterator核心源代碼
template<class Value,class Key,class HashFcn,
class ExtractKey,class EqualKey,class Alloc>
struct __hashtable_iterator{
typedef hashtable<Value,Key,HashFcn,ExtractKey,EqualKey,Alloc>
hashtable;
typedef __hashtable_iterator<Value,Key,HashFcn,
ExtractKey,EqualKey,Alloc>
iterator;
typedef __hashtable_const_iterator<Value,Key,HashFcn,ExtraceKey,EqualKey,Alloc>
const_iterator;
typedef __hashtable_node<Value> node;
typedef forward_iterator_tag iterator_vategory;
typedef Value value_type;
node* cur;
hashtable* ht;
__hashtable_iterator(node* n,hashtable* tab): cur(n),ht(tab) {}
__hashtable_iterator() {}
reference operator*() const { return cur->val;}
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const {return &(operator*());}
#endif /*__SGI_STL_NO_ARROW_OPERATOR*/
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& it) const {return cur==it.cur;}
bool operator!=(const iterator& it) const {return cur!=it.cur;}
template<class V,class K,class HF,class ExK,class EqK,class A>
__hashtable_iterator<V,K,HF,ExK,EqK,A>&
__hashtable_iterator<V,K,HF,ExK,EqK,A>::operator++(){
const node* old=cur;
cur=cur->next;
if(!cur){
size_type bucket=ht->bkt_num(old->val);
while(!curL&&++bucket<ht->buckets.size())
cur=ht->buckets[bucket];
}
return *this;
}iterator實(shí)現(xiàn)思路分析
●iterator實(shí)現(xiàn)的大框架跟list的iterator思路是一致的，用一個類型封裝節(jié)點(diǎn)的指針，再通過重載運(yùn)算符實(shí)現(xiàn)，迭代器像指針一樣訪問的行為，要注意哈希表的迭代器是單向迭代器。
●難點(diǎn)是operator++的實(shí)現(xiàn)。iterator中有一個指向節(jié)點(diǎn)的指針，若當(dāng)前桶下面還有節(jié)點(diǎn)，則節(jié)點(diǎn)的指針指向下一個節(jié)點(diǎn)即可。若當(dāng)前桶走完了，則需要想辦法計(jì)算找到下一個桶。這里的難點(diǎn)反而是結(jié)構(gòu)設(shè)計(jì)的問題，上面的源碼，我們可以看到iterator中除了有節(jié)點(diǎn)的指針，還有哈希桶對象的指針，這樣當(dāng)前桶走完了，要計(jì)算下一個桶就相對容易多了，用key值計(jì)算出當(dāng)前桶位置，依次往后找下一個不為空的桶即可。
●begin（）返回第一個桶中的第一個節(jié)點(diǎn)指針構(gòu)造的迭代器，這里end（）返回迭代器可以用空表示。
●unoedered_set的iterator也不支持修改，把unordered_set的第二個模板參數(shù)改成const K即可，HashTable<k,const K,SetKeyOfT,Hash> _ht;
●unordered_map的iterator不支持修改key但是可以修改value，把unordered_map的第二個模板參數(shù)pair的第一個參數(shù)改成const K即可，HashTable<K,pair<const K,V>,MapKeyOfT,Hash> _ht;
2.3map支持[]
●unordered_map要支持[]主要需要修改insert返回值支持，修改HashTable中的insert返回值為pair<Iterator,bool> Insert(const T& data)
2.4Achieve::unordered_map和Achieve::unordered_set代碼實(shí)現(xiàn)
namespace Achieve{
template<class K,class Hash=HashFunc<K>>
class unordered_set{
struct KeyOfT{
const K& operator()(const K& key){
return key;
}
};
public:
typedef typename hash_buckte::HashTable<K,const K,KeyOfT,Hash>::Iterator iterator;
typedef typename hash_buckte::HashTable<K,const K,KeyOfT,Hash>::ConstIterator 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:
hash_buckte::HashTable<K,const K,KeyOfT,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;
for(auto e:s){
cout<<e<<' ';
}
cout<<endl;
}
void test_set(){
int a[]={3,11,86,88,1,881,5,6,7,6};
unordered_set<int> s;
for(auto e:a){
s.insert(e);
}
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);
}
}
namespace Achieve{
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_buckte::HashTable<K,pair<const K,V>,MapKeyOfT,Hash>::Iterator iterator;
typedef typename hash_buckte::HashTable<K,pair<const K,V>,MapKeyOfT,Hash>::ConstIterator 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();
}
V& operator[](const K& key){
pair<iterator,bool> ret=insert({key,V()});
return ret.first->second;
}
pair<iterator,bool> insert(const pair<K,V>& kv){
return _ht.Insert(kv);
}
iterator Find(const K& key){
return _ht.Find(key);
}
bool erase(const K& key){
return _ht.Erase(key);
}
private:
hash_buckte::HashTable<K,pair<const K,V>,MapKeyOfT,Hash> _ht;
};
void test_map(){
unordered_map<string,string> dict;
dict.insert({"sort","排序"});
dict.insert({"字符串","string"});
dict.insert({"sort","排序"});
dict.insert({"left","左邊"});
dict.insert({"right","右邊"});
dict["left"]="左邊、剩余";
dict["insert"]="插入";
dict["string"];
for(auto& kv:dict){
cout<<kv.first<<":"<<kv.second<<endl;
}
cout<<endl;
unordered_map<string,string>::iterator it=dict.begin();
while(it!=dict.end()){
it->second+='x';
cout<<it->first<<":"<<it->second<<endl;
++it;
}
cout<<endl;
}
}
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){
//BKDR
size_t hash=0;
for(auto ch:s){
hash+=ch;
hash*=131;
}
return hash;
}
};
inline unsigned long __stl_next_prime(unsigned long n){
//Note:assumes long is at least 32 bits
static const int __stl_num_primes=28;
static const unsigned long __stl_prime_list[__stl_num_primes]={
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
};
const unsigned long* first=__stl_prime_list;
const unsigned long* last=__stl_prime_list+__stl_num_primes;
const unsigned long* pos=lower_bound(first,last,n);
return pos==last?*(last-1):*pos;
}
namespace hash_buckte{
template<class T>
struct HashNode{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
};
//前置聲明，防止HashIterator不認(rèn)識HashTable
template<class K,class T,class KeyOfT,class Hash>
class HashTable;
template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash>
struct HTIterator{
typedef HashNode<T> Node;
typedef HashTable<K,T,KeyOfT,Hash> HT;
typedef HTIterator<K,T,Ref,Ptr,KeyOfT,Hash> Self;
Node* _node;
const HT* _ht;//取模時(shí)要用
HTIterator(Node* node,const HT* ht)
:_node(node)
,_ht(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){
_node=_node->_next;
}
else{
//找下一個不為空的桶
Hash hash;
KeyOfT kot;
size_t hash0=hash(kot(_node->_data))%_ht->_tables.size();
++hash0;
while(hash0<_ht->_tables.size()){
_node=_ht->_tables[hash0];
if(_node){
break;
}
else ++hash0;
}
//所有桶都走完了，end（）給的空的標(biāo)識的_node
if(hash0==_ht->_tables.size()){
_node=nullptr;
}
}
return *this;
}
};
template<class K,class T,class KeyOfT,class Hash>
class HashTable{
//友元聲明,為防止模板參數(shù)沖突，將參數(shù)改名
template<class K1,class T1,class Ref,class Ptr,class KeyOfT1,class Hash1>
friend struct HTIterator;
typedef HashNode<T> Node;
public:
typedef HTIterator<K,T,T&,T*,KeyOfT,Hash> Iterator;
typedef HTIterator<K,T,const T&,const T*,KeyOfT,Hash> ConstIterator;
HashTable()
:_tables(__stl_next_prime(0))
,_n(0)
{}
~HashTable(){
for(int i=0;i<_tables.size();i++){
Node* cur=_tables[i];
while(cur){
Node* next=cur->_next;
delete cur;
cur=next;
}
_tables[i]=nullptr;
}
}
Iterator Begin(){
if(_n==0){
return End();
}
for(int i=0;i<_tables.size();i++){
Node* cur=_tables[i];
if(cur) return Iterator(cur,this);;
}
return End();
}
Iterator End(){
return Iterator(nullptr,this);
}
ConstIterator Begin() const{
if(_n==0){
return End();
}
for(int i=0;i<_tables.size();i++){
Node* cur=_tables[i];
if(cur) return ConstIterator(cur,this);;
}
return End();
}
ConstIterator End() const{
return ConstIterator(nullptr,this);
}
pair<Iterator,bool> Insert(const T& data){
KeyOfT kot;
Hash hash;
Iterator it=Find(kot(data));
if(it!=End()) return {it,false};
//當(dāng)負(fù)載因子為1時(shí)，擴(kuò)容
if(_n==_tables.size()){
//直接復(fù)用Insert，不好
/*HashTable<K,V> newht;
newht._tables.resize(_tables.size()*2);
for(int i=0;i<_tables.size();i++){
Node* cur=_tables[i];
while(cur){
newht.Insert(cur);
cur=cur->_next;
}
}
_tables.swap(newht);*/
vector<Node*> newTable(__stl_next_prime(_tables.size()+1));
//newht._tables.resize(_tables.size()*2);
//newht._tables.resize(__stl_next_prime(_tables.size()+1));
for(int i=0;i<_tables.size();i++){
Node* cur=_tables[i];
while(cur){
Node* next=cur->_next;
size_t hash1=hash(kot(cur->_data))%newTable.size();
//頭插
cur->_next=newTable[hash1];
newTable[hash1]=cur;
cur=next;
}
_tables[i]=nullptr;
}
_tables.swap(newTable);
}
//頭插
size_t hash1=hash(kot(data))%_tables.size();
Node* newNode=new Node(data);
newNode->_next=_tables[hash1];
_tables[hash1]=newNode;
++_n;
return {Iterator(newNode,this),true};
}
Iterator Find(const K& key){
KeyOfT kot;
Hash hash;
size_t hash0=hash(key)%_tables.size();
Node* cur=_tables[hash0];
while(cur){
if(kot(cur->_data)==key)
return Iterator(cur,this);
cur=cur->_next;
}
return End();
}
bool Erase(const K& key){
KeyOfT kot;
Hash hash;
//沒有這個值
if(!Find(key)) return false;
size_t hash0=hash(key)%_tables.size();
Node* cur=_tables[hash0];
Node* prev=nullptr;
while(cur){
if(kot(cur->_data)==key){
//刪除的節(jié)點(diǎn)是鏈表的頭
if(!prev){
_tables[hash0]=cur->_next;
}
else{
prev->_next=cur->_next;
}
delete cur;
--_n;
return true;
}
else{
prev=cur;
cur=cur->_next;
}
}
return false;
}
private:
vector<Node*> _tables;
size_t _n;
};
}以上就是C++中用哈希表封裝myunordered_set和myunordered_map方法詳解的詳細(xì)內(nèi)容，更多關(guān)于C++封裝myunordered_set和myunordered_map的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C語言鏈表實(shí)現(xiàn)學(xué)生成績管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言鏈表實(shí)現(xiàn)學(xué)生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-07-07
這篇文章主要介紹了C++輸入輸出注意事項(xiàng)總結(jié),對C++的輸入輸出各個注意事項(xiàng)進(jìn)行了很好的總結(jié),需要的朋友可以參考下2014-08-08
本篇文章是對互斥量與條件變量的應(yīng)用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)雙向鏈表，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
在C++中，鎖（Lock）是一種同步工具，用于保護(hù)共享資源，防止多個線程同時(shí)訪問，那么如何避免死鎖的情況出現(xiàn)呢，下面就為大家簡單講講2023-07-07
QT網(wǎng)絡(luò)編程Tcp下C/S架構(gòu)的即時(shí)通信實(shí)例
下面小編就為大家?guī)硪黄猀T網(wǎng)絡(luò)編程Tcp下C/S架構(gòu)的即時(shí)通信實(shí)例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08
本篇文章是對用C語言去除字符串兩邊空字符的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
快速排序是一種高效的排序算法,通過分治法將數(shù)組劃分為兩部分,遞歸排序,直到整個數(shù)組有序,通過代碼解析和示例,詳細(xì)解釋了快速排序的工作原理和實(shí)現(xiàn)過程,需要的朋友可以參考下2025-03-03
this?指針在C++類和對象中是個很方便實(shí)用的關(guān)鍵字，可以簡化對象成員屬性的調(diào)用，使代碼表達(dá)的含義更加準(zhǔn)確；在之前的學(xué)習(xí)中我們都可以判斷變量所占內(nèi)存空間大小，那么我們創(chuàng)建的類對象所占的內(nèi)存空間怎么計(jì)算呢?想知道this的妙用和類對象占用的內(nèi)存空間就來跟我學(xué)習(xí)吧2022-07-07
本案例通過使用OpenCV中的approxPolyDP進(jìn)行多邊形近似，進(jìn)而進(jìn)行基礎(chǔ)形狀識別（圓、三角形、矩形、星形…），快跟隨小編一起動手嘗試一下2022-07-07