在之前的篇章当中我们已经了解了AVL树和红黑树等的数据结构，并且还基于红黑树封装实现了map和set，那么接下来在本篇当中我们就将进行学习到一种新的数据结构——哈希表，但在学习哈希表的结构之前需要了解哈希相关的概念，以及了解一些处理哈希冲突的方法。接下来继续了解unordered_map和unordered_set的使用，最后试着基于哈希表实现模拟对应的unordered_map和unordered_set，接下来就开始本篇的学习吧！！！
1.哈希表实现
1.1 哈希概念
哈希（hash）又称散列，是一种组织数据的方式，在此也可以说是一种技术。本质就是通过哈希函数吧关键字key和跟存储位置建立一个映射关系，查找的时候通过这个哈希函数计算出key存储的位置，就可以进行快速的查找。
1.2 哈希函数
在哈希当中其实最重要的就是将对应key到映射值之间的计算，在此我们将这之间进行转换的叫做哈希函数，哈希函数实现的方法有很多种，接下来我们就来了解看看。
2.1 直接定址法
当关键字范围比较集中的时，直接定址法就是比较简单高效的方法，就例如当一组的跟蒋总都在[0，99]之间，那么这时就可以开一个大小为100个数的数组，每个关键字的值就是将直接存储到对应数组的下标当中。再例如一组关键字都在[a，z]的小写字母，那么我们开一个大小为26个的数组，每个关键字acsii码就是存储的下标。
实际上直接定址法本质就是用关键字来计算出一个绝对或者相对的位置。例如以下的OJ题当中就可以使用以上的方法来解决。
387. 字符串中的第一个唯一字符 - 力扣（LeetCode）
以上的OJ题就可以使用到创建一个大小为26的数组，之后通过直接定址法来进行解决
class Solution {
public:
int firstUniqChar(string s)
{
int arr[26]={0};
for(auto x:s)
{
arr[x-'a']++;
}
for(int i=0;i<s.size();i++)
{
if(arr[s[i]-'a']==1)
return i;
}
return -1;
}
};直接定址法的使用比较的简单，但是同时缺点也非常的明显，那就是当关键字比较的分散时，就会出现非常浪费空间的问题，甚至可能会引发内存不足的问题。假设我们当前数据的范围是[0，9999]的N个值，那么这时候需要将这些的值映射到大小为M的空间数组当中，假设当前M<N,那么就需要使用到直接定址法将对应的关键字key放到数组的相应位置。
这时候就会出现问题当两个不同的key可能会映射到同一个位置上这种问题就叫做哈希冲突或者哈希碰撞。而理想的哈希函数应该尽量避免哈希冲突的个数，这是因为在实际的场景当中冲突是不可避免的，我们只能做到尽量的减少冲突的次数。
假设当前的哈希表当中已经映射了N个值，而哈希表的大小为M，那么负载因子就为N/M，负载因子越大，那么就可以说明哈希冲突的概率更大，空间利用率越大；负载因子越小，哈希冲突的概率就越小，空间利用率越低。
2.2 除留余数法
除留余数法其实也叫做除法散列法，当应该哈希表的大小为M，那么通过key除以M得到的余数就可以作为映射位置的下标，也就是哈希函数：hash(key)=key%key。
但是实际上M的取值也是有一定的要求的，那就是要尽量避免M为某些值，如2的幂，10的幂等。如果是 ，那么key %本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就冲突了。如：{63 , 31}看起来没有关联的值，如果M是16，也就是 ，那么计算出的哈希值都是15，因为63的⼆进制后8位是 00111111，31的⼆进制后8位是 00011111。如果是 ，就更明显了，保留的都是10进值的后x位，如：{112, 12312}，如果M是100，也就是 ，那么计算出的哈希值都是12。
因此综上所述当使用除法散列法时，建议M取不太接近2的整数次幂的⼀个质数(素数)。
但其实也不是就说在实际当中就不能使用2的整数幂来作为M，再通过一些的手段也是可以使用的，就例如在Java当中的HashMap就是采⽤除法散列法时就是2的整数次幂做哈希表的大小M，这样玩的话，就不用取模，而可以直接位运算，相对而言位运算比模更高效⼀些。但是他不是单纯的去取模，比如M是2^16次方，本质是取后16位，那么用key’ =key>>16，然后把key和key' 异或的结果作为哈希值。本质上就是避免只让key的后几位进行运算，以上的方式就可以让key当中的所有位都进行运算。
2.3 乘法散列法
乘法散列法对哈希表大小M没有要求，他的大思路第⼀步：用关键字 K 乘上常数 A (0<A<1)，并抽取出 k*A 的小数部分。第⼆步：后再⽤M乘以k*A 的小数部分，再向下取整。
• h(key) = floor(M × ((A × key)%1.0))，其中floor表示对表达式进行下取整，A∈(0,1)，这里最重要的是A的值应该如何设定，Knuth认为A = ( 5 - 1)/2 = 0.6180339887....(黄金分割点])比较好。
• 乘法散列法对哈希表大小M是没有要求的，假设M为1024，key为1234，A = 0.6180339887, A*key= 762.6539420558，取小数部分为0.6539420558, M×((A×key)%1.0) = 0.6539420558*1024 =669.6366651392，那么h(1234) = 669。
2.4 全域散列法
如果存在⼀个恶意的对手，他针对我们提供的散列函数，特意构造出⼀个发生严重冲突的数据集，⽐如，让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决方法自然是见招拆招，给散列函数增加随机性，攻击者就⽆法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。
• h(key) = ((a × key + b)%P )%M，P需要选⼀个足够大的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了⼀个P*(P-1)组全域散列函数组。假设P=17，M=6，a = 3， b = 4, 则 。h(8) = ((3 × 8 + 4)%17)%6 =5。
注：注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使用，后续增删查改都固定使用这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插入是⼀个散列函数，查找⼜是另⼀个散列函数，就会导致找不到插⼊的key了。
1.3 处理哈希冲突
实际上在哈希表当中无论使用了什么样的方法作为哈希函数都是无法避免哈希冲突的，那么问题就来了，在产生哈希冲突的时候如何解决冲突呢？在此主要有两种方法分别是开发地址法和链地址法。
1.3.1 开放地址法
在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是小于的。这⾥的规则有三种：线性探测、二次探测、双重探测。
线性探测
从发生的冲突的位置开始，依次的向后探测，直到寻找到一个没有存储数据的位置为止，如果走到了哈希表的尾部，则回绕到哈希表头的位置。
h(key)=hash0=key%M，如果hash0位置冲突了，则线性探测公式为：h(key,i)=hashi=(hash0+i)%M，i={1,2,3……,M-1}，因为负载因子小于1，则最多探测M-1次就一定能找到存储key的位置。
例如以下示例：
在此我们需要将{19,30,5,36,13,20,21,12}这一组的数映射到M等于11的表中。
| h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1 |
二次探测
在线性探测当中如果hash0的位置冲突，并且之后的hash1,hash2,hash3等位置都出现冲突了话，那么这时后面映射到hash1,hash2,hash3位置的值都会争抢hash4位置，那么这时这种情况就称为群集/堆积。在此使用二次探测就可以一定程度的改善以上的问题。
二次探测是从冲突开始，依次左右二次方的方式进行跳跃式探测，直到寻找的下一个位置没有存储数据的位置为止，如果从左走来到了哈希表头接下来就会回绕到哈希表尾，如果从右走到哈希表的尾那么接下来就会回绕到哈希表的头。
k(key)=hash0=key%M，当hash0的位置冲突了，则二次探测公式为：hc(key,i)=hashi=(hash0+i^2)%M,i={1,2,3……,M/2}。
例如以下示例：将{}等一组数映射到M=11的表中
| h(19) = 8, h(30) = 8, h(52) = 8, h(63) = 8, h(11) = 0, h(22) = 0 |
双重散列
第⼀个哈希函数计算出的值发⽣冲突，使⽤第⼆个哈希函数计算出⼀个跟key相关的偏移量值，不断往后探测，直到寻找到下⼀个没有存储数据的位置为止。
h1(key)=hash0=key%M，hash0位置位置冲突了，那么接下来双重探测的公式为：hc(key,i)=hashi=(hash0+i*h2(key))%M,i={1,2,3……,M}。
要求 且 和M互为质数，有两种简单的取值⽅法：1、当M为2整数幂时， 从[0，M-1]任选⼀个奇数；2、当M为质数时，h2(key) = key % (M - 1) + 1。
保证 与M互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群，若最⼤公约数p=gcd(M，h1(key))>1 ，那么所能寻址的位置的个数为 M/P<M，使得对于⼀个关键字来说⽆法充分利⽤整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，那么所能寻址的位置为{1, 4, 7, 10}，寻址个数为12/gcd(12,3)=4。
例如以下示例：{19，30，52，74}等数据映射到M=11的表中，设h2(key)=key%10+1。
开发地址法代码实现
在了解了开发地址法的基本概念之后接下来就试着来实现基于开发地址法的哈希表的代码，在此我们选择最简单的线性探测实现即可。
实现代码如下所示：
首先实现一个枚举来表示哈希表当中元素的三种状态
enum State
{
EXIST,//存在
EMPTY,//空
DELETE//被删除
};
接下来再创建哈希表当中每个元素内需要存储的数据
template<class K,class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;//状态
};其余hash结构以及插入，删除等代码实现如下所示：
//使用仿函数解决某些key不能被整除
template<class K,class V>
struct HashData
{
pair<K, V> _kv;
State _state = EMPTY;//状态
};
//仿函数中string的特化
template<class K>
class HashFunc
{
public:
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
class HashFunc<string>
{
public:
size_t operator()(const string& key)
{
size_t hash=0;
for (auto& x : key)
{
hash += x;
hash *= 131;
}
return hash;
}
};
template <class K,class V ,class Hash = HashFunc<K>>
class HashTable
{
private:
//近似二倍的扩容表
inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
public:
HashTable()
{
_tables.resize(__stl_next_prime(1));
}
//插入
bool Insert(const pair<K,V> &kv)
{
if (Find(kv.first))
{
return false;
}
Hash ha;
//当超出指定的负载因子范围之后进行扩容
if ((double)_n / (double)_tables.size() >= 0.7)
{
size_t newSize = __stl_next_prime(_tables.size()+1);
HashTable<K, V> newHash;
newHash._tables.resize(newSize);
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
newHash.Insert(_tables[i]._kv);
}
}
_tables.swap(newHash._tables);
}
size_t hash0 = ha(kv.first) % _tables.size();
size_t i = 1;
size_t hashi = hash0;
while (_tables[hashi]._state == EXIST)
{
hashi = (hash0 + i) % _tables.size();
i++;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
_n++;
return true;
}
//查找
HashData<K, V>* Find(const K& key)
{
Hash ha;
size_t hash0 = ha(key) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
hashi = (hash0 + i) % _tables.size();
++i;
}
return nullptr;
}
//删除
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
ret->_state = DELETE;
--_n;
return true;
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;
};实现了开发地址法哈希表的代码之后接下来就来测试以上实现的代码是否符合我们的要求
以下代码来测试增删查基本功能是否符合要求：
void TestHT1()
{
HashTable<int, int> ht1;
ht1.Insert({ 54, 1 });
ht1.Insert({ 1, 1 });
cout << ht1.Find(1) << endl;
cout << ht1.Erase(1) << endl;
cout << ht1.Find(1) << endl;
cout << ht1.Find(54) << endl;
for (int i = 0; i < 53; i++)
{
ht1.Insert({rand(), i});
}
cout << ht1.Find(54) << endl;
}
在以上的测试的代码当中首先插入了两个键值对到哈希表当中，之后再将键为1的元素从哈希表中删除，接下来由于我们知道哈希表第一次扩容的大小是53，那么接下来就插入54个元素来验证扩容是否能正常运行。
程序执行
通过以上输出的结果可以看出删除的操作是正常运行的，删除之后键为1的元素就不存在了。接下来插入多个元素之后可以看到用来键为54的元素的地址发生了变化这就说明我们实现的扩容是没问题的。
1.3.2 链地址法
以上我们已经了解了开发地址法的的原理和基本实现方法，那么接下来就继续来了解哈希表当中了另外一种处理哈希冲突的方法——链地址法。
相比开发地址法，链地址法当中每个数据不是在直接存储在对应的哈希表当中，而是将哈希表存储对应的指针，每个指针会指向一个对应的链表，链表的每个节点就是一个映射到对应位置的值。
例如以下的示例，将{19,30,5,36,13,20,21,12,24,96}这一组的值映射到M=11的表中
| h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) =10，h(12) = 1,h(24) = 2,h(96) = 88 |
使用链地址法实现的效果如下所示：
以上哈希表有的元素下挂着一个个链表，这不就像挂着一个个的桶吗？因此链地址法实现的哈希表一般也称为哈希桶。
我们知道在开发地址法当中是要求负载因子是必须小于1的，但是在链地址当中就没有了该限制了，是可以大于1的。但是负载因子越大哈希表当中冲突的概率也是越大的。但正常的情况下链地址法当中也不会将负载因子保持的很高，正常情况下是会及那个最大的负载因子保持在1，大于1就会进行扩容。
那么接下来我们就来试着实现链地址法的哈希表
首先实现的哈希桶当中的链表当中的每个结构体，在结构体当中除了有节点内的属性信息之外还要有下一个节点的指针。实现结构如下所示：
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;
private:
//扩容大小计划
inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
public:
HashTable()
{
_tables.resize(__stl_next_prime(1));
}
//插入
bool Insert(const pair<K, V>& kv)
{
Hash hs;
//负载因子到1进行扩容
if (_n == _tables.size())
{
size_t newsize = __stl_next_prime(_tables.size() + 1);
vector<Node*> newtables(newsize);
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) % newsize;
//进行头插
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* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
//节点为头节点时
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
//节点不为头节点时
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0;
};在以上的代码当中我们就可以发现在实现插入当中的扩容好像和之前我们在实现开放地址法当中的扩容不太一样啊？在之前我们是再创建应该对应的哈希表对象，通过直接的调用对应的插入函数来实现旧数据到新表当中的转移，而在以上的代码当中是通过直接将节点转移到新的哈希桶当中，这样实现的原因是什么呢？
其实以上这样实现是因为如果通过调用插入的方式来实现会造成每次进行插入都需要创建新的节点，而原来存在的节点是会到最后直接被释放，这时如果节点的数量很多就会造成效率较低，因此我们就采取直接使用原来的节点，直接将原来的节点转移到新表当中，这样相比原来的方式效率会高许多。
2. unordered_map和unordered_set
以上我们了解了哈希相关的概念之后接下来就来学习unordered_set和unordered_map的使用，实际上这两个容器底层就是基于哈希表实现的，之后也会来模拟实现这两个容器，不过在此之前先来试着了解这两个容器的使用方法，不过实际上这两个容器的使用是和之前了解过的map和set是非常相似的。在用户使用层基本上接口都是类似的，只不过在一些特性上有所不同。
2.1 unordered_set
通过以上的官方文档就可以看出unorder_set和set使用的增删查等的接口都是类似的，只不过不同的unordered_set要求传的key是要求能进行取模的，而set是要求传的key是可以进行比较大小的。
除此之外set是双向迭代器，由于其底层是红黑树，那么在进行遍历的时候是有序的，而unorder_set是单向迭代器，因为其底层是哈希表，在遍历哈希表的时候是无序的。但是我们知道哈希表在进行查找的时候效率是O(1)，而红黑树查找的效率是O(logn)，那么这就说明在进行遍历或者查找的时候unorder_set的效率会高很多。
接下来就通过代码来查看差别：
int test_set2()
{
const size_t N = 1000000;
unordered_set<int> us;
set<int> s;
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();
us.reserve(N);
for (auto e : v)
{
us.insert(e);
}
size_t end2 = clock();
cout << "unordered_set insert:" << end2 - begin2 << endl;
int m1 = 0;
size_t begin3 = clock();
for (auto e : v)
{
auto ret = s.find(e);
if (ret != s.end())
{
++m1;
}
}
size_t end3 = clock();
cout << "set find:" << end3 - begin3 << "->" << m1 << endl;
int m2 = 0;
size_t begin4 = clock();
for (auto e : v)
{
auto ret = us.find(e);
if (ret != us.end())
{
++m2;
}
}
size_t end4 = clock();
cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;
cout << "插入数据个数：" << s.size() << endl;
cout << "插入数据个数：" << us.size() << endl << endl;
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 << endl;
return 0;
}以上代码当中向set和unordered_set当中都插入了同样的一系列的数据，并且接下来去还进行了查找和删除等操作，通过代码的输出结果就可以看出set和unorder_set效率的差别。
通过以上的输出结果就可以看出相比于set，unordered_set的效率要高非常多。
2.2 unordered_map
通过以上的官方文档就可以看出unordered_map和map的差异与set和unorder_set是类似的，其本质的原因还是map底层是红黑树，而unordered_map的底层是哈希表。map的模板参数当中的key要求支持比较大小，而unorder_map模板参数当中的key要求支持取模运算。
其他接口方面unordered_map和map类似在此就不再进行讲解。
3.unordered_set和unordered_map模拟实现
以上我们已经了解了unordered_set和unordered_map的使用，那么接下来就来试着模拟实现unordered_set和unordered_map。
首先要进行模拟实现我们先要来创建四个文件，分别是HashTable.h、myunordered_set.h、myunordered_map.h和test.cpp，在这几个文件当中我们将分别实现底层的哈希表、unordered_set各个接口的实现、unordered_map各个接口的实现以及在test.cpp内进行对模拟实现的unordered_set和unordered_map进行测试是否符合我们的要求。
以下我们实现的两个容器都是基于哈希桶实现的，由于我们要只编写一份代码就可以实现对应的就可以实现以上的两个容器那么就需要对原来实现的哈希桶的代码进行修改，就例如红黑树当中我们基于一套模板就可以实现set和map一样，只需要将原来的代码当中的类的模板参数进行修改即可。
其实和之前模拟实现set和map非常的类似，因为unordered_set和unordered_map分别对应的是存储Key和存储Key和Val的映射，那么这是就需要将以上实现的哈希表当中使得每个每个元素的对应的结构体的模板参数改变。
将原来HashNode修改为以下形式：
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data), _next(nullptr)
{
}
};接下来将模拟实现的unordered_set和unordered_map类的基本框架
unordered_set
#pragma once
#include"HashTable.h"
namespace zhz
{
template<class K>
class unordered_set
{
public:
//unordered_set接口实现……
private:
//哈希表对象
};
}unordered_map
#pragma once
#include"HashTable.h"
namespace zhz
{
template<class K,class V>
class unordered_map
{
public:
//unordered_map接口实现……
private:
//哈希表对象
};
}接下来将两个容器的大致模板实现之后就可以来修改HashTable当中的代码了，
template<class K, class T ,class Hash>
class HashTable
{
typedef HashNode<T> Node;
private:
inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
public:
HashTable()
{
_tables.resize(__stl_next_prime(1));
}
bool Insert(const T& data)
{
Hash hs;
bool find=Find(data);
if (find != false)
{
return false;
}
if (_n == _tables.size())
{
size_t newsize = __stl_next_prime(_tables.size() + 1);
vector<Node*> newtables(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hs(cur->_data) % newsize;
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(data)% _tables.size();
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
bool Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kt(cur->_data)== key)
{
return true;
}
cur = cur->_next;
}
return false;
}
bool Erase(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_data == key)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0;
};
以上代码当中将Insert当中直接插入原来直接插入pair对象改为T的对象，那么这时就可以根据上层传入的值来实例化出不同的Insert函数，但是目前的问题在于以上是直接使用data进行取模，但是这样就会出现在map当中使用pair进行取模的情况，这是会报错的。
就需要我们在上层实现实现出对应的仿函数来让下层支持取模运算。
struct SetkeyofT
{
const K& operator()(const K& key)
{
return key;
}
};
struct MapkeyofT
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};除此之外一般我们还需要能让用户自己能提供对应的支持取模运算的仿函数接口。那么就需要在unordered_set和unordered_map中在添加一个类模板参数。
template<class K,class Hash=HashFunc<K>>
template<class K,class V, class Hash = HashFunc<K>>接下来就再继续修改HashTable当中的类参数
template<class K, class T ,class Hash,class keyofT>有了以上的仿函数就可以在Hashtable当中将来Insert当中进行取模的地方使用两层的仿函数包围起来
实现了以上的代码之后接下来就可以来试着实现哈希表对应的迭代器以让对应的容器能提供迭代器的功能。
在此实现一个__HTIterator结构体，在结构体内部就需要有两个成员变量分别是哈希桶当中链表对应的节点的指针一个哈希表对象的指针，这里哈希表指针的作用是当对应的HashNode节点为当前链表的最后一个时，那么这时就需要定位道哈希表当中的下一个元素，因此才需要在实现迭代器的结构体当中有一个哈希表的指针。
在迭代器的实现当中其他的实现都是较为简单的，只有++的运算符重载函数需要我们仔细地思考如何实现。
注：由于哈希表是单项迭代器，那么就只需要在以上地迭代器结构体当中实现++的运算符重载函数即可。
在此就先将除了++运算符重载函数的实现之外的成员函数实现，代码如下所示：
template<class K,class T,class Ref,class Ptr,class Hash,class KeyofT>
struct __HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyofT> HT;
typedef __HTIterator<K, T, Ref, Ptr, Hash, KeyofT> Self;
Node* _node;
const HT* _ht;
//构造函数
__HTIterator(Node* node, const HT* ht)
:_node(node), _ht(ht)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
//支持比较大小
bool operator==(const Self& s)
{
return _node == s._node;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};而++的实现就需要我们先判断当前节点对应的链表的下一个节点是否为空，不是的话就可以直接返回下一个节点的指针，否则就需要遍历当前哈希表元素之后的的元素，直到下一个不为空的元素为止。
按照以上的要求实现的代码如下所示：
Self operator++()
{
//链表下一个节点不为空的时候就继续访问下一个节点
if (_node->_next)
{
_node = _node->_next;
}
//当前链表的节点的下一个节点为空时就跳转道哈希表当中的下一个元素
else
{
Hash hs;
KeyofT kt;
//得到当前的key对应的哈希下标
size_t hashi = hs(kt(_node->_data)) % _ht->_tables.size();
//将下标加1
++hashi;
//遍历得到下一个下标内有元素的哈希表下标
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
//返回对应的节点
_node = _ht->_tables[hashi];
break;
}
else
{
++hashi;
}
}
//到达哈希表的最后，返回nullptr
if (hashi == _ht->_tables.size())
{
_node= nullptr;
}
}
return *this;
}但是这时就存在一个问题了，那就是以上我们实现的++函数当中有访问HashTable对象内的私有成员，这是不允许的，那么接下来有什么解决的方法呢？
其实很简单，只需要将__HTIterator设置为HashTable的友元即可。
template<class K, class T ,class Hash,class keyofT>
class HashTable
{
template<class K, class T, class Ref, class Ptr, class Hash, class KeyofT>
friend struct __HTIterator;
//……
}那么以上将__HTIterator实现之后，HashTable.h内实现的完整的代码如下所示：
#pragma once
#include<vector>
template<class K>
class HashFunc
{
public:
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
class HashFunc<string>
{
public:
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto& x : key)
{
hash += x;
hash *= 131;
}
return hash;
}
};
namespace hash_bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data), _next(nullptr)
{
}
bool operator==(const HashNode& hs)
{
return _data == hs._data;
}
bool operator!=(const HashNode& hs)
{
return _data != hs._data;
}
};
template<class K, class T, class Hash, class keyofT>
class HashTable;
template<class K,class T,class Ref,class Ptr,class Hash,class KeyofT>
struct __HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyofT> HT;
typedef __HTIterator<K, T, Ref, Ptr, Hash, KeyofT> Self;
Node* _node;
const HT* _ht;
__HTIterator(Node* node, const HT* ht)
:_node(node), _ht(ht)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self operator++()
{
//链表下一个节点不为空的时候就继续访问下一个节点
if (_node->_next)
{
_node = _node->_next;
}
//当前链表的节点的下一个节点为空时就跳转道哈希表当中的下一个元素
else
{
Hash hs;
KeyofT kt;
//得到当前的key对应的哈希下标
size_t hashi = hs(kt(_node->_data)) % _ht->_tables.size();
//将下标加1
++hashi;
//遍历得到下一个下标内有元素的哈希表下标
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
//返回对应的节点
_node = _ht->_tables[hashi];
break;
}
else
{
++hashi;
}
}
//到达哈希表的最后，返回nullptr
if (hashi == _ht->_tables.size())
{
_node= nullptr;
}
}
return *this;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<class K, class T ,class Hash,class keyofT>
class HashTable
{
template<class K, class T, class Ref, class Ptr, class Hash, class KeyofT>
friend struct __HTIterator;
typedef HashNode<T> Node;
public:
typedef __HTIterator<K, T, T&, T* ,Hash, keyofT> Iterator;
typedef __HTIterator<K, T, const T&, const T* ,Hash, keyofT> Const_Iterator;
Iterator Begin()
{
for (int i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return Iterator(cur,this);
}
}
return Iterator(nullptr, this);
}
Iterator End()
{
return Iterator(nullptr, this);
}
Const_Iterator Begin()const
{
for (int i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return Const_Iterator(cur, this);
}
}
return Const_Iterator(nullptr, this);
}
Const_Iterator End()const
{
return Const_Iterator(nullptr, this);
}
private:
inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
public:
HashTable()
{
_tables.resize(__stl_next_prime(1));
}
pair<Iterator,bool> Insert(const T& data)
{
keyofT kt;
Hash hs;
Iterator find=Find(kt(data));
if (find != End())
{
return { find,false };
}
if (_n == _tables.size())
{
size_t newsize = __stl_next_prime(_tables.size() + 1);
vector<Node*> newtables(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hs(kt(cur->_data)) % newsize;
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(kt(data))% _tables.size();
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return { {newnode,this},true };
}
Iterator Find(const K& key)
{
keyofT kt;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kt(cur->_data)== key)
{
return Iterator(cur,this);
}
cur = cur->_next;
}
return Iterator(nullptr,this);
}
bool Erase(const K& key)
{
keyofT kt;
Hash hs;
size_t hashi = hs(kt(key)) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_data == key)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0;
};
}
接下来就来实现myunordered_set和unordered_map的代码。在此实现的过程和之前实现set和map类似，都是将底层进行封装即可。因此在此就不再进行讲解，直接展示实现的代码。
unordered_set
namespace zhz
{
template<class K,class Hash=HashFunc<K>>
class unordered_set
{
struct SetkeyofT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename hash_bucket::HashTable<K, K, Hash, SetkeyofT>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, K, Hash, SetkeyofT>::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 K& key)
{
return _ht.Insert(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, K, Hash,SetkeyofT> _ht;
};
}unordered_map
#pragma once
#include"HashTable.h"
namespace zhz
{
template<class K,class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapkeyofT
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};
public:
typedef typename hash_bucket::HashTable<K, pair<K,V>, Hash, MapkeyofT>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<K, V>, Hash, 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);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
V& operator[](const K& key)
{
pair < iterator, bool > ret = _ht.Insert({ key,V() });
return ret.first->second;
}
private:
hash_bucket::HashTable<K, pair<K,V>, Hash, MapkeyofT> _ht;
};
}实现了以上的代码之后接下来就对以上实现的代码进行测试，unordered_set测试的代码如下所示：
void Print(const unordered_set<int>& s)
{
unordered_set<int>::const_iterator it = s.begin();
while (it != s.end())
{
// *it += 1;
cout << *it << " ";
++it;
}
cout << endl;
}
void test_set1()
{
unordered_set<int> s;
s.insert(1);
s.insert(12);
s.insert(54);
s.insert(107);
Print(s);
}在test.cpp内进行测试
#include<iostream>
using namespace std;
#include"myunordered_set.h"
int main()
{
zhz::unordered_set<int> st;
zhz::test_set1();
return 0;
}
输出效果如下所示：
unordered_map测试的代码如下所示：
void Print(const unordered_map<string, string>& dict)
{
unordered_map<string, string>::const_iterator it = dict.begin();
while (it != dict.end())
{
//it->first += 'x';
//it->second += 'x';
cout << it->first << " " << it->second;
++it;
cout << endl;
}
cout << endl;
}
void test_map1()
{
string arr[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
unordered_map<string, int> countMap;
for (const auto& str : arr)
{
countMap[str]++;
}
for (const auto& e : countMap)
{
cout << e.first << ":" << e.second << endl;
}
cout << endl;
unordered_map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });
dict["left"] = "左边，剩余";
dict["insert"] = "插入";
dict["string"];
Print(dict);
}在test.cpp内测试，代码如下所示：
#include<iostream>
using namespace std;
#include"myunordered_map.h"
int main()
{
zhz::unordered_map<string, int> mp;
zhz::test_map1();
return 0;
}
输出结果如下所示：
以上测试就说明我们实现的代码是没问题的，以上就是本篇的所有内容了