＜C++＞ unordered_map、unordered_set模拟实现
目录
前言
模拟实现过STL版的map、set之后，我们再来模拟实现STL版的unordered_map、unordered_set，相较于上一次模拟实现，这次的封装又稍微复杂了一些。
- 先写哈希表，测试
- map、set基本封装，此时要修改哈希表模板，达到适配效果，KeyOfT
- 普通迭代器
- const迭代器
- insert返回值、operator[]
- key不能修改的问题
一、底层HashTable
在数据结构专栏中，我们已经实现了哈希表的闭散列开放寻址法和哈希桶这两种数据结构，本文将参考STL，封装哈希桶作为unordered_set、unordered_map的底层容器。
以下是之前实现的哈希桶数据结构，采用的是key-value模型
#pragma once
#include <iostream>
#include <vector>
using namespace std;
// 获取 size_t 类型的 key 值
template<class K>
struct DefaultHashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 模板特化string
template<>
struct DefaultHashFunc<string>
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto ch : str)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
// 哈希桶
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 HashFunc = DefaultHashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;// 哈希节点类型
public:
// 获取本次增容后哈希表的大小
size_t GetNextPrime(size_t prime)
{
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
};
size_t i = 0;
for (; i < __stl_num_primes; i++)
{
if (__stl_prime_list[i] > prime)
{
return __stl_prime_list[i];
}
}
return __stl_prime_list[i];
}
HashTable()
{
_table.resize(GetNextPrime(1), nullptr);
}
HashTable(const HashTable<K, V>& hashtable)
{
_table.resize(hashtable._table.size(), nullptr);
for (int i = 0; i < hashtable._table.size(); i++)
{
Node* cur = hashtable._table[i];
while (cur)
{
Insert(cur->_kv);
cur = cur->_next;
}
}
}
//赋值运算符重载函数
HashTable& operator=(HashTable ht)
{
//交换哈希表中两个成员变量的数据
_table.swap(ht._table);
swap(_n, ht._n);
return *this; //支持连续赋值
}
// 哈希桶需要析构，因为vector内数据类型为Node*，是内置类型，vector在调用析构函数时，不会析构Node*，所以需要手动析构
~HashTable()
{
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
// 提前记录下一个节点位置，因为delete之后cur找不到next
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
bool Insert(const pair<K, V>& kv)
{
// 1. 查看哈希表中是否存在该键值的键值对
if (Find(kv.first))
return false;
HashFunc hf;
// 2. 判断是否需要调整哈希表的大小，负载因子到1就扩容
if (_n == _table.size()
{
// newSize为素数数组的下一个元素
size_t newSize = GetNextPrime(_table.size());
// a.这里只用创建一个vector重新映射，最后与this的_table swap即可
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
// b.将原哈希表中节点插入到新哈希表，节点hashi值需要重新计算，重新映射
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = hf(cur->_kv.first) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
// c.交换两个vector类型的哈希表
_table.swap(newTable);
}
// 3. 将键值对插入哈希表
// 计算hashi时，需要考虑模板K的类型，所以使用仿函数获取size_t类型的key值
size_t hashi = hf(kv.first) % _table.size();
// 头插
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
// 4. 有效载荷++
++_n;
return true;
}
Node* Find(const K& key)
{
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
HashFunc hf;
// 1. 通过哈希函数计算对应的哈希桶编号hashi
size_t hashi = hf(key) % _table.size();
// 2. 在hashi桶寻找待删除节点，需要记录删除节点的上一个节点
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)// 直到遍历完为止
{
// 找到了对应key
if (cur->_kv.first == hf(key))
{
// 如果待删除节点是头节点
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
// 有效载荷--
--_n;
delete cur;
return true;// 删除成功
}
prev = cur;
cur = cur->_next;
}
return false;
}
void Print()
{
for (int i = 0; i < _table.size(); i++)
{
printf("[%d]->", i);
Node* cur = _table[i];
while (cur)
{
printf("(%d, %d)->", cur->_kv.first, cur->_kv.second);
//cour << cur->_kv.first << ":" << cur->_kv.second << "->";
cur = cur->_next;
}
cout << "NULL" << endl;
}
cout << endl;
}
private:
// Node** _table; C语言版
// vector<list>; 不好实现迭代器，并且有些牛刀杀鸡
vector<Node*> _table;// 哈希表
size_t _n;// 有效载荷个数
};
}相关说明：
- 哈希桶内我们实现了最为重要的几个成员函数insert、erase、find、拷贝构造、析构函数
- 哈希桶需要析构，因为vector内数据类型为Node*，是一个内置类型，所以vector在调用析构函数时，析构函数不会主动析构Node*，而Node*是我们new出来的空间，所以需要手动写一个析构函数
- Insert函数：在插入前就需要判断哈希桶中是否已经存在该key值的映射，如果不存在才可以进行插入，这里的插入就是头插链表。
- 当插入一定数量后，就需要进行扩容，扩容的原因是数据量很大的时候，一个桶中可能链接成千上万的节点，这对于find来说效率很低，所以及时的根据负载因子来扩容，分散节点，这样的效率才更高。
- 最后 _n++
- Erase函数：prev、cur遍历key对应的hashi桶，使prev指向要删除节点的上一个节点，这样才能实现删除功能，如果找到了就删除节点，并返回true。删除时要注意删除掉是否是头结点，如果是头节点那么prev此时还是nullptr，需要提前判断。最后 _n--
- 遍历完没有找到那么就返回false
- Find函数：根据形参key计算hashi值（所在桶），然后遍历链表即可
1. 哈希表默认成员函数实现
构造函数
哈希表中有两个成员变量，对于_n在构造函数处会被默认初始化为整形0，对于_table我们可以在构造函数内resize，当然了如果不进行resize，也没有问题，因为inset函数内载荷因子处有两重含义，一个是判断载荷因子是否为1，另一个含义是判断哈希表载荷因子是否为0
HashTable()
{
_table.resize(GetNextPrime(1), nullptr);
}拷贝构造
哈希表在拷贝时需要进行深拷贝，否则拷贝出来的哈希表和原哈希表中存储的都是同一批结点，就会出现浅拷贝带来的问题，析构时会析构两次导致段错误。
哈希表的拷贝构造函数实现逻辑如下：
- 将哈希表的大小调整为ht._table的大小。
- 将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中，可以直接复用insert函数
HashTable(const HashTable<K, V>& hashtable)
{
_table.resize(hashtable._table.size(), nullptr);
for (int i = 0; i < hashtable._table.size(); i++)
{
Node* cur = hashtable._table[i];
while (cur)
{
Insert(cur->_kv);
cur = cur->_next;
}
}
}赋值运算符重载
实现赋值运算符重载函数时，可以通过参数间接调用拷贝构造函数，之后将拷贝构造出来的哈希表和当前哈希表的两个成员变量分别进行交换即可，当赋值运算符重载函数调用结束后，拷贝构造出来的哈希表会因为出了作用域而被自动析构，此时原哈希表之前的数据也就顺势被释放了。
//赋值运算符重载函数
HashTable& operator=(HashTable ht)
{
//交换哈希表中两个成员变量的数据
_table.swap(ht._table);
swap(_n, ht._n);
return *this; //支持连续赋值
}
析构函数
哈希桶需要析构，因为vector内数据类型为Node*，是内置类型，vector在调用析构函数时，不会析构Node*，所以需要手动析构。在析构哈希表时我们只需要依次取出非空的哈希桶，遍历哈希桶当中的结点并进行释放即可。
// 哈希桶需要析构，因为vector内数据类型为Node*，是内置类型，vector在调用析构函数时，不会析构Node*，所以需要手动析构
~HashTable()
{
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
// 提前记录下一个节点位置，因为delete之后cur找不到next
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}2. DefaultHashFunc仿函数
问题：string类型不能进行哈希函数计算hashi值
因为字符串并不像一些整数，可以进行模运算，语言并没有支持字符串的模运算，但是在我们日常编写的代码中，用字符串去做键值key是非常常见的事，比如我们用unordered_map容器统计水果出现的次数时，就需要用各个水果的名字作为键值。
而字符串并不是整型，也就意味着字符串不能直接用于计算哈希地址，我们需要通过某种方法将字符串转换成整型后，才能代入哈希函数计算哈希地址。
但遗憾的是，我们无法找到一种能实现字符串和整型之间一对一转换的方法，因为在计算机中，整型的大小是有限的，比如用无符号整型能存储的最大数字是4294967295，而众多字符能构成的字符串的种类却是无限的。
鉴于此，无论我们用什么方法将字符串转换成整型，都会存在哈希冲突，只是产生冲突的概率不同而已。
由于工程中常常使用字符串哈希，所以编程界就出现了众多优秀的字符串哈希算法，BKDRHash算法无论是在实际效果还是编码实现中，效果都是最突出的。该算法由于在Brian Kernighan与Dennis Ritchie（C语言之父）的《The C Programing Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的hash算法。
该字符串哈希算法就是取出字符串的每一位字符，然后乘上一个素数131，最后将所有计算值相加，就可以得出极小概率会发生冲突的hashi值，而选择 131（或其他类似的质数）作为乘数，并非基于严格的数学证明，而是基于经验和实践，旨在尽量减少哈希冲突，并提高哈希值的均匀性。 选择 131 并没有什么特殊的理论依据，它只是一个经验上效果不错的质数。
为什么选择质数？
选择质数作为乘数的主要原因是：
-
减少冲突: 使用质数可以减少哈希冲突的概率。如果使用非质数作为乘数，例如 10，那么对于一些特定的字符串，哈希值可能会出现规律性，导致冲突增多。 而质数的整除数较少，能使哈希值更加均匀地分布在哈希表的索引上。
-
均匀分布: 质数乘法有助于将字符串映射到哈希表中的索引更均匀地分布，减少冲突，提高哈希表的效率。
为什么是 131？
131 是一个比较常用的质数，它并非具有什么特殊的数学性质，而是经过大量的实践测试后发现它在许多情况下表现良好。 其他一些常用的质数，例如 13331 或 13131，也经常被使用。 关键在于选择一个足够大的质数，以减少哈希冲突的概率。
// 获取 size_t 类型的 key 值
template<class K>
struct DefaultHashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 模板特化string
template<>
struct DefaultHashFunc<string>
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto ch : str)
{
hash *= 131;
hash += ch;
}
return hash;
}
};然后在类内使用实例化对象的仿函数获取key即可
二、HashTable基本封装
因为map、set的数据类型不同，map的数据类型是一个键值对<key, value>，set的数据类型是一个key，所以要适配 HashTable 就要修改 HashTable 的模板，将 HashTable 内的数据类型模板、成员函数模板进行修改。
要想只用一份哈希表代码同时封装出K模型和KV模型的容器，我们必定要对哈希表的模板参数进行控制。为了与原哈希表的模板参数进行区分，这里将哈希表的第二个模板参数的名字改为T。
// 哈希桶
template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable1. HashNode节点模板修改
- 如果上层使用的是unordered_set容器，那么传入哈希表的模板参数就是key和key。
- 如果上层使用的是unordered_map容器，那么传入哈希表的模板参数就是key以及key和value构成的键值对。
而哈希结点的模板参数也应该由原来的K、V变为T：
- 上层容器是unordered_set时，传入的T是键值，哈希结点中存储的就是键值。
- 上层容器是unordered_map时，传入的T是键值对，哈希结点中存储的就是键值对。
更改模板参数后，哈希结点的定义如下：
// 节点的类型，这里的T要适配unorderedset、map
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};在哈希映射过程中，我们需要获得元素的键值，然后通过哈希函数计算出对应的哈希地址进行映射。
现在由于我们在哈希结点当中存储的数据类型是T，这个T可能就是一个键值，也可能是一个键值对，对于底层的哈希表来说，它并不知道哈希结点当中存储的数据究竟是什么类型，因此需要由上层容器提供一个仿函数，用于获取T类型数据当中的键值。
因此，unordered_map容器需要向底层哈希表提供一个仿函数，该仿函数返回键值对当中的键值。
template<class K, class V>
class unordered_map
{
//仿函数
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值key
{
return kv.first;
}
};
public:
//...
private:
HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};
虽然unordered_set容器传入哈希表的T就是键值，但是底层哈希表并不知道上层容器的种类，底层哈希表在获取键值时会统一通过传入的仿函数进行获取，因此unordered_set容器也需要向底层哈希表提供一个仿函数。
template<class K>
class unordered_set
{
//仿函数
struct SetKeyOfT
{
const K& operator()(const K& key) //返回键值key
{
return key;
}
};
public:
//...
private:
HashTable<K, K, SetKeyOfT> _ht;
};
#pragma once
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 获取 size_t 类型的 key 值
template<class K>
struct DefaultHashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 模板特化string
template<>
struct DefaultHashFunc<string>
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto ch : str)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
// 哈希桶
namespace Hash_bucket
{
// 节点的类型，这里的T要适配unorderedset、map
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 HashFunc>
class HashTable;
// KeyOfT是获取set、map的类型的Key值
// HashFunc是获取size_t类型的Key
// 哈希桶
template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
typedef HashNode<T> Node;
// 声明Iterator是HashTable的友元，即Iterator可以使用HashTable的私有变量_table
template<class K, class T, class KeyOfT, class HashFunc>
friend struct HTIterator;
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
return iterator(cur, this);
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
HashTable()
{
_table.resize(10, nullptr);
}
HashTable(const HashTable<K, T, KeyOfT, HashFunc>& hashtable)
{
_table.resize(hashtable._table.size(), nullptr);
for (int i = 0; i < hashtable._table.size(); i++)
{
Node* cur = hashtable._table[i];
while (cur)
{
Insert(cur->_kv);
cur = cur->_next;
}
}
}
// 哈希桶需要析构，因为vector内数据类型为Node*，是内置类型，vector在调用析构函数时，不会析构Node*，所以需要手动析构
~HashTable()
{
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
// 提前记录下一个节点位置，因为delete之后cur找不到next
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
bool Insert(const T& data)
{
KeyOfT kot;
HashFunc hf;
if (Find(kot(data)))
return false;
// 负载因子到1就扩容
if (_n == _table.size())
{
size_t newSize = _table.size() * 2;
// 这里只用创建一个vector重新映射，最后与this的_table swap即可
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = hf(kot(cur->_data)) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
// 计算hashi时，需要考虑模板K的类型，所以使用仿函数获取size_t类型的key值
size_t hashi = hf(kot(data)) % _table.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;
}
Node* Find(const K& key)
{
KeyOfT kot;
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
// 注意：只要不是计算hashi值，都不需要将key类型转为size_t类型，不要搞混了
if (kot(cur->_data) == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
KeyOfT kot;
HashFunc hf;
size_t hashi = hf(key) % _table.size();
// 单链表的删除操作，需要记录删除节点的上一个节点
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
void Print()
{
for (int i = 0; i < _table.size(); i++)
{
printf("[%d]->", i);
Node* cur = _table[i];
while (cur)
{
printf("(%d, %d)->", cur->_kv.first, cur->_kv.second);
//cour << cur->_kv.first << ":" << cur->_kv.second << "->";
cur = cur->_next;
}
cout << "NULL" << endl;
}
cout << endl;
}
private:
// Node** _table; C语言版
// vector<list>; 不好实现迭代器，并且有些牛刀杀鸡
vector<Node*> _table;
size_t _n;
};
}
三、HashTable迭代器
1. 普通迭代器
哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，但是由于在实现++运算符重载时，可能需要在哈希表中去寻找下一个非空的哈希桶，因此每一个正向迭代器中都应该存储哈希表的地址，即 HashTabe 的 this 指针。
对于迭代器的模板，同list、map、set模拟实现。因为要一起适配普通的迭代器和const迭代器，所以我们增加两个模板ptr、
// 迭代器类，因为++时一个桶走完了，要前往下一个桶，此时需要_table数组，
// 所以需要使用哈希表对象指针，所以要这几个模板类型
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
// 封装Node为成员变量
Node* _node;
HashTable<K, T, KeyOfT, HashFunc>* _pht;
};因此在构造正向迭代器时，我们不仅需要对应哈希结点的指针，还需要该哈希结点所在哈希表的地址。
// 构造函数
HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
:_node(node), _pht(pht)
{}当对正向迭代器进行解引用操作时，我们直接返回对应结点数据的有引用即可。
// T传入的是什么类型，就返回什么类型
// 例如unorderedset传入的只有Key，unorderedmap传入的是一个键值对
Ref operator*()
{
return _node->_data;
}当对正向迭代器进行->操作时，我们直接返回对应结点数据的地址即可。
Ptr operator->()
{
return &_node->_data;
}当我们需要比较两个迭代器是否相等时，只需要判断这两个迭代器所封装的结点是否是同一个即可。
bool operator!=(const Self& s) const
{
return _node != s._node; //判断两个结点的地址是否不同
}
bool operator==(const Self& s) const
{
return _node == s._node; //判断两个结点的地址是否相同
}
++运算符重载函数的实现逻辑并不是很难，我们只需要知道如何找到当前结点的下一个结点即可。
- 若当前结点不是当前哈希桶中的最后一个结点，则++后走到当前哈希桶的下一个结点。
- 若当前结点是当前哈希桶的最后一个结点，则++后走到下一个非空哈希桶的第一个结点。
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
// 定义对象，使用仿函数
KeyOfT kot;
HashFunc hf;
// 计算当前所在桶的hashi值，然后往后找
size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
++hashi;
while (hashi < _pht->_table.size())
{
if (_pht->_table[hashi])
{
_node = _pht->_table[hashi];
return *this;
}
++hashi;
}
// 找到尾还找不到，就返回end()，这里就直接用nullptr表示
_node = nullptr;
}
return *this;
}注意： 哈希表的迭代器类型是单向迭代器，没有反向迭代器，即没有实现–运算符的重载，若是想让哈希表支持双向遍历，可以考虑将哈希桶中存储的单链表结构换为双链表结构。
在HashTable中定义begin、end函数
// 哈希桶
template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
typedef HashNode<T> Node;
// 声明Iterator是HashTable的友元，即Iterator可以使用HashTable的私有变量_table
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
friend struct HTIterator;
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
return iterator(cur, this);
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
}2. const迭代器
构造const迭代器，我们还跟以前一样，在模板处动手
// 迭代器类，因为++时一个桶走完了，要前往下一个桶，此时需要_table数组，
// 所以需要使用哈希表对象指针，所以要这几个模板类型
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
// 封装Node为成员变量
Node* _node;
HashTable<K, T, KeyOfT, HashFunc>* _pht;
// 构造函数
HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
:_node(node), _pht(pht)
{}
// T传入的是什么类型，就返回什么类型
// 例如unorderedset传入的只有Key，unorderedmap传入的是一个键值对
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
// 定义对象，使用仿函数
KeyOfT kot;
HashFunc hf;
// 计算当前所在桶的hashi值，然后往后找
size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
++hashi;
while (hashi < _pht->_table.size())
{
if (_pht->_table[hashi])
{
_node = _pht->_table[hashi];
return *this;
}
++hashi;
}
// 找到尾还找不到，就返回end()，这里就直接用nullptr表示
_node = nullptr;
}
return *this;
}
bool operator!=(const Self& s) const
{
// 比地址
return this->_node != s._node;
}
bool operator==(const Self& s) const
{
// 比地址
return this->_node == s._node;
}
};根据HashTable传入的模板类型来决定是普通迭代器还是const迭代器
// 哈希桶
template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
typedef HashNode<T> Node;
// 声明Iterator是HashTable的友元，即Iterator可以使用HashTable的私有变量_table
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
friend struct HTIterator;
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
return iterator(cur, this);
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
// const一方面是为了重载，一方面是更好的const对象的类型适配
// const unordered_map或set对象调用begin时会调用const版本迭代器
const_iterator begin() const
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
return const_iterator(cur, this);
}
return const_iterator(nullptr, this);
}
const_iterator end() const
{
return const_iterator(nullptr, this);
}
}然后再继续在unordered_set和unordered_map中定义const_iterator使用即可。
四、unordered_set封装
对于unordered_set我们需要清楚，set的key是不能进行修改的，所以unordered_set的普通迭代器在底层其实是const迭代器。
例如以下场景，看似我们定义的是普通迭代器，但是这只是用户层，实际上在底层iterator是typedef的const_iterator ，所以*it += 1是不被允许的
my_UnorderedSet::unordered_set<int> us;
my_UnorderedSet::unordered_set<int>::iterator it = us.begin();
while (it != us.end())
{
*it += 1;
cout << *it << " ";
++it;
}实现unordered_set的各个接口时，就只需要调用底层哈希表对应的接口就行了。
namespace my_UnorderedSet
{
template<class K>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename Hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename Hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
return _ht.begin();
}
iterator end() const
{
return _ht.end();
}
bool insert(const K& key)
{
return _ht.Insert(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
Hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}特别注意：
- 因为set不允许修改key，同样的map也不允许修改key，因为哈希表的秩序就是按照key来制定了，一旦key被随意修改那么整个哈希表的秩序就会被破坏，find就会出现问题，所以我们仿照STL库中unordered_set的设计方案，将const迭代器typedef为普通迭代器，这样应用层用户在使用时虽然使用的是普通迭代器，但实际上在底层使用的是const迭代器
五、unordered_map封装
实现unordered_map的各个接口时，也是调用底层哈希表对应的接口就行了。
namespace my_UnorderedMap
{
template<class K, class V>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::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();
}
bool insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}特别注意：
- map中普通迭代器就是普通迭代器，因为map是键值映射关系，key不可以修改但是value可以修改，所以还是需要普通迭代器来修改value值，并在传入模板K前，加上const修饰，以此达到set的const迭代器的效果
六、修改HashTable的返回值类型
同map、set的封装，在STL库中，unordered_map、unordered_set返回值都是一个键值对pair<itrerator, bool> ，所以我们还要修改HashTable底层容器insert、find的返回值，改为pair<itrerator, bool> 类型
1. Insert
返回时构建一个pair对象，可以pairpair<itrerator, bool>({}）方式返回匿名对象，也可以调用模板函数make_pair（函数内部会构造并返回一个pair），类型为pair<itrerator, bool>
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
HashFunc hf;
iterator it = Find(kot(data));
if (it != end())
{
return make_pair(it, false);
}
// 负载因子到1就扩容
if (_n == _table.size())
{
size_t newSize = GetNextPrime(_table.size());
//cout << "扩容了，原大小是 " << _table.size() << "扩容后为 " << newSize << endl;
// 这里只用创建一个vector重新映射，最后与this的_table swap即可
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = hf(kot(cur->_data)) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
// 计算hashi时，需要考虑模板K的类型，所以使用仿函数获取size_t类型的key值
size_t hashi = hf(kot(data)) % _table.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return make_pair(iterator(newnode, this), true);
}2. Find
iterator Find(const K& key)
{
KeyOfT kot;
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
// 注意：只要不是计算hashi值，都不需要将key类型转为size_t类型，不要搞混了
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return end();
}3. unordered_map修改
然后修改unordered_map、unordered_set中insert函数的返回值
#pragma once
#include "HashTable.h"
namespace my_UnorderedMap
{
template<class K, class V>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::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);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}4. unordered_set修改
#pragma once
#include "HashTable.h"
namespace my_UnorderedSet
{
template<class K>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename Hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename Hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
return _ht.begin();
}
iterator end() const
{
return _ht.end();
}
pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
Hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}5. operator[]
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
//return (*ret.first).second;
}问题
问题一
那么这样就结束了吗？
并不是，编译后会出现这样的错误
- 严重性错误 C2440 “<function-style-cast>”: 无法从“initializer list”转换为“Hash_bucket::HTIterator<K,T,const T *,const T &,KeyOfT,HashFunc>”
问题定位，是以下这三个红框出现了问题，即const_iterator迭代器构造出现了类型转换问题
为什么会出现错误？
因为const_iterator迭代器函数被const修饰了，我们知道，在类中，被const修饰的函数实际上是*this被const修饰了，即this指向的内容不能被修改（this默认有const修饰），即此时形参this的类型为：
const HashTable<K, T, KeyOfT, HashFunc>* const this所以问题就是iterator构造函数出现了问题，因为const_iterator是typedef的HTItreator，返回匿名对象时，要先调用该对象的构造函数，即HTIterator的构造函数
typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
构造函数的第二个参数pht没有被const修饰，所以被const修饰的this不能传递到第二个参数内，因为const权限不能放大
那么我们直接重载一个构造函数，在构造函数的第二个参数前加上const修饰就好了吧?
同样不对，因为我们的操作只解决了实参到形参的通行，而在初始化列表处形参到成员也还是不可以，因为我们定义的成员变量HashTable的指针类型是普通类型
那么我们干脆直接将_pht类型前面加上const修饰，因为我们是为了实现operator++才传入的this指针，对于operator++函数，我们并没有修改this的任何成员，只是获取_table的信息而已 ，那么我们再来看看
编译成功。
为什么红黑树封装时就没有这个问题呢？
因为红黑树迭代器不需要红黑树这个对象，它只需要红黑树的节点即可，没有传递this指针的步骤
实际上，在STL库中，STL库干脆又写了一个const_iterator类，并将cur、pht都加上了const修饰，当然了我们的这种写法也对
问题二
问题一解决了，但是随之而来了另一个问题，set的普通迭代器是const迭代器
因为HashTable返回的pair键值对中，第一个参数iterator是一个普通迭代器，而set中iterator是一个const迭代器，类型不同，又没有构造函数，所以return报错
这两个pair中的iterator类型不一样，所以pair类型不同。例如，vector<int>，vector<char>模板类型不同，也就是两个不同的类型
我们期待pair中的普通迭代器转为const迭代器，要怎么实现两个不同类型之间的转换呢？
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
// 封装Node为成员变量
Node* _node;
const HashTable<K, T, KeyOfT, HashFunc>* _pht;
// 构造函数
HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
:_node(node), _pht(pht)
{}
// 该函数是为了处理set的insert返回值类型不一致问题，不能从iterator转为const_iterator
HTIterator(const Iterator& it)
:_node(it._node), _pht(it._pht)
{}
}在迭代器中写一个“构造函数”，形参我们直接指定为普通迭代器，准确来说
- 当this是普通迭代器时，该函数是拷贝构造函数
- 当this是const迭代器时，该函数是构造函数
这是因为当模板参数不同时，实例化出来的迭代器就是不同的类型，类型相同才是拷贝构造函数，类型不同就是构造函数。
这里有一个隐藏的细节，就是我们的迭代器类是struct类型，成员的权限默认是public公开，也就是可以在类外访问成员，但是如果我们将类的迭代器写为class，并将成员变量用private修饰，那么在这个函数的初始化列表处就会出现权限问题，因为我们知道，只有在同一个类内部才可以无视private访问成员，而iterator和const_iterator是不同的类模板参数，类型不同，所以在初始化列表处就会因在类外获取private成员而失败！所以如果将迭代器类写为class类型，那么就需要public修饰成员变量。
了解了错误原因，并写完了构造函数后我们再回到unordered_set的insert返回值处进行修改
- 此时可以直接 return _ht.Insert(key)，但是这种构造方式可能有编译器不支持，所以我们有第二种方式
- 我们在函数内构造一个pair再返回，return返回时先构造pair匿名对象，然后在初始化列表处会调用自定义类型的构造函数，所以ret.first，即iterator，就会被构造为cosnt_iterator
pair<iterator, bool> insert(const K& key)
{
pair<typename Hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
return pair<iterator, bool>(ret.first, ret.second);
// return返回时先构造pair匿名对象，然后在初始化列表处会调用自定义类型的构造函数，
// 所以ret.first，即iterator，就会被构造为cosnt_iterator
}强调
类模板相同，但是类模板参数不同，那么实例化出来的就是不同的类型，就如同，vector<int>，vector<char>，不要想着能隐式类型转换，因为这是自定义类型！！！所以insert返回的键值对一个是普通迭代器实例化的键值对，另一个是const迭代器实例化的键值对，这是两个不同的类型，也不要想什么这属于const权限缩小情况，对于const权限缩小和放大只针对引用和指针并且是同类型，这两个类型都不相同，就不是权限问题！！！
例如这两个例子： 这两个迭代器就是我们底层实现的迭代器，这两个迭代器类型相同吗？
不同！因为这两个迭代器虽然使用的是同一个类模板，但是传入的模板参数不同，也就是说这两个迭代器是不同的类型，并且相互之间赋值、构造都是不支持的
封装后代码
HashTable.h
#pragma once
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 获取 size_t 类型的 key 值
template<class K>
struct DefaultHashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 模板特化string
template<>
struct DefaultHashFunc<string>
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto ch : str)
{
hash *= 131;
hash += ch;
}
return hash;
}
};
// 哈希桶
namespace Hash_bucket
{
// 节点的类型，这里的T要适配unorderedset、map
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 HashFunc>
class HashTable;
// KeyOfT是获取set、map的类型的Key值
// HashFunc是获取size_t类型的Key
// 迭代器类，因为++时一个桶走完了，要前往下一个桶，此时需要_table数组，
// 所以需要使用哈希表对象指针，所以要这几个模板类型
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
// 封装Node为成员变量
Node* _node;
const HashTable<K, T, KeyOfT, HashFunc>* _pht;
// 构造函数
HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
:_node(node), _pht(pht)
{}
// 该函数是为了处理set的insert返回值类型不一致问题，不能从iterator转为const_iterator
// this为普通迭代器时，该函数为拷贝构造函数
// this为const迭代器时，该函数为构造函数，因为类模板传入的参数不同，两者为不同的类型
HTIterator(const Iterator& it)
:_node(it._node), _pht(it._pht)
{}
// T传入的是什么类型，就返回什么类型
// 例如unorderedset传入的只有Key，unorderedmap传入的是一个键值对
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
// 定义对象，使用仿函数
KeyOfT kot;
HashFunc hf;
// 计算当前所在桶的hashi值，然后往后找
size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
++hashi;
while (hashi < _pht->_table.size())
{
if (_pht->_table[hashi])
{
_node = _pht->_table[hashi];
return *this;
}
++hashi;
}
// 找到尾还找不到，就返回end()，这里就直接用nullptr表示
_node = nullptr;
}
return *this;
}
bool operator!=(const Self& s) const
{
// 比地址
return this->_node != s._node;
}
bool operator==(const Self& s) const
{
// 比地址
return this->_node == s._node;
}
};
// 哈希桶
template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
typedef HashNode<T> Node;
// 声明Iterator是HashTable的友元，即Iterator可以使用HashTable的私有变量_table
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
friend struct HTIterator;
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
return iterator(cur, this);
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
// const一方面是为了重载，一方面是更好的const对象的类型适配
// const unordered_map或set对象调用begin时会调用const版本迭代器
const_iterator begin() const
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
if (cur)
return const_iterator(cur, this);
}
return const_iterator(nullptr, this);
}
const_iterator end() const
{
return const_iterator(nullptr, this);
}
size_t GetNextPrime(size_t prime)
{
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
};
size_t i = 0;
for (; i < __stl_num_primes; i++)
{
if (__stl_prime_list[i] > prime)
{
return __stl_prime_list[i];
}
}
return __stl_prime_list[i];
}
HashTable()
{
_table.resize(GetNextPrime(1), nullptr);
}
HashTable(const HashTable<K, T, KeyOfT, HashFunc>& hashtable)
{
_table.resize(hashtable._table.size(), nullptr);
for (int i = 0; i < hashtable._table.size(); i++)
{
Node* cur = hashtable._table[i];
while (cur)
{
Insert(cur->_kv);
cur = cur->_next;
}
}
}
//赋值运算符重载函数
HashTable& operator=(HashTable ht)
{
//交换哈希表中两个成员变量的数据
_table.swap(ht._table);
swap(_n, ht._n);
return *this; //支持连续赋值
}
// 哈希桶需要析构，因为vector内数据类型为Node*，是内置类型，vector在调用析构函数时，不会析构Node*，所以需要手动析构
~HashTable()
{
for (int i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
// 提前记录下一个节点位置，因为delete之后cur找不到next
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
HashFunc hf;
iterator it = Find(kot(data));
if (it != end())
{
return make_pair(it, false);
}
// 负载因子到1就扩容
if (_n == _table.size())
{
size_t newSize = GetNextPrime(_table.size());
//cout << "扩容了，原大小是 " << _table.size() << "扩容后为 " << newSize << endl;
// 这里只用创建一个vector重新映射，最后与this的_table swap即可
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = hf(kot(cur->_data)) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
// 计算hashi时，需要考虑模板K的类型，所以使用仿函数获取size_t类型的key值
size_t hashi = hf(kot(data)) % _table.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return make_pair(iterator(newnode, this), true);
}
iterator Find(const K& key)
{
KeyOfT kot;
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
// 注意：只要不是计算hashi值，都不需要将key类型转为size_t类型，不要搞混了
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return end();
}
bool Erase(const K& key)
{
KeyOfT kot;
HashFunc hf;
size_t hashi = hf(key) % _table.size();
// 单链表的删除操作，需要记录删除节点的上一个节点
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
void Print()
{
for (int i = 0; i < _table.size(); i++)
{
printf("[%d]->", i);
Node* cur = _table[i];
while (cur)
{
printf("(%d, %d)->", cur->_kv.first, cur->_kv.second);
//cour << cur->_kv.first << ":" << cur->_kv.second << "->";
cur = cur->_next;
}
cout << "NULL" << endl;
}
cout << endl;
}
private:
// Node** _table; C语言版
// vector<list>; 不好实现迭代器，并且有些牛刀杀鸡
vector<Node*> _table;
size_t _n;
};
}
// 闭散列开放寻址法哈希表
namespace open_addr
{
// 状态
enum STATE
{
EXIST,//存在
EMPTY,//空
DELETE//被删除
};
// 哈希表内数据类型
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
STATE _state = EMPTY;
};
template<class K, class V>
class HashTable
{
public:
HashTable()
{
// 同步size和capcacity
_table.resize(10);
}
bool Insert(const pair<K, V>& kv)
{
// 扩容，扩容因子
//if ((double)_n / _table.szie() >= 0.7)，这里需要注意类型转换问题
if (_n * 10 / _table.size() >= 7)
{
// 扩容之后，原来不冲突的key现在可能冲突了，需要重新映射到新表
size_t newSize = _table.size() * 2;
// 创建新表
HashTable<K, V> newHT;
newHT._table.resize(newSize);
// 建立新表的映射，这里复用insert不会进入扩容逻辑，因为空间是原空间二倍
for (int i = 0; i < _table.size(); ++i)
{
if (_table[i]._state == EXIST)
newHT.Insert(_table[i]._kv);
}
// 现代写法，很巧妙，局部对象出作用域直接销毁
_table.swap(newHT._table);
}
// 线性探测
size_t hashi = kv.first % _table.size();
// 如果不是有数据，那么这个位置就是可以放数据
while (_table[hashi]._state == EXIST)
{
++hashi;
hashi %= _table.size();// 下标循环
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;// 有效数据量++
return true;
}
HashData<const K, V>* Find(const K& key)
{
size_t hashi = key % _table.size();
while (_table[hashi]._state != EMPTY)
{
if (_table[hashi]._state == EXIST && _table[hashi].kv.first == key)
{
return (HashData<const K, V>*) & _table[hashi];
}
++hashi;
hashi %= _table.size();
}
return nullptr;
}
bool Erase(const K& key)
{
// 复用Find函数，找到元素之后直接改状态即可
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_n;
return true;
}
return false;
}
private:
// 该哈希表不需要手写析构函数，因为vector的数据类型是自定义类型，vector析构时自动调用自定义类型的析构函数
vector<HashData<K, V>> _table;//适配vector容器
size_t _n = 0;//有效数据量, 即使vector有size(), 但是意义不同
};
}unordered_set.h
#pragma once
#include "HashTable.h"
namespace my_UnorderedSet
{
template<class K>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename Hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename Hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
return _ht.begin();
}
iterator end() const
{
return _ht.end();
}
pair<iterator, bool> insert(const K& key)
{
//return _ht.Insert(key);
pair<typename Hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
return pair<iterator, bool>(ret.first, ret.second);
// return返回时先构造pair匿名对象，然后在初始化列表处会调用自定义类型的构造函数，
// 所以ret.first，即iterator，就会被构造为cosnt_iterator
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
Hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}unordered_map.h
#pragma once
#include "HashTable.h"
namespace my_UnorderedMap
{
template<class K, class V>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::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->second;
//return (*ret.first).second;
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}
原文地址：https://blog.csdn.net/prodigy623/article/details/142185454
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！