跳到主要内容手写 C++ 哈希表:unordered_set/unordered_map 用法、模拟实现与性能对比 | 极客日志C++
手写 C++ 哈希表:unordered_set/unordered_map 用法、模拟实现与性能对比
从标准库用法切入,逐步实现一套基于哈希桶的 unordered_set 和 unordered_map,涵盖节点设计、迭代器构造、桶扩容、key 提取仿函数以及 const 正确性处理。性能测试显示,桶顺序遍历的迭代器比标准库按插入顺序维护的方式更快,最大桶长度仅 2,平均桶长约 1.28,接近 O(1)。
标准库的 unordered_set 和 unordered_map 用起来顺手,但真自己写一个才知道哈希表里藏了多少细节。下面从用法切入,然后一步步模拟实现,顺便看看不同实现策略对性能的影响。
标准库用法
先快速过一下基本操作,顺便留意那些平时不太关注的桶状态。
unordered_set
#include <iostream>
#include <unordered_set>
using namespace std;
void test1() {
unordered_set<int> st;
st.insert(1);
st.insert(3);
st.insert(2);
st.insert(4);
unordered_set<int>::iterator it = st.begin();
while (it != st.end()) {
cout << *it << " ";
++it;
}
cout << endl;
it = st.find(3);
if (it != st.end()) cout << *it << "存在" << endl;
st.erase(1);
if (st.count(1)) cout << "1存在" << endl;
}
void test2() {
unordered_set<int> st;
st.insert(1);
st.();
st.();
st.();
cout << st.() << endl;
cout << st.() << endl;
st.();
st.();
cout << st.() << endl;
cout << st.() << endl;
st.();
st.();
cout << st.() << endl;
cout << st.() << endl;
}
{
unordered_set<> st;
( i = ; i < ; i++) st.(() + i);
cout << << st.() << endl;
cout << << st.() << endl;
( < st.()) {
cout << << st.() << endl;
}
it = st.();
(it != st.()) {
cout << << st.() << << endl;
} {
cout << << endl;
}
}
{
();
();
();
;
}
insert
3
insert
2
insert
4
load_factor
max_load_factor
insert
6
insert
8
load_factor
max_load_factor
insert
5
insert
7
load_factor
max_load_factor
void test3()
int
for
int
0
100000
insert
rand
"当前桶数:"
bucket_count
"最大桶数:"
max_bucket_count
if
33
bucket_count
"33 号桶的大小:"
bucket_size
33
auto
find
33
if
end
"元素 33 在桶"
bucket
33
"中"
else
"元素 33 不存在"
int main()
test1
test2
test3
return
0
unordered_map
#include <iostream>
#include <unordered_map>
using namespace std;
void test1() {
unordered_map<int, int> mp;
mp.insert(make_pair(1, 1));
mp.insert(make_pair(5, 5));
mp.insert(make_pair(2, 2));
mp.insert(make_pair(4, 4));
mp.insert(make_pair(3, 3));
unordered_map<int, int>::iterator it = mp.begin();
while (it != mp.end()) {
cout << it->first << ":" << it->second << endl;
it++;
}
it = mp.find(3);
if (it != mp.end()) {
cout << "找到了 " << it->first << ":" << it->second << endl;
}
mp.erase(it);
if (!mp.count(3)) {
cout << "没有找到 3" << endl;
}
mp[3] = 5;
cout << mp[3] << endl;
}
void test2() {
string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
unordered_map<string, int> mp;
for (auto& e : arr) {
unordered_map<string, int>::iterator ret = mp.find(e);
if (ret != mp.end()) {
ret->second++;
} else {
mp.insert(make_pair(e, 1));
}
}
for (auto& e : mp) {
cout << e.first << " " << e.second << endl;
}
}
int main() {
test1();
test2();
return 0;
}
以上代码展示了插入、查找、删除、遍历以及桶状态的查询。留意 max_load_factor() 默认是 1,所以 load_factor() 到达 1 时触发 rehash。test3 里还演示了安全访问桶元素的方式——先确认桶存在再查看大小。
模拟实现
看过标准库怎么用,现在动手写一套自己的 unordered_set 和 unordered_map,底层都用同一个哈希桶。整体框架和 set/map 的红黑树封装很像,所以重复的部分就不展开了。
哈希节点
节点只存数据 T,不区分 key 和 value——谁知道封装自己的是 unordered_set 还是 unordered_map。
template<class T> class HashNode {
public:
T _data;
HashNode<T>* _next;
HashNode(const T& data) :_data(data), _next(nullptr) {}
};
封装逻辑
- 底层哈希表的 Hash 模版参数作为上层的缺省值更合理。
- 查找或删除时需要用 key 值,所以上层容器必须保留第一个模版参数
K。
- 从节点
T 中提取 key 需要 KeyOfT 仿函数。
迭代器
迭代器里封装节点指针,模拟原生指针行为。不过真正的难点是 operator++:当前节点 _next 不为空时直接走下一个;为空则说明当前桶已遍历完,得找到下一个非空桶。这需要访问哈希表的 _tables 数组,所以迭代器里还得存上哈希表的指针。
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> struct __HTIterator {
typedef HashNode<T> Node;
Node* _node;
const HashTable<K, T, KeyOfT, Hash>* _pht;
size_t _hashi;
};
这里需要哈希表的前置声明,因为迭代器定义在哈希表之前。
template<class K, class T, class KeyOfT, class Hash> class HashTable;
另外迭代器内部要用到 _tables 这个私有成员,所以迭代器类得被声明为友元:
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;
};
operator++ 的实现就把上面两种分支写清楚:
typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
self& operator++() {
if (_node->_next) {
_node = _node->_next;
} else {
_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;
}
我们把当前桶的编号 _hashi 直接存在迭代器里,省得每次用哈希计算,虽然多占点内存但逻辑更直白。
哈希表提供迭代器接口
template<class K, class T, class KeyOfT, class Hash> class HashTable {
typedef HashNode<T> Node;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator;
public:
typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
public:
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();
}
const_iterator end() const {
return const_iterator(nullptr, this, -1);
}
};
const 版本的 begin() / end() 在返回迭代器时,如果构造函数参数不是 const HashTable*,会出现权限放大问题,所以迭代器的 _pht 成员和构造函数参数都加了 const。
unordered_set / unordered_map 的迭代器类型
unordered_set 内元素不可修改,所以普通迭代器和 const 迭代器其实都是底层哈希表的 const_iterator。
namespace dck {
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, K, SetKeyOfT, Hash>::const_iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;
const_iterator begin() const { return _ht.begin(); }
const_iterator end() const { return _ht.end(); }
private:
hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
}
unordered_map 稍微复杂点:普通迭代器的 key 不能改,value 可以改;const 迭代器什么都不能改。所以普通迭代器是底层普通迭代器,const 迭代器是底层 const 迭代器,并且 pair 的 key 带 const。
namespace dck {
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;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, 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(); }
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
插入、查找、删除
这三个接口的核心是把原来的 bool 改成迭代器或 pair<iterator,bool>,并且在需要 key 的地方一律使用仿函数。
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();
}
插入:负载因子设为 1,超过就扩容两倍,重新映射节点。返回 pair<iterator,bool> 表示插入位置和是否成功。
pair<iterator, bool> Insert(const T& data) {
KeyOfT kot;
iterator it = Find(kot(data));
if (it != end()) return make_pair(it, false);
Hash hf;
if (_n == _tables.size()) {
size_t newSize = _tables.size() * 2;
vector<Node*> newTables;
newTables.resize(newSize);
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)) % newSize;
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;
return make_pair(iterator(newNode, this, hashi), true);
}
上层封装时,unordered_map 直接调用 Insert 即可;unordered_set 需要把返回的普通迭代器转换成 const_iterator,否则类型不匹配。
pair<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);
}
bool Erase(const K& key) {
Hash hf;
size_t hashi = hf(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
if (cur->_kv.first == key) {
if (prev == nullptr) {
_tables[hashi] = cur->_next;
} else {
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
unordered_map 的 operator[] 就靠 Insert 实现:
V& operator[](const K& key) {
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
桶统计与效率测试
为了方便观察哈希表的健康状况,加一个 Some() 函数输出桶使用数、最大链长、平均链长等信息。
void Some() {
size_t bucketSize = 0;
size_t maxBucketLen = 0;
size_t sum = 0;
double averageBucketLen = 0;
for (size_t i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
if (cur) ++bucketSize;
size_t bucketLen = 0;
while (cur) {
++bucketLen;
cur = cur->_next;
}
sum += bucketLen;
if (bucketLen > maxBucketLen) maxBucketLen = bucketLen;
}
averageBucketLen = (double)sum / (double)bucketSize;
printf("all bucketSize:%d\n", _tables.size());
printf("bucketSize:%d\n", bucketSize);
printf("maxBucketLen:%d\n", maxBucketLen);
printf("averageBucketLen:%lf\n\n", averageBucketLen);
}
下面用 100 万个随机数比较 set、unordered_set 和我们自己的 HashTable 的插入、查找、删除耗时。
#include <set>
#include <unordered_set>
#include "HashTable.h"
void test() {
const size_t N = 1000000;
unordered_set<int> us;
set<int> s;
hash_bucket::HashTable<int, int> ht;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; ++i) {
v.push_back(rand() + i);
}
size_t begin1 = clock();
for (auto e : v) s.insert(e);
size_t end1 = clock();
cout << "set insert:" << end1 - begin1 << endl;
size_t begin2 = clock();
for (auto e : v) us.insert(e);
size_t end2 = clock();
cout << "unordered_set insert:" << end2 - begin2 << endl;
size_t begin10 = clock();
for (auto e : v) ht.Insert(make_pair(e, e));
size_t end10 = clock();
cout << "HashTbale insert:" << end10 - begin10 << endl << endl;
size_t begin3 = clock();
for (auto e : v) s.find(e);
size_t end3 = clock();
cout << "set find:" << end3 - begin3 << endl;
size_t begin4 = clock();
for (auto e : v) us.find(e);
size_t end4 = clock();
cout << "unordered_set find:" << end4 - begin4 << endl;
size_t begin11 = clock();
for (auto e : v) ht.Find(e);
size_t end11 = clock();
cout << "HashTable find:" << end11 - begin11 << endl << endl;
cout << "插入数据个数:" << us.size() << endl << endl;
ht.Some();
size_t begin5 = clock();
for (auto e : v) s.erase(e);
size_t end5 = clock();
cout << "set erase:" << end5 - begin5 << endl;
size_t begin6 = clock();
for (auto e : v) us.erase(e);
size_t end6 = clock();
cout << "unordered_set erase:" << end6 - begin6 << endl;
size_t begin12 = clock();
for (auto e : v) ht.Erase(e);
size_t end12 = clock();
cout << "HashTable Erase:" << end12 - begin6 << endl << endl;
}
int main() {
test();
return 0;
}
在数据量较大时,unordered_set 的插入、查找、删除都比 set 快很多。我们自己实现的哈希表甚至比标准库的 unordered_set 还快一点,主要原因是标准库为了保持迭代器按插入顺序遍历,需要额外维护链表等结构,而我们的迭代器只按桶顺序走,实现更轻量。从统计上看,最大桶长度只有 2,平均桶长度约 1.28,时间复杂度接近 O(1)。
完整代码
#pragma once
#include <iostream>
#include <vector>
using namespace std;
template<class K> struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};
template<> struct HashFunc<string> {
size_t operator()(const string& key) {
size_t hash = 0;
for (auto& e : key) {
hash *= 31;
hash += e;
}
return hash;
}
};
namespace hash_bucket {
template<class T> class HashNode {
public:
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 __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
Node* _node;
const HashTable<K, T, KeyOfT, Hash>* _pht;
size_t _hashi;
__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi) :_node(node), _pht(pht), _hashi(hashi) { }
self& operator++() {
if (_node->_next) {
_node = _node->_next;
} else {
_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;
}
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> class HashTable {
typedef HashNode<T> Node;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator;
public:
typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
public:
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();
}
const_iterator end() const {
return const_iterator(nullptr, this, -1);
}
public:
HashTable() { _tables.resize(10); }
~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) {
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();
}
pair<iterator, bool> Insert(const T& data) {
KeyOfT kot;
iterator it = Find(kot(data));
if (it != end()) return make_pair(it, false);
Hash hf;
if (_n == _tables.size()) {
size_t newSize = _tables.size() * 2;
vector<Node*> newTables;
newTables.resize(newSize);
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)) % newSize;
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;
return make_pair(iterator(newNode, this, hashi), true);
}
bool Erase(const K& key) {
Hash hf;
size_t hashi = hf(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
if (cur->_kv.first == 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<Node*> _tables;
size_t _n;
};
}
#pragma once
#include "HashTable.h"
namespace dck {
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, K, SetKeyOfT, Hash>::const_iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;
pair<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);
}
iterator find(const K& key) { return _ht.Find(key); }
iterator erase(const K& key) { return _ht.Erase(key); }
const_iterator begin() const { return _ht.begin(); }
const_iterator end() const { return _ht.end(); }
private:
hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
}
#pragma once
#include "HashTable.h"
namespace dck {
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;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;
pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
V& operator[](const K& key) {
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
iterator find(const K& key) { return _ht.Find(key); }
iterator erase(const K& key) { return _ht.Erase(key); }
iterator begin() { return _ht.begin(); }
iterator end() { return _ht.end(); }
const_iterator begin() const { return _ht.begin(); }
const_iterator end() const { return _ht.end(); }
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
最后是一个简单的功能测试,可以看看自定义容器和标准库在迭代顺序上的差异。
#include <unordered_set>
#include "MyUnorderedSet.h"
#include "MyUnorderedMap.h"
void test_unordered_set() {
dck::unordered_set<int> st;
st.insert(4);
st.insert(1);
st.insert(2);
st.insert(3);
dck::unordered_set<int>::iterator it = st.begin();
while (it != st.end()) {
cout << *it << " ";
++it;
}
cout << endl;
unordered_set<int> st1;
st1.insert(4);
st1.insert(1);
st1.insert(2);
st1.insert(3);
unordered_set<int>::iterator it1 = st1.begin();
while (it1 != st1.end()) {
cout << *it1 << " ";
++it1;
}
cout << endl;
}
void print(const dck::unordered_map<int, int>& mp) {
dck::unordered_map<int, int>::const_iterator it = mp.begin();
while (it != mp.end()) {
cout << it->first << " " << it->second << endl;
++it;
}
cout << endl;
}
void test_unordered_map() {
dck::unordered_map<int, int> mp;
mp.insert(make_pair(4, 4));
mp.insert(make_pair(1, 1));
mp.insert(make_pair(2, 2));
mp.insert(make_pair(3, 3));
print(mp);
dck::unordered_map<int, int>::iterator it = mp.begin();
while (it != mp.end()) {
it->second++;
cout << it->first << " " << it->second << endl;
++it;
}
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
dck::unordered_map<string, int> countMap;
for (auto x : arr) countMap[x]++;
for (auto t : countMap) {
cout << t.first << " " << t.second << endl;
}
cout << endl;
}
int main() {
test_unordered_set();
test_unordered_map();
return 0;
}
整个实现里,迭代器顺序选择了桶优先,省掉了维护插入顺序的额外开销,换来更直接的结构和略优的性能。这种取舍在实际项目里按场景权衡就好。
相关免费在线工具
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
- Markdown转HTML
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online
- JSON美化和格式化
将JSON字符串修饰为友好的可读格式。 在线工具,JSON美化和格式化在线工具,online