番禺建设网站专家,广州市网站设计公司,石河子做网站的公司,四川省建设工程造价信息网哈希 unordered系列关联式容器unordered_map介绍 底层结构哈希概念哈希冲突哈希函数哈希冲突解决方式闭散列开散列 模拟实现哈希表的改造 哈希应用位图概念实现 布隆过滤器提出概念 unordered系列关联式容器
在C98中#xff0c;STL提供了底层为红黑树结构的一系列关联式容器98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率很高即使最差的情况下需要红黑树的高度次当树中的节点非常多时查询的效率不理想最理想的查询是进行很少的比较次数就能够将元素找到因此在C11中STL有提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同
unordered_map
介绍
unordered_map是存储键值对pairK,V的关联式容器允许通过键值key快速查找到与其对应的实值value在unordered_map中键值通常唯一地标识元素而映射值是一个对象其内容与键值关联键值和映射对象类型可能不同在内部unordered_map没有将键值对按照任何特定顺序进行排序无序为了能在常数范围内找到键值对应的实值unordered_map将相同哈希值的键值对存放在相同的桶中unordered_map实现了直接访问操作符operator[]允许使用键值作为参数直接访问实值迭代器只能向前
底层结构
unordered系列关联式容器之所以效率高是因为底层结构是哈希接下来深入了解这个结构
哈希概念
顺序结构和平衡树中元素的键值与其存储的位置无关因此在查找某一个元素时必须通过键值进行多次比较搜索的效率取决于搜索过程中元素的比较次数
哈希结构提供一种搜索方式通过数组实现的结构不经过任何比较直接从其结构中搜索待查找的元素通过某种函数将元素的键值与存储位置之间建立联系也就是映射关系在查找时便可通过该函数快速找到该元素
插入元素根据元素的键值通过此函数计算出该元素的存储位置并存放
查找元素对元素的键值进行同样的计算将求得的函数值当作元素的存储位置在结构中此位置取元素进行比较若键值相等则搜索成功
哈希方法中使用的转换函数称为哈希函数hash(key)key%size()结构称为哈希表
例如
int arr[]{3,6,7,1,4}哈希函数hash(key)key%size()size()存储元素底层空间的大小 哈希冲突
按照上述哈希方式再次向表中插入元素14结果会怎样呢 从图中可以发现在表中下标为4的格子中同时出现两个元素此时如果进行元素查找便可能会出现问题
对于两个元素的键值通过哈希函数计算之后相等的情景称为哈希冲突
既然问题已经存在首先是要找到解决方法接下来慢慢揭晓
哈希函数
造成哈希冲突的其中一个原因可能是哈希函数设计的不合理
设计原则
哈希函数的定义域必须包括要存储的全部键值如果表中允许有 n个地址时其值域必须在 [0,n-1]之间哈希函数计算出的地址能均匀分布在整个表中
常见哈希函数这里只介绍一种除留余数法
设表中允许的地址数为 n取一个不大于 n但最接近或者等于 n的数 p作为除数按照哈希函数 hash(key)key%p(pn)将键值转换为哈希地址有点类似于基数排序
哈希冲突解决方式
解决哈希冲突的两种常见方法闭散列和开散列
闭散列
也称开放定址法当发生哈希冲突时如果哈希表还未被装满表明在表中还有空余地址便可以将冲突的键值存放到冲突位置的“下一个”空地址中那么又该如何去寻找空地址呢
这里只简单介绍一种寻找空地址的方法线性探测 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空地址为止
插入通过哈希函数获取待插入元素在表中的位置当发生哈希冲突时使用线性探测寻找下一个空地址插入新元素 删除
采取闭散列处理哈希冲突时不可以随便删除表中的元素如果直接删除元素会影响其他元素的查找比如直接删除元素 4当查找元素 14时便会显示元素不存在但实际上该元素是存在的所以还表中的每个地址都需要一个标记来表示当前位置的状态
在模拟实现之前先介绍新的概念负载因子即元素个数除以表格的大小在闭散列中负载因子永远小于1范围是 (0,1)这样的做法是为了保障效率一般规定负载因子的大小为 0.7一旦超过此大小哈希表便需要进行扩容 //标识位置的状态enum State{EXIST,EMPTY,DELETE,};//表中每个位置的结构templateclass K,class Vstruct Hashnode{pairK, V _kv;State _state EMPTY;};//表的结构templateclass K,class V,class HashHashFuncKclass Hashtable{typedef HashnodeK, V Data;public:Hashtable():_n(0){_table.resize(10);}Data* find(const K key){Hash hf;size_t hashi hf(key) % _table.size();while (_table[hashi]._state ! EMPTY){if (_table[hashi]._state EXIST _table[hashi]._kv.first key){return _table[hashi];}hashi;hashi % _table.size();}return nullptr;}bool insert(const pairK, V kv){if (find(kv.first)){return false;}//大于规定负载因子扩容if (_n * 10 / _table.size() 7){//旧表的元素重写计算映射到新表中HashtableK, V, Hash newht;newht._table.resize(_table.size() * 2);for (auto e : _table){if (e._state EXIST){newht.insert(e._kv);}}_table.swap(newht._table);}Hash hf;size_t hashi hf(kv.first) % _table.size();while (_table[hashi]._state EXIST){//线性探测hashi;hashi % _table.size();}_table[hashi]._kv kv;_table[hashi]._state EXIST;_n;return true;}bool erase(const K key){Hash hf;size_t hashi hf(key) % _table.size();while (_table[hashi]._state ! EMPTY){if (_table[hashi]._state EXIST _table[hashi]._kv.first key){return _table[hashi];}hashi;hashi % _table.size();}return nullptr;}private:vectorData _table;size_t _n 0;//表中存储元素的有效个数};测试 void test(){int arr[] { 3,6,7,1,4,14};Hashtableint, intht;for (auto e : arr){ht.insert(make_pair(e,e));}}运行结果 上面的测试对象是整型数组当遇到字符串又该如何呢 由于哈希只能处理整型所以需要将字符串转换成整型之后再通过哈希函数计算位置进行各种操作采取仿函数 HashFunc()来将各种数据类型转换成整型也就是为什么在创建Hashtable类时模板中存在 class HashHashFuncK缺省值的原因
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};//特化
template
struct HashFuncstring
{size_t operator()(const string key){size_t hash 0;for (auto e : key){e * 131;hash e;}return hash;}
};总结 线性探测的优点实现起来非常简单 线性探测的缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据堆积从而导致效率降低
开散列
又称地址法首先对键值通过哈希函数计算位置具有相同的位置的键值归于同一个子集每一个子集称为一个桶每个桶中的元素通过一个单链表连接起来每个链表的头节点存储在哈希表中此时的哈希表就是一个指针数组此结构也称哈希桶 从上图可以发现开散列中每个桶中存放的都是发生哈希冲突的元素开散列的负载因子一般规定不超过1一旦超过便会进行扩容操作 templateclass K, class Vstruct Hashnode{pairK, V _kv;HashnodeK, V* _next;Hashnode(const pairK, V kv):_kv(kv), _next(nullptr){}};templateclass K, class V, class Hash HashFuncKclass Hashbucket{typedef HashnodeK, V node;public:Hashbucket():_n(0){_table.resize(10);}~Hashbucket(){for (size_t i 0; i _table.size(); i){node* cur _table[i];while (cur){node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}node* find(const K key){size_t hashi Hash()(key) % _table.size();node* cur _table[hashi];while (cur){if (cur-_kv.first key){return cur;}else{cur cur-_next;}}return nullptr;}bool insert(const pairK, V kv){if (find(kv.first)){return false;}if (_table.size() n){vectornode* newtable;newtable.resize(2 * _table._size());for (size_t i 0; i _table.size(); i){while (cur){node* next cur-_next;size_t hashi Hash()(cur-_kv.first) % _table.size();//头插到新表cur-_next newtable[hashi];newtable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newtable);}size_t hashi Hash()(kv.first) % _table.size();node* newnode new node(kv);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;}bool erase(const K key){size_t hashi Hash()(key) % _table.size();node* prev nullptr;node* cur _table[hashi];while (cur){if (cur-_kv.first key){//准备删除//没有哈希冲突if (cur _table[hashi]){_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--_n;return true;}else{prev cur;cur cur-_next;}}return false;}private:vectornode* _table;size_t _n 0;//表中存储元素的有效个数};测试 void test(){int arr[] { 3,6,7,1,4,14 };Hashtableint, intht;for (auto e : arr){ht.insert(make_pair(e, e));}}运行结果 闭散列和开散列的比较 应用地址法处理哈希冲突需要增设链表指针似乎增加了存储开销实际上由于地址法必须保持大量的空闲空间以确保搜索效率而哈希表所占空间又比指针大得多所以开散列比闭散列更加地节省存储空间
模拟实现
哈希表的改造
增加迭代器 templateclass K, class T, class Hash, class KeyofTstruct _Hashiterator{typedef HashnodeT node;typedef _HashiteratorK, T, Hash, KeyofT Self;typedef HashbucketK, T, Hash, KeyofT HB;node* _node;//指向哈希桶的指针用来获取HB* _hb;_Hashiterator(node* node, HB* hb):_node(node), _hb(hb){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const Self s)const{return _node ! s._node;}bool operator(const Self s)const{return _node s._node;}Self operator(){if (_node-_next){_node _node-_next;}else{//当前的桶已经遍历完需要到下一个桶进行遍历KeyofT kot;Hash hash;size_t hashi hash(kot(_node-_data)) % _hb-_table.size();hashi;while (hashi _hb-_table.size()){if (_hb-_table[hashi]){_node _hb-_table[hashi];break;}else{hashi;}}if (hashi _hb-_table.size()){_node nullptr;}}return *this;}};哈希表中每个元素的设计 templateclass Tstruct Hashnode{T _data;HashnodeT* _next;Hashnode(const T data):_data(data), _next(nullptr){}};这里同样考虑到数据T可能是键值key也可能是键值对pairK,V;所以许还需要一个能够通过键值key获取实值value的仿函数KeyofT此仿函数的实现在模拟实现的类对象中实现 //前置声明templateclass K,class T,class Hash,class KeyofTclass Hashbucket;templateclass K, class T, class Hash, class KeyofTstruct _Hashiterator{typedef HashnodeT node;typedef _HashiteratorK, T, Hash, KeyofT Self;typedef HashbucketK, T, Hash, KeyofT HB;node* _node;//指向哈希桶的指针用来获取HB* _hb;_Hashiterator(node* node, HB* hb):_node(node), _hb(hb){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const Self s)const{return _node ! s._node;}bool operator(const Self s)const{return _node s._node;}Self operator(){if (_node-_next){_node _node-_next;}else{//当前的桶已经遍历完需要到下一个桶进行遍历KeyofT kot;Hash hash;size_t hashi hash(kot(_node-_data)) % _hb-_table.size();hashi;while (hashi _hb-_table.size()){if (_hb-_table[hashi]){_node _hb-_table[hashi];break;}else{hashi;}}if (hashi _hb-_table.size()){_node nullptr;}}return *this;}};templateclass K, class T, class Hash,class KeyofTclass Hashbucket{typedef HashnodeT node;templateclass K,class T,class Hash,class KeyofTfriend struct _Hashiterator;public:typedef _HashiteratorK, T, Hash, KeyofT iterator;Hashbucket():_n(0){_table.resize(10);}~Hashbucket(){for (size_t i 0; i _table.size(); i){node* cur _table[i];while (cur){node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}}iterator begin(){for (size_t i 0; i _table.size(); i){//寻找第一个不为空的位置if (_table[i]){return iterator(_table[i], this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}iterator find(const K key){KeyofT kot;size_t hashi Hash()(key) % _table.size();node* cur _table[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur, this);}else{cur cur-_next;}}return end();}pairiterator,bool insert(const Tdata){KeyofT kot;iterator it find(kot(data));if (it ! end()){return make_pair(it, false);}if (_table.size() _n){vectornode*newtable;newtable.resize(_table.size() * 2);for (size_t i 0; i _table.size(); i){node* cur _table[i];while (cur){node* next cur-_next;size_t hashi Hash()(kot(data)) % newtable.size();//头插到新表中cur-_next newtable[hashi];newtable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newtable);}size_t hashi Hash()(kot(data)) % _table.size();//头插node* newnode new node(data);newnode-_next _table[hashi];_table[hashi] newnode;_n;return make_pair(iterator(newnode, this), true);}bool erase(const K key){size_t hashi Hash()(key) % _table.size();node* prev nullptr;node* cur _table[hashi];while (cur){if (cur-_kv.first key){//准备删除//没有哈希冲突if (cur _table[hashi]){_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--_n;return true;}else{prev cur;cur cur-_next;}}return false;}private:vectornode* _table;size_t _n 0;//表中存储元素的有效个数};模拟实现unordered_map 仿函数MapKeyofT的实现 struct MapKeyofT{const K operator()(const pairconst K, V kv){return kv.first;}};完整代码 templateclass K,class V,class HashHashFuncKclass unordered_map{ struct MapKeyofT{const K operator()(const pairconst K, V kv){return kv.first;}};public:typedef typename yjm::HashbucketK, pairconst K, V, Hash, MapKeyofT::iterator iterator;iterator begin(){return _hb.begin();}iterator end(){return _hb.end();}pairiterator, bool insert(const pairK, V data){return _hb.insert(data);}V operator[](const K key){pairiterator, bool ret _hb.insert(make_pair(key, V()));return ret.first-second;}private:yjm::HashbucketK, pairconst K, V, Hash, MapKeyofT _hb;};测试 void test(){string arr[] { 篮球,羽毛球,排球,乒乓球,羽毛球 ,羽毛球 ,排球 };unordered_mapstring, int countmap;for (auto e : arr){countmap[e];}}运行结果
哈希应用
位图
概念
所谓位图就是用每一位来存放某种状态适用海量数据数据无重复的场景通常是用来判断某个数据存在或者不存在的信息如果二进制比特位byte) 1代表存在0代表不存在
举个栗子
int arr[] { 3,6,7,1,4,14 };每个字节共有8个比特位可以保存8个数据的状态存在或不存在 通过位图的概念解决一个问题 给40亿个不重复的无符号整数没有排过序给定一个无符号整数如何快速判断这个数是否在这40亿个数中
如果没有位图的概念可能会想着将这些数放到红黑树或者哈希中但是40亿个整数所需的内存大概是16G所以这种想法不切实际接下来就通过位图的概念进行解题
通过位图概念首先要确定数据的位置这里采用直接定址法数据的值是几就将第几个位标记成1 数据映射在第几个字节上x/8 在这个字节的第几个比特位上x%8 找到位置之后需要做的便是如何设置状态在之前的学习中位运算可以解决这个问题接下来就是通过灵活运用位运算对数据的状态进行设置
其他位不变第j位标记成1 如果第 j位之前就是1结果也就是1如果不是1按位或之后也会变成1 void set(size_t x){size_t i x / 8;size_t j x % 8;_bit[i] | (1 j);}其他位不变第j位标记成0
如果第 j位之前就是0结果也就是0如果不是0按位与之后也会变成0 void reset(size_t x){size_t i x / 8;size_t j x % 8;_bit[i] (~(1 j));}测试该位的数据是否存在 bool test(size_t x){size_t i x 3;size_t j x % 8;return _bit[i] (1 j);}实现
此题目只是判断数据是否存在一个比特位便可以进行判断 0不存在 1存在由于是在40亿个数字中进行判断所以将40亿个数据放入容量为 size_t int i-1比特位的容器中进行判断
代码实现 templatesize_t Nclass bitset{public:bitset(){_bit.resize((N 3) 1, 0);}void set(size_t x){size_t i x / 8;size_t j x % 8;_bit[i] | (1 j);}void reset(size_t x){size_t i x / 8;size_t j x % 8;_bit[i] (~(1 j));}bool test(size_t x){size_t i x 3;size_t j x % 8;return _bit[i] (1 j);}private:vectorchar _bit;};测试 void test(){bitset-1 bs;bs.set(3);bs.set(6);bs.set(7);bs.set(1);bs.set(4);bs.set(14);cout bs.test(3) endl;cout bs.test(6) endl;cout bs.test(7) endl;cout bs.test(1) endl;cout bs.test(4) endl;cout bs.test(14) endl;bs.reset(3);bs.reset(6);bs.reset(7);bs.reset(1);bs.reset(4);bs.reset(14);cout bs.test(3) endl;cout bs.test(6) endl;cout bs.test(7) endl;cout bs.test(1) endl;cout bs.test(4) endl;cout bs.test(14) endl;}运行结果 位图的应用
快速查找某个数据是否存在一个集合中排序去重求两个集合的交集并集操作系统中对磁盘进行标记
布隆过滤器
提出
当通过哈希函数对字符串映射到位图上时可能会出现两个字符串同时映射到同一个比特位上便会出现误判的情况误判是不可避免的那么又该如何降低误判呢
概念
使用多个哈希函数将一个数据映射到位图结构中特点是高效地插入和查询还可以节省大量的内存空间 对于一个字符串通过不止一个哈希函数进行映射便可以降低误判 对于判断为不存在时一定是正确的判断存在时不一定正确可能存在着冲突
