文章目录
什么是哈希表，哈希表其实就是一种映射。
在C++中底层使用了哈希表的有unordered_map、unordered_set这两个STL的容器。unordered就是无序的意思。他们的使用类似map和set，但是有所不同的是map和set遍历后得到的序列是有序的，但unordered_map和unordered_set遍历后得到的是无序的序列。
unordered_map
unordered_map是在C++11的标准中新加入的容器，目的是为了解决map底层的红黑树在查找数据的时候需要进行比较（红黑树的额高度次）查询的效率不是很高，而哈希表中查找数据的比较次数是常数次，效率很高，至于为什么是常数次，后面会详细讲解。
unordered_map底层存储的是<key,value>键值对，可以通过key快速的索引到value，在unordered_map内部因为是数据是通过映射存入哈希桶内的，所以对unordered_map进行遍历得到的是一个无序的序列。
unordered_map通过key进行访问的速度比map快，但是遍历元素的迭代效率就要低于map了。
unordered_map也实现了operator[ ] 可以通过key直接访问到value
常用函数说明
首先是迭代器，unordered_map只支持单向迭代器，但是使用该容器一般情况下不会去遍历。
insert函数，常用的就是第一个，value_type就是模板参数Key和T组成的键值对<const Key , T>。
第二个插入的就是使用了C++11的右值引用特性。
operator[ ],返回值就是第二个模板参数T
operator[ ]底层其实还是调用了insert函数接口将键值对< const Key , T( )>插入到容器中，最后返回insert插入后返回的那个iterator中的键值对里面的第二个参数，其实就是T&。
unordered_multimap
unordered_multimap和unordered_map的使用方法都是一样的。唯一的不同就是unordered_multimap里面的key是可以重复的。因此unordered_multimap不支持operator[ ]
unordered_set
unordered的容器这里的第三个模板参数的作用就是将key这个关键字转换成一个可以取模的映射数字。
unordered_set和set的使用是一样的，但是底层的存储方式是不同的，set使用的是红黑树，unordered_set底层使用的是哈希桶，进行查找的时间复杂度是常数次，但是底层的数据是无序的。接口函数方面也是和set近乎相同的。
只有迭代器不同，unordered_set的迭代器是单向的迭代器。
unordered_multiset
unoredred_multiset和unordered_set的唯一区别就是unordered_set里面的key是不可重复的。但是unoredred_multiset里面的键值是可以重复的。
所以这里就不过多解释了。具体用法可见官方文档
总结：为什么在STL已经有了map和set之后C++11中又添加了功能类似的unordered_map和unoredered_set呢？这是因为unordered系列的底层使用的是哈希表，哈希表的增删查改的效率都是在常数次。所以综合效率会比map和set的红黑树的logn的效率要高。下面我们使用代码来进行一下性能测试。
void test_disorder()
{
srand((unsigned int)time(0));
const int N = 10000000;
int* arr = new int[N];
set<int> st;
unordered_set<int> ust;
size_t begin1 = clock();
for (int i = 0; i < N; i++)
{
arr[i] = rand();
st.insert(arr[i]);
}
size_t end1 = clock();
cout << "set无序插入 ： " << end1 - begin1 << endl;
size_t begin3 = clock();
for (int i = 0; i < N; i++)
{
st.find(arr[i]);
}
size_t end3 = clock();
cout << "set无序查找 ： " << end3 - begin3 << endl;
size_t begin2 = clock();
for (int i = 0; i < N; i++)
{
arr[i] = rand();
ust.insert(arr[i]);
}
size_t end2 = clock();
cout << "unordered_set无序插入 ： " << end2 - begin2 << endl;
size_t begin4 = clock();
for (int i = 0; i < N; i++)
{
st.find(arr[i]);
}
size_t end4 = clock();
cout << "unordered_set无序查找 ： " << end4 - begin4 << endl;
}
运行结果可以看到在无序数据量是十万的时候，unordered系列的效率要高一倍左右。
数据量为100w的时候，unordered系列的效率是要高出三倍左右的效率。
千万级无序数据下也是三倍左右的差距，这个原因其实是因为，c++这里能产生的随机数只有32767个，所以在数据量如此大的情况下，有很多的数字都是重复的，因此，效率的改变几乎就没有差异的。但是还是能够看出来，在无序数据的情况下unordered系列的效率还是要高一些的。
下面来看一下有序数据下的性能测试
void test_order()
{
set<int> st;
unordered_set<int> ust;
const int N = 100000;
size_t begin1 = clock();
for (int i = 0; i < N; i++)
{
st.insert(i);
}
size_t end1 = clock();
size_t begin2 = clock();
for (int i = 0; i < N; i++)
{
st.find(i);
}
size_t end2 = clock();
cout << "set有序插入 ： " << end1 - begin1 << endl;
cout << "set有序查找 ： " << end2 - begin2 << endl;
size_t begin3 = clock();
for (int i = 0; i < N; i++)
{
ust.insert(i);
}
size_t end3 = clock();
size_t begin4 = clock();
for (int i = 0; i < N; i++)
{
ust.find(i);
}
size_t end4 = clock();
cout << "unordered_set有序插入 ： " << end3 - begin3 << endl;
cout << "unordered_set有序查找 ： " << end4 - begin4 << endl;
}
在十万量级的有序数据下，这两个表的效率是没有很大差距的。
在百万量级的有序数据下，unordered系列的效率是要慢上一倍左右的。
在千万量级的有序数据下，unordered系列的数据就要慢上三倍左右了。
面对有序数据下的随机查找，两个表的效率是差不多的。
所以根据上面的性能测试中我们可以看到，在无序数据面前红黑树的插入和查找效率是不如哈希表的。这是因为在插入无序数据的情况下，红黑树为了保持性质需要进行大量的旋转调整。这时哈希表的效率是要更高的。
但是在有序的数据测试下，我们可以发现这时候红黑树的效率反而要高出哈希表，这是因为在插入有序数据的时候，红黑树不需要进行大量的旋转，减少了旋转所消耗的时间之后，红黑树的效率也就高了。
总结，虽然红黑树在有序的场景下效率要高于底层是哈希表的unordered系列，但是实际应用中有序数据后者接近有序的数据毕竟是比较少的场景，大部分的情况都是unordered系列的效率更优，这也是C++11增加了这两个容器的愿意。
哈希表
这里我们要谈到的哈希表就是unordered系列的底层结构。
那么什么是哈希呢？
哈希的概念
回想我们以前不管是遍历一个数组（O（N））去查找一个数据还是去搜索树（logN）里面查找一个数据，不可避免的一个步骤就是要比较大小或者是否相等。搜索的效率就取决于比较的次数。那么我们是不是可以使用一种方法，这种方法不需要进行比较就可以直接判断出这个数据在不在。由此就出现了哈希算法。
哈希算法就是不通过比较的方式就能确定一个数据是不是在表中。（当然这是最理想的哈希）
哈希算法的概述
哈希算法是如何不通过比较就能确定一个数据在不在呢？
答案是：通过将数据插入的位置与关键字建立映射关系，这种映射关系就是后面要说到的哈希函数
简单举个例子：
现在有这样一个场景，给你了一个长度为N的字符串，需要你在O（N）的时间复杂度内找出所有只出现过一次的字符。
这时候我们就可使用哈希算法中的直接定址法来解决。什么是直接定址法呢？就是我们创建一个长度为128的计数数组，然后用字符的ascii码值直接映射到数组的这个位置，对这个位置进行++。最后遍历整个数组，找到值为1的位置，这个位置的下标就是只出现过一次的字符的ASCII码值。
void test(char* str)
{
int count[128] = { 0 };
int length = strlen(str);
for (int i = 0; i < length; i++)
{
++count[str[i]];
}
for (int i = 0; i < 128; i++)
{
if (count[i] == 1)
printf("%c ", str[i]);
}
}
根据上面的代码，同样的思路我们也可以写出，在一个字符串中查找给定的字符有没有出现的代码。同样是用一个计数数组来记录字符串中所有出现的字符，然后用给出来的字符通过ASCII码值直接映射到那个位置，如果不为0，则代表该字符在字符串内出现过。
这里引出了两个概念，插入元素和搜索元素，根据上面的例子，我们插入计数数组的字符串就是插入元素，给定的字符就是搜索元素。
这种通过映射来解决问题的方法就叫做哈希（散列）方法。构造出来的结构，类比上面的数组，就叫哈希表或者散列标。
哈希冲突
哈希冲突就是指两个不同的元素映射到了同一个位置上，那么什么样子的情况会发生哈希冲突呢？
哈希函数
其实哈希的映射方法有很多种，这些方法被叫做哈希函数。
1.直接定址法
我们上面使用的哈希函数就叫做直接定址法。
直接定址法是不会发生哈希冲突的，因为每个元素都是根据其自己唯一的标识来定位的。
这种方法的优点就是简单，且没有哈希冲突。
缺点是：这种方法只适合提前知道数据的分布范围，并且最好是较小的分布集中的数据，不然会造成大量的空间浪费。
2.除留余数法
除留余数法就是将插入元素模上一个固定的值（通常是数组的大小）来映射到相应的位置。这时候就会有不同的数他们的余数相同于是就会映射到相同的位置，发生了哈希冲突。那么如何解决哈希冲突呢？马上就会讲到。
3.平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为
4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知
道关键字的分布，而位数又不是很大的情况。
4.折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加
求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
5.随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为
随机数函数。通常应用于关键字长度不等时采用此法。
6.数学分析法
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能
在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出
现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我
们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字
进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改
成12+34=46)等方法。
**数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布 **
较均匀的情况。
这里需要注意的是，哈希函数设计的越科学，那么产生哈希冲突的概率越小，这个哈希函数就越好。但是哈希冲突是无法避免的（除了直接定址法）
这里的哈希函数只需要知道前两个是比较常用的，剩下的稍作了解即可。
如何解决哈希冲突
哈希冲突出现了我们应该如何解决呢？
这里存在两种方法，闭散列和开散列。
闭散列
1.线性探测
当我们使用除留余数法进行哈希映射的时候一定会出现不同的数值映射到了同一个位置上的情况。比如下面：
如果这时候我们插入44这个值，就和4这个位置的值发生了冲突，线性探测的方法就是，如果遇到了冲突，那么就向后继续查找，直到找到一个空位置，然后将自己的值插入到这个空位置中。这里我们可以看到向后遍历找到的空位置就是8下标位置处。
注意：如果走到了数组末尾要绕回去从数组的头开始继续找，只需要将坐标模上数组长度即可。
闭散列删除元素
在闭散列中删除元素是不能随便删除的，这里需要用三种状态标记每个位置，这里我们可以使用枚举类型。
enum States
{
EXIST,
EMPTY,
DELETE
};
为什么要用三种状态标记，两种不行吗，只用exist和emty就够了呀。
第三种状态可以说是为了查找而实现的，因为我们在查找的时候遇到empty就会停下，如果把删除掉的元素也标记为empty那么就会出现被删除元素后面的元素查找不到的情况了。
下面我们来看看哈希表的线性探测的代码实现
template<class K,class V>
struct HashData
{
pair<K, V> _kv;
State _st;
HashData(const pair<K,V>& kv = pair<K,V>())
:_kv(kv)
,_st(EMPTY)
{}
};
这一部分就是哈希表内每个元素的构成，每个元素都有一个数据变量和一个状态变量。
template<class K,class V,class HashFunc = Hash<K>>
class HashTable
{
typedef HashData<K, V> Data;
public:
HashTable()
{}
private:
vector<Data> _tables;
size_t _n = 0;
};
这一部分就是哈希表的整体结构只是缺少了内部函数。哈希表的成员这里我们使用了一个vector来存储HashData。用一个_n来标记这个数组内的有效元素个数，因为我们的数据在数组内的存储并不是连续可控的，所以我们也不知道到底里面存放了多少元素。因此需要一个变量来计数。
Data* Find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
HashFunc hf;
size_t start = hf(key) % _tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._st != EMPTY)
{
if (_tables[index]._kv.first == key && _tables[index]._st == EXIST)
return &(_tables[index]);
i++;
index = start + i;
index %= _tables.size();
}
return nullptr;
}
这里的查找我们使用的就是线性探测，其实就是映射的位置冲突了之后就向后找，只要找到了就返回，最后走到了nullptr也没有找到就返回nullptr。
这里的HashFunc就是一个哈希函数，可以将任何类型的关键字转换成可以取模的关键值，等下会详细讲到。
template <class K>
struct Hash
{
size_t operator()(const K& k)
{
return k;
}
};
template<>
struct Hash<string>
{
size_t operator()(const string& s)
{
size_t count = 0;
for (auto e : s)
{
count *= 31;
count += e;
}
return count;
}
};
这个类就是HashFunc，这里使用了模板可以对多种类型使用，对于能转成无符号类型的数值就直接转成无符号类型就可以了。
对于字符串这种无法直接转成数值的类型我们可以使用相应的字符串函数，字符串函数有很多种。这里我贴一个链接，是对多种字符串哈希函数的总结。这里我们使用的是BKDR算法来将字符串转换成哈希值。
bool Erase(const K& key)
{
Data* ret = Find(key);
if (ret == nullptr)
return false;
ret->_st = DELETE;
--_n;
return true;
}
这里就是哈希表的删除，直接将删除的那个元素的状体置为DELETE即可，最后不要忘记将有效个数减一。
bool Insert(const pair<K, V>& kv)
{
Data* ret = Find(kv.first);
if (ret)
return false;
if (_tables.size() == 0 || (_n * 10 / _tables.size() > 7))
{
//扩容
size_t newcapacity = _tables.size() == 0 ? 10 : 2 * _tables.size();
HashTable<K,V> newtable;
newtable._tables.resize(newcapacity);
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._st == EXIST)
newtable.Insert(_tables[i]._kv);
}
_tables.swap(newtable._tables);
}
//插入节点
HashFunc hf;
size_t start = hf(kv.first)%_tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._st == EXIST)
{
i++;
index = start + i;
index %= _tables.size();
}
_tables[index]._kv = kv;
_tables[index]._st = EXIST;
++_n;
return true;
}
在讲到插入之前必须了解到哈希表如何扩容，最重要的是什么时候扩容呢？
这里就涉及到了一个名词，载荷因子又叫负载因子，这个值其实就是哈希表内有效元素的个数，和哈希表长度的比值
载荷因子越大那么发生冲突的概率就越大，但是空间利用率就越高
载荷因子越小那么发生冲突的概率就越小，但是空间利用率就越低
所以扩容的条件就是当载荷因子达到了0.7的时候我们就进行扩容，这里因为载荷因子是小数，为了防止小数的产生我们可以将有效数字个数_n*10然后再除哈希表的大小，最后当这个载荷因子大于7的时候就进行扩容即可
如何进行扩容呢？
其实很简单，只需要复用即可，先创建 一个更大的哈希表，然后遍历原来的哈希表将原来的哈希数据重新复用插入函数插入即可。不可以将原来的节点直接复制到新表，因为哈希表的容量变了那么映射的位置就会发生变化。
线性探测的优点就是简单，缺点也很明显那就是遇到连续的冲突之后，会产生堆积效应，也就是插入一个元素要进行很多次查找才能最终插入，搜索的时候也会遇到同样的问题，因此造成了效率的低下。 由此就产生了二次探测。
2.二次探测
二次探测其实没有什么神秘的。就是将线性探测每次都是start+i改成每次都是start+i*i。这样子随着i的增大元素和元素之间的距离也就会增大，这样就将元素分散开来减少了冲突堆积在一起的现象。
这里要注意的是，如果插入的时候使用的是二次探测，那么在查找的时候也要使用二次探测，如果使用线性探测可能遇到元素中间的空位置就停下了。只有也使用二次探测才能连续在有效位置查找直到走到EMPTY的位置。
下面来看一下二次探测的插入代码
bool Insert(const pair<K, V>& kv)
{
Data* ret = Find(kv.first);
if (ret)
return false;
if (_tables.size() == 0 || (_n * 10 / _tables.size() > 7))
{
//扩容
size_t newcapacity = _tables.size() == 0 ? 10 : 2 * _tables.size();
HashTable<K,V> newtable;
newtable._tables.resize(newcapacity);
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._st == EXIST)
newtable.Insert(_tables[i]._kv);
}
_tables.swap(newtable._tables);
}
//插入节点
HashFunc hf;
size_t start = hf(kv.first)%_tables.size();
size_t i = 0;
size_t index = start + i;
while (_tables[index]._st == EXIST)
{
i++;
index = start + i*i;
index %= _tables.size();
}
_tables[index]._kv = kv;
_tables[index]._st = EXIST;
++_n;
return true;
}
研究表明：**当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置 **
**都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装 **
**满的情况，但在插入时必须确保表的装载因子a不超过0.5，**如果超出必须考虑增容.
因此只要保证载荷因子一直处于一个较小值，此时闭散列的插入查找效率都是很高的。但是相应的就会存在大量的空间没有使用造成了空间的浪费。所以这也是闭散列的一个缺点。闭散列的另一个缺点就是发生冲突的数据会相互影响（争抢位置）
那么有没有一种更优的办法能解决冲突的同时又可以减少空间的浪费呢？当然就是下面的开散列啦。
开散列
开散列又叫哈希桶或拉链法。
他的结构实际就是用一个数组来存放哈希节点的指针，一旦发生冲突就将冲突的节点链接在冲突位置之后。相当于是一个数组下面挂着很多的单链表。
将没有映射到的位置置为空指针，将映射到该位置的节点链接到这个位置的后面
发生冲突的位置也是很好解决的，只需要将冲突节点头插到这个链表中即可。
开散列的结构代码
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data = T())
:_data(data)
, _next(nullptr)
{}
};
这是开散列中挂着的单链表的节点，由一个数据域和一个指针域组成。
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
typedef HashNode<T> Node;
public:
HashTable()
{}
private:
vector<Node*> _tables;
size_t _n = 0;
};
这个就是哈希表的整体架构，其中使用了四个模板参数，第一个模板参数就是key，第二个模板参数是数据域，如果要封装成set，那么T就是K，如果要封装成map那么T就是pair<K,V>.
第三个参数就是从T这个类型里面取出K的数据，如果是set直接返回key，如果是pair那么就需要返回pair的first。第四个参数就是哈希函数将key的数据类型转换成可以取模的哈希数值。
这里的哈希表里面也会保存一个有效元素的个数_n，同闭散列一样也是负责增容的，开散列如果不控制载荷因子也可能会出现极端情况
比如一个长度是100的哈希表，插入50个值，可能会出现40个值链接成一条单链表，这时候的查找效率就很低了，接近于O（N）遍历了所有的数据。
上面是一个桶很长的情况，还有所有的桶都很长的情况，那就是插入10000个数据，这时候不管分布是否均匀每个桶的长度都是很长的。
因此为了控制哈希桶的效率，在开散列这里也是需要载荷因子的，只是载荷因子的控制可以比起闭散列松一些，一般控制的是载荷因子达到了1就要进行扩容。
下面我们来看看哈希桶的成员函数：
哈希桶的查找函数
iterator Find(const K& key)
{
if (_tables.size() == 0)
return iterator(nullptr,this);
HashFunc hf;
KeyOfT kot;
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (kot(cur->_data) == key)
return iterator(cur,this);
cur = cur->_next;
}
return iterator(nullptr,this);
}
这里返回的迭代器是按照官方文档里面的查找函数进行模拟的。后面会讲到迭代器的设计，现在只需要关注返回的是不是空指针即可。
查找一个值其实就是将这个key%tables.size()找到key映射到的那个单链表，然后遍历这个单链表，如果能找到就返回，找不到就返回nullptr
哈希桶的插入函数
pair<iterator,bool> Insert(const T& data)
{
KeyOfT kot;
HashFunc hf;
iterator ret = Find(kot(data));
if (ret._node)
return make_pair(ret,false);
if (_n == _tables.size())
{
//扩容
size_t newcapacity = _tables.size() == 0 ? 11 : GetPrime(_tables.size());
vector<Node*> newtables;
newtables.resize(newcapacity);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = hf(kot(cur->_data)) % newtables.size();
cur->_next = newtables[index];
newtables[index] = cur;
cur = next;
}
}
_tables.swap(newtables);
}
//插入节点
size_t index = hf(kot(data)) % _tables.size();
Node* newnode = new Node(data);
newnode->_next = _tables[index];
_tables[index] = newnode;
++_n;
return make_pair(iterator(newnode,this),true);
}
size_t GetPrime(size_t sz)
{
static size_t PrimeNum[] =
{
11, 28, 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
};
for (auto num : PrimeNum)
{
if (num > sz)
return num;
}
return 4294967291;
}
插入之前先查找要插入的节点是否已经再哈希表内存在了，如果存在直接返回false即可。
极端情况的哈希桶
就算我们控制负载因子不超过1，但是在某些极端情况之下，还是会出现某个链表过长的情况，其实这个情况出现的概率并不大，所以我们可以选择不处理，到那时如果想要处理可以参考java里面的HashTable的处理。
处理方案就是，在每个链表里面增加一个计数器，这个计数器可以用来记录这个链表里面插入了几个节点，当我们插入的节点数大于8的时候，就对单链表进行转换，将链表节点的值插入到红黑树的节点里面，然后哈希桶的这个位置的指针指向的是红黑树的根节点。当然为了存储不同的节点这里我们同样的也是开了两个不同的哈希表，如果是单链表的长度大于8，就在该位置使用红黑树的哈希表进行插入映射。
虽然出现了空间的浪费，但是这种写法，可以保证哈希桶在任何情况下的效率都是很高的。
哈希桶的扩容
扩容的条件就是载荷因子要超过1的时候，这里的扩容要注意，不能像闭散列那样直接复用插入，主要是效率问题，因为每次调用都会进行一次查找。并且扩容会进行节点的拷贝也是性能的消耗。
所以我们这里的扩容就是直接遍历旧链表，将旧链表的节点插入到新链表，减少了节点的拷贝提高了效率。
关于节点的插入这里使用的是链表的头插，注意要++_n.
关于扩容后的表的大小问题，经过前人的努力推算出哈希表的大小最好是素数，这时候哈希表的冲突是最少的，也就是说插入和查找的效率是最高的。所以每次扩容我们都要保证大小是素数，这里我们可以通过手写一个素数表，每次扩容的时候到素数表内查找一个比当前容量还要大的数返回即可。
哈希桶的查找和删除函数
iterator Find(const K& key)
{
if (_tables.size() == 0)
return iterator(nullptr,this);
HashFunc hf;
KeyOfT kot;
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (kot(cur->_data) == key)
return iterator(cur,this);
cur = cur->_next;
}
return iterator(nullptr,this);
}
查找函数的思路很简单，从key取模之后得到的那个链表位置开始，遍历整个单链表即可。
bool Erase(const K& key)
{
if (_tables.size() == 0)
return false;
HashFunc hf;
KeyOfT kot;
size_t index = hf(key)%_tables.size();
Node* cur = _tables[index];
Node* prev = nullptr;
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
//头删
_tables[index] = cur->_next;
}
else
{
//中间删除
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
删除先就是用key取模得到单链表的开始位置，然后问题就变成了单链表的删除
1.删除头节点
保存头节点之后，令表内保存的指针为头节点的下一个节点，然后delete头节点即可
2.删除中间节点，需要维护被删除节点的头节点pre，pre的next指向cur的next，最后删除cur就可以了
哈希桶的哈希函数
对于key是string类型的函数，这里我们使用的BKDR字符串哈希算法，将字符串转换成可以进行取模的值。
template <class K>
struct Hash
{
size_t operator()(const K& k)
{
return k;
}
};
template<>
struct Hash<string>
{
size_t operator()(const string& s)
{
size_t count = 0;
for (auto e : s)
{
count *= 31;
count += e;
}
return count;
}
};
对比于闭散列，开散列的虽然每个节点需要保存地址，但是实际上根据负载因子的差距，开散列还是要比闭散列节省空间的额。
使用哈希桶模拟unordered系列容器
哈希桶的迭代器设计
首先在模拟实现unordered系列容器之前我们需要实现出一个完整的，有迭代器的哈希桶。
哈希桶最重要的就是迭代器的设计，下面我们来看一下迭代器的设计代码
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable;//哈希表的声明，因为迭代器里面引用了哈希表的指针，所以要提前声明
template<class K, class T, class Ptr,class Ref,class KeyOfT, class HashFunc = Hash<K>>
struct HashTableIterator
{
typedef HashNode<T> Node;
typedef HashTableIterator<K, T, Ptr, Ref, KeyOfT> Self;
typedef HashTable<K, T, KeyOfT> HashTable;
Node* _node;
HashTable* _htb;
HashTableIterator(Node* node,HashTable* htb)
:_node(node)
,_htb(htb)
{}
Self& operator++()
{
Node* cur = _node;
if (cur->_next == nullptr)
{
//换桶
HashFunc hf;
KeyOfT kot;
size_t index = hf(kot(cur->_data)) % (_htb->_tables.size());
index++;
while (index < _htb->_tables.size())
{
if (_htb->_tables[index])
{
cur = _htb->_tables[index];
break;
}
index++;
}
if (index == _htb->_tables.size())
cur = nullptr;
_node = cur;
}
else
{
cur = cur->_next;
_node = cur;
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
};
首先迭代器的结构成员是一个节点的指针，一个哈希表的指针，这个和常规的迭代器不同，为什么我们要在这里增加一个哈希表的指针呢？问题出现再operator++这里先记住，马上就会提到。
在讲operator++这里之前，先来看一下迭代器的模板参数。
K和T自然就是键值和节点的数据类型，Ptr和Ref自然是为了方便实现const迭代器而给出的。这里和list的迭代器类似。KeyOfT就是从T里面取出key的值。最后的Hash Func就是将key转换成无符号数的一个算法仿函数。
下面我们先来看operator++的实现
Self& operator++()
{
Node* cur = _node;
if (cur->_next == nullptr)
{
//换桶
HashFunc hf;
KeyOfT kot;
size_t index = hf(kot(cur->_data)) % (_htb->_tables.size());
index++;
while (index < _htb->_tables.size())
{
if (_htb->_tables[index])
{
cur = _htb->_tables[index];
break;
}
index++;
}
if (index == _htb->_tables.size())
cur = nullptr;
_node = cur;
}
else
{
cur = cur->_next;
_node = cur;
}
return *this;
}
首先就是要判断我们当前的迭代器处于那个节点的位置，如果当前节点的下一节点不是nullptr，那么直接将当前节点移动到下一个节点的位置，然后返回即可。
比较麻烦的是如果当前节点的下一个节点是nullptr，就需要换到下一个单链表，如何换过去呢？这时候就需要用到我们迭代器里面的哈希表的指针了。先用当前节点的data进行取模然后找到当前节点所在的位置，将这个位置++到下一个位置，进入循环找到下一个不为空的位置，这个位置就是新的单链表的头，如果走到了最后都没有找到非空位置，那么说明此时的哈希桶已经遍历完了。返回nullptr即可。
哈希桶的设计
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
friend struct HashTableIterator;
typedef HashNode<T> Node;
public:
typedef HashTableIterator<K, T, T*, T&, KeyOfT> iterator;
typedef HashTableIterator<K, T, const T*, const T&, KeyOfT> const_iterator;
HashTable()
{}
HashTable(const HashTable<K, T, KeyOfT>& ht)
{
this->_n = ht._n;
this->_tables.resize(ht._tables.size());
for (size_t i = 0; i < ht._tables.size(); i++)
{
Node* cur = ht._tables[i];
while (cur)
{
Node* newnode = new Node(cur->_data);
newnode->_next = _tables[i];
_tables[i] = newnode;
cur = cur->_next;
}
}
}
HashTable<K, T, KeyOfT>& operator=(HashTable<K, T, KeyOfT> ht)
{
_tables.swap(ht._tables);
std::swap(_n, ht._n);
return *this;
}
~HashTable()
{
Clear();
}
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
bool Erase(const K& key)
{
if (_tables.size() == 0)
return false;
HashFunc hf;
KeyOfT kot;
size_t index = hf(key)%_tables.size();
Node* cur = _tables[index];
Node* prev = nullptr;
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
//头删
_tables[index] = cur->_next;
}
else
{
//中间删除
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
iterator Find(const K& key)
{
if (_tables.size() == 0)
return iterator(nullptr,this);
HashFunc hf;
KeyOfT kot;
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (kot(cur->_data) == key)
return iterator(cur,this);
cur = cur->_next;
}
return iterator(nullptr,this);
}
size_t GetPrime(size_t sz)
{
static size_t PrimeNum[] =
{
11, 28, 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
};
for (auto num : PrimeNum)
{
if (num > sz)
return num;
}
return 4294967291;
}
pair<iterator,bool> Insert(const T& data)
{
KeyOfT kot;
HashFunc hf;
iterator ret = Find(kot(data));
if (ret._node)
return make_pair(ret,false);
if (_n == _tables.size())
{
//扩容
size_t newcapacity = _tables.size() == 0 ? 11 : GetPrime(_tables.size());
vector<Node*> newtables;
newtables.resize(newcapacity);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = hf(kot(cur->_data)) % newtables.size();
cur->_next = newtables[index];
newtables[index] = cur;
cur = next;
}
}
_tables.swap(newtables);
}
//插入节点
size_t index = hf(kot(data)) % _tables.size();
Node* newnode = new Node(data);
newnode->_next = _tables[index];
_tables[index] = newnode;
++_n;
return make_pair(iterator(newnode,this),true);
}
size_t Size()const
{
return _n;
}
bool Empty()const
{
return _n == 0;
}
void Clear()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
--_n;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
private:
vector<Node*> _tables;
size_t _n = 0;
};
这里唯一没有解释的就是拷贝构造和复制运算符重载函数了。
拷贝构造，先拷贝一个同样大小的数组用来存放节点指针，然后遍历旧表，将每个节点拷贝一遍插入到新表的相同位置，当然这里可以使用头插或者尾插，头插的话每个节点的位置比起原来的表都是逆序的，但是这不会有什么影响，尾插的话我们就需要保存一下尾指针方便插入。
复制运算重载这里使用的是现代写法，传参过来的时候调用了拷贝构造构造了新的一个哈希表ht，我们只需要将ht的vector和_n同旧表进行交换即可。
我们知道构造函数如果不写，编译器会自动生成一个，但是如果我们写了一个拷贝构造，因为拷贝构造也是一个特殊的构造函数，此时编译器就不会自动生成了。如果我们不写一个默认构造函数的话创建对象的时候就会报错。但是我们不想自己写，还是想用编译器自己生成的构造函数该怎么办呢？
HashTable() = default;
只需要加上这句代码，那么编译器就会自己生成一个默认构造函数。
unordered_set的封装设计
#include"HashTable.h"
namespace xzj
{
template<class K>
struct KeyOfSet
{
const K& operator()(const K& k)
{
return k;
}
};
template<class K,class hash = Hash<K>>
class unordered_set
{
typedef LinkHash::HashTable<K, K, KeyOfSet<K>, hash> HashTable;
public:
typedef typename LinkHash::HashTable<K, K, KeyOfSet<K>, hash>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
bool erase(const K& key)
{
return _t.Erase(key);
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
LinkHash::HashTable<K, K, KeyOfSet<K>, hash> _t;
};
}
外层设计很简单，只需要调用哈希表的对应接口即可。在set这里T就是K。
unordered_map的封装设计
#include"HashTable.h"
namespace xzj
{
template<class K, class V>
struct KeyOfMap
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
template<class K,class V,class hash = Hash<K>>
class unordered_map
{
public:
typedef typename LinkHash::HashTable<K, pair<K, V>, KeyOfMap<K, V>, hash>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
bool erase(const K& key)
{
return _t.Erase(key);
}
iterator find(const K& key)
{
return _t.Find(key);
}
V& operator[](const K& key)
{
pair<iterator,bool> ret = _t.Insert(make_pair(key,V()));
return (((ret.first)._node)->_data).second;
}
size_t size()const
{
return _t.Size();
}
bool empty()const
{
return _t.Empty();
}
private:
LinkHash::HashTable<K, pair<K, V>, KeyOfMap<K,V>, hash> _t;
};
}
map的KeyOfMap的设计因为map的T是一个pair的键值对，所以取出K就是返回pair的first。还有一个区别就是map这里要实现operator[ ]，返回值就是value的引用，方便键值对的插入和value的修改。
关于比较器的问题
我们在看官方文档的时候发现有些容器，比如map和set他们都需要传一个比较器通常是缺省参数给出。
我们知道在红黑树底层是要实现大于小于等于的比较的，那么这里只用了一个小于的比较器是如何实现出这三种比较关系的呢？
我们可以通过一段形象的代码来演示
if(a < b)//实现了比较a < b
else if(b < a) //实现了比较a > b
else//走到这里就是a == b
同过这段代码我们可以看出，只需要一个小于的比较器，我们通过交换比较数的位置即可实现大于小于等于的比较了。