目录

前言一、哈希表的模拟实现1.1 哈希表的改造1.1.1 模板参数列表的改造1.1.2 增加迭代器操作

1.2 哈希表的模拟实现1.2.1 哈希表中仿函数的实现1.2.2 哈希表中节点类的实现1.2.3 哈希表中迭代器类的实现1.2.4 哈希表中构造函数、析构函数和 Clear() 函数的实现1.2.5 哈希表中Swap 和 Size 函数的实现1.2.6 哈希表中 begin 和 end 函数的实现1.2.7 哈希表中 Find 函数的实现1.2.8 哈希表中 Insert 和 Erase 函数的实现1.2.9 哈希表的整体实现

二、unordered_set的实现及测试三、unordered_map的实现及测试结尾

前言

上一篇文章中讲到了哈希的概念和STL中关于哈希容器的使用，并且在后面对开散列进行了模拟实现，那么在这一篇文章中在开散列的基础上进行改造成哈希表，并且在哈希表的基础上封装 unordered_set 和 unordered_map。

一、哈希表的模拟实现

1.1 哈希表的改造

1.1.1 模板参数列表的改造

K：表示关键码类型

T：不同容器V的类型不同，如果是unordered_map，K代表一个键值对，如果是unordered_set，T 为 K。

KOfT： 因为V的类型不同，通过value取key的方式就不同，详细见

unordered_map/set的实现

HF: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模

<code>template<class K, class T , class KOfT , class HF>

class hash_table;

1.1.2 增加迭代器操作

// 前置声明，否则后面的__HTIterator找不到hash_table

template<class K, class T, class KOfT, class HF>

class hash_table;

template<class K, class T , class Ref, class Ptr, class KOfT, class HF>

struct __HTIterator

{

typedef HashNode<T> Node;

typedef __HTIterator<K, T, Ref , Ptr , KOfT, HF> self;

// 成员变量

Node* _node;

// 由于const迭代器中const修饰this

// 所以这里需要加const，否则会导致权限放大

// 编译无法通过的情况

const hash_table<K, T, KOfT, HF>* _pht;

//

size_t hashi;

// 构造函数

__HTIterator(Node* node, hash_table<K, T, KOfT, HF>* pht , size_t i)

:_node(node)

,_pht(pht)

,hashi(i)

{ }

// 构造函数

__HTIterator(Node* node, const hash_table<K, T, KOfT, HF>* pht, size_t i)

:_node(node)

, _pht(pht)

, hashi(i)

{ }

self& operator++()

{

if (_node->_next)

{

// 若当前桶其他节点没有走完

// 那么继续走下一个节点

_node = _node->_next;

}

else

{

// 若当前桶的所有节点都已经走完

// 那么继续向下一个桶不为空的桶走

hashi++;

while (hashi < _pht->_table.size())

{

if (_pht->_table[hashi])

{

_node = _pht->_table[hashi];

break;

}

hashi++;

}

if (hashi == _pht->_table.size())

_node = nullptr;

}

return *this;

}

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

bool operator!=(const self& s)

{

return _node != s._node;

}

};

1.2 哈希表的模拟实现

1.2.1 哈希表中仿函数的实现

若存储key的类型不是整形时，需要将其转化为整数，整形不需要处理，日常中我们最常用到的类型是string，那么这里就写一个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 sum = 0;

for (size_t i = 0; i < s.size(); i++)

{

sum = sum * 31 + s[i];

}

return sum;

}

};

1.2.2 哈希表中节点类的实现

namespace hash_bucket

{

template<class T>

struct HashNode

{

HashNode* _next;

T _data;

HashNode(const T& data)

:_data(data)

, _next(nullptr)

{ }

};

}

1.2.3 哈希表中迭代器类的实现

namespace hash_bucket

