C++用哈希表封装unordered_set和unordered_map
2023-12-21 01:20:13
目录
1.添加MyUnorderedSet.h和MyUnorderedMap.h
前言? ? ? ??
????????在上一篇文章中，我们手写了一份哈希表，也确实实现了插入删除查找等功能，但是我们只写了一份“Key，Value”模型的哈希表，并没有“Key”模型的，同时我们也没有迭代器遍历的功能，因此我们现在要用写好的哈希表去模仿库里面的unordered_ser和unordered_map。
? ? ? ?本文是根据这个哈希表进行的修改添加，具体代码如下
HashTable.h
#pragma once
#include<vector>
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 (auto& e : s)
{
sum *= 31;
sum += e;
}
return sum;
}
};
namespace kky_open_address
{
enum Status
{
EMPTY,
EXIST,
DELETE,
};
template<class K, class V>
struct HashDate
{
pair<K, V> _kv;
Status _s;
};
template<class K,class V ,class Hash = HashFunc<K>>
class HashTable
{
public:
HashTable()
{
_tables.resize(10);
}
Hash hs;
HashDate<K,V>* Find(const K& key)
{
size_t hashi = hs(key) % _tables.size();
while (_tables[hashi]._s != EMPTY)
{
if (_tables[hashi]._s != DELETE && _tables[hashi]._kv.first == key)
return &_tables[hashi];
hashi++;
hashi %= _tables.size();
}
return nullptr;
}
bool Erase(const K& key)
{
HashDate<K, V>* ret = Find(key);
if (ret)
{
ret->_s = DELETE;
--_n;
return true;
}
return false;
}
bool Insert(const pair<K,V>& kv)
{
if (Find(kv.first))
{
return false;
}
if (_n*10 / _tables.size() >= 7)
{
int newcapacity = _tables.size() * 2;
HashTable<K, V> newHT;
newHT._tables.resize(newcapacity);
for (size_t i = 0; i < _tables.size(); i++)
{
if(_tables[i]._s == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}
size_t hashi = hs(kv.first) % _tables.size();
while (_tables[hashi]._s == EXIST)
{
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._s = EXIST;
++_n;
return true;
}
void Print()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._s == EXIST)
{
//printf("[%d]->%d:%s\n", i,_tables[i]._kv.first, "EXIST");
cout << "[" << i << "]->" << _tables[i]._kv.first<<":" << _tables[i]._kv.second << endl;
}
else if(_tables[i]._s == EMPTY)
{
//printf("[%d]->%d:%s\n", i, _tables[i]._kv.first, "EMPTY");
cout << "[" << i << "]->" <<endl;
}
else
{
//printf("[%d]->%d:%s\n", i, _tables[i]._kv.first, "DELETE");
cout << "[" << i << "]->" <<"DELETE" << endl;
}
}
cout << endl;
}
private:
vector<HashDate<K,V>> _tables;
size_t _n;
};
void test01()
{
HashTable<int, int> ht;
int arr[] = { 3,13,23,4,5,14,7,13 };
for (auto e : arr)
{
ht.Insert(make_pair(e, e));
}
ht.Print();
ht.Erase(13);
ht.Print();
ht.Insert(make_pair(33,33));
ht.Print();
}
void test02()
{
string arr[] = { "香蕉","苹果","橘子","香蕉","苹果" ,"香蕉","苹果" ,"香蕉" };
HashTable<string, int> ht;
for (auto e : arr)
{
HashDate<string, int>* ret = ht.Find(e);
if(ret)
ret->_kv.second++;
else
ht.Insert(make_pair(e, 1));
}
ht.Print();
}
}
namespace kky_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.resize(10);
}
HashTable(const HashTable<K,V>& ht)
{
_tables.resize(ht._tables.size(), nullptr);
for (size_t i = 0; i < ht._tables.size(); i++)
{
Node* cur = ht._tables[i];
while (cur)
{
Node* newnode = new Node(cur->_kv);
if (_tables[i]==nullptr)
{
_tables[i] = newnode;
}
else
{
newnode->_next = _tables[i];
_tables[i] = newnode;
}
cur = cur->_next;
}
}
}
HashTable<K, V>& operator=(HashTable<K, V> ht)
{
_tables.swap(ht._tables);
swap(_n, ht._n);
return *this;
}
~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;
}
}
bool Insert(const pair<K, V>& kv)
{
Hash hs;
if (Find(kv.first))
return false;
if (_n == _tables.size())
{
vector<Node*> newtables;
newtables.resize(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
//映射到新表
size_t hashi = hs(cur->_kv.first) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
//置空，防止析构出现问题
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(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 hs;
size_t hashi = hs(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)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
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;
}
void Print()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
cout << "[" << i << "]" << "挂载"<<"->";
while (cur)
{
cout << cur->_kv.first << ":" << cur->_kv.second << "->";
cur = cur->_next;
}
cout << endl;
}
cout << endl;
}
void Some()
{
size_t bucketSize = 0;
size_t maxBucketLen = 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;
}
if (bucketLen > maxBucketLen)
{
maxBucketLen = bucketLen;
}
}
averageBucketLen = (double)bucketSize / (double)_n;
printf("all bucketSize:%d\n",_tables.size());
printf("bucketSize:%d\n", bucketSize);
printf("maxBucketLen:%d\n", maxBucketLen);
printf("averageBucketLen:%lf\n\n", averageBucketLen);
}
private:
vector<Node*> _tables;
size_t _n;
};
void test01()
{
HashTable<int, int> ht;
int arr[] = { 3,13,23,4,5,14,33,34,43,44 };
for (auto e : arr)
{
ht.Insert(make_pair(e, e));
}
ht.Print();
cout << ht.Find(43) << endl;
ht.Erase(43);
ht.Print();
cout << ht.Find(43) << endl;
}
void test02()
{
string arr[] = { "香蕉","苹果","橘子","香蕉","苹果" ,"香蕉","苹果" ,"香蕉" };
HashTable<string, int> ht;
for (auto e : arr)
{
HashNode<string, int>* ret = ht.Find(e);
if (ret)
ret->_kv.second++;
else
ht.Insert(make_pair(e, 1));
}
}
void test03()
{
const size_t N = 1000000;
unordered_set<int> us;
set<int> s;
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()); // 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 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 - begin12 << endl << endl;
}
}? ? ? ? 我们也借鉴了红黑树封装set和map的思想来进行封装。（画图还算比较详细，没看过最好可以小看一下，不然会有点难懂）
? ? ? ? 大厦并不是一下子建成，我们在封装过程中需要缝缝补补，这也是为什么我们看库里面的文件，一时间难以看懂，因为库里面的也是一步一步封装好的。那接下来让我们开始封装吧！
一、修改kv模型为data模型
一样的，我们要将“Key，Value”模型普适化，让这一份代码既可以封装“Key”模型，也可以封装“Key，Value”模型。
1.添加MyUnorderedSet.h和MyUnorderedMap.h
HashTable的第一个参数是Key，无需多说，“Key”模型，和“Key，Value”模型都需要Key。
让第二个参数来决定到底是“Key”模型还是“Key，Value”模型。“Key”模型第二个参数也是Key，“Key，Value”第二个参数是pair<const K,V>。（加const目的是让K无法修改）
同时，将Hash函数放在unordered_set和unordered_map里，因为我们封装的目的就是让你去调用这两个类，而不是去调用HashTable，因此你应该在这里传递Hash函数，并给缺省值。
MyUnorderedSet.h添加
#pragma once
#include"HashTable.h"
namespace kky
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
private:
kky_hash_bucket::HashTable<K, K, Hash> ht;
};
}MyUnorderedMap.h添加?
#pragma once
#include"HashTable.h"
namespace kky
{
template<class K,class V,class Hash = HashFunc<K>>
class unordered_map
{
private:
kky_hash_bucket::HashTable<K, pair<const K, V>, Hash> ht;
};
}2.修改HashNode
? ? ? ? 首先，将HashNode模板参数改成T，你传递的T是“pair<K,V>”，那我里面的数据_data就是pair<K,V>，你传递T的是“Key”，数据_data也是Key。
3.修改HashTable
模板类型改成T，同时修改下面的类型，该给T就给T。
但我们仅仅修改这个T也是无法达到想要的效果。比如find函数我们传递的类型是单值key，通过key判断在不在，你如果是kv模型，就会存在问题，所以我们应该添加上仿函数帮助我们处理。
unordered_set里添加SetKeyOfT，走个过场，取出key，并将类型传递给HashTable当做第三参数
unordered_map里添加MapKeyOfT，取出kv中的key，传递给HashTable当做第三参数。
?在HashTable也添加KeyOfT，后续构建的地方也都添加这个类。如下
用KeyOfT构建对象，无论是k还是kv，利用仿函数就可以取出存在data里面的key了。
后续的地方都可以这样取出，为了方便观看，这里就不多做展示了。?
最后使用代码测试一下，set测试
map测试
没问题，成功的用一张哈希表构建出了k模型和kv模型。?
二、普通迭代器
现在我们要封装迭代器了，但是迭代器的++还算是个问题。
如下图，如果当前结点是4，那么我们很容易找到他的下一个结点为14，但如果一直++到44呢？44的下一个应该是5了，那我们如何知道当前的索引hashi为多少呢？并且我们哈希表也没有，就算知道了索引hashi也没办法计算。
因此，至少我们得将哈希表的地址传递给iterator当做参数，只有能够访问到哈希表，才可以进行迭代器的++。
????????那么hashi我们要不要传，如果传，就可以直接用，如果不传，我们也可以通过哈希表来计算。因为迭代器我们并不会生成很多个，大部分的使用场景都是只使用O（1）个迭代器帮我们遍历。这里为了效率，我们牺牲了一点点空间，我们选择传递hashi。
????????那么我们现在就有三个参数，一个结点node，一个哈希表pht，还有一个索引hashi。
????????并写出构造函数、operator++、operator!=、operator*、operator->?。
operator!=、operator*、operator-> 都很简单不多赘述。
????????对于operator++，如果当前节点的_next存在，就走到_next即可，若不存在，根据hashi++，一直走到结点存在的地方，_node = _pht->_tables[_hashi];? 如果hashi==_tables.size()，也就是走到了末尾还没遇到不为空的结点，证明后续没有结点了，就将_node给到nullptr，最后return *this;
代码如下
template<class K, class T, class KeyOfT, class Hash>
struct __HTIterator
{
typedef HashNode<T> Node;
typedef __HTIterator<K, T, KeyOfT, Hash> Self;
HashTable<K, T, KeyOfT, Hash>* _pht;
Node* _node;
size_t _hashi;
__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht,size_t hashi)
:_node(node)
,_pht(pht)
,_hashi(hashi)
{}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
while (++_hashi < _pht->_tables.size())
{
if (_pht->_tables[_hashi])
{
_node = _pht->_tables[_hashi];
break;
}
}
if (_hashi == _pht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};后续我们就在HashTable里面添加iterator的begin()和end()，同时再unordered_map和unordered_set里复用一下迭代器就可以了。
HashTable添加如下代码
unordered_set添加 （为什么要用typename，因为走到当前iterator的时候，哈希表里面的iterator，还没有实例化，加了typename告诉编译器，你先别急，等后面实例化之后再去找iterator?在红黑树封装map和set有更详细的介绍。）
?unordered_map添加
我们用如下代码测试一下
报错了，看下面的第二张图，我们发现_pht根本找不到，这是为什么呢？
这是因为编译器会往上找，并不会往下找，目前的_HTIterator和HashTable他们两个存在相互依赖的关系，HashTable要用_HTIterator里面的iterator,_HTIterator要用HashTable这一张表，那么我们应该如何处理呢？
- 第一个方法是不要传递HashTable，传递HashTable里面的vector，因为我们只使用到了HashTable里面的那个vector，来进行遍历（实现++操作里面需要）。这是一个办法。
- 第二个方法是前置声明，告诉编译器HashTable在下面，你去下面找。
这里我们选择了第二种方法，目的是让我们可以更好的掌握前置声明，还有友元（等下会提到）
那么我们只需要在前面添加上声明即可。
?????????添加前置声明后，再次编译，又报错了，看下面第二张图，报错提示告诉我们_pht里_tables是私有成员，外部无法访问。
????????这就可以用到C++友元的概念了，在A中写友元B，代表B是A的友元，B类里面可以访问A类私有成员。那么我想让__HTIterator访问HashTable的私有成员，那么就应该在HashTable里面写友元__HTIterator。
? ? ? ? HashTable添加如下代码即可
现在就没有问题了。
三、const迭代器?
老生常谈了，const迭代器只有这两个地方改为const就可以了。
HashTable中iterator和const_iterator模板参数为
再如下修改一下即可?
?再添加一份const_iterator的begin()和end()方便调用
unordered_set修改如下，因为set的特性是只有key，因此无论iterator还是const_iterator我们都不要修改，因此typedef都为const_iterator，也就是无论iterator还是const_iterator本质都为const_iterator
unordered_map需要普通的迭代器不能修改key，const的迭代器kv都不能修改，因此是正常操作，代码如下
完成修改后，我们就按照之前的代码运行一下，看看普通的有没有bug，发现报错了，这是为什么呢？
分析情况如下，你构建const迭代器时传递的this被const修饰过，由于构造参数写的是普通的，因此传参发生了权限扩大，就报错了，?
修改如下，添加上const关键字，同时也要在变量_pht的地方也用const修饰，不然用const的赋值给普通的也是不可以的。
再次运行就没问题了。
切换为const迭代器再做测试。
我们在__HTIterator写一个拷贝构造函数，支持从普通的转为const的就可以了。?
?最后测试，没问题了。
四、unordered_map重载operator[]?
要将Insert返回类型从bool转化为iterator （为什么可以去红黑树封装set和map查看）
同时Find函数也应该修改，需要返回一个迭代器 ，修改如下
?Insert函数修改
?unordered_set修改
unordered_map也修改?
重载operator[]，为什么返回的是ret.frist->second呢？
ret.frist是iterator，我们iterator里面重载了operator->，这样就可以去到_data数据的地址了，再->second就可以取到第二个数据，这里编译器帮我们简化了，因此可以少些一个->
实际上应该这样写，但是太不美观了，为了可读性采用上面的写法。
最后测试一下，没问题。?
总结
????????我们修改了很多地方，一直在缝缝补补，为什么不一下子就弄好呢？因为我刚学会走路，你偏要我去跨栏，那我不得先把走路联系好，再学跑步，最后再去跨栏嘛，一步一步虽然慢，但是胜在稳健，封装也是如此。
? ? ? ? 最后附上总代码
HashTable.h
#pragma once
#include<vector>
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 (auto& e : s)
{
sum *= 31;
sum += e;
}
return sum;
}
};
namespace kky_open_address
{
enum Status
{
EMPTY,
EXIST,
DELETE,
};
template<class K, class V>
struct HashDate
{
pair<K, V> _kv;
Status _s;
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
HashTable()
:_n(0)
{
_tables.resize(10);
}
Hash hs;
HashDate<K, V>* Find(const K& key)
{
size_t hashi = hs(key) % _tables.size();
while (_tables[hashi]._s != EMPTY)
{
if (_tables[hashi]._s != DELETE && _tables[hashi]._kv.first == key)
return &_tables[hashi];
hashi++;
hashi %= _tables.size();
}
return nullptr;
}
bool Erase(const K& key)
{
HashDate<K, V>* ret = Find(key);
if (ret)
{
ret->_s = DELETE;
--_n;
return true;
}
return false;
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
if (_n * 10 / _tables.size() >= 7)
{
size_t newcapacity = _tables.size() * 2;
HashTable<K, V> newHT;
newHT._tables.resize(newcapacity);
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._s == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}
size_t hashi = hs(kv.first) % _tables.size();
while (_tables[hashi]._s == EXIST)
{
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._s = EXIST;
++_n;
return true;
}
void Print()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._s == EXIST)
{
//printf("[%d]->%d:%s\n", i,_tables[i]._kv.first, "EXIST");
cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;
}
else if (_tables[i]._s == EMPTY)
{
//printf("[%d]->%d:%s\n", i, _tables[i]._kv.first, "EMPTY");
cout << "[" << i << "]->" << endl;
}
else
{
//printf("[%d]->%d:%s\n", i, _tables[i]._kv.first, "DELETE");
cout << "[" << i << "]->" << "DELETE" << endl;
}
}
cout << endl;
}
private:
vector<HashDate<K, V>> _tables;
size_t _n;
};
void test01()
{
HashTable<int, int> ht;
int arr[] = { 3,13,23,4,5,14,7,13 };
for (auto e : arr)
{
ht.Insert(make_pair(e, e));
}
ht.Print();
ht.Erase(13);
ht.Print();
ht.Insert(make_pair(33, 33));
ht.Print();
}
void test02()
{
string arr[] = { "香蕉","苹果","橘子","香蕉","苹果" ,"香蕉","苹果" ,"香蕉" };
HashTable<string, int> ht;
for (auto e : arr)
{
HashDate<string, int>* ret = ht.Find(e);
if (ret)
ret->_kv.second++;
else
ht.Insert(make_pair(e, 1));
}
ht.Print();
}
}
namespace kky_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 __HTIterator<K, T,Ref, Ptr, KeyOfT, Hash> Self;
typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
const HashTable<K, T, KeyOfT, Hash>* _pht;
Node* _node;
size_t _hashi;
__HTIterator(Node* node,const HashTable<K, T, KeyOfT, Hash>* pht,size_t hashi)
:_node(node)
,_pht(pht)
,_hashi(hashi)
{}
__HTIterator(const iterator& it)
:_node(it._node)
,_pht(it._pht)
,_hashi(it._hashi)
{}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
while (++_hashi < _pht->_tables.size())
{
if (_pht->_tables[_hashi])
{
_node = _pht->_tables[_hashi];
break;
}
}
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
{
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> const_iterator;
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);
}
HashTable()
:_n(0)
{
_tables.resize(10);
}
HashTable(const HashTable<K, T,KeyOfT, Hash>& ht)
{
_tables.resize(ht._tables.size(), nullptr);
for (size_t i = 0; i < ht._tables.size(); i++)
{
Node* cur = ht._tables[i];
while (cur)
{
Node* newnode = new Node(cur->_kv);
if (_tables[i] == nullptr)
{
_tables[i] = newnode;
}
else
{
newnode->_next = _tables[i];
_tables[i] = newnode;
}
cur = cur->_next;
}
}
}
HashTable<K, T,KeyOfT,Hash>& operator=(HashTable<K, T, KeyOfT, Hash> ht)
{
_tables.swap(ht._tables);
swap(_n, ht._n);
return *this;
}
~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;
}
}
pair<iterator, bool> Insert(const T& data)
{
Hash hs;
KeyOfT koft;
iterator it = Find(koft(data));
if (it._node)
return make_pair(it, false);
if (_n == _tables.size())
{
vector<Node*> newtables;
newtables.resize(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
//映射到新表
size_t hashi = hs(koft(cur->_data)) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
//置空，防止析构出现问题
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(koft(data)) % _tables.size();
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return make_pair(iterator(newnode, this, hashi), true);
}
iterator Find(const K& key)
{
Hash hs;
KeyOfT koft;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (koft(cur->_data)== key)
{
return iterator(cur, this, hashi);
}
cur = cur->_next;
}
return iterator(nullptr, this, -1);
}
bool Erase(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
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;
}
void Print()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
cout << "[" << i << "]" << "挂载" << "->";
while (cur)
{
cout << cur->_kv.first << ":" << cur->_kv.second << "->";
cur = cur->_next;
}
cout << endl;
}
cout << endl;
}
void Some()
{
size_t bucketSize = 0;
size_t maxBucketLen = 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;
}
if (bucketLen > maxBucketLen)
{
maxBucketLen = bucketLen;
}
}
averageBucketLen = (double)bucketSize / (double)_n;
printf("all bucketSize:%d\n", _tables.size());
printf("bucketSize:%d\n", bucketSize);
printf("maxBucketLen:%d\n", maxBucketLen);
printf("averageBucketLen:%lf\n\n", averageBucketLen);
}
private:
vector<Node*> _tables;
size_t _n;
};
}MyUnorderedSet.h
#pragma once
#include"HashTable.h"
namespace kky
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename kky_hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
typedef typename kky_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();
}
pair<iterator,bool> Insert(const K& key)
{
return ht.Insert(key);
}
private:
kky_hash_bucket::HashTable<K, K, SetKeyOfT, Hash> ht;
};
void set_test01()
{
unordered_set<int> s;
s.Insert(1);
s.Insert(555);
s.Insert(55);
s.Insert(5);
unordered_set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << endl;
++it;
}
}
}?MyUnorderedMap.h
#pragma once
#include"HashTable.h"
namespace kky
{
template<class K,class V,class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K,V>& kv)
{
return kv.first;
}
};
public:
typedef typename kky_hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
typedef typename kky_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();
}
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.operator->()->second;
}
private:
kky_hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> ht;
};
void map_test01()
{
unordered_map<string, string> dict;
dict.Insert(make_pair("sort", "排序"));
dict.Insert(make_pair("left", "左边"));
dict.Insert(make_pair("right", "右边"));
unordered_map<string, string>::const_iterator it = dict.begin();
while (it != dict.end())
{
/*it->second = "test";*/
cout << it->first<<":"<<it->second << endl;
++it;
}
}
void map_test02()
{
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;
}
}test.cpp
#include<iostream>
#include<string>
#include<set>
#include<unordered_set>
using namespace std;
#include"HashTable.h"
#include"MyUnorderedMap.h"
#include"MyUnorderedSet.h"
int main()
{
kky::set_test01();
kky::map_test02();
}?谢谢大家观看！！！！！
文章来源:https://blog.csdn.net/kkbca/article/details/135090556
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！