网站建设的营业执照,游戏平台代理,wordpress 开启手机,网站中文字内容左右切换的js代码哈希表 unordered系列unordered_set和unordered_map的使用哈希哈希概念哈希冲突哈希函数闭散列开散列哈希表的扩容哈希表源码#xff08;开散列和闭散列#xff09; 封装unordered_set/和unordered_map#xff0c;以及实现迭代器节点定义unordered_set定义unordered_map定义… 哈希表 unordered系列unordered_set和unordered_map的使用哈希哈希概念哈希冲突哈希函数闭散列开散列哈希表的扩容哈希表源码开散列和闭散列 封装unordered_set/和unordered_map以及实现迭代器节点定义unordered_set定义unordered_map定义哈希表实现迭代器实现 unordered系列
C98中引入了map和set这两种类型底层数据结构都是红黑树不管是插入、删除、查询等操作都是log2n ,这个时间复杂度已经非常快了但是有没有一种数据结构能通过值直接定位到存储位置所以C11中引入了unordered系列这次重点讨论unordered_set/unordered_mapunordered底层就是用的哈希表也可以称为散列表。接下来我会详细剖析哈希表的原理以及哈希表如何被封装成unordered_set和unordered_map。
unordered_set和unordered_map的使用
其实unordered_set和unordered_map使用上基本没有区别。
void test_unordered_set1()
{unordered_setint s;s.insert(1);s.insert(3);s.insert(2);s.insert(7);s.insert(2);unordered_setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;
}void test_unordered_map()
{string arr[] { 苹果, 菠萝, 葡萄, 菠萝, 哈密瓜, 香蕉, 苹果, 香蕉, 梨, 西红柿, 香蕉, 菠萝 };mapstring, int countMap;for (auto e : arr){countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}
}这就是unordered最常用的函数和map/set没什么区别如果想详细了解这些接口的使用可以通过这个C的网址进行查询链接: cplusplus。
哈希
哈希概念
了解哈希表之前我先浅浅的提问一个问题给你一个字符串统计每个字母出现的次数(默认都是小写)应该怎么统计 这是一道非常简单的题目可能方法很多但是我们可以采用比较快捷的方式采用映射的方式总共有26的英文字母开一个int类型大小为26的数组存储a~z出现的次数遍历字符串每个字母减去a就是数组对应的下标只需要通过数组下标内的值就可以完成对字母出现次数的统计。 这问题的本质其实就是通过一种特定的映射方式一次就可以找到相对应的位置哈希表也称散列表也是通过这种原理通过特定的函数计算key的唯一存储位置。 哈希概念以不经过任何比较一次直接从表中得到要搜索的元素。如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。
该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表)
例如数据集合{176459} 哈希函数设置为hash(key) key % capacity 除留余数法哈希函数介绍; capacity为存储元素底层空间总的大小。 用该方法进行搜索不必进行多次关键码的比较所以哈希表的查询速度是O(1)的非常快。
哈希冲突
上面通过key除以capacity求得了存储位置这种方式有什么问题呢?答案是肯定有例如在插入一个44通过44%104可是4的位置已经有了元素这种情况称为哈希冲突。
哈希冲突可以用开散列和闭散列的方式去解决。
哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。 哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
常见的哈希函数
直接定址法–(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀 缺点需要事先知道关键字的分布情况 使用场景适合查找比较小且连续的情况除留余数法–(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数 按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址。
我们最常用的就是除留余数法所以其他哈希函数了解就好了。 还有一个问题就是上面举例中key都是整数所以可以拿key直接%数组大小得到存储位置但是如果是字符串或者浮点数或者自定义类型呢这个就需要哈希函数把相应的类型转换成int或者unsigned int。 例如 字符串需要怎么转换成整形呢或许很多人想到把他们相加可是如果只是相加的话大量字符串只是排列组合不一样也会映射到同一个存储位置闭散列会发生大量踩踏开散列就是把数据都挂到一个桶内所以采用下列这种方式。加每个字符之后乘31也可以乘以131、1313、13131、131313… 。本算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得 名是一种简单快捷的hash算法也是Java目前采用的字符串的Hash算法累乘因子为31。
//特化
template
struct HashFuncstring
{// BKDRsize_t operator()(const string s){size_t hash 0;for (auto ch : s){hash ch;hash * 31;}return hash;}
};闭散列 也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢 例如数组中现在需要插入元素44先通过哈希函数计算哈希地址hashAddr为4因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。 解决方案
线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 二次探测依次检测第i2个位置是否为空
线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为 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是表的大小。
闭散列的删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
enum Status {EMPTY,//位置为空EXIST,//位置不为空DELETE//删除状态
};总结
线性探测和二次探测是解决哈希冲突的两种方法。 线性探测顾名思义是一种按线性方式探测的方法。如果发生了哈希冲突它会尝试顺序地检查下一个哈希槽直到找到一个空位或者检查完了整个哈希表。但是线性探测容易导致聚集性冲突即相邻位置都被占用的情况。如果哈希表的利用率比较高那么冲突解决的效率也会越来越低。 而二次探测是一种按照平方探测的方式解决哈希冲突的方法。相对于线性探测它探测的跨度更大可以充分利用哈希表的空间。当一个位置已经被占用时它会依次探测第 1 2 1^2 12、第 2 2 2^2 22、第 3 2 3^2 32……个位置直到找到一个空位或者找遍整个哈希表。但是二次探测容易导致“二次探测陷阱”使得某些哈希槽永远无法被探测到。 综上线性探测和二次探测各有优劣并且适用于不同的场景。在哈希表的容量比较大利用率比较低的情况下二次探测效率更高。但如果哈希表的利用率比较高那么线性探测可能更加适用。在实际应用中可以通过选择不同的哈希函数和调节哈希表的容量来优化哈希表的性能。
闭散列学习了解即可实际运用中开散列是用的比较多的。
闭散列源码实现 enum Status {EMPTY,EXIST,DELETE};templateclass K, class Vstruct HashData {pairK, V _kv;Status status EMPTY;};templateclass K, class Vclass HashTable {typedef HashDataK, V Node;public:Node* Find(const K key){if (_table.size() 0){return nullptr;}int hashi key % _table.size();int index hashi;while (_table[index]._kv.first ! key){index;index % _table.size();if (index hashi){return nullptr;}}if (_table[index].status EXIST){return _table[index];}else {return nullptr;}}bool Erase(const K key){Node* ret Find(key);if (ret){ret-status DELETE;return true;}else{return false;}}bool insert(const pairK, V kv){if (Find(kv.first)){return false;}if (_table.size() 0 || n * 10 / _table.size() 7) {//扩容size_t newsize _table.size() 0 ? 10 : _table.size() * 2;HashTableK, V newtable;//扩容需要重新开辟空间newtable._table.resize(newsize);for (auto data : _table) {if (data.status EXIST){newtable.insert(data._kv);}}_table.swap(newtable._table);}int hashi kv.first % _table.size();int index hashi;while (_table[index].status EXIST) {index;index % _table.size();if (index hashi){break;}}_table[index]._kv kv;_table[index].status EXIST;n;return true;}private:vectorNode _table;int n 0;};开散列
闭散列有许多的弊端让哈希表实际当中并不是那么理想开散列也是解决哈希冲突的一种方式也是实际当中用的比较多的一种方法。 开散列也成为哈希桶数组里面存储的是单链表发生了哈希冲突之后不会向后找空位置而是插入到存储位置的链表尾部。
templateclass K, class Vstruct HashNode{HashNodeK, V* _next;pairK, V _kv;HashNode(const pairK, V kv):_next(nullptr), _kv(kv){}};所以我们通过哈希函数就可以找到存储位置插入单链表节点就好想要删除也是单链表的删除。
开散列哈希桶实现源码 templateclass K,class Vstruct HashData{pairK, V _kv;HashDataK, V* next;HashData(const pairK,V kv):_kv(kv),next(nullptr){}};templateclass K,class Vclass HashTable{typedef HashDataK, V Node;public:~HashTable(){if (_table.size() 0){for (auto cur : _table){while (cur){Node* next cur-next;delete cur;cur next;}}}}bool Erase(const K key){int hashi key % _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key){if (prev nullptr){_table[hashi] cur-next;delete cur;}else{prev-next cur-next;delete cur;}cur nullptr;return true;}prev cur;cur cur-next;}return false;}Node* Find(const K key){if (_table.size() 0){return nullptr;}int hashi key % _table.size();Node* cur _table[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-next;}return nullptr;}bool Insert(const pairK, V kv){if (Find(kv.first)){return false;}if (_table.size() 0 || n / _table.size() 1){//扩容size_t newsize _table.size() 0 ? 10 : _table.size() * 2;vectorNode* newtable;newtable.resize(newsize,nullptr);for (auto cur : _table){while (cur){Node* next cur-next;size_t i cur-_kv.first % newtable.size();cur-next newtable[i];newtable[i] cur;cur next;}}_table.swap(newtable);}Node* newnode new Node(kv);int hashi kv.first % _table.size();newnode-next _table[hashi];_table[hashi] newnode;n;return true;}private:vectorNode* _table;int n 0;};哈希表的扩容
引入载荷因子 散列表的载荷因子定义为: α 填入表中的元素个数/散列表的长度 α是散列表装满程度的标志因子。由于表长是定值α与“填入表中的元素个数”成正比所以a越大表明填入表中的元素越多产生冲突的可能性就越大;反之α越小标明填入表中的元素越少产生冲突的可能性就越小。实际上散列表的平均查找长度是载荷因子α的函数只是不同处理冲突的方法有不同的函数。 对于开放定址法荷载因子是特别重要因素应严格限制在0.7-0.8以下。超过0.8查表时的CPU缓存不命中(cachemissing按照指数曲线上升。因此一些采用开放定址法的hash库如Java的系统库限制了荷载因子为0.75超过此值将resize散列表。 哈希桶的载荷因子控制在1即可。 哈希表源码开散列和闭散列
源码链接
封装unordered_set/和unordered_map以及实现迭代器
哈希表的原理说明已经讲解清楚了接下来需要对源码稍微改动一下对其封装。所有代码拿来就能用。代码的含义会在注释里面讲解清楚。
节点定义
templateclass T
struct HashNode
{T _data;HashNodeT* _next;HashNode(const T data):_data(data), _next(nullptr){}
};unordered_set定义 templateclass K,class Hash HashFunK//HashFun是保证传进来的类型能转换成整型如果key是自定义类型HashFun需要自己定义如果是string就用哈希函数中介绍的方法class unorder_set{struct SetOfT {size_t operator()(const K key){return key;}};public://由于key不可修改所以const迭代器就是普通迭代器typedef typename HashTableK, K, SetOfT, Hash::const_iterator iterator;//全部调用哈希表中的接口iterator begin() const{return ht.begin();}iterator end() const{return ht.end();}bool insert(const K key){return ht.Insert(key);}bool Erase(const K key){return ht.Erase(key);}private:HashTableK,K, SetOfT,Hash ht;};unordered_map定义 #pragma once
#include hash_table.h
namespace JRG {templateclass K,class V,class Hash HashFunKclass unorder_map{struct MapOfT {size_t operator()(const pairK,V key){return key.first;}};public:typedef typename HashTableK, pairconst K, V, MapOfT, Hash::iterator iterator;typedef typename HashTableK, pairconst K, V, MapOfT, 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();}pairiterator, bool insert(const pairK,V data){return ht.Insert(data);}bool erase(const K data){return ht.Erase(data);}private:HashTableK,pairconst K,V , MapOfT, Hash ht;};
}
哈希表实现
这是哈希表改动之后的源码我就直接在代码上面讲解默认用哈希桶的方式实现详情请看注释。
#pragma once
//哈希表实现
templateclass K,class T,class KeyOfT,class Hash
class HashTable
{
private:vectorNode* _table;int n 0;//存储元素的个数
public:typedef HashNodeT Node;//迭代器需要访问哈希表把迭代器定义为友元类。templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashfriend struct _HashIterator;typedef _HashIteratorK, T, T, T*, KeyOfT, Hash iterator;typedef _HashIteratorK, T, const T, const T*, KeyOfT, Hash const_iterator;//Hash hash;KeyOfT keyOfT;iterator begin(){Node* curnullptr;for (size_t i 0; i _table.size(); i){cur _table[i];if (cur){break;}}return iterator(cur, this);}iterator end() {return iterator(nullptr, this);}~HashTable(){if (_table.size() 0){for (auto cur : _table){while (cur){Node* next cur-next;delete cur;cur next;}}}}//每次扩容数组大小都为质数这是哈希表每次扩容之后的大小每次从数组获取下次扩容的大小。size_t GetNextPrime(size_t prime){// SGIstatic const int __stl_num_primes 28;static const unsigned long __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};size_t i 0;for (; i __stl_num_primes; i){if (__stl_prime_list[i] prime)return __stl_prime_list[i];}return __stl_prime_list[i];}//根据哈希桶原理传入key可以对其进行删除bool Erase(const K key){size_t hashi hash(key) % _table.size();Node* prev nullptr;Node* cur _table[hashi];while (cur){if (keyOfT(cur-_data) key){if (prev nullptr){_table[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;n--;return true;}else{prev cur;cur cur-_next;}}return false;}//查找keyiterator Find(const K key){if (_table.size() 0){return end();}size_t hashi hash(key) % _table.size();Node* cur _table[hashi];while (cur){if (keyOfT(cur-_data) key){return iterator(cur, this);}cur cur-_next;}return end();}//根据哈希桶的原理实现插入函数扩容逻辑也是在insert内部完成pairiterator, bool Insert(const T data){//如果要插入的值已经存在返回迭代器iterator it Find(keyOfT(data));if (it ! end()){return make_pair(it, false);}//需要扩容if (_table.size() 0 || n / _table.size() 1){vectorNode* newtable;newtable.resize(GetNextPrime(_table.size()), nullptr);for (auto cur : _table){while (cur){Node* next cur-_next;size_t i hash(keyOfT(cur-_data)) % newtable.size();cur-_next newtable[i];newtable[i] cur;cur next;}}_table.swap(newtable);}//找到对应的哈希桶插入链表节点Node* newnode new Node(data);int hashi keyOfT(data) % _table.size();newnode-_next _table[hashi];_table[hashi] newnode;n;return make_pair(it, true);}};
迭代器实现
//提前声明因为迭代器中要传入哈希表
templateclass K, class T, class KeyOfT, class Hash
class HashTable;//迭代器的实现哈希表的迭代器是单向迭代器所以不支持--。
templateclass K, class T, class Ref,class Ptr,class KeyOfT, class Hash
struct _HashIterator
{typedef HashNodeT Node;typedef HashTableK, T, KeyOfT,Hash Table;typedef _HashIteratorK, T, Ref, Ptr, KeyOfT, Hash Self;typedef _HashIteratorK, T, T, T*, KeyOfT, Hash iterator;Node* _node;const Table* _Table; //迭代器被哈希表定为友元类所以可以直接访问哈希表的成员变量_HashIterator(Node* node, const Table* table):_node(node), _Table(table){}//由于unordered_set只有const迭代器所以需要用普通迭代器构建const迭代器_HashIterator(const iterator it):_node(it._node), _Table(it._Table){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}Self operator(){if (_node-next){_node _node-next;return *this;}else { //证明这个桶内节点访问完了寻找下一个不为空的桶Hash hash;//这是Hash类重载的函数体负责保证可以把不是整数的类型转换成整数。KeyOfT keyoft;//这是KeyOfT类重载()如果是set就返回keymap返回kv.frist。size_t hashi hash(keyoft(_node-_data)) % _Table-_table.size(); //除留余数法计算当前桶的位置hashi;while (hashi _Table-_table.size())//保证不越界的情况下查找下一个不为空的桶{if (_Table-_table[hashi])//找到不为空的桶返回迭代器本身{_node _Table-_table[hashi];return *this;}hashi;}//哈希表遍历结束没有下一个节点。_node nullptr;return *this;}}
};所有源码链接link
这就是哈希表的全部内容有什么问题可以直接私信我码字不易觉得还不错点个赞和关注吧。