{

// 前置声明，否则后面的__HTIterator找不到hash_table

template<class K, class T, class KOfT, class HF>

class hash_table;

template<class K, class T, class Ref, class Ptr, class KOfT, class HF>

struct __HTIterator

{

typedef HashNode<T> Node;

typedef __HTIterator<K, T, Ref, Ptr, KOfT, HF> self;

// 成员变量

Node* _node;

// 由于const迭代器中const修饰this

// 所以这里需要加const，否则会导致权限放大

// 编译无法通过的情况

const hash_table<K, T, KOfT, HF>* _pht;

//

size_t hashi;

// 构造函数

__HTIterator(Node* node, hash_table<K, T, KOfT, HF>* pht, size_t i)

:_node(node)

, _pht(pht)

, hashi(i)

{ }

// 构造函数

__HTIterator(Node* node, const hash_table<K, T, KOfT, HF>* pht, size_t i)

:_node(node)

, _pht(pht)

, hashi(i)

{ }

self& operator++()

{

if (_node->_next)

{

// 若当前桶其他节点没有走完

// 那么继续走下一个节点

_node = _node->_next;

}

else

{

// 若当前桶的所有节点都已经走完

// 那么继续向下一个桶不为空的桶走

hashi++;

while (hashi < _pht->_table.size())

{

if (_pht->_table[hashi])

{

_node = _pht->_table[hashi];

break;

}

hashi++;

}

if (hashi == _pht->_table.size())

_node = nullptr;

}

return *this;

}

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

bool operator!=(const self& s)

{

return _node != s._node;

}

};

}

1.2.4 哈希表中构造函数、析构函数和 Clear() 函数的实现

namespace hash_bucket

{

template<class K, class T, class KOfT, class HF>

class hash_table

{

public:

typedef HashNode<T> Node;

public:

// 构造函数

hash_table(int n = 10)

:_table(vector<Node*>(n))

, _n(0)

{ }

// 析构函数

~hash_table()

{

Clear();

}

void Clear()

{

for (size_t i = 0; i < _table.size(); i++)

{

Node* cur = _table[i];

while (cur)

{

Node* next = cur->_next;

delete cur;

cur = next;

}

_table[i] = nullptr;

}

}

private:

vector<Node*> _table;

int _n;

};

}

1.2.5 哈希表中Swap 和 Size 函数的实现

namespace hash_bucket

{

template<class K, class T, class KOfT, class HF>

class hash_table

{

public:

size_t Size()

{

return _n;

}

void Swap(hash_table<K, T, KOfT, HF>& ht)

{

_table.swap(ht._table);

swap(_n, ht._n);

}

private:

vector<Node*> _table;

int _n;

};

}

1.2.6 哈希表中 begin 和 end 函数的实现

namespace hash_bucket

{

template<class K, class T, class KOfT, class HF>

class hash_table

{

public:

typedef HashNode<T> Node;

typedef __HTIterator<K, T, T&, T*, KOfT, HF> iterator;

typedef __HTIterator<K, T, const T&, const T*, KOfT, HF> const_iterator;

// 将__HTIterator设置为hash_table的友元

// 使__HTIterator可以访问hash_table的私有

template<class K, class T, class Ref, class Ptr, class KOfT, class HF>

friend struct __HTIterator;

public:

// 迭代器

iterator begin()

{

for (size_t i = 0; i < _table.size(); i++)

{

if (_table[i])

return iterator(_table[i], this, i);

}

return end();

}

iterator end()

{

return iterator(nullptr, this, -1);

}

const_iterator begin()const

{

for (size_t i = 0; i < _table.size(); i++)

{

if (_table[i])

return const_iterator(_table[i], this, i);

}

return end();

}

const_iterator end()const

{

return const_iterator(nullptr, this, -1);

}

private:

vector<Node*> _table;

int _n;

};

}

1.2.7 哈希表中 Find 函数的实现

namespace hash_bucket

{

template<class K, class T, class KOfT, class HF>

class hash_table

{

public:

typedef HashNode<T> Node;

typedef __HTIterator<K, T, T&, T*, KOfT, HF> iterator;

typedef __HTIterator<K, T, const T&, const T*, KOfT, HF> const_iterator;

// 将__HTIterator设置为hash_table的友元

// 使__HTIterator可以访问hash_table的私有

template<class K, class T, class Ref, class Ptr, class KOfT, class HF>

friend struct __HTIterator;

public:

// 查找

iterator Find(const K& key)

{

HF hf;

KOfT koft;

int hashi = hf(key) % _table.size();

Node* cur = _table[hashi];

while (cur)

{

if (koft(cur->_data) == key)

return iterator(cur, this, hashi);

cur = cur->_next;

}

// 找不到返回空

return end();

}

private:

vector<Node*> _table;

int _n;

};

}

