目录
在哈希提出之前,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;
};
}