从零带你底层实现unordered_map （1）
💯 博客内容：从零带你实现unordered_map
😀 作 者：陈大大陈
🚀 个人简介：一个正在努力学技术的准C++后端工程师，专注基础和实战分享 ，欢迎私信！
💖 欢迎大家：这里是CSDN，我总结知识和写笔记的地方，喜欢的话请三连，有问题请私信 😘 😘 😘
目录
超级容易踩坑的地方
unordered_map怎么实现
哈希冲突
开放寻址法
代码
unordered_map也就是哈希表，今天就来讲解它的用法。
unordered的意思是“无序”,这里强调了和map功能上的不同，因为map里面的东西是排好序的。
超级容易踩坑的地方
它是一个单向的迭代器。
为什么专门提到这个呢？因为这是我踩过坑的地方！！
单向迭代器压根就不能使用sort函数来排序！
std::unordered_map的迭代器类型是ForwardIterator，而不是sort函数要求的RandomAccessIterator，这里不符合。
我们要排序的话，还是将unordered_map里存的值，转存到vector<pair>里面。
然后我们再自定义一个排序方法，对vector<pair>进行排序。
可参考下面的代码:
class Solution {
public:
struct comp
{
bool operator()(const pair<string,int>&p1,const pair<string,int>&p2)
{
return p1.second>p2.second||(p1.second==p2.second&&p1.first<p2.first);
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string,int> hash;
for(auto &str:words) hash[str]++;
vector<pair<string,int>> sortV(hash.begin(),hash.end());
sort(sortV.begin(),sortV.end(),comp());
vector<string> v;
for(int i=0;i<k;i++)
{
v.push_back(sortV[i].first);
}
return v;
}
};692. 前K个高频单词 - 力扣（LeetCode）
也可以使用std::set结构对键进行排序，如下所示：
std::unordered_map<int, int> unordered;
std::set<int> keys;
for (auto& it : unordered) keys.insert(it.first);
for (auto& it : keys) {
std::cout << unordered[it] << ' ';
}unordered_map怎么实现
哈希冲突
hash也叫散列。
举一个例子，学校图书馆提供借书义务，怎么快速找到某个同学借的书？
我们可以引入一个关键值（日期），借书记录存的位置。
哈希和散列就是这样。
关键值和存储位置，建立一个关联关系。
如果值的跳跃很大，那空间就会很浪费。
有一个方法可以减少空间浪费，就是让数值统一对一个数取模。
但是这样就又会衍生出一个问题，就是哈希碰撞，也叫做哈希冲突。
例如，3对10取模是3,33对10取模也是3
这样一来，本来不同位置的两个值，现在映射到了相同的位置。
对于闭散列，我们有一个方法来解决这种情况。
开放寻址法
当前空间已经被占用，在开放空间里按照某种规则，再寻找一个未被占用的位置存储。
开放寻址法有两种方法。
1.线性探测 hashi+i (i>=0)
2.二次探测 hashi+i^2 (i>=0)
不需要担心后面找不到位置，因为有负载因子在控制。
负载因子是当前值的个数和空间的比率，它会保持在一个值一下。
到一定程度，就会引发扩容。
负载因子太大，冲突可能会增加,效率降低。
负载因子太小，冲突会变少，但是空间消耗会增大，空间利用率降低。
要底层实现哈希表，有一个很尴尬的问题。
我们不知道如何判断一个位置有没有存值。
因为find是碰到空就停止，假设我们删除了20，那20的位置变为空。
我们再想寻找21,22，就找不到了，因为find在20的位置就停止了。
所以，我们需要区分开两种情况，一个位置是被删除了而导致空，还是本来就是空。
假设是本来就是空，那我们到这个位置就可以停止查找，假设是被删除才导致的空，我们就继续查找下去。
知道查找到这个值，或者查找到空为止。
不能直接扩容，因为映射关系会改变。
要扩容的话，要直接新开一段空间，重新映射，再释放旧空间。
代价很大，但是没有别的方式。
最难想到的就是扩容，咱们就新开一段空间，复用一下插入函数。
最后用swap交换一下新旧空间的内容。
这样写的好处是，函数调用完成后会自动释放空间。
下面是第一版的代码，之后的补全版本代码会在接下来几个博客中发出来。
代码
#pragma once
#include<vector>
namespace bit
{
enum Status
{
EMPTY,
EXIST,
DELETE
};
template<class T, class V>
struct HashData
{
pair<K, V> _kv;
Status _s;//状态
};
template<class T,class V>
class HashTable
{
public:
HashTable()
{
_tables.resize(10);
}
bool insert(const pair<K, V>& kv)
{
if (_n*10 / _tables.size() == 0.7) //因为整形相除不可能是0.7,所以乘10,也可以转换成double
{
size_t NewSize = _tables.size() * 2;
HashTable<K, V> newHT;
newHT._tables.resize(NewSize);
for (int i = 0; i < _tables.size(); i++)
{
if (_tables[i]._s == EXIST)
{
newHT.insert(_tables[i].kv);
}
}
_tables.swap(newHT._tables);
}
size_t hashi = kv.first % _tables.size();
while (_tables[hashi]._s == EXIST)
{
++hashi;//当等于存在时，往后查找
hashi %= _tables.size();//防止越界访问
}
_tables[hashi]._kv = kv;
_tables[hashi]._s = EXIST;
++_n;
return true;
}
private:
vector<HashData> _tables;
size_t _n = 0;//存储的关键字的个数
};
}