1.2.8 哈希表中 Insert 和 Erase 函数的实现

namespace hash_bucket

{

template<class K, class T, class KOfT, class HF>

class hash_table

{

public:

typedef HashNode<T> Node;

typedef __HTIterator<K, T, T&, T*, KOfT, HF> iterator;

typedef __HTIterator<K, T, const T&, const T*, KOfT, HF> const_iterator;

// 将__HTIterator设置为hash_table的友元

// 使__HTIterator可以访问hash_table的私有

template<class K, class T, class Ref, class Ptr, class KOfT, class HF>

friend struct __HTIterator;

public:

// 插入

pair<iterator, bool> Insert(const T& data)

{

HF hf;

KOfT koft;

iterator tmp = Find(koft(data));

// 不允许有相同的值

if (tmp != end())

return make_pair(tmp, false);

// 扩容

if (_n == _table.size())

{

int newcapacity = 2 * _table.size();

hash_table newtable(newcapacity);

for (size_t i = 0; i < _table.size(); i++)

{

Node* cur = _table[i];

while (cur)

{

Node* next = cur->_next;

int hashi = hf(koft(cur->_data)) % newcapacity;

cur->_next = newtable._table[hashi];

newtable._table[hashi] = cur;

cur = next;

}

_table[i] = nullptr;

}

_table.swap(newtable._table);

}

// 头插

int hashi = hf(koft(data)) % _table.size();

Node* newnode = new Node(data);

newnode->_next = _table[hashi];

_table[hashi] = newnode;

_n++;

return make_pair(iterator(newnode, this, hashi), true);

}

// 删除

bool Erase(const K& key)

{

Node* tmp = Find(key);

// 找不到则删除失败

if (tmp == nullptr)

return false;

HF hf;

KOfT koft;

int hashi = hf(key) % _table.size();

Node* prev = nullptr;

Node* cur = _table[hashi];

while (cur)

{

Node* next = cur->_next;

if (koft(cur->_data) == key)

{

if (prev == nullptr)

{

_table[hashi] = next;

}

else

{

prev->_next = next;

}

_n--;

delete cur;

return true;

}

else

{

prev = cur;

cur = next;

}

}

return false;

}

private:

vector<Node*> _table;

int _n;

};

}

1.2.9 哈希表的整体实现

#pragma once

#include<iostream>

#include<string>

#include<vector>

#include<unordered_set>

#include<set>

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 sum = 0;

for (size_t i = 0; i < s.size(); i++)

{

sum = sum * 31 + s[i];

}

return sum;

}

};

namespace hash_bucket

{

template<class T>

struct HashNode

{

HashNode* _next;

T _data;

HashNode(const T& data)

:_data(data)

, _next(nullptr)

{ }

};

// 前置声明，否则后面的__HTIterator找不到hash_table

template<class K, class T, class KOfT, class HF>

class hash_table;

template<class K, class T , class Ref, class Ptr, class KOfT, class HF>

struct __HTIterator

{

typedef HashNode<T> Node;

typedef __HTIterator<K, T, Ref , Ptr , KOfT, HF> self;

// 成员变量

Node* _node;

// 由于const迭代器中const修饰this

// 所以这里需要加const，否则会导致权限放大

// 编译无法通过的情况

const hash_table<K, T, KOfT, HF>* _pht;

//

size_t hashi;

// 构造函数

__HTIterator(Node* node, hash_table<K, T, KOfT, HF>* pht , size_t i)

:_node(node)

,_pht(pht)

,hashi(i)

{ }

// 构造函数

__HTIterator(Node* node, const hash_table<K, T, KOfT, HF>* pht, size_t i)

:_node(node)

, _pht(pht)

, hashi(i)

{ }

self& operator++()

{

if (_node->_next)

{

// 若当前桶其他节点没有走完

// 那么继续走下一个节点

_node = _node->_next;

}

else

{

// 若当前桶的所有节点都已经走完

// 那么继续向下一个桶不为空的桶走

hashi++;

while (hashi < _pht->_table.size())

{

if (_pht->_table[hashi])

{

_node = _pht->_table[hashi];

break;

}

hashi++;

}

if (hashi == _pht->_table.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 KOfT , class HF>

class hash_table

{

public:

typedef HashNode<T> Node;

typedef __HTIterator<K, T, T& , T* ,KOfT, HF> iterator;

typedef __HTIterator<K, T, const T&, const T*, KOfT, HF> const_iterator;

// 将__HTIterator设置为hash_table的友元

// 使__HTIterator可以访问hash_table的私有

template<class K, class T, class Ref, class Ptr, class KOfT, class HF>

friend struct __HTIterator;

public:

// 构造函数

hash_table(int n = 10)

:_table(vector<Node*>(n))

,_n(0)

{ }

// 析构函数

~hash_table()

{

Clear();

}

void Clear()

{

for (size_t i = 0; i < _table.size(); i++)

{

Node* cur = _table[i];

while (cur)

{

Node* next = cur->_next;

delete cur;

cur = next;

}

_table[i] = nullptr;

}

}

size_t Size()

{

return _n;

}

void Swap(hash_table<K,T,KOfT,HF>& ht)

{

_table.swap(ht._table);

swap(_n, ht._n);

}

// 迭代器

iterator begin()

{

for (size_t i = 0; i < _table.size(); i++)

{

if (_table[i])

return iterator(_table[i], this, i);

}

return end();

}

iterator end()

{

return iterator(nullptr, this, -1);

}

const_iterator begin()const

{

for (size_t i = 0; i < _table.size(); i++)

{

if (_table[i])

return const_iterator(_table[i], this, i);

}

return end();

}

const_iterator end()const

{

return const_iterator(nullptr, this, -1);

}

// 插入

pair<iterator,bool> Insert(const T& data)

{

HF hf;

KOfT koft;

iterator tmp = Find(koft(data));

// 不允许有相同的值

if (tmp != end())

return make_pair(tmp,false);

// 扩容

if (_n == _table.size())

{

int newcapacity = 2 * _table.size();

hash_table newtable(newcapacity);

for (size_t i = 0; i < _table.size(); i++)

{

Node* cur = _table[i];

while (cur)

{

Node* next = cur->_next;

int hashi = hf(koft(cur->_data)) % newcapacity;

cur->_next = newtable._table[hashi];

newtable._table[hashi] = cur;

cur = next;

}

_table[i] = nullptr;

}

_table.swap(newtable._table);

}

// 头插

int hashi = hf(koft(data)) % _table.size();

Node* newnode = new Node(data);

newnode->_next = _table[hashi];

_table[hashi] = newnode;

_n++;

return make_pair(iterator(newnode,this,hashi),true);

}

// 删除

bool Erase(const K& key)

{

Node* tmp = Find(key);

// 找不到则删除失败

if (tmp == nullptr)

return false;

HF hf;

KOfT koft;

int hashi = hf(key) % _table.size();

Node* prev = nullptr;

Node* cur = _table[hashi];

while (cur)

{

Node* next = cur->_next;

if (koft(cur->_data) == key)

{

if (prev == nullptr)

{

_table[hashi] = next;

}

else

{

prev->_next = next;

}

_n--;

delete cur;

return true;

}

else

{

prev = cur;

cur = next;

}

}

return false;

}

// 查找

iterator Find(const K& key)

{

HF hf;

KOfT koft;

int hashi = hf(key) % _table.size();

Node* cur = _table[hashi];

while (cur)

{

if (koft(cur->_data) == key)

return iterator(cur,this,hashi);

cur = cur->_next;

}

// 找不到返回空

return end();

}

void Some()

{

size_t bucketSize = 0;

size_t maxBucketLen = 0;

size_t sum = 0;

double averageBucketLen = 0;

for (size_t i = 0; i < _table.size(); i++)

{

Node* cur = _table[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", _table.size());

printf("bucketSize:%d\n", bucketSize);

printf("maxBucketLen:%d\n", maxBucketLen);

printf("averageBucketLen:%lf\n\n", averageBucketLen);

}

private:

vector<Node*> _table;

int _n;

public:

void TestHT1()

{

hash_table<int, int> ht;

int a[] = { 4,14,24,34,5,7,1 };

for (auto e : a)

{

ht.Insert(make_pair(e, e));

}

ht.Insert(make_pair(3, 3));

ht.Insert(make_pair(3, 3));

ht.Insert(make_pair(-3, -3));

ht.Some();

}

void TestHT2()

{

string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

//HashTable<string, int, HashFuncString> ht;

hash_table<string, int> ht;

for (auto& e : arr)

{

//auto ret = ht.Find(e);

HashNode<string, int>* ret = ht.Find(e);

if (ret)

{

ret->_kv.second++;

}

else

{

ht.Insert(make_pair(e, 1));

}

}

ht.Insert(make_pair("apple", 1));

ht.Insert(make_pair("sort", 1));

ht.Insert(make_pair("abc", 1));

ht.Insert(make_pair("acb", 1));

ht.Insert(make_pair("aad", 1));

}

void TestHT3()

{

const size_t N = 1000;

unordered_set<int> us;

set<int> s;

hash_table<int, int> ht;

vector<int> v;

v.reserve(N);

srand(time(0));

for (size_t i = 0; i < N; ++i)

{

//v.push_back(rand()); // N比较大时，重复值比较多

v.push_back(rand() + i); // 重复值相对少

//v.push_back(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 begin3 = clock();

for (auto e : v)

{

ht.Insert(make_pair(e, e));

}

size_t end3 = clock();

cout << "hash_table insert:" << end3 - begin3 << endl << endl;

size_t begin4 = clock();

for (auto e : v)

{

s.find(e);

}

size_t end4 = clock();

cout << "set find:" << end4 - begin4 << endl;

size_t begin5 = clock();

for (auto e : v)

{

us.find(e);

}

size_t end5 = clock();

cout << "unordered_set find:" << end5 - begin5 << endl;

size_t begin6 = clock();

for (auto e : v)

{

ht.Find(e);

}

size_t end6 = clock();

cout << "hash_table find:" << end6 - begin6 << endl << endl;

cout << "插入数据个数：" << us.size() << endl << endl;

ht.Some();

size_t begin7 = clock();

for (auto e : v)

{

s.erase(e);

}

size_t end7 = clock();

cout << "set erase:" << end7 - begin7 << endl;

size_t begin8 = clock();

for (auto e : v)

{

us.erase(e);

}

size_t end8 = clock();

cout << "unordered_set erase:" << end8 - begin8 << endl;

size_t begin9 = clock();

for (auto e : v)

{

ht.Erase(e);

}

size_t end9 = clock();

cout << "hash_table Erase:" << end9 - begin9 << endl << endl;

}

};

}

二、unordered_set的实现及测试

#pragma once

#include"HashTable.h"

namespace aj

{

template<class K>

class unordered_set

{

public:

struct SetKeyOfT

{

const K& operator()(const K& k)

{

return k;

}

};

public:

// 因为unordered_set中K是不能被改变

// 所以普通迭代器也无法改变K的值

// 所以让普通迭代器也是const迭代器

typedef typename hash_bucket::hash_table<const K, K, SetKeyOfT, HashFunc<K>>::const_iterator iterator;

typedef typename hash_bucket::hash_table<const K, K, SetKeyOfT, HashFunc<K>>::const_iterator const_iterator;

// 由于_ht.Insert(key)返回的普通迭代器

// 而pair<iterator, bool>中的迭代器

// 看起来是普通迭代器，但实际上是const迭代器

// 所以这里不能直接 return _ht.Insert(key)

pair<iterator, bool> insert(const K& key)

{

auto tmp = _ht.Insert(key);

return make_pair(iterator(tmp.first._node, tmp.first._pht, tmp.first.hashi), tmp.second);

}

// 由于这里普通迭代器也是const迭代器

// 那么这里只保留const迭代器版本

/*iterator begin()

{

return _ht.begin();

}

iterator end()

{

return _ht.end();

}*/

const_iterator begin()const

{

return _ht.begin();

}

const_iterator end()const

{

return _ht.end();

}

bool erase(const K& key)

{

return _ht.Erase(key);

}

iterator find(const K& key)

{

return _ht.Find(key);

}

void clear()

{

_ht.Clear();

}

size_t size()

{

return _ht.Size();

}

void swap(unordered_set<K>& us)

{

_ht.Swap(us._ht);

}

private:

// unordered_set中K是不能被改变的

hash_bucket::hash_table <const K, K , SetKeyOfT , HashFunc<K>> _ht;

};

void test_unordered_set()

{

// 17:05

/*unordered_set<int> us;

us.insert(5);

us.insert(15);

us.insert(52);

us.insert(3);*/

//unordered_set<int>::iterator it = us.begin();

//while (it != us.end())

//{

//// *it += 5;

//cout << *it << " ";

//++it;

//}

//cout << endl;

unordered_set<int> us1;

us1.insert(1);

us1.insert(2);

us1.insert(3);

us1.insert(4);

unordered_set<int> us2;

us2.insert(10);

us2.insert(20);

us2.insert(30);

us2.insert(40);

for (auto e : us1)

{

cout << e << " ";

}

cout << endl;

for (auto e : us2)

{

cout << e << " ";

}

cout << endl;

us1.swap(us2);

for (auto e : us1)

{

cout << e << " ";

}

cout << endl;

for (auto e : us2)

{

cout << e << " ";

}

cout << endl;

}

}

三、unordered_map的实现及测试

#pragma once

#include"HashTable.h"

namespace aj

{

template<class K , class V>

class unordered_map

{

public:

struct MapKeyOfT

{

const K& operator()(const pair<K, V>& kv)

{

return kv.first;

}

};

public:

typedef typename hash_bucket::hash_table<K, pair<const K, V>, MapKeyOfT, HashFunc<K>>::iterator iterator;

typedef typename hash_bucket::hash_table<K, pair<const K, V>, MapKeyOfT, HashFunc<K>>::const_iterator const_iterator;

pair<iterator,bool> insert(const pair<K, V>& kv)

{

return _ht.Insert(kv);

}

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 tmp = _ht.Insert(make_pair(key,V()));

return tmp.first->second;

}

const V& operator[](const K& key)const

{

auto tmp = _ht.Insert(make_pair(key, V()));

return tmp.first->second;

}

bool erase(const K& key)

{

return _ht.Erase(key);

}

iterator find(const K& key)

{

return _ht.Find(key);

}

void clear()

{

_ht.Clear();

}

size_t size()

{

return _ht.Size();

}

void swap(unordered_map<K,V>& um)

{

_ht.Swap(um._ht);

}

private:

// unordered_map中K是不能被改变的

hash_bucket::hash_table <K, pair<const K, V>, MapKeyOfT , HashFunc<K>> _ht;

};

void test_unordered_map1()

{

unordered_map<int, int> um;

um.insert(make_pair(1, 1));

um.insert(make_pair(2, 2));

um.insert(make_pair(3, 3));

um.insert(make_pair(4, 4));

unordered_map<int, int>::iterator it = um.begin();

while (it != um.end())

{

cout << it->first << ' ' << it->second << endl;

++it;

}

}

void test_unordered_map2()

{

unordered_map<string, string> dict;

dict.insert(make_pair("sort", "排序"));

dict.insert(make_pair("insert", "插入"));

dict.insert(make_pair("string", "字符串"));

for (auto& kv : dict)

{

// kv.first += 'x';

kv.second += 'x';

cout << kv.first << ":" << kv.second << endl;

}

cout << endl;

string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

unordered_map<string, int> count_map;

for (auto& e : arr)

{

count_map[e]++;

}

for (auto& kv : count_map)

{

cout << kv.first << ":" << kv.second << endl;

}

cout << endl;

}

}

结尾

到目前已经将哈希的大部分内容讲述完了，那么下一篇文章将继续完善哈希，讲述位图和布隆过滤器。

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。

希望大家以后也能和我一起进步！！🌹🌹

如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