文章目录
- 哈希
- 哈希容器:unordered_set与unordered_map
- 哈希
- 哈希表
- 哈希函数
- 哈希冲突
- 解决哈希冲突
- 扩容
- 哈希表的代码实现
- 线性探测法解决哈希冲突
- 哈希桶解决哈希冲突
哈希
哈希容器:unordered_set与unordered_map
-
unordered_set
-
定义如下:
-
常用接口
-
跟桶有关的接口
-
unordered_set与set的核心功能的重叠度有90%。 其差异如下
- 不同:unordered_set的底层是哈希表,set的底层是红黑树。
- 对key的要求不同。
- set要求key支持比较大小
- unordered_set要求支持key转成整形 + 支持比较相等
- 是否有序
- set遍历有序
- unordered_set遍历无序
- 迭代器不同
- set是双向迭代器
- unordered_set是单向迭代器。
即支持正向访问,但不支持反向访问。即只要begin(),end()。没有rbegin(),rend()
- find的性能差异很大。set的find为O(logN),unordered_set的find为O(1)。
- 对于无序且重复的数据/无序不重复的数据而言unordered_set在insert,erase,find等等方面的效率都是远远大于set的,不过随着数据量的增加,unordered_set的效率逐渐变低,甚至当数据量到达1000w以上且重复数据较少时,set的效率就和unordered_set的效率差不多了,甚至set的insert效率要高于unordered_set。
对于有序的数据而言,unordered_set和set的效率差异就没有那么大了,甚至set的效率要高于unordered_set - 随着数据量增大,unordered_set的效率逐渐降低的原因与unordered_set的扩容有关
- 对于无序且重复的数据/无序不重复的数据而言unordered_set在insert,erase,find等等方面的效率都是远远大于set的,不过随着数据量的增加,unordered_set的效率逐渐变低,甚至当数据量到达1000w以上且重复数据较少时,set的效率就和unordered_set的效率差不多了,甚至set的insert效率要高于unordered_set。
- 对key的要求不同。
- 不同:unordered_set的底层是哈希表,set的底层是红黑树。
-
-
unordered_map
-
定义如下: 相对于unordered_set而言,unordered_set存储key,而unordered_map存储<key,value>。
实际上unordered_map和map的使用几乎没有区别
-
常用接口
-
跟桶相关的接口
-
unordered_map与map的核心功能的重叠度有90%。 其差异与unordered_set与set的差异相同
-
哈希
哈希是一种思想。即值和值建立映射关系
哈希表
哈希表又称为散列表。 哈希表是值和存储位置建立映射关系,把对应的值放到存储位置,方便快速查找
这里很像一个<key,value>模型,通过key与存储位置建立映射关系,然后返回存储位置的值,即value的值
哈希函数
key通过某种运算与存储位置建立映射关系,而这里对key进行的某种运算被称为哈希函数
引起哈希冲突的一个原因可能是:哈希函数设计不够合理。如除留余数法会导致哈希冲突。不过除留余数法的哈希冲突是可以解决的
-
常见的哈希函数
-
直接定址法
hashi 通过 key去进行+运算或者-运算得来,甚至hashi与key的相同也可以。hashi是存储位置
- 优点:快,没有哈希冲突
- 缺点:只适合范围集中
-
除留余数法
hashi = key%N。 N是表的大小,key是值,hashi是存储位置。
-
优点:key取模的大小N以后,都可以映射到一个表中位置
-
缺点: 存在哈希冲突。
**哈希冲突:**哈希冲突也称为哈希碰撞。是指不同的值,取模以后映射到了相同位置
-
-
哈希冲突
哈希冲突也称为哈希碰撞。是指不同的值,取模以后映射到了相同位置
-
哈希冲突不可能完全避免!
可以降低哈希冲突的概率,但是不能完全避免哈希冲突。
如:对于直接定址法而言,将存储空间开大些可以降低哈希冲突的概率,但是当存储数据越来越多时,不可避免的会出现哈希冲突。特别是当key为string的时候,string要映射为size_t,然后size_t再作为key来与存储位置建立映射关系。
-
但是string的种类数量远远大于size_t能存储的数据量,因此肯定会有不同的string映射为同一个size_t类型的数据的时候,导致哈希冲突。
不过我们可以尽量减小哈希冲突的概率-
例如对于key一开始为string时尽量避免哈希冲突的方法有一个字符串哈希算法
字符串哈希算法如下:
各种字符串Hash函数 - clq - 博客园
-
-
解决哈希冲突
-
第一种方法:闭散列:开放定址法
*思路:当出现哈希冲突时,对应新插入的出现冲突的数据,通过某种规则去其他位置找一个空的。*
**常用的某种规则:**a.线性探测。 b.二次探测- **线性探测:**按照当前位置+1,+2,+3…。不过到hashi+n 大于N时,要进行回绕。回绕就是让(hashi+n)%N,即再从哈希表的前端开始查找
举个例子,如果key取模的大小为N以后,映射的位置为hashi,而此时hashi的位置已经有数据了,就出现了哈希冲突。那么就看hashi+1的位置是否有数据,如果有,那么就看hashi+2的位置,依次类推,直至hashi+n的位置没有数据,那么将 要存的数据存到hashi+n的位置上。 - **二次探测:**按照当前位置+12 , + 22, + 32…。不过当hashi+n2大于N时,要进行回绕
- 查找时: 从映射位置按照某种规则开始查找,这个规则与插入数据时的规则对应。遇到没有数据的位置会停止查找。
即如果通过线性探测插入数据,那么查找时也通过线性探测来查找数据;如果通过二次探测插入数据,那么查找时也通过二次探测来查找数据。-
查找时出现一个问题,当一个数据没删除,导致原本相连的数据出现了一个空白,而空白后的数据的映射位置在空白前的时候,如何才能找到该数据的位置。
例子如下图:
这里的某种规则是 线性探测法。查找数据16,16的映射位置是6,从存储位置6开始向后线性探测,到存储位置7时,由于存储位置7的数据为空,那么会导致到7时停止,无法探测到存储位置8的16
-
解决这个问题的方法是给每个位置给一个状态标记 。停止查找不再通过没有数据的位置而停止,而是遇到标记为空的位置而停止
如下图
空位置标记为横线,有数据的位置标记为对号,原本有数据的位置但后来被删除的标记为叉号。当检测到横线的时候,查找才停止
-
- **线性探测:**按照当前位置+1,+2,+3…。不过到hashi+n 大于N时,要进行回绕。回绕就是让(hashi+n)%N,即再从哈希表的前端开始查找
-
**第二种方法:开散列:**哈希桶/拉链法
思路:hashi存储的数据是一个节点,当哈希冲突时,将key都链接到hashi位置的节点下面
如下图
- 为了防止太多数据key链接到一个hashi存储位置存储的链下面,因此每个hashi存储位置的节点上除了指针,还有一个负载因子。当链接的key的数量大于负载因子时,会对哈希表进行扩容。
哈希桶的负载因子可以到1,实际上哈希桶解决哈希冲突时是当负载因子=1的时候进行扩容
- 为了防止太多数据key链接到一个hashi存储位置存储的链下面,因此每个hashi存储位置的节点上除了指针,还有一个负载因子。当链接的key的数量大于负载因子时,会对哈希表进行扩容。
扩容
无论是那种方法去解决哈希冲突,在实现时,哈希表都需要扩容,而哈希表通过负载因子/载荷因子对扩容进行控制。
-
负载因子/载荷因子: 负载因子和载荷因子是同一种东西的两种叫法而已
散列表的载荷因子=填入表中的元素个数/散列表的长度
上面的公式是数学公式,即计算出的结果应是小数,而不是取整。- 负载因子表示散列表装满程度的标志因子
由于表长是定值,负载因子与"填入表中的元素个数"成正比,所以,负载因子越大,表明填入表中的元素越多,空闲位置越少,因此产生冲突的可能性越大;反之,负载因子越小,产生冲突的可能性越小。
实际上,散列表的平均查找长度是负载因子的函数,只是不同处理冲突的方法有不同的函数- 如何通过负载因子来对扩容进行控制?
当负载因子达到一个数值时,我们进行扩容即可。
- 如何通过负载因子来对扩容进行控制?
- 对于开放定址法,负载因子是特别重要的因素,应严格限制在0.7 ~ 0.8以下。
超过0.8,查表时的CPU缓存不命中按照指数曲线上升。因此,一些采用开放定址法的hash库,当负载因子0.7 ~ 0.8时,就会对其扩容。 - 哈希桶的负载因子可以到1,实际上哈希桶解决哈希冲突时是当负载因子=1的时候进行扩容
- 负载因子表示散列表装满程度的标志因子
-
扩容后哈希表的映射关系会发生改变了
eg:扩容前N为10,那么key为16时,映射位置为6,然后根据某种规则进行插入数据。扩容后N为20,那么key为16时,映射位置为16,然后根据某种规则进行插入数据。
哈希表的代码实现
*下文的哈希表的实现,在哈希函数上采用除留余数法,然后分别用闭散列(即线性探测法),**开散列(即哈希桶)*来解决哈希冲突
线性探测法解决哈希冲突
-
数组中存储的数据的结构
数据应存储一个 pair<key,value> ,一个表示状态的标志
enum State {EXIST,EMPTY,DELETE }; template<class K , class V> struct HashNode {pair<K, V> _data;State _state;HashNode(const pair<K,V>& val = pair<K,V>()):_data(val),_state(EMPTY){} };
-
哈希表的结构
一个存储数据HashNode的数组,一个表示 已经填充的数据的个数的变量
template<class K , class V , class Hash = HashFunc<K>> class HashTable {typedef HashNode<K, V> Node; private:vector<Node> _table;size_t _n; public:HashTable():_table(10),_n(0){} };
-
接口
下文的接口包含:插入(Insert),查找(find),删除(erase)
-
Insert
bool Insert(const pair<K, V>& x) {if (find(x.first) != nullptr){return false;}//扩容if (_n * 10 / _table.size() >= 7){HashTable<K, V , Hash> newhash;newhash._table.resize(_table.size() * 2);for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newhash.Insert(_table[i]._data);}}_table.swap(newhash._table);}//插入Hash hs;size_t hashi = hs(x.first) % _table.size();while (_table[hashi]._state == EXIST){hashi = (hashi + 1) % _table.size();}_table[hashi] = x;_table[hashi]._state = EXIST;_n++;return true; }
-
find
Node* find(const K& key) {Hash hs;size_t hashi = hs(key) % _table.size();while (_table[hashi]._state != EMPTY){if (_table[hashi]._state == EXIST && _table[hashi]._data.first == key){return &(_table[hashi]);}hashi = (hashi + 1) % _table.size();}return nullptr; }
-
erase
bool erase(const K& key) {Node* e_node = find(key);if (e_node){e_node->_state = DELETE;_n--;return true;}return false; }
-
-
为了支持key为string类型或者其他无法直接强转为整形的类型,在HashTable的模板中设计了Hash类型,此类型是一个仿函数类型。
此处我提供了对于可以强转为整形的类型的仿函数,而对于string类型的仿函数是该仿函数的特化template<class T> struct HashFunc {size_t operator()(const T& key){return (size_t)key;} };template<> struct HashFunc<string> {size_t operator()(const string& s){size_t hashi = 0;for (auto& e : s){hashi *= 10;hashi += e;}return hashi;} };
-
完整代码
namespace open_address {enum State{EXIST,EMPTY,DELETE};template<class K , class V>struct HashNode{pair<K, V> _data;State _state;HashNode(const pair<K,V>& val = pair<K,V>()):_data(val),_state(EMPTY){}};template<class T>struct HashFunc{size_t operator()(const T& key){return (size_t)key;}};template<>struct HashFunc<string>{size_t operator()(const string& s){size_t hashi = 0;for (auto& e : s){hashi *= 10;hashi += e;}return hashi;}};template<class K , class V , class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;private:vector<Node> _table;size_t _n;public:HashTable():_table(10),_n(0){}bool Insert(const pair<K, V>& x){if (find(x.first) != nullptr){return false;}//扩容if (_n * 10 / _table.size() >= 7){HashTable<K, V , Hash> newhash;newhash._table.resize(_table.size() * 2);for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newhash.Insert(_table[i]._data);}}_table.swap(newhash._table);}//插入Hash hs;size_t hashi = hs(x.first) % _table.size();while (_table[hashi]._state == EXIST){hashi = (hashi + 1) % _table.size();}_table[hashi] = x;_table[hashi]._state = EXIST;_n++;return true;}Node* find(const K& key){Hash hs;size_t hashi = hs(key) % _table.size();while (_table[hashi]._state != EMPTY){if (_table[hashi]._state == EXIST && _table[hashi]._data.first == key){return &(_table[hashi]);}hashi = (hashi + 1) % _table.size();}return nullptr;}bool erase(const K& key){Node* e_node = find(key);if (e_node){e_node->_state = DELETE;_n--;return true;}return false;}};void Test1(){HashTable<int, int> hs;vector<int> a = { 12,21,24,56,74,28,29,81,23,22 };for (auto& e : a){hs.Insert({ e,e });}hs.Insert({ 66,66 });hs.Insert({ 66,67 });for (auto& e : a){cout << hs.find(e)->_data.first << ' ' << hs.find(e)->_data.second << endl;}}void Test2(){HashTable<string, string> hs;hs.Insert({ "abcd","insert" });hs.Insert({ "aadd","find" });hs.Insert({ "adcb","erase" });cout << (hs.find("abcd"))->_data.first << ":" << (hs.find("abcd"))->_data.second << endl;cout << (hs.find("aadd"))->_data.first << ":" << (hs.find("aadd"))->_data.second << endl;cout << (hs.find("adcb"))->_data.first << ":" << (hs.find("adcb"))->_data.second << endl;} }
哈希桶解决哈希冲突
-
数组中存储的数据的结构
存储的数据结构由一个pair<k,value>和一个指向该数据节点的指针组成
template<class K , class V> struct HashNode {pair<K, V> _data;HashNode<K, V>* _next;HashNode(const pair<K,V>& val = pair<K,V>()): _data(val), _next(nullptr){} };
-
哈希表的结构
哈希表由一个存储数据节点的指针的数组构成
template<class K , class V, class Hash = HashFunc<K>> class HashTable {typedef HashNode<K, V> Node; private:vector<Node*> _table;size_t _n; public:HashTable():_table(10, nullptr), _n(10){}~HashTable(){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;}} };
-
接口
下文的接口包括:插入(Insert),查找(find),删除(erase)
-
Insert
此处扩容不使用线性探测法中扩容的方法,因为如果使用的话,在每次扩容时,都需要将之前的数据节点进行delete,然后重新new相同数量的节点,显然这种做法会使得插入的效率很低。
因此此处扩容是将之前new出来的节点,在扩容后的数组中通过映射关系重新找到对应的存储位置,然后将之前的节点链接到对应的位置。最后将两个数组进行交换
bool Insert(const pair<K, V>& x) {if (find(x.first) != nullptr){return false;}Hash hs;//扩容if (_n * 10 / _table.size() == 1){vector<Node*> newtable(_table.size() * 2, nullptr);for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hashi = hs(cur->_data.first) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}}_table.swap(newtable);}size_t hashi = hs(x.first) % _table.size();Node* cur = new Node(x);cur->_next = _table[hashi];_table[hashi] = cur;_n++;return true; }
-
find
Node* find(const K& key) {Hash hs;size_t hashi = hs(key) % _table.size();Node* cur = _table[hashi];while (cur){if (cur->_data.first == key){return cur;}cur = cur->_next;}return nullptr; }
-
erase
bool erase(const K& key) {Hash hs;size_t hashi = hs(key) % _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (cur->_data.first == key){if (prev == nullptr){_table[hashi] = nullptr;}else{prev->_next = cur->_next;}delete cur;_n--;return true;}}return false; }
-
-
为了支持key为string类型或者其他无法直接强转为整形的类型,在HashTable的模板中设计了Hash类型,此类型是一个仿函数类型。
此处我提供了对于可以强转为整形的类型的仿函数,而对于string类型的仿函数是该仿函数的特化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 *= 31;hashi += e;}return hashi;} };
-
完整代码
namespace hash_bucket {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 *= 31;hashi += e;}return hashi;}};template<class K , class V>struct HashNode{pair<K, V> _data;HashNode<K, V>* _next;HashNode(const pair<K,V>& val = pair<K,V>()): _data(val), _next(nullptr){}};template<class K , class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;private:vector<Node*> _table;size_t _n;public:HashTable():_table(10, nullptr), _n(10){}bool Insert(const pair<K, V>& x){if (find(x.first) != nullptr){return false;}Hash hs;//扩容if (_n * 10 / _table.size() == 1){vector<Node*> newtable(_table.size() * 2, nullptr);for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hashi = hs(cur->_data.first) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}}_table.swap(newtable);}size_t hashi = hs(x.first) % _table.size();Node* cur = new Node(x);cur->_next = _table[hashi];_table[hashi] = cur;_n++;return true;}Node* find(const K& key){Hash hs;size_t hashi = hs(key) % _table.size();Node* cur = _table[hashi];while (cur){if (cur->_data.first == key){return cur;}cur = cur->_next;}return nullptr;}bool erase(const K& key){Hash hs;size_t hashi = hs(key) % _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (cur->_data.first == key){if (prev == nullptr){_table[hashi] = nullptr;}else{prev->_next = cur->_next;}delete cur;_n--;return true;}}return false;}~HashTable(){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;}}};void Test1(){HashTable<int, int> hs;vector<int> a = { 12,21,24,56,74,28,29,81,23,22 };for (auto& e : a){hs.Insert({ e,e });}hs.Insert({ 66,66 });hs.Insert({ 66,67 });for (auto& e : a){cout << hs.find(e)->_data.first << ' ' << hs.find(e)->_data.second << endl;}}void Test2(){HashTable<string, string> hs;hs.Insert({ "abcd","insert" });hs.Insert({ "aadd","find" });hs.Insert({ "adcb","erase" });cout << (hs.find("abcd"))->_data.first << ":" << (hs.find("abcd"))->_data.second << endl;cout << (hs.find("aadd"))->_data.first << ":" << (hs.find("aadd"))->_data.second << endl;cout << (hs.find("adcb"))->_data.first << ":" << (hs.find("adcb"))->_data.second << endl;} }