unordered_map和unordered_set相关知识详细梳理
0. 引言
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到O()，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。为了只进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，但查询效率更高。
1. unordered_map的介绍
1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此
键关联。键和映射值的类型可能不同。
3. 在内部,unordered_map没有对<key, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问
value。
6. 它的迭代器至少是前向迭代器。
2. unordered_set的介绍
unordered_set是一种无序集合，用于存储唯一元素。其特点是没有特定的顺序，并且能够快速地根据元素值进行检索。- 在
unordered_set中，元素的值即为其键，这个键唯一地标识元素。键是不可变的，因此一旦元素被插入，无法再更改其值，只能插入或删除元素。 unordered_set内部没有排序。元素根据其哈希值分配到不同的桶（buckets）中，这种结构使得可以根据值直接访问单个元素。在平均情况下，这种访问的时间复杂度是常数级（O(1)）。- 与有序集合（
set）相比，unordered_set在通过键直接访问元素时更为迅速。然而，在对部分元素进行范围遍历时，unordered_set的效率通常较低。 unordered_set的迭代器至少是前向迭代器，能够遍历集合中的元素，但遍历顺序不确定。
3. 底层数据结构
unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。
3.1 哈希的概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即
O()，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立
一一映射的关系，那么在查找时通过该函数可以很快找到该元素
这个方法成为哈希（散列）方法，该方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。
举例进行说明：
现有数据{1，4，5，6，7，9}，和一顺序结构。
通过哈希函数hash（key）= key（关键字） % capacity（容器总容量）
建立映射关系，并将数据在对应位置填入。
但是显然会出现两个元素映射到同一个位置的情况，该如何应对呢？于是便有了哈希冲突的概念。
3.2 哈希冲突
不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
例如
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
在说明哈希冲突的解决办法前，先说说哈希函数。
3.3 哈希函数
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
所以说要解决哈希冲突，第一步要设计合理的哈希函数。
哈希函数设计原则：
1. 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间。
2. 哈希函数计算出来的地址能均匀分布在整个空间中。
3. 哈希函数应该比较简单。
常见的哈希函数实现：
1. 直接定址法（常见）：
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B。
该方法得到的散列地址简单、均匀，但是需要事先知道关键字的分布情况。
使用场景：适合查找比较小且连续的情况
2. 除留余数法（常见）：
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
3. 平方取中法：
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
使用场景：适合不知道关键字的分布，其位数又不太大的情况。
4. 折叠法：
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这
几部分叠加求和，并按散列表表长，取后几位作为散列地址。
使用场景：适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。
5. 随机数法：
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中
random为随机数函数。
使用场景：通常应用于关键字长度不等时。
6. 数学分析法：
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定
相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只
有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散
列地址。
使用场景：通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的
若干位分布较均匀的情况。
3.4 处理哈希冲突
要处理哈希冲突，一方面要设计合理的哈希函数，哈希函数设计得越精妙，产生哈希冲突的可能性就越低，但是哈希冲突是无法避免的，为了解决哈希冲突，还要从哈希的存储结构上做处理。
在结构设计上，解决哈希冲突两种常见的方法是：闭散列和开散列。
3.5 散列的扩容
显然当数据大小一定，哈希函数一定的情况下，表的容量越小，出现哈希冲突的可能性就越大，反之越小。所以说为了减少哈希冲突，要合理的规划散列表的容量，不能过小，也不能过大（会导致空间浪费）。
为了处理扩容的问题，我们可以引入负载因子的概念：
4 闭散列
4.1 闭散列原理
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
关于“下一个”空位置的定义，又分为几种：
1. 线性探测：
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
例如：
插入时：
查找时：
删除：
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素
会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影
响。因此线性探测采用标记的伪删除法来删除一个元素。
2. 二次探测
线性探测的缺陷是产生冲突的数据会堆积在一块，可能会使冲突不断累积，而为了避免该问题设计了二次探测。
假设哈希函数为 h(key)，初始哈希地址为 = h(key) % table_size，探测序列的公式如下：
= (
+
) % table_size
其中：
是由哈希函数计算的初始位置。
- i 表示第 i 次探测。
是一个常数，通常为 1。
table_size是哈希表的大小，通常取素数以减少冲突。
因此，探测位置的序列为：
优点：
相比于线性探测减少了一次聚集的问题，探测分布较为均匀。
不需要额外的存储空间（相比链地址法）。
缺点：
当装载因子较大时（接近 1），二次探测性能会下降，因为空位变少。
仍然可能产生二次聚集，不能完全避免聚集问题。
实现上比线性探测稍复杂，适用于负载较低的哈希表。
4.2 闭散列模拟实现
以线性探测为例：
#include <string>
#include <vector>
#include <utility>
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 哈希表中支持字符串的操作(特化)
template<>
struct HashFunc<std::string>
{
size_t operator()(const std:: string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash *= 31;
hash += e;
}
return hash;
}
};
//采用开放定址法，即线性探测
namespace open_address
{
//表中位置状态
enum State
{
EXIST,//已有元素
EMPTY,//没有元素
DELETE//元素被删除
};
template<class K,class V>
struct HashData
{
HashData(const std::pair<K, V>& val = std::pair<K,V>())
:_val(val)
,_state(EMPTY)
{}
std::pair<K, V> _val;
State _state;
};
template<class K,class V,class Hash =HashFunc<K>>
class HashTable
{
public:
HashTable()
{
_tables.resize(10);//调用vector的resize
}
//无需写析构函数，用默认生成的析构函数自动调用vector的析构
//
//插入数据
bool Insert(const std::pair<K, V>& val)
{
//如果有重复元素，返回false
if (Find(val.first))
return false;
//检查是否需要扩容
Checkcapcity();
HashFunc<K> Hashf;
size_t hash = Hashf(val.first)%_tables.size();
//走到这步只用考虑插入了
while (_tables[hash]._state == EXIST)
{
++hash;
hash %= _tables.size();
}
_tables[hash] = HashData<K, V>(val);
_tables[hash]._state = EXIST;
++_n;
return true;
}
//查找
HashData<K, V>* Find(const K& key)
{
HashFunc<K> Hashf;
size_t hash = Hashf(key)%_tables.size();
size_t pos;
while (_tables[hash]._state != EMPTY)
{
//找到对应位置返回
if (_tables[hash]._state == EXIST && _tables[hash]._val.first == key)
return &_tables[hash];
++hash;
//若找到表尾，模后变为0
hash %= _tables.size();
}
//未找到返回空指针
return nullptr;
}
bool Erase(const K& key)
{
HashData<K, V>* find = Find(key);
if (find)
{
//找到后将状态置为DELETE
find->_state = DELETE;
return true;
}
//没找到，返回false
return false;
}
private:
//检查是否需要扩容，若需要则扩容
void Checkcapcity()
{
size_t oldsize = _tables.size();
//如果负载因子大于等于 0.7，扩容
if (_n * 10 / oldsize >= 7)
{
HashTable<K, V> newht;
newht._tables.resize(_tables.size() * 2);
for (size_t i = 0; i < oldsize; ++i)
{
if (_tables[i]._state == EXIST)
newht.Insert(_tables[i]._val);
}
_tables.swap(newht._tables);
}
}
std::vector<HashData<K, V>> _tables; //用vector顺序存储
size_t _n = 0; //存储数据个数
};
}
需要注意的是在插入操作时，不仅状态为空的位置可以插入元素，状态为被删除的位置也可以，在查找元素时，一定要查找到对应元素或者查找到空状态的位置才算结束。
5 开散列
5.1 开散列原理
开散列：开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
示意图：
插入：
查找：
删除：
5.2 开散列模拟实现
#pragma once
#include <string>
#include <vector>
#include <utility>
template<class K, class V>
struct HashNode
{
std::pair<K, V> _val; //元素
HashNode* _next; //指向下一个节点的指针
HashNode(const std::pair<K,V>& val)
:_val(val)
,_next(nullptr)
{}
};
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//特化
template<>
struct HashFunc<std::string>
{
size_t operator()(const std::string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash *= 31;
hash += e;
}
return hash;
}
};
namespace hash_bucket
{
template<class K,class V,class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
//默认构造
HashTable()
:_n(0)
{
_table.resize(10);
}
// 析构函数
~HashTable()
{
for (int i = 0; i < _table.size(); ++i)
{
Node* del = _table[i];
Node* next = del == nullptr ? nullptr : del->_next;
while (next)
{
delete del;
del = next;
next = del->_next;
}
delete del;
}
}
//插入
bool Insert(const std::pair<K,V>& data)
{
HashFunc<K> Hash;
size_t hash = Hash(data.first)%_table.size();
if (Find(data.first))//如果已有相同key的数据存在，插入失败
return false;
CheckCapacity();//若需要则扩容
//无论对应位置存不存在节点，头插
HashNode<K, V>* newnode = new HashNode<K, V>(data);
newnode->_next = _table[hash];
_table[hash] = newnode;
++_n;
return true;
}
//查找
std::pair<K,V>* Find(const K& key)
{
HashFunc<K> Hash;
size_t hash = Hash(key) % _table.size();
//如果hash位置存在数据，就在桶中查找
Node* pcur = _table[hash];
while (pcur && pcur->_val.first != key)
{
pcur = pcur->_next;
}
//判断是否找到
if (pcur)
return &pcur->_val;
else
return nullptr;
}
//删除指定元素
bool Erase(const K& key)
{
HashFunc<K> Hash;
size_t hash = Hash(key) % _table.size();
Node* pcur = _table[hash];
Node* prev = nullptr;
while (pcur && pcur->_val.first != key)
{
prev = pcur;
pcur = pcur->_next;
}
//如果找到了pcur
if (pcur)
{
//如果prev存在
if (prev)
{
prev->_next = pcur->_next;
}
//头删
else
{
_table[hash] = pcur->_next;
}
delete pcur;
--_n;
return true;
}
//如果没找pcur
else
{
return false;
}
}
private:
//检查是否需要扩容，如需要则扩容
void CheckCapacity()
{
//若负载因子大于7，则扩容
if (_n * 10 / _table.size() >= 7)
{
HashTable<K, V> newht;
newht._table.resize(_table.size() * 2);
for (size_t i = 0; i < _table.size(); ++i)
{
//如果节点指针不为空
Node* pcur = _table[i];
while (pcur)
{
newht.Insert(pcur->_val);
pcur = pcur->_next;
}
}
_table.swap(newht._table);
}
}
std::vector<Node*> _table;//指针数字
size_t _n;//表中元素个数
};
}
总体来说就是维护各个单链表的增删查改，这里用的单链表，因为头插操作更简单，而且也不需要维护头节点。
6. 封装unordered_set
无论是unordered_set还是unordered_map，这里和STL库保持一致，底层都用开散列。
首先要加入新的模板参数，KeyofValue来让开散列可以同时兼容unordered_set和unordered_map两种结构。（KeyofValue需传入获得pair键值对的key值的仿函数类型）。同时，所有设计key值比较的地方，都要更改为调用仿函数获取key值再进行比较。
然后要实现开散列的迭代器，方便上层封装时直接调用底层接口。
主体结构：
template<class K,class V,class KeyofValue,class Hash>
class HashTable
{
//声明友元
template<class K, class V, class Ptr, class Ref, class KeyofValue, class Hash>
friend struct HTIterator;
public:
typedef HashNode<K, V> Node;
typedef HTIterator<K, V, V*, V&, KeyofValue, Hash> Iterator;
typedef HTIterator<K, V, const V*, const V&, KeyofValue, Hash> Const_Iterator;
//默认构造
HashTable()
:_n(0)
{
_table.resize(10);
}
// 析构函数
~HashTable()
{
for (int i = 0; i < _table.size(); ++i)
{
Node* del = _table[i];
Node* next = del == nullptr ? nullptr : del->_next;
while (next)
{
delete del;
del = next;
next = del->_next;
}
delete del;
}
}
//迭代器
Iterator Begin()
{
if (_n == 0)
return End();
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
return Iterator(_table[i],this);
}
return End();
}
Iterator End()
{
return Iterator( nullptr,this);
}
Const_Iterator Begin() const
{
if (_n == 0)
return End();
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
return Const_Iterator(_table[i], this);
}
return End();
}
Const_Iterator End() const
{
return Const_Iterator(nullptr,this);
}
//插入
std::pair<Iterator,bool> Insert(const V& data)
{
KeyofValue kov;
HashFunc<K> Hash;
Iterator it = Find(kov(data));
if (it._node)//如果已有相同key的数据存在，插入失败
{
return { Iterator(it._node, this),false };
}
CheckCapacity();//若需要则扩容
size_t hash = Hash(kov(data)) % _table.size();
//无论对应位置存不存在节点，头插
HashNode<K, V>* newnode = new HashNode<K, V>(data);
newnode->_next = _table[hash];
_table[hash] = newnode;
++_n;
return { Iterator(newnode, this),true};
}
//查找
//std::pair<K,V>* Find(const K& key)
Iterator Find(const K& key)
{
KeyofValue kov;
HashFunc<K> Hash;
size_t hash = Hash(key) % _table.size();
//如果hash位置存在数据，就在桶中查找
Node* pcur = _table[hash];
while (pcur && kov(pcur->_val) != key)
{
pcur = pcur->_next;
}
判断是否找到
//if (pcur)
// return &pcur->_val;
//else
// return nullptr;
return Iterator(pcur,this);
}
Const_Iterator Find(const K& key) const
{
KeyofValue kov;
HashFunc<K> Hash;
size_t hash = Hash(key) % _table.size();
//如果hash位置存在数据，就在桶中查找
Node* pcur = _table[hash];
while (pcur && kov(pcur->_val) != key)
{
pcur = pcur->_next;
}
判断是否找到
//if (pcur)
// return &pcur->_val;
//else
// return nullptr;
return Const_Iterator(pcur, this);
}
//删除指定元素
bool Erase(const K& key)
{
KeyofValue kov;
HashFunc<K> Hash;
size_t hash = Hash(key) % _table.size();
Node* pcur = _table[hash];
Node* prev = nullptr;
while (pcur && kov(pcur->_val) != key)
{
prev = pcur;
pcur = pcur->_next;
}
//如果找到了pcur
if (pcur)
{
//如果prev存在
if (prev)
{
prev->_next = pcur->_next;
}
//头删
else
{
_table[hash] = pcur->_next;
}
delete pcur;
--_n;
return true;
}
//如果没找pcur
else
{
return false;
}
}
private:
//检查是否需要扩容，如需要则扩容
void CheckCapacity()
{
//若负载因子大于7，则扩容
if (_n * 10 / _table.size() >= 7)
{
HashTable<K, V, KeyofValue,Hash> newht;
newht._table.resize(_table.size() * 2);
for (size_t i = 0; i < _table.size(); ++i)
{
//如果节点指针不为空
Node* pcur = _table[i];
while (pcur)
{
newht.Insert(pcur->_val);
pcur = pcur->_next;
}
}
_table.swap(newht._table);
}
}
std::vector<Node*> _table;//指针数字
size_t _n;//表中元素个数
};迭代器部分：
//前置声明
template<class K, class V, class KeyofValue, class Hash = HashFunc<K>>
class HashTable;
template<class K, class V,class Ptr,class Ref, class KeyofValue, class Hash>
struct HTIterator
{
typedef HashNode<K, V> Node;
typedef HTIterator<K, V, Ptr, Ref, KeyofValue, Hash> Self;
HTIterator(Node* node, const HashTable<K, V, KeyofValue, Hash>* pht)
:_node(node)
,_pht(pht)
{}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &_node->_val;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Self& operator++()
{
//判断当前桶是否还有节点
if (_node->_next)
{
//当前桶还有节点
_node = _node->_next;
}
else//找到下一个不为空的桶
{
KeyofValue kov;
Hash hs;
size_t hashi = hs(kov(_node->_val)) % (_pht->_table.size()) + 1;
while (hashi < _pht->_table.size())
{
if (_pht->_table[hashi])
{
break;
}
++hashi;
}
if (hashi == _pht->_table.size())
{
//如果找到末尾
_node = nullptr;
}
else
{
//没找到末尾就找到了
_node = _pht->_table[hashi];
}
}
return *this;
}
//成员变量
Node* _node;
const HashTable<K, V, KeyofValue, Hash>* _pht;
};上层封装：
#pragma once
#include "Bucket_HashTable.h"
namespace kia
{
template<class K,class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyofV
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//这里体现了底层结构的泛型设计
typedef typename hash_bucket::HashTable<K, K, SetKeyofV, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKeyofV, 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();
}
//插入
std::pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}
//查找
iterator find(const K& key)
{
return _ht.Find(key);
}
//查找
const_iterator find(const K& key) const
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, K, SetKeyofV, Hash> _ht;
};
}
基本调用开散列的实现就可以了。
7. 封装unordered_map
关于开散列的变更，上面已经说过，不再赘述。
主体结构：
template<class K,class V,class KeyofValue,class Hash>
class HashTable
{
//声明友元
template<class K, class V, class Ptr, class Ref, class KeyofValue, class Hash>
friend struct HTIterator;
public:
typedef HashNode<K, V> Node;
typedef HTIterator<K, V, V*, V&, KeyofValue, Hash> Iterator;
typedef HTIterator<K, V, const V*, const V&, KeyofValue, Hash> Const_Iterator;
//默认构造
HashTable()
:_n(0)
{
_table.resize(10);
}
// 析构函数
~HashTable()
{
for (int i = 0; i < _table.size(); ++i)
{
Node* del = _table[i];
Node* next = del == nullptr ? nullptr : del->_next;
while (next)
{
delete del;
del = next;
next = del->_next;
}
delete del;
}
}
//迭代器
Iterator Begin()
{
if (_n == 0)
return End();
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
return Iterator(_table[i],this);
}
return End();
}
Iterator End()
{
return Iterator( nullptr,this);
}
Const_Iterator Begin() const
{
if (_n == 0)
return End();
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
return Const_Iterator(_table[i], this);
}
return End();
}
Const_Iterator End() const
{
return Const_Iterator(nullptr,this);
}
//插入
std::pair<Iterator,bool> Insert(const V& data)
{
KeyofValue kov;
HashFunc<K> Hash;
Iterator it = Find(kov(data));
if (it._node)//如果已有相同key的数据存在，插入失败
{
return { Iterator(it._node, this),false };
}
CheckCapacity();//若需要则扩容
size_t hash = Hash(kov(data)) % _table.size();
//无论对应位置存不存在节点，头插
HashNode<K, V>* newnode = new HashNode<K, V>(data);
newnode->_next = _table[hash];
_table[hash] = newnode;
++_n;
return { Iterator(newnode, this),true};
}
//查找
//std::pair<K,V>* Find(const K& key)
Iterator Find(const K& key)
{
KeyofValue kov;
HashFunc<K> Hash;
size_t hash = Hash(key) % _table.size();
//如果hash位置存在数据，就在桶中查找
Node* pcur = _table[hash];
while (pcur && kov(pcur->_val) != key)
{
pcur = pcur->_next;
}
判断是否找到
//if (pcur)
// return &pcur->_val;
//else
// return nullptr;
return Iterator(pcur,this);
}
Const_Iterator Find(const K& key) const
{
KeyofValue kov;
HashFunc<K> Hash;
size_t hash = Hash(key) % _table.size();
//如果hash位置存在数据，就在桶中查找
Node* pcur = _table[hash];
while (pcur && kov(pcur->_val) != key)
{
pcur = pcur->_next;
}
判断是否找到
//if (pcur)
// return &pcur->_val;
//else
// return nullptr;
return Const_Iterator(pcur, this);
}
//删除指定元素
bool Erase(const K& key)
{
KeyofValue kov;
HashFunc<K> Hash;
size_t hash = Hash(key) % _table.size();
Node* pcur = _table[hash];
Node* prev = nullptr;
while (pcur && kov(pcur->_val) != key)
{
prev = pcur;
pcur = pcur->_next;
}
//如果找到了pcur
if (pcur)
{
//如果prev存在
if (prev)
{
prev->_next = pcur->_next;
}
//头删
else
{
_table[hash] = pcur->_next;
}
delete pcur;
--_n;
return true;
}
//如果没找pcur
else
{
return false;
}
}
private:
//检查是否需要扩容，如需要则扩容
void CheckCapacity()
{
//若负载因子大于7，则扩容
if (_n * 10 / _table.size() >= 7)
{
HashTable<K, V, KeyofValue,Hash> newht;
newht._table.resize(_table.size() * 2);
for (size_t i = 0; i < _table.size(); ++i)
{
//如果节点指针不为空
Node* pcur = _table[i];
while (pcur)
{
newht.Insert(pcur->_val);
pcur = pcur->_next;
}
}
_table.swap(newht._table);
}
}
std::vector<Node*> _table;//指针数字
size_t _n;//表中元素个数
};迭代器部分：
//前置声明
template<class K, class V, class KeyofValue, class Hash = HashFunc<K>>
class HashTable;
template<class K, class V,class Ptr,class Ref, class KeyofValue, class Hash>
struct HTIterator
{
typedef HashNode<K, V> Node;
typedef HTIterator<K, V, Ptr, Ref, KeyofValue, Hash> Self;
HTIterator(Node* node, const HashTable<K, V, KeyofValue, Hash>* pht)
:_node(node)
,_pht(pht)
{}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &_node->_val;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Self& operator++()
{
//判断当前桶是否还有节点
if (_node->_next)
{
//当前桶还有节点
_node = _node->_next;
}
else//找到下一个不为空的桶
{
KeyofValue kov;
Hash hs;
size_t hashi = hs(kov(_node->_val)) % (_pht->_table.size()) + 1;
while (hashi < _pht->_table.size())
{
if (_pht->_table[hashi])
{
break;
}
++hashi;
}
if (hashi == _pht->_table.size())
{
//如果找到末尾
_node = nullptr;
}
else
{
//没找到末尾就找到了
_node = _pht->_table[hashi];
}
}
return *this;
}
//成员变量
Node* _node;
const HashTable<K, V, KeyofValue, Hash>* _pht;
};上层封装：
#pragma once
#include "Bucket_HashTable.h"
namespace kia
{
template<class K,class V,class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyofV
{
const K& operator()(const std::pair<K, V>& kv)
{
return kv.first;
}
};
public:
//对比此处和unordered_set的不同
typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyofV, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyofV, 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();
}
//插入
std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
{
return _ht.Insert(kv);
}
//[]重载
V& operator[](const K& key)
{
std::pair<iterator, bool> ret = insert({key,V()});
return ret.first->second;
}
//查找
iterator find(const K& key)
{
return _ht.Find(key);
}
//查找
const_iterator find(const K& key) const
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, std::pair<const K, V>,MapKeyofV, Hash> _ht;
};
}