目录
在哈希提出之前，stl的设计者认为有红黑树就足够了，但是的确在有些场景下，哈希的性能要优于红黑树，红黑树和哈希的功能相似度大约是90%，主要区别有几点：
1.有序 无序：哈希实现的map和set在C++的STL中叫做unordered map和unordered set，从名字上就能看出unordered map和unordered set是无序的，而红黑树实现的map和set是有序的。
2.性能，map和set的时间复杂度是O（logN），unordered map和unordered set的时间复杂度是O（1）。
3.底层角度区分适合场景
unordered系列关联式容器
unordered_set
unordered_set和set的功能类似，接口也很类似
1.unordered_set的构造
| 函数声明 | 功能介绍 |
| unordered_set | 构造不同格式的unordered_set对象 |
2.unordered_set的容量
| 函数声明 | 功能介绍 |
| bool empty() const | 检测unordered_set是否为空 |
| size_t size() const | 获取unordered_set的有效元素个数 |
3.unordered_set的迭代器
| 函数声明 | 功能介绍 |
| begin | 返回unordered_set第一个元素的迭代器 |
| end | 返回unordered_set最后一个元素的迭代器 |
和set不同的是，unordered_set的迭代器是单向的。
4.unordered_set的查询
| 函数声明 | 功能介绍 |
| iterator find(const K& key) | 返回key在哈希桶位置的迭代器 |
| size_t count(const K& key) | 返回哈希桶中关键码为key的元素的个数 |
5.unordered_set的修改操作
| 函数声明 | 功能介绍 |
| insert | 向容器中插入元素 |
| erase | 删除容器元素 |
| clear | 清空容器元素 |
6.unordered_set的桶操作
| 函数声明 | 功能介绍 |
| size_t bucket_count()const | 返回哈希桶中通的个数 |
| size_t bucket_size(size_t n)const | 返回第n个哈希桶元素的个数 |
| size_t bucket(const K& key) | 返回元素key所在的桶号 |
unordered_map
底层结构
什么是哈希
哈希是一种映射，是值和值进行1对1或者1对多的映射，哈希表是哈希思想实现的数据结构，是值和存储位置建立映射关系。 但是，值和存储位置建立映射关系也会存在问题：
1.值很分散（如1,5,1000,52,18），这样就需要很多的存储位置，很多存储位置没有被使用，会被浪费
2.有些值不好映射，如string、结构体对象
为了解决第一个问题，提出了除留余数法，i=key%空间的大小，这样就做到空间和值的范围无关，
但是这样就会引入另外一个问题--哈希冲突，
哈希冲突
也叫哈希碰撞，不同的值可能会映射到相同位置（如上面的10001和1），
为了解决互哈希冲突的问题，提出了两种解决方法：
1.闭散列：开放定址法
当一个元素插入时，当它本应该插入的位置被占用时，按照某种方法往后找空位置去插入它。
某种方法：
1.线性探测：从当前位置挨着往后找一个空的位置插入，
2.二次探测：跳跃着往后找空位置
思路：我的位置被占了，我就去后面抢别人的位置用。这样导致的问题是元素间相互影响，查找的效率低下，查找时，找到空的位置才能确认没有这个元素。这种方式不是我们重点的解决方式。
虽然这种方法的效率不高，但是早期有些地方可能也会用，所以我们还是来实现一下：
首先第一个问题，当我们查找某个元素是否存在时，找到空位置就说明这个元素不存在。那么，怎样算空位置呢？
第二个问题，删除55后，再查31,会发生31存在，但是找不到的情况（尴尬￣□￣｜｜）
为了解决这样的问题，我们可以给每个节点加一个状态标记，
当把某个节点删除了，不是把它标为EMPTY，而是标为DELETE，这样问题就解决了。
接下来就要完成哈希表的插入，当插入某个节点时，需要除留取余得到这个结点应该放的位置，如果这个位置状态是EXIST，就需要依次找下一个位置，直到找到状态为EMPTY或DELETE的节点。但是，在找下一个状态为EMPTY或DELETE的节点时，有可能当前所有节点的状态都是EXIST，这时的哈希表已满，需要扩容。
这里先引入负载因子的概念，就是当前数据个数/总数据个数，取值范围为0-1。
虽然哈希表看起来效率不错，但是如果负载因子越高，冲突率越高，效率就越低；负载因子越小，冲突率越低，效率就越高，但是空间利用率越低。比如，哈希表的size是10，但是已经有8个数据了，这时候插入数据极有可能会造成哈希冲突。
所以，并不是哈希表满了再进行扩容，一般当负载因子超过0.7就会扩容。扩容完成后，我们不能直接memcpy原来表里的内容到新的表里，这样会发生错乱（比如之前的表大小是10,12要放到下标为2的位置处，当表大小扩容到20后，12就需要放在下标为12的位置）。因此，扩容后，原有的值不能直接拷贝，需要重新映射。实际上，扩容这一步效率很低，因此哈希表的插入效率会呈现出这样的形式，但是整体平均的效率依然很高：
看一个扩容的示意图：
可以看出，扩容后数据变得更分散，冲突率就会变低。
哈希表插入的代码如下：
bool Insert(const pair<K, V>& kv)
{
//防止重复插入
if (Find(kv.first))
return false;
//负载因子>=0.7,就扩容;不需要担心刚开始size是0，我们在自己写的默认构造里初始化大小为10了
if (_n * 10 / _tables.size() >= 7)
{
//现代写法，本质上是一种复用
size_t newsize = 2 * _tables.size();
//创建一个新的Hash表
HashTable<K, V> newHT;
newHT._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}
size_t hashi = kv.first % _tables.size();
//线性探测
while (_tables[hashi]._state == EXIST)
{
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}接着，我们来写一下哈希表查找的代码，查找的思路就是从除留余数的位置开始找，直到找到状态为EMPTY的节点：
HashData<K, V>* Find(const K& key)
{
size_t hashi = key % _tables.size();
while ( _tables[hashi]._state != EMPTY)
{
//_tables[hashi]._state != EMPTY这个条件很有必要，如果没有，当删除某个值，再查找这个值，仍然能找到
if (_tables[hashi]._state == EXIST
&&_tables[hashi]._kv.first == key)
return &_tables[hashi];
hashi++;
}
return nullptr;
}需要注意的是，while循环里面if语句的判断条件_tables[hashi]._state == EXIST是必要的，如果没有，当删除某个值后，再查找这个值，仍然能找到，这就不对了！
接着我们再来写一下删除的代码，删除的思路就是把所删除节点的状态改为DELETE：
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret != nullptr)
{
ret->_state = DELETE;
--_n;
return true;
}
else
return false;
}以上解决了值很分散的问题，但是，还存在另一个问题，那就是值的类型如果为string、结构体怎么办？
我们可以再建立一层哈希：
我们知道，哈希就是值 --> 存储位置建立映射关系，如果值是int，那么就可以直接建立映射关系；如果是string，可以把string转换成int，然后int再和存储位置建立映射。
那么如何把string转换成int，可以考虑把string[0]的ascii码当成int，为了实现这样的功能，需要在HashTable的模版参数中增加一个，从而在类中可以使用仿函数：
默认使用HashFunc这个类，它的实现：
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};将这个类作为模版参数传入后，不管元素的值是负数、浮点数，都可以转换成size_t。
如果值是string，可以构造如下类：
struct StringHashFunc
{
size_t operator()(const string& key)
{
return key[0];
}
};字符串和其首字母的ascii码值一一对应。
但是，这个字符串转换成整形的方案不太好，这时只要首字母一样，就会冲突，所以，我们可以换一种方案，遍历string，把每个字母的ascii加起来：
struct StringHashFunc
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash += e;
}
return hash;
}
};但是，这种方案也有缺陷，如abcd，acbd，aadd等的ascii值加起来是一样的。实际上，现实中有很多字符串哈希算法，其中，BKDR方法效果最好：
//BKDR
struct StringHashFunc
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash = hash * 131 + e;
}
return hash;
}
};那这种BKDR算法还存在冲突吗？
仍然存在。 假设字符串长度是10，共有256的10次方个，但是映射的整形size_t是42亿左右，仍然存在冲突。
总结一下思路：如果key不支持强转整形取模，那么就要自己提供转换成整形的仿函数。
还有一点值得注意，我们在使用unordered_map插入string时，并没有使用仿函数，它其实由于string经常作为key，所以可以给string做一个特化：
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//string 特化
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash = hash * 131 + e;
}
return hash;
}
};那如果把日期类作为key呢？ 那也需要自己写仿函数，仿函数中可以把年月日加起来。如果是Person类作为key呢？可以把名字转换成整形，再加年龄，依次类推。
2.哈希桶
哈希桶，又叫拉链法，哈希桶的方式才是我们要重点学习的方式。哈希桶的思想是，当一个元素插入时，当它本应该插入的位置被占用时，在这个位置下面插入一个节点，把这个节点挂起来，
这样尽管节点数量很多，也不会互相影响。哈希桶的效率很高，比如我们要查找64，在原来的序列里需要查8次，但是在哈希桶只需要查3次。
那么，我们先来设置一下Hash节点：
template<class K,class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K, V>* _next;
};首先来实现一下插入：先找到元素待插入的位置，然后通过头插插入这个位置的链表中。真正的问题在于扩容，首先最容易想到的思路是：在扩容时，创建一个新的哈希表，表的大小是原来大小的2倍，遍历原表的每一个桶的每一个节点，然后插入到新表里，再拿这两个表的_tables交换。如下代码：
bool Insert(const pair<K, V>& kv)
{
//方法1，构建一个新的哈希表，遍历原表每一个节点，插入到新表上
//扩容
//负载因子为1时扩容，这时大概一个节点下面挂一个
if (_n == _tables.size())
{
size_t newsize = _tables.size() * 2;
HashTable<K, V> newHT;
newHT._tables.resize(newsize);
//旧表内容重新计算放到新表上
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
newHT.Insert(cur->_kv);
cur = cur->_next;
}
}
_tables.swap(newHT._tables);
}
size_t hashi = kv.first % _tables.size();
Node* newnode = new Node(kv);
//头插，时间复杂度是O(1)
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}上面的newHT出了作用域应该被销毁，需要调用析构函数，_tables是vector，会自动销毁，但是其上面挂的节点是自定义类型，需要自己写析构函数：
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}但是这种扩容写法是有改进空间的，如果原表上挂了10000个节点，那么在插入时，需要创建10000个节点，这样效率很低，所以，可以考虑将原表的节点算出来应该挂到新表的哪个位置，然后直接挂到新表上：
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
//方法2，创建一个新表，遍历原表的每一个节点，将原表的节点算出来应该挂到新表的哪个位置，然后直接挂到新表上
//扩容
if (_n == _tables.size())
{
vector<Node*> newTables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
//头插
size_t hashi = cur->_kv.first % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t hashi = kv.first % _tables.size();
Node* newnode = new Node(kv);
//头插，时间复杂度是O(1)
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}再来看一下查找，比较简单：
Node* Find(const K& key)
{
size_t hashi = key % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}剩下的还有Erase，删除节点要分删除某个桶的头节点和中间节点两种情况：
bool Erase(const K& key)
{
size_t hashi = key % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (cur->_kv.first == key)
{
//删除的是头节点
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
//删除的是中间节点
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}同样的，为了解决值的类型是string、结构体等类型，我们也需要在HashTable的模版参数中增加一个，从而在类中可以使用仿函数，这和上面的开放定址法很类似，就不再重复写了。
和红黑树封装map和set类似，可以将哈希桶的值类型作为模版参数：
但是，Class Hash这个参数应该在unordered_map和unordered_set这层，因为我们在实际用的时候，只能调用到unordered_map和unordered_set：
哈希桶的迭代器
实现迭代器最难的地方还是在于++的实现，
当it遍历完当前桶后，现在我们只是知道一个Node*，如何找到下一个桶呢？为此，我们还需要知道这个哈希桶的表才行，所以，在__HTIterator中，还要加上HashTable*这个模版参数：
加上HashTable*后，当++需要跳到下一个桶时，就从当前桶出发，找到下一个桶：
Self& operator++()
{
if (_node->_next)
{
//当前桶没走完，取当前桶的下一个节点
//_node和_node->_next在同一个桶中
_node = _node->_next;
}
else
{
//当前桶走完了，取下一个不为空的桶的第一个节点
KeyOfT kot;
Hash hs;
//先找出当前节点在哪个桶中
size_t i = hs(kot(_node->_data)) % (_pht->_tables.size());
//++指向下一个位置
++i;
//从下一个位置开始找，找到下一个桶
for (; i < _pht->_tables.size(); i++)
{
if (_pht->_tables[i])
{
_node = _pht->_tables[i];
break;
}
}
if (i == _pht->_tables.size())
{
//所有桶都走完了，最后一个的下一个用nullptr标记
_node = nullptr;
}
}
return *this;
}这段程序就是迭代器的精华所在！
继续封装operator!=、operator*、operator->，
bool operator!=(const Self& self)
{
return _node != self._node;
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}我们运行后，可能会报错误，原因在于struct __HTIterator和class HashTable在实现时要互相依赖，在这里，我们有两种方法可以考虑：第一种是使用内部类解决这个问题，即将struct __HTIterator放在class HashTable中实现；第二种是在struct __HTIterator的前面加上class HashTable的前置声明，并将struct __HTIterator声明为class HashTable的友元。
HashTable的封装
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//string 特化
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto e : key)
{
hash = hash * 131 + e;
}
return hash;
}
};
namespace hash_bucket
{
template<class T>
struct HashNode
{
HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
T _data;
HashNode<T>* _next;
};
template<class K,class T,class KeyOfT,class Hash>
class HashTable
{
typedef HashNode<T> Node;
public:
template<class K, class T,class Ptr,class Ref ,class KeyOfT, class Hash>
struct __HTIterator
{
typedef HashNode<T> Node;
typedef __HTIterator<K, T,Ptr,Ref ,KeyOfT, Hash> Self;
__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
:_node(node)
, _pht(pht)
{}
Self& operator++()
{
if (_node->_next)
{
//当前桶没走完，取当前桶的下一个节点
//_node和_node->_next在同一个桶中
_node = _node->_next;
}
else
{
//当前桶走完了，取下一个不为空的桶的第一个节点
KeyOfT kot;
Hash hs;
//先找出当前节点在哪个桶中
size_t i = hs(kot(_node->_data)) % (_pht->_tables.size());
//++指向下一个位置
++i;
//从下一个位置开始找，找到下一个桶
for (; i < _pht->_tables.size(); i++)
{
if (_pht->_tables[i])
{
_node = _pht->_tables[i];
break;
}
}
if (i == _pht->_tables.size())
{
//所有桶都走完了，最后一个的下一个用nullptr标记
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& self)
{
return _node != self._node;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Node* _node;
const HashTable<K, T, KeyOfT, Hash>* _pht;
};
typedef __HTIterator<K, T, T*, T&, KeyOfT, Hash> iterator;
typedef __HTIterator<K, T,const T*,const T&, KeyOfT, Hash> const_iterator;
//friend struct __HTIterator<K, T, KeyOfT, Hash>;//把struct __HTIterator声明为这个的友元，就可以在struct __HTIterator中访问_tables
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
return iterator(_tables[i], this);//this就是哈希表的指针
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin()const
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
return iterator(_tables[i], this);//this就是哈希表的指针
}
return end();
}
const_iterator end()const
{
//this -> const HashTable*
return iterator(nullptr, this);
}
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
HashTable()
{
_tables.resize(10, nullptr);
_n = 0;
}
pair<iterator,bool> Insert(const T& data)
{
//方法1，构建一个新的哈希表，遍历原表每一个节点，插入到新表上
//扩容
//负载因子为1时扩容，这时大概一个节点下面挂一个
//if (_n == _tables.size())
//{
// size_t newsize = _tables.size() * 2;
// HashTable<K, V> newHT;
// newHT._tables.resize(newsize);
// //旧表内容重新计算放到新表上
// for (size_t i = 0; i < _tables.size(); i++)
// {
// Node* cur = _tables[i];
// while (cur)
// {
// newHT.Insert(cur->_kv);
// cur = cur->_next;
// }
// }
// _tables.swap(newHT._tables);
//}
KeyOfT kot;
iterator it = Find(kot(data));
if (it != end())
return make_pair(it,false);
//方法2，创建一个新表，遍历原表的每一个节点，将原表的节点算出来应该挂到新表的哪个位置，然后直接挂到新表上
//扩容
Hash hf;
if (_n == _tables.size())
{
vector<Node*> newTables(_tables.size() * 2, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
//头插
size_t hashi = hf(kot(cur->_data)) % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t hashi = hf(kot(data)) % _tables.size();
Node* newnode = new Node(data);
//头插，时间复杂度是O(1)
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return make_pair(iterator(newnode,this),true);
}
iterator Find(const K& key)
{
KeyOfT kot;
Hash hf;
size_t hashi = hf(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur,this);
}
cur = cur->_next;
}
return end();
}
bool Erase(const K& key)
{
KeyOfT kot;
Hash hf;
size_t hashi = hf(key) % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (kot(cur->_data) == key)
{
//删除的是头节点
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
//删除的是中间节点
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<Node*> _tables;
size_t _n;
};
}unordered_set封装
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, const K, SetKeyOfT, Hash>::iterator iterator;
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::const_iterator const_iterator;
pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
const_iterator begin()const
{
return _ht.begin();
}
const_iterator end()const
{
return _ht.end();
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K,const K, SetKeyOfT, Hash> _ht;
};需要注意的是， HashTable的第二个模版参数要用const K，这样可以保证key不被修改。
unordered_map封装
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<const K, V>, MapKeyOfT, Hash>::iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, 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();
}
pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}
V& operator[](const K& key)
{
pair<iterator,bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT,Hash> _ht;
};
}
