C++手撕哈希表之封裝unordered_set和unordered_map實踐
更新時間：2026年07月16日 14:12:21 作者：Brilliantwxx
這篇文章主要介紹了C++手撕哈希表之封裝unordered_set和unordered_map實踐,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
1. 前言
在 STL 中，unordered_set和 unordered_map的底層都是 哈希表。它們的區(qū)別僅僅在于：
容器 | 存儲單元 | 是否允許重復(fù) | 鍵是否可變 |
|---|---|---|---|
unordered_set | 單個值 | 否 | 否 |
unordered_map | 鍵值對 | 否 | 鍵不可變，值可變 |
本文將展示：如何用同一份哈希表代碼，通過模板參數(shù)差異，分別實現(xiàn)這兩種容器。
2. 核心設(shè)計思想：模板參數(shù)萃取
這是 STL 最精妙的設(shè)計之一 ??
template<
class K, // 關(guān)鍵碼類型
class T, // 節(jié)點中真正存儲的數(shù)據(jù)
class KeyOfT, // 從 T 中提取 K 的方法
class Hash // 哈希函數(shù)
>
class HashTable;容器 | T | KeyOfT |
|---|---|---|
set | K | 返回自身 |
map | pair<const K, V> | 返回 first |
? 一套代碼，兩種形態(tài)
3. 底層哈希表回顧（簡化版）
template<class K, class T, class KeyOfT, class Hash>
class HashTable {
public:
using Node = HashNode<T>;
using Iterator = __HashIterator<K, T, KeyOfT, Hash>;
pair<Iterator, bool> Insert(const T& data) { /* ... */ }
Iterator Find(const K& key) { /* ... */ }
bool Erase(const K& key) { /* ... */ }
private:
vector<Node*> _tables;
size_t _n = 0;
};?? 注意：哈希表只關(guān)心 T? 和 如何從 T 取 K，不關(guān)心它是 set 還是 map。
4. 封裝 unordered_set
4.1 設(shè)計要點
存儲的是 單個值
值即鍵
值不可修改
4.2 代碼實現(xiàn)
namespace wxx {
template<class K, class Hash = HashFunc<K>>
class unordered_set {
struct SetKeyOfT {
const K& operator()(const K& key) const {
return key;
}
};
public:
using iterator = typename HashTable<K, K, SetKeyOfT, Hash>::Iterator;
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);
}
iterator begin() { return _ht.Begin(); }
iterator end() { return _ht.End(); }
private:
HashTable<K, K, SetKeyOfT, Hash> _ht;
};
} // namespace bit? set 的本質(zhì)：一個“只有鍵”的哈希表
5. 封裝 unordered_map
5.1 設(shè)計要點
- 存儲的是
pair<const K, V> - 鍵來自
pair.first - 鍵不可修改，值可修改
5.2 代碼實現(xiàn)
namespace wxx {
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map {
struct MapKeyOfT {
const K& operator()(const pair<const K, V>& kv) const {
return kv.first;
}
};
public:
using iterator = typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator;
pair<iterator, bool> insert(const pair<const 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);
}
V& operator[](const K& key) {
auto ret = _ht.Insert({key, V()});
return ret.first->second;
}
iterator begin() { return _ht.Begin(); }
iterator end() { return _ht.End(); }
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
} // namespace wxx? map 的本質(zhì)：一個“鍵值對”的哈希表
6. set 與 map 的差異對比
對比項 | unordered_set | unordered_map |
|---|---|---|
存儲類型 | K | pair<const K, V> |
KeyOfT | 返回自身 | 返回 first |
operator[] | ? | ? |
值是否可改 | ? | ?（僅 second） |
底層哈希表 | 同一套 | 同一套 |
7. 完整代碼
HashTable.h
#pragma once
#include<vector>
#include<string>
#include<iostream>
using namespace std;
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFunc<string>
{
// BKDR
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto ch : str)
{
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;
}
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;
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;
HTIterator(Node* node, const HT* ht)
:_node(node)
, _ht(ht)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next) // 當(dāng)前還有節(jié)點
{
_node = _node->_next;
}
else // 當(dāng)前桶為空，找下一個不為空的桶的第一個
{
size_t hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_tables.size();
++hashi;
while (hashi != _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
hashi++;
}
// 最后一個桶的最后一個節(jié)點已經(jīng)遍歷結(jié)束，走到end()去，nullptr充當(dāng)end()
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
// 友元聲明
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
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;
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);
}
ConstIterator Begin() const
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return ConstIterator(_tables[i], this);
}
}
return End();
}
ConstIterator End() const
{
return ConstIterator(nullptr, this);
}
HashTable()
:_tables(__stl_next_prime(1), nullptr)
, _n(0)
{
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
// 當(dāng)前桶的節(jié)點重新映射掛到新表
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
pair<Iterator, bool> Insert(const T& data)
{
KeyOfT kot;
auto it = Find(kot(data));
if (it != End())
return { it, false };
Hash hs;
// 負(fù)載因子==1擴(kuò)容
if (_n == _tables.size())
{
//HashTable<K, V> newHT;
//newHT._tables.resize(_tables.size()*2);
//// 遍歷舊表將所有值映射到新表
//for (auto cur : _tables)
//{
// while (cur)
// {
// newHT.Insert(cur->_kv);
// cur = cur->_next;
// }
//}
//_tables.swap(newHT._tables);
vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
// 當(dāng)前桶的節(jié)點重新映射掛到新表
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 };
}
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 { cur, this };
cur = cur->_next;
}
return End();
}
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 == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
//vector<list<pair<K, V>>> _tables;
vector<Node*> _tables;
size_t _n = 0; // 實際存儲的數(shù)據(jù)個數(shù)
};Unordered_Set.h
#include"HashTable.h"
namespace bit
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
typedef typename HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
const_iterator begin() const
{
return _t.Begin();
}
const_iterator end() const
{
return _t.End();
}
pair<iterator, bool> insert(const K& k)
{
return _t.Insert(k);
}
bool erase(const K& key)
{
return _t.Erase(key);
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
HashTable<K, const K, SetKeyOfT, Hash> _t;
};
void Func(const unordered_set<int>& s)
{
auto it1 = s.begin();
while (it1 != s.end())
{
// *it1 = 1;
cout << *it1 << " ";
++it1;
}
cout << endl;
}
struct Date
{
int _year;
int _month;
int _day;
bool operator==(const Date& d) const
{
return _year == d._year
&& _month == d._month
&& _day == d._day;
}
};
struct DateHashFunc
{
// BKDR
size_t operator()(const Date& d)
{
//2025 1 9
//2025 9 1
//2025 2 8
size_t hash = 0;
hash += d._year;
hash *= 131;
hash += d._month;
hash *= 131;
hash += d._day;
hash *= 131;
return hash;
}
};
};Unordered_Map.h
#include<vector>
#include<string>
using namespace std;
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFunc<string>
{
// BKDR
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto ch : str)
{
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;
}
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;
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;
HTIterator(Node* node, const HT* ht)
:_node(node)
, _ht(ht)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next) // 當(dāng)前還有節(jié)點
{
_node = _node->_next;
}
else // 當(dāng)前桶為空，找下一個不為空的桶的第一個
{
size_t hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_tables.size();
++hashi;
while (hashi != _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
hashi++;
}
// 最后一個桶的最后一個節(jié)點已經(jīng)遍歷結(jié)束，走到end()去，nullptr充當(dāng)end()
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
// 友元聲明
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
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;
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);
}
ConstIterator Begin() const
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return ConstIterator(_tables[i], this);
}
}
return End();
}
ConstIterator End() const
{
return ConstIterator(nullptr, this);
}
HashTable()
:_tables(__stl_next_prime(1), nullptr)
, _n(0)
{
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
// 當(dāng)前桶的節(jié)點重新映射掛到新表
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
pair<Iterator, bool> Insert(const T& data)
{
KeyOfT kot;
auto it = Find(kot(data));
if (it != End())
return { it, false };
Hash hs;
// 負(fù)載因子==1擴(kuò)容
if (_n == _tables.size())
{
//HashTable<K, V> newHT;
//newHT._tables.resize(_tables.size()*2);
//// 遍歷舊表將所有值映射到新表
//for (auto cur : _tables)
//{
// while (cur)
// {
// newHT.Insert(cur->_kv);
// cur = cur->_next;
// }
//}
//_tables.swap(newHT._tables);
vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
// 當(dāng)前桶的節(jié)點重新映射掛到新表
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 };
}
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 { cur, this };
cur = cur->_next;
}
return End();
}
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 == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
//vector<list<pair<K, V>>> _tables;
vector<Node*> _tables;
size_t _n = 0; // 實際存儲的數(shù)據(jù)個數(shù)
};總結(jié)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
復(fù)選框是一種可同時選中多項的基礎(chǔ)控件，主要是有兩種明顯的狀態(tài)：選中與非選中。本文將通過MFC框架實現(xiàn)自定義復(fù)選框效果，感興趣的可以了解一下2022-02-02
C語言數(shù)據(jù)結(jié)構(gòu)之?dāng)U展字符詳解
掌握C語言數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵在于理解其核心概念,擴(kuò)展字符作為其中的重要一環(huán),對于編程人員來說至關(guān)重要,本指南將為您深入剖析擴(kuò)展字符的相關(guān)知識,帶您輕松掌握C語言數(shù)據(jù)結(jié)構(gòu),讓我們一起探索這個令人著迷的領(lǐng)域吧！2024-03-03
這篇文章主要介紹了C++運(yùn)算符重載規(guī)則詳解,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
這篇文章主要為大家詳細(xì)介紹了C++堆棧類模板的實現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-12-12
這篇文章主要給大家介紹了關(guān)于C語言狀態(tài)機(jī)設(shè)計的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
這篇文章主要介紹了C++類基本語法實例分析,非常適合初學(xué)者學(xué)習(xí)借鑒,需要的朋友可以參考下2014-08-08
這篇文章主要介紹了C語言基礎(chǔ)知識分享續(xù)篇的相關(guān)資料,需要的朋友可以參考下2023-01-01
在學(xué)習(xí)c++中用到一些古老的c語言庫時,在工作中我們經(jīng)常要使用C和C++混合編程,下面這篇文章主要給大家介紹了關(guān)于C和C++如何實現(xiàn)互相調(diào)用的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-01-01
這篇文章主要介紹了C++ 中指針和引用有什么區(qū)別詳解的相關(guān)資料,需要的朋友可以參考下2017-05-05
C語言調(diào)用攝像頭實現(xiàn)生成yuv未壓縮圖片
這篇文章主要為大家詳細(xì)介紹了C語言如何調(diào)用攝像頭實現(xiàn)生成yuv未壓縮圖片,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價值,感興趣的小伙伴可以參考一下2023-11-11