跳到主要内容 C++ 哈希表原理与 unordered 容器详解 | 极客日志
C++ 算法
C++ 哈希表原理与 unordered 容器详解 介绍 C++ 中 unordered_set 和 unordered_map 的特性，对比其与 set/map 的差异。详细讲解哈希概念、哈希函数设计、负载因子及哈希冲突处理方法（开放定址法、链地址法），并提供了基于链地址法的哈希表封装实现代码。
链路追踪 发布于 2026/3/30 更新于 2026/4/17 哈希
unordered_set 和 unordered_map
unordered_set
set 和 unordered_set 的功能高度相似，只是底层结构不同。
unordered_set 与 set 的差异
unordered_set 和 set 的第一个差异是对 key 的要求不同，set 要求 Key 支持小于比较，而 unordered_set 要求 Key 支持转成整形且支持等于比较 。
unordered_set 和 set 的第二个差异是迭代器的差异，set 的 iterator 是双向迭代器，unordered_set 是单向迭代器 。其次 set 底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以 set 迭代器遍历是有序 + 去重。而 unordered_set 底层是哈希表，迭代器遍历是无序 + 去重 。
unordered_set 和 set 的第三个差异是性能的差异，整体而言大多数场景下，unordered_set 的增删查改更快一些 ，因为红黑树增删查改效率是 O(logN)，而 哈希表增删查平均效率是 O(1) 。
unordered_map
map 和 unordered_map 也是高度相似，只有些许差异。
map 要求 Key 支持小于比较，而 unordered_map 要求 Key 支持转成整形且支持等于比较 。
map 的 iterator 是双向迭代器，unordered_map 是单向迭代器 ，map 底层是红黑树，unordered_map 底层是哈希表，迭代器遍历是 Key 无序 + 去重 。
大多数场景下，unordered_map 的增删查改更快一些 ，因为红黑树增删查改效率是 O(logN)，而 哈希表增删查平均效率是 O(1) 。
代码使用
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int 微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
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
main
()
int
3
1
6
7
8
2
1
1
5
6
7
6
int
begin
while
end
" "
return
0
unordered_multiset/unordered_multimap unordered_multiset/unordered_multimap 与 multiset/multimap 也是高度相似，支持 Key 冗余 。差异也如上。
哈希概念 哈希 (hash) 又称散列，是一种组织数据的方式。本质就是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系 ，查找时通过这个哈希函数计算出 Key 存储的位置，进行快速查找。
直接定址法 当关键字的范围比较集中时，如一组关键字都在 [0,99] 之间，那么开一个 100 个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在 [a,z] 的小写字母，那么我们开一个 26 个数的数组，每个关键字 ASCII 码 - 字符 a 得到的值就是存储位置的下标。也就是说 直接定址法本质即用关键字计算出一个绝对位置 或者 相对位置 。（比如计数排序）
哈希冲突 使用直接定址法，当关键字的范围比较分散时，会很浪费内存甚至内存不够用。假设我们只有数据范围是 [0, 9999] 的 N 个值，要映射到一个 M 个空间的数组中（一般 M >= N ），那么就要借助哈希函数 h(x)，关键字 key 被放到数组的 h(key) 位置，注意，h(key) 计算出的值必须在 [0, M) 之间 。
这里存在的一个问题是，两个不同的 key 可能会映射到同一个位置 ，这种问题即 哈希冲突 ，或者哈希碰撞。理想情况是找出一个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的方案。
负载因子 假设哈希表中已经映射存储了 N 个值，哈希表的大小为 M，那么 负载因子=N/M 。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低 。
将关键字转为 size_t 将关键字映射到数组中位置，一般是整数好做映射计算，如果不是整数，我们要想办法转换成整数。源码中用仿函数 Hash 把 key 转换成 size_t。如果遇到像 string、Date 无法强转的，则自己实现，string 较为常用，可以特化模板。
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 & e : s)
hash += e;
hash *= 131 ;
return hash;
}
};
哈希函数 一个好的哈希函数应该让 N 个关键字被等概率且均匀地散列分布到哈希表的 M 个空间中 ，实际中很难做到，但是要尽量往这个方向去考量设计。
除法散列法/除留余数法 除法散列法 也叫除留余数法，假设哈希表的大小为 M，key 除以 M 的余数作为映射位置的下标 ，即哈希函数为：h(key) = key % M 。
使用除法散列法时，要尽量 避免 M 为某些值 ，如 2 的幂 ，10 的幂 等。如果是 2^x，key % 2^x 本质相当于保留 key 的后 X 位（把 key 转成二进制表示的位），那么后 x 位相同的值，计算出的哈希值都是一样的，就冲突了。如果是 10^x，保留的都是 10 进值的后 x 位，如：{112, 12312}，如果 M 是 100，也就是 10^2，那么计算出的哈希值都是 12。
所以，使用除法散列法时，建议 M 取不太接近 2 的整数次幂的一个素数 。
sgi 版本的哈希表使用的方法，给了一个 近似 2 倍的素数表 。
inline unsigned long __stl_next_prime(unsigned long n)
{
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;
}
初始时哈希表的大小 M 可以为 __stl_next_prime(0)，即 M=53，此时 M 既不接近 2^5，也不接近 2^6，同时也是素数。扩容后 M=97，也实现了近似 2 倍扩容。
哈希函数还有其他方法，如乘法散列法、全域散列法等。
处理哈希冲突：开放定址法 在开放定址法中，所有的元素都放到哈希表，当一个关键字 key 用哈希函数计算出的位置冲突了，则 按照某种规则找到一个没有存储数据的位置进行存储 。规则有三种：线性探测、二次探测、双重探测。开放定址法要求 负载因子小于 1 。
线性探测
从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止 ，如果走到哈希表尾，则回绕到哈希表头的位置。h(key)=hash0=key % M ，hash0 位置 冲突 了，则 线性探测公式 为：hc(key,i)=hashi=(hash0+i) % M，i={1，2，3……M-1} 。由于负载因子小于 1，哈希表中一定有空位置，所以最多探测 M-1 次，一定能找到一个存储 key 的位置。如果 hash0 位置连续冲突 ，hash0，hash1，hash2 位置 已经存储数据 ，后续映射到 hash0，hash1，hash2，hash3 的值都会 争夺 hash3 位置 ，这种现象叫做 群集 /堆积 。二次探测可在一定程度上改善。
二次探测
从发生冲突的位置开始，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止 ，如果往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则回绕到哈希表尾的位置。h(key)=hash0=key % M ，hash0 位置 冲突 了，则 二次探测公式 为：hc(key,i)=hashi=(hash0 ± i^2) % M，i={1，2，3……M/2} 。当 hashi=(hash0 - i^2) % M 时，若 hashi<0，则 hashi+=M。
开放定址法线性探测代码实现 要给每个存储位置加一个 状态标识 ，否则删除一些值以后，会影响后面冲突的值的查找。例如删除 30，查找 20，用哈希函数求得映射下标为 9，但是下标为 9 的位置已经为空，没找到，但哈希表中其实又是有 20 的。
给每个存储位置加一个标识状态 {EXIST，DELETE，EMPTY} 。查找一个 key，求得 映射位置 h(key) ，发现状态为 EMPTY，说明整个哈希表中没有 key。如果哈希表的其他位置存在 key，表明因为冲突，h(key) 位置已经被别的值占了，则 h(key) 位置的状态应是 EXIST 或 DELETE，矛盾，所以整个哈希表中绝对没有 key。
如果 key 不能取模则用仿函数转成 size_t。
#include <vector>
enum State { EXIST, EMPTY, DELETE };
template <class K , class V >
struct HashData {
pair<K, V> _kv;
State _state = EMPTY;
};
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 & e : s) {
hash += e;
hash *= 131 ;
}
return hash;
}
};
inline unsigned long __stl_next_prime(unsigned long n) {
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 open_address {
template <class K , class V , class Hash = HashFunc<K>>
class HashTable {
public :
HashTable () : _tables(__stl_next_prime(0 )), _n(0 ) {}
bool Insert (const pair<K, V>& kv) {
if (Find (kv.first)) return false ;
if (_n * 10 / _tables.size () >= 7 )
{
HashTable<K, V, Hash> newht;
newht._tables.resize (__stl_next_prime(_tables.size () + 1 ));
for (auto & e : _tables) {
if (e._state == EXIST) newht.Insert (e._kv);
}
_tables.swap (newht._tables);
}
Hash hash;
size_t hash0 = hash (kv.first) % _tables.size ();
size_t hashi = hash0;
size_t i = 1 ;
while (_tables[hashi]._state == EXIST) {
hashi = (hash0 + i) % _tables.size ();
i++;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true ;
}
HashData<K, V>* Find (const K& key) {
Hash hash;
size_t hash0 = hash (key) % _tables.size ();
size_t hashi = hash0;
size_t i = 1 ;
while (_tables[hashi]._state != EMPTY) {
if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
return &_tables[hashi];
hashi = (hash0 + i) % _tables.size ();
i++;
}
return nullptr ;
}
bool Erase (const K& key) Find (key);
if (ret) {
ret->_state = DELETE;
return true ;
} else
return false ;
}
private :
vector<HashData<K, V>> _tables;
size_t _n;
};
}
#include "HashTable.h"
int main () int , int > ht;
int a[] = {19 , 30 , 5 , 36 , 13 , 20 , 21 , 12 };
for (auto e : a) {
ht.Insert ({e, e});
}
if (ht.Find (13 )) ht.Erase (13 );
else cout << "没找到" << endl;
return 0 ;
}
struct Date {
int _year;
int _month;
int _day;
Date (int year=1 , int month=1 , int day=1 ) : _year(year), _month(month), _day(day) {}
bool operator ==(const Date& d) {
return _year == d._year && _month == d._month && _day == d._day;
}
};
struct DateHashFunc {
size_t operator () (const Date& d) size_t hash = 0 ;
hash += d._year; hash *= 131 ;
hash += d._month; hash *= 131 ;
hash += d._day; hash *= 131 ;
return hash;
}
};
int main () "sort" , "insert" , "abcd" , "bcad" , "aadd" };
open_address::HashTable<string, string> ht;
for (auto & e : a1) ht.Insert ({e, e});
int a2[] = {-19 , -30 , 5 , 36 , 13 , 20 , 21 , 12 };
open_address::HashTable<int , int > ht1;
for (auto & e : a2) ht1. Insert ({e, e});
open_address::HashTable<Date, int , DateHashFunc> ht2;
ht2. Insert ({{2026 , 1 , 2 }, 1 });
ht2. Insert ({{2026 , 2 , 1 }, 2 });
return 0 ;
}
处理哈希冲突：链地址法 开放定址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针 ，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，则把这些冲突的数据链接成一个链表 ，挂在哈希表这个位置下面，链地址法也叫做拉链法或者 哈希桶 。
链地址法对负载因子没有要求，我们把 负载因子控制在 1 ，如果某个桶特别长时，当桶的长度大于 8，就把链表转成红黑树。
代码实现 namespace hash_bucket {
template <class K , class V >
struct HashNode {
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode (const pair<K,V>& kv) : _kv(kv), _next(nullptr ) {}
};
template <class K , class V , class Hash = HashFunc<K>>
class HashTable {
typedef HashNode<K, V> Node;
public :
HashTable () : _tables(__stl_next_prime(0 )), _n(0 ) {}
HashTable (const HashTable<K, V, Hash>& ht) {
_tables.resize (ht._tables.size ());
for (int i = 0 ; i < ht._tables.size (); i++) {
Node* htcur = ht._tables[i];
while (htcur) {
Node* newnode = new Node (htcur->_kv);
Node* cur = _tables[i];
if (cur == nullptr ) _tables[i] = newnode;
else {
while (cur->_next) cur = cur->_next;
cur->_next = newnode;
}
htcur = htcur->_next;
}
}
_n = ht._n;
}
~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 pair<K, V>& kv) if (Find (kv.first)) return false ;
Hash hash;
if (_n == _tables.size ())
{
vector<Node*> newTable (__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 hashi = hash (kv.first) % newTable.size ();
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_tables[i] = nullptr ;
}
_tables.swap (newTable);
}
size_t hashi = hash (kv.first) % _tables.size ();
Node* newnode = new Node (kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true ;
}
Node* Find (const K& key) {
Hash hash;
size_t hashi = hash (key) % _tables.size ();
Node* cur = _tables[hashi];
while (cur) {
if (cur->_kv.first == key) return cur;
cur = cur->_next;
}
return nullptr ;
}
bool Erase (const K& key) size_t hashi = hash (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;
--_n;
return true ;
} else {
prev = cur;
cur = cur->_next;
}
}
return false ;
}
private :
vector<Node*> _tables;
size_t _n = 0 ;
};
}
int main () int a[] = {19 , 30 , 5 , 36 , 13 , 20 , 21 , 12 , 24 , 96 };
hash_bucket::HashTable<int , int > ht;
for (auto & e : a) {
ht.Insert ({e, e});
}
ht.Insert ({100 , 100 });
ht.Insert ({101 , 101 });
cout << ht.Find (19 ) << endl;
cout << ht.Find (36 ) << endl;
cout << ht.Find (96 ) << endl;
cout << ht.Find (101 ) << endl << endl;
ht.Erase (19 );
ht.Erase (36 );
ht.Erase (96 );
ht.Erase (101 );
cout << ht.Find (19 ) << endl;
cout << ht.Find (36 ) << endl;
cout << ht.Find (96 ) << endl;
cout << ht.Find (101 ) << endl << endl;
return 0 ;
}
哈希表封装 unordered_set 和 unordered_map 与红黑树封装 set 和 map 类似，HashTable 也实现了泛型，其中 HashTable 用链地址法实现，仿函数 KeyOfT 取出 T 类型对象的 Key 对象，仿函数 Hash 转成 size_t。
代码实现
#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> {
size_t operator () (const string& s) size_t hash = 0 ;
for (auto & e : s) {
hash += e;
hash *= 131 ;
}
return hash;
}
};
inline unsigned long __stl_next_prime(unsigned long n) {
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_bucket {
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;
}
bool operator !=(const Self& s) {
return _node != s._node;
}
Self& operator ++()
{
if (_node->_next)
_node = _node->_next;
else
{
KeyOfT kot;
Hash hash;
size_t hashi = hash (kot (_node->_data)) % _ht->_tables.size ();
hashi++;
while (hashi < _ht->_tables.size ()) {
_node = _ht->_tables[hashi];
if (_node) break ;
else hashi++;
}
if (hashi == _ht->_tables.size ())
_node = nullptr ;
}
return *this ;
}
};
template <class K , class T , class KeyOfT , class Hash = HashFunc<T>>
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 () {
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 Iterator (nullptr , this );
}
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 ;
}
}
pair<Iterator, bool > Insert (const T& data) {
KeyOfT kot;
auto it = Find (kot (data));
if (it != End ()) return {it, false };
Hash hash;
if (_n == _tables.size ())
{
vector<Node*> _newTable;
_newTable.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 hashi = hash (kot (cur->_data)) % _newTable.size ();
cur->_next = _newTable[hashi];
_newTable[hashi] = cur;
cur = next;
}
}
_tables.swap (_newTable);
}
size_t hashi = hash (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 hash;
size_t hashi = hash (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) size_t hashi = hash (key) % _tables.size ();
Node* cur = _tables[hashi];
Node* prev = nullptr ;
while (cur) {
if (kot (cur->_data) == key)
{
if (prev == nullptr )
_tables[hashi] = 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 = 0 ;
};
}
#include "HashTable.h"
namespace mine {
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;
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, 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 ();
}
bool erase (const K& key) return _ht.Erase (key);
}
private :
hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
void print (const unordered_set<int >& us)
int >::const_iterator cit = us.begin ();
cout << typeid (us).name () << endl;
while (cit != us.end ()) {
cout << *cit << " " ;
++cit;
}
cout << endl;
for (auto e : us) {
cout << e << " " ;
}
cout << endl << endl;
}
}
#include "HashTable.h"
namespace mine {
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>::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) {
auto 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_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
void print (const unordered_map<string, string>& um)
begin ();
while (cit != um.end ()) {
cout << cit->first << "：" << cit->second << endl;
++cit;
}
cout << endl;
for (auto & e : um) {
cout << e.first << "：" << e.second << endl;
}
}
}
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include "UnorderedSet.h"
#include "UnorderedMap.h"
int main () int a[] = {3 , 11 , 86 , 7 , 88 , 82 , 1 , 881 , 5 , 6 , 7 , 6 };
mine::unordered_set<int > us;
for (auto e : a) {
us.insert (e);
}
auto it = us.begin ();
while (it != us.end ()) {
cout << *it << " " ;
++it;
}
cout << endl;
for (auto & e : us) {
cout << e << " " ;
}
cout << endl << endl;
mine::print (us);
return 0 ;
}
int main () insert ({"sort" , "排序" });
dict.insert ({"字符串" , "string" });
dict.insert ({"left" , "左" });
dict.insert ({"right" , "右" });
for (auto & e : dict) {
cout << e.first << "：" << e.second << endl;
}
cout << endl;
dict["left" ] = "左，剩余" ;
dict["insert" ] = "插入" ;
dict["string" ];
auto it = dict.begin ();
while (it != dict.end ()) {
cout << it->first << "：" << it->second << endl;
++it;
}
cout << endl;
print (dict);
return 0 ;
}
