文章目录
- 1. unordered系列关联式容器
- 1.1 unordered_map
- 1.2 unordered_set
- 1.3.底层结构
- 2.哈希
- 2.1哈希概念
- 2.2哈希冲突
- 2.3 哈希函数
- 2.4 哈希冲突解决
- 2.4.1闭散列
- 2.4.1开散列
- 2.5开散列与闭散列比较
- 3.哈希的模拟实现
- 1. 模板参数列表
- 2. 迭代器的实现
- 3. 增加通过key获取value操作
- 4. 哈希实现总代码:
- 4.用实现的哈希封装unordered_map与unordered_set前的模板参数的梳理及相关联系的梳理
- 5.unordered_map的封装实现
- 6.unordered_set的封装实现
🎉个人名片:
🐼作者简介:一名乐于分享在学习道路上收获的大二在校生
🙈个人主页🎉:GOTXX
🐼个人WeChat:ILXOXVJE
🐼本文由GOTXX原创,首发CSDN🎉🎉🎉
🐵系列专栏:零基础学习C语言----- 数据结构的学习之路----C++的学习之路
🐓每日一句:如果没有特别幸运,那就请特别努力!🎉🎉🎉
————————————————
文章简介:
本篇博文主要会涉及到STL关联式容器,unordered系列关联式容器,unordered_set和unordered_map的底层数据结构,哈希表的底层及迭代器实现,以及在其上对unordered_set****和unordered_map的封装。
1. unordered系列关联式容器
在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 l o g 2 N log_2 N log2N,即最差情况下需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次数就能够将元素找到,因此在C++11中,STL又提供了4个unordered系列的关联式容器,分别为:unordered_map与unordered_set和unordered_multimap与unordered_multiset 这四个容器,他们与红黑树结构的关联式容器使用方式基本类似,只是其底层结构不同。
- unordered_map和unordered_set与map与set类似,map与set是有序的,但是unordered系列都不是有序的,但是也不允许出现重复值。
- unordered_multimap和unordered_multiset与unordered_map和unordered_set类似,unordered_map和unordered_set不允许重复值出现,但是multi系列是允许重复值出现的。
- 只要是前缀带了unordered的就是无序,后缀带了multi的就是允许键值重复。
- 他们在使用方面上与set与map非常类似,这里不作详解。
1.1 unordered_map
unordered_map的文档介绍链接: link
文档说明:
- unordered_map是存储<key, value>键值对的关联式容器,其允许通过keys快速的索引到与其对应的value。
- 在unordered_map中,键值通常用于惟一地标识元素,而映射值是一个对象,其内容与此键关联。键和映射值的类型可能不同。
- 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value,unordered_map将相同哈希值的键值对放在相同的桶中。
- unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集的范围迭代方面效率较低。
- unordered_maps实现了直接访问操作符(operator[ ]),它允许使用key作为参数直接访问value。
- 它的迭代器至少是前向迭代器。
1.2 unordered_set
unordered_mset的文档介绍链接: link
1.3.底层结构
STL关联式容器中:
set和map的底层数据结构为红黑树,因为map和set要求是自动排序的,红黑树能够实现这一功能,并且各个操作的时间复杂度都较低,而unordered_set和unordered_map的底层数据结构为哈希表,查找时间复杂度为常数级。
2.哈希
2.1哈希概念
顺序结构以及平衡树中,元素 关键码 与其 存储位置 之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( l o g 2 N log_2 N log2N),搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。
如果构造一种存储结构,通过某种函数(hashFunc)使元素的 存储位置 与它的 关键码 之间能够建立一一 映射 的关系,那么在查找时通过该函数可以很快找到该元素。
当向该结构中:
插入元素
根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放。
搜索元素
对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。
该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表)。
例如有一个数组arr[ ]={ 4 , 9 , 17 , 28 , 16 , 22 , 13 , 10 };
哈希函数设置为:hash(key) = key % capacity( capacity为存储元素底层空间总的大小)。
用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快,
但是如果我们再插入一个数7,就会和存放17的位置冲突,这个就引发了哈希冲突;
2.2哈希冲突
对于两个数据元素的关键字
k
i
k_i
ki和
k
j
k_j
kj(i != j),有
k
i
k_i
ki !=
k
j
k_j
kj,但有:Hash(
k
i
k_i
ki) ==
Hash(
k
j
k_j
kj),即:不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
2.3 哈希函数
引起哈希冲突的一个原因可能是:哈希函数设计不够合理。
哈希函数设计原则:
- 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间。
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
常见哈希函数
这里只讲解常用的几种方法
- 直接定址法
取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B
优点:简单、均匀
缺点:需要事先知道关键字的分布情况
使用场景:适合查找比较小且连续的情况
面试题:字符串中第一个只出现一次字符
例如:数组arr[ ]={ 1 , 4 , 6 , 2 , 8 }; 假设线性函数我们取:Hash(key) = 2*key+1。
那么:Hash(6)=2 *1+1=13; 就把 6 存放到哈希表中对应映射位置为 13 的位置中,这样如果我们想要快速找元素6时,就可以直接利用该函数找到地址。
- 除留余数法
设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址
例如有一个数组arr[ ]={ 4 , 9 , 17 , 28 , 16 , 22 , 13 , 10 };
哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
2.4 哈希冲突解决
解决哈希冲突两种常见的方法是: 闭散列 和 开散列
2.4.1闭散列
闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置
呢?
- 线性探测
现在需要插入元素44(如下图),先通过哈希函数计算哈希地址,hashAddr为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。
线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
插入
通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素。
删除
采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影
响。因此线性探测采用标记的伪删除法来删除一个元素。(例如使用枚举,列出三种状态(存在,不存在,已删除))
// 哈希表每个空间给个标记
// EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};
线性探测优点:实现非常简单(就不实现了,重点实现后面的开散列)
线性探测缺点:一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”,即:不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要许多次比较,导致搜索效率降低。
如何缓解呢?
- 二次探测
二次探测就是与线性探测寻找下一个位置的方法不同而已。
线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题
*找下一个空位置的方法为: H i H_i Hi = ( H 0 H_0 H0 + i 2 i^2 i2 )% m, 或者: H i H_i Hi = ( H 0 H_0 H0 - i 2 i^2 i2 )% m。其中:i = 1,2,3…, H 0 H_0 H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。
研究表明:当表的长度为质数且表装载因子a(存放的数据个数/最多能存放的数据个数)不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容。
因此:闭散列 最大的 缺陷 就是 空间利用率比较低,这也是哈希的缺陷。
2.4.1开散列
- 开散列概念
开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素。
- 开散列实现
template<class K>
struct Hashfunc //整型数据不用转换
{
size_t operator()(const K& key)
{
return (size_t)key; //直接返回
}
};
template<> //特化
struct Hashfunc<string> //如果为字符串类型,需要将其转化为整形
{
size_t operator()(const string& s)
{
size_t hashi = 0;
for (auto e : s)
{
hashi += e;
hashi *= 131; //这里13 131 1313.....都可以
}
return hashi; //转换为整型返回
}
};
template<class K, class V> //储存数据的节点
struct HashNode
{
HashNode(const pair<K, V>& kv)
:_next(nullptr)
, _kv(kv)
{}
HashNode<K, V>* _next; //指向写一个节点的指针
pair<K, V> _kv; //数据
};
template<class K,class V,class HFunc = Hashfunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable(size_t size = 10)
{
_table.resize(size, nullptr);
_n = 0;
}
插入函数的实现(这里只有插入函数,扩容与检查函数文章后面会有)
bool insert(const pair<K,V>& kv)
{
//1.查重,如果已经存在,不用插入了
//2.检查是否需要扩容
//3.插入代码
Hashfunc<K> HFunc; //转换能取模的整型
size_t hashi = HFunc(kv.first) % _table.size();
if (_table[hashi]) //如果不为bullptr,则说明改位置已经有数据了,直接头插
{ //因为单链表的头插效率高
//头插
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;
}
else //如果为nullptr,则说明该位置还没有数据,直接插入
{
Node* newnode = new Node(kv);
_table[hashi] = newnode;
++_n;
return true;
}
}
删除函数的实现
bool Erase(const K& key)
{
Hashfunc<K> HFunc; //转换能取模的整型
size_t hashi = HFunc(key) % _table.size(); //找到该元素对应到哈希表中的位置
if (_table[hashi]) //如果不为空,则说明有元素
{
Node* cur = _table[hashi];
Node* parent = nullptr; //保存上一个节点,因为如果不是第一个节点需要链接
while (cur) //寻找要删除的元素的节点
{
if (cur->_kv.first == key) //找到了
{
if (cur == _table[hashi]){ //如果是第一个节点,特殊处理
delete cur;
_table[hashi] = nullptr;
_n--;
return true;
}
else{ //不是第一个节点
if(parent)
parent->_next = cur->_next; //链接
delete cur;
_n--;
return true;
}
}
parent = cur;
cur = cur->_next;
}
return false;
}
else{
return false;
}
}
private:
vector<Node*> _table; ///表
size_t _n; //记录储存的有效数据个数
};
-
开散列增容
桶的个数是一定的,随着元素的不断插入,每个桶中元素的个数不断增多,极端情况下,可能会导致一个桶中链表节点非常多,会影响的哈希表的性能,因此在一定条件下需要对哈希表进行增容,那该条件怎么确认呢?开散列最好的情况是:每个哈希桶中刚好挂一个节点,再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶的个数时,可以给哈希表增容。 -
数据类型为非整型时的定址方法
因为%取模的操作数只能是整型,那么当我们存储的数据类型为string或则Date(日期类)时,应该怎样去计算位置呢?
这时,如果存储的数据不是整型的时候,就需要先转换为整型再定址;
2.5开散列与闭散列比较
应用链地址法处理溢出,需要增设链接指针,似乎增加了存储开销。事实上:
由于开地址法必须保持大量的空闲空间以确保搜索效率,如二次探查法要求装载因子a <= 0.7,而表项所占空间又比指针大的多,所以使用链地址法反而比开地址法节省存储空间。
3.哈希的模拟实现
1. 模板参数列表
// K:关键码类型
// T: 不同容器T的类型不同,如果是unordered_map,T代表一个键值对,如果是unordered_set,T为 K
// KeyOfValue: 因为T的类型不同,通过value取key的方式就不同,详见见unordered_map/set的实现
// HFunc : 哈希函数仿函数对象类型,哈希函数使用除留余数法,需要将Key转换为整形数字才能取模
template<class K, class T, class KeyofT, class HFunc = Hashfunc<K> >
class HashTable;
2. 迭代器的实现
解析:
-
因为我们实现的hashTable是开散列的,底层是一个数组,数组里面存储的一个一个的节点,节点下面有可能挂着一个哈希桶;迭代器的实现必须要实现 ++,*,!= 操作,++ 指向下一个节点的,这里如果迭代器里面我们只选择封装一个节点的指针的话,那么如果当这个节点是一个哈希桶里面的最后一个节点时,则没有办法找到下一个节点,所以需要加一个哈希表的地址,当然也可以是哈希表中存放节点指针的vector;
其中下一个节点的寻找方法:- 判断当前节点的下一个节点是否为空,如果不为空,则让其指向下一个节点即可,如果当前节点的下一个节点为空,则需要步骤二。
- 计算出当前节点所在哈希表中的下标(哈希地址),向后寻找数组中不为空的位置,让其指向该位置。
-
因为我们需要访问HashTable里面的私有成员(vector<Node*> ),所以需要将迭代器设置成HashTable的友元类。
代码实现:
template<class K, class T, class KeyofT, class HFunc> //前置声明,因为迭代器需要一HashTable的一个指针,需要使用到HashTable,编译器默认向上找,如果不加前置声明,则会找不到报错
class HashTable;
template<class K, class T, class KeyofT,class HFunc = Hashfunc<K>>
struct Iterator
{
typedef HashTable<K, T, KeyofT, HFunc> HashTable;
typedef Iterator<K, T, KeyofT,HFunc> Self;
typedef HashNode<T> Node; //存放数据的节点
Node* _node; //节点指针
HashTable* _ht; //哈希表
Iterator(Node* node, HashTable* ht)
:_node(node)
,_ht(ht)
{}
T& operator*()
{
return _node->_date;
}
T* operator->()
{
return &_node->_date;
}
Self& operator++()
{
KeyofT kot;
if (_node->_next) //如果该节点的下一个节点存在
{
_node = _node->_next;
}
//找下一个桶
else
{
Hashfunc<K> Hfunc;
size_t hashi = Hfunc(kot(_node->_date)) % _ht->_table.size();
hashi++;
while (hashi < _ht->_table.size())
{
if (_ht->_table[hashi])
{
_node = _ht->_table[hashi];
break;
}
hashi++;
}
if (hashi == _ht->_table.size())
{
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
3. 增加通过key获取value操作
//map
struct mapKeyofT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
///set
struct setKeyofT
{
const K& operator()(const K& key)
{
return key;
}
};
4. 哈希实现总代码:
#pragma once
#include<iostream>
#include<string>
#include<vector>
using namespace std;
template<class T>
struct HashNode
{
HashNode(const T& date)
:_next(nullptr)
, _date(date)
{}
HashNode<T>* _next;
T _date;
};
template<class K>
struct Hashfunc //整型数据不用转换
{
size_t operator()(const K& key)
{
return (size_t)key; //直接返回
}
};
template<> //特化
struct Hashfunc<string> //如果为字符串类型,需要将其转化为整形
{
size_t operator()(const string& s)
{
size_t hashi = 0;
for (auto e : s)
{
hashi += e;
hashi *= 131; //这里13 131 1313.....都可以
}
return hashi; //转换为整型返回
}
};
///迭代器的实现
template<class K, class T, class KeyofT, class HFunc> //前置声明
class HashTable;
template<class K, class T, class KeyofT,class HFunc = Hashfunc<K>>
struct Iterator
{
typedef HashTable<K, T, KeyofT, HFunc> HashTable;
typedef Iterator<K, T, KeyofT,HFunc> Self;
typedef HashNode<T> Node;
Node* _node;
HashTable* _ht;
Iterator(Node* node, HashTable* ht)
:_node(node)
,_ht(ht)
{}
T& operator*()
{
return _node->_date;
}
T* operator->()
{
return &_node->_date;
}
Self& operator++()
{
KeyofT kot;
if (_node->_next)
{
_node = _node->_next;
}
//找下一个桶
else
{
Hashfunc<K> Hfunc;
size_t hashi = Hfunc(kot(_node->_date)) % _ht->_table.size();
hashi++;
while (hashi < _ht->_table.size())
{
if (_ht->_table[hashi])
{
_node = _ht->_table[hashi];
break;
}
hashi++;
}
if (hashi == _ht->_table.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 KeyofT, class HFunc = Hashfunc<K>>
class HashTable
{
typedef HashNode<T> Node;
public:
template<class K, class T, class KeyofT, class HFunc>
friend struct Iterator;
typedef Iterator<K, T, KeyofT, HFunc> iterator;
iterator begin()
{
for (int i = 0; i <_table.size(); i++)
{
if (_table[i])
{
return iterator(_table[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
HashTable(size_t size = 10)
{
_table.resize(size, nullptr);
_n = 0;
}
~HashTable()
{
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i])
{
Node* cur = _table[i];
Node* next = nullptr;
while (cur)
{
next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
}
pair<iterator,bool> insert(const T& date)
{
KeyofT kot;
//查重,如果已经存在,不用插入了
Node* ret = find(kot(date));
if (ret)
{
return make_pair(iterator(ret,this), false);
}
//扩容
if (_n == _table.size())
{
vector<Node* > newtable(2 * _table.size(), nullptr); //创建一个新的newtable
Hashfunc<K> HFunc;
for (size_t i = 0; i < _table.size(); i++) //遍历原hashtable,将节点移到新的hastable里
{
if (_table[i]) //如果不为空,则移动节点到新表的对应位置上
{
Node* cur = _table[i];
while (cur)
{
//头插到新表对应位置
size_t hashi = HFunc(kot(cur->_date)) % newtable.size();
Node* next = cur->_next;
cur->_next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
_table[i] = nullptr; //移动完后,将原表中映射位置置空
}
}
_table.swap(newtable); //调用vector的的swap函数完成交换
}
//插入代码
Hashfunc<K> HFunc;
size_t hashi = HFunc(kot(date)) % _table.size();
if (_table[hashi])
{
//头插
Node* newnode = new Node(date);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return make_pair(iterator(newnode,this),true);
}
else
{
Node* newnode = new Node(date);
_table[hashi] = newnode;
++_n;
return make_pair(iterator(newnode, this), true);
}
}
//查找
Node* find(const K& key)
{
KeyofT kot;
Hashfunc<K> HFunc;
size_t hashi = HFunc(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (kot(cur->_date) == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key)
{
Hashfunc<K> HFunc;
size_t hashi = HFunc(key) % _table.size();
if (_table[hashi])
{
Node* cur = _table[hashi];
Node* parent = nullptr;
while (cur)
{
KeyofT kot;
if (kot(cur->_date) == key) //找到了
{
if (cur == _table[hashi]) //是第一个节点
{
delete cur;
_table[hashi] = nullptr;
_n--;
return true;
}
else //不是第一个节点
{
if(parent)
parent->_next = cur->_next;
delete cur;
_n--;
return true;
}
}
parent = cur;
cur = cur->_next;
}
return false;
}
else
{
return false;
}
}
private:
vector<Node*> _table; //表
size_t _n; //记录储存的有效数据个数
};
4.用实现的哈希封装unordered_map与unordered_set前的模板参数的梳理及相关联系的梳理
我们是想要用同一个哈希表封装出不同的容器(unordered_map与unordered_set),所以就需要对相关操作参数及操作做出改变。
- unordered_map与unordered_set存储的数据类型不同,unordered_map存储的是pair<K,V> ,K为key的类型,V为value的类型而unordered_set,存储的是K,所以就需要对节点所存储的数据类型做出改变,如图:
- 因为unordered_map中的key为pair中的第一个数据,而unordered_set中存储的数据就是key,所以当在需要取出数据里面的key进行操作时,unordered_map与unordered_set取出的方法有差异,所以需要各自提供一个仿函数来实现:如图:
5.unordered_map的封装实现
#pragma once
#include"HashTable.h"
namespace map
{
template<class K, class V, class HFunc = Hashfunc<K>>
class unorderedmap
{
struct mapKeyofT //取数据中的key,即pair<K,V>中的k
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<K, V>, mapKeyofT, HFunc>::iterator iterator;
pair<iterator,bool> insert(const pair<K, V>& kv)
{
return _ht.insert(kv);
}
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.insert(make_pair(key,V()));
return (ret.first)->second;
}
private:
HashTable<K, pair<K, V>, mapKeyofT, HFunc> _ht; //需要用自己的mapKeyofT去实例化一个HashTable
};
6.unordered_set的封装实现
#pragma once
#include"HashTable.h"
namespace set
{
template<class K, class HFunc = Hashfunc<K>>
class unorderedset
{
struct setKeyofT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashTable<K, K, setKeyofT, HFunc>::iterator iterator;
pair<iterator, bool> insert(const K& key)
{
return _ht.insert(key);
}
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
private:
HashTable<K, K, setKeyofT, HFunc> _ht; //需要用自己的setKeyofT去实例化一个HashTable
};
本章完~