当前位置： 首页 > news >正文

【C++】哈希 Hash

news 2024/10/21 17:05:27

目录

一概念

二 哈希冲突解决

1 闭散列

a 线性探测

b 二次探测

2 开散列

3 闭散列和开散列比较 

三 Hash基础操作

1 unordered_map

2 unordered_set

四 Hash线性探测的模拟实现

五 Hash开散列模拟实现

1 HashTable.h

2 unordered_map.h

3 unordered_set .h

一概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O($log_2 N$)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素

当向该结构中

插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置 取元素比较，若关键码相等，则搜索成功 该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称 为哈希表(Hash Table)(或者称散列表)

查找的时间复杂度平均都是O(1)

哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

二 哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列 

1 闭散列

a 线性探测

b 二次探测

 二次探测的核心思想是在哈希冲突发生时，使用一个二次函数的增量来探测下一个位置。

 二次探测避免了线性探测中的一次聚集（Primary Clustering）问题，因为二次探测的探测序列是非线性的。

2 开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地 址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链 接起来，各链表的头结点存储在哈希表中。

3 闭散列和开散列比较 

应用链地址法(开散列)处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法(闭散列)必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

三 Hash基础操作

1 unordered_map

1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。

2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。

3. 在内部, unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。

4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。

5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。

这里操作方法不一一赘述, 在前面的map和set章节已经讲解

2 unordered_set

四 Hash线性探测的模拟实现

#pragma once
namespace open_address
{//枚举enum State{EMPTY,EXIST,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY; // 标记};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 hash = 0;for (auto e : s){hash += e;hash *= 131;}return hash;}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public://为vector开空间HashTable(size_t size = 10){_tables.resize(size);}HashData<K, V>* Find(const K& key){Hash hs;// 线性探测size_t hashi = hs(key) % _tables.size();while (_tables[hashi]._state != EMPTY){if (key == _tables[hashi]._kv.first&& _tables[hashi]._state == EXIST){return &_tables[hashi];}++hashi;hashi %= _tables.size();// 如果hashi == size 给它归零}return nullptr;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 扩容的问题//if ((double)_n / (double)_tables.size() >= 0.7)if (_n * 10 / _tables.size() >= 7){//size_t newSize = _tables.size() * 2;//vector<HashData> newTables(newSize);遍历旧表，映射到新表....//_tables.swap(newTables);HashTable<K, V, Hash> newHT(_tables.size() * 2);// 遍历旧表，插入到新表for (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}Hash hs;// 线性探测size_t hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){++hashi;hashi %= _tables.size();// 加到尾部了 就回到头部位置}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){_n--;ret->_state = DELETE;return true;}else{return false;}}private:vector<HashData<K, V>> _tables;size_t _n = 0;};void TestHT1(){cout << "Test1: " << endl;int a[] = { 1,4,24,34,7,44,17,37 };HashTable<int, int> ht;for (auto e : a){ht.Insert(make_pair(e, e));}for (auto e : a){auto ret = ht.Find(e);if (ret){cout << ret->_kv.first << ":E" << endl;}else{cout << ret->_kv.first << ":D" << endl;}}cout << endl;ht.Erase(34);ht.Erase(4);for (auto e : a){auto ret = ht.Find(e);if (ret){cout << ret->_kv.first << ":E" << endl;}else{cout << e << ":D" << endl;}}cout << endl;}void TestHT2(){HashTable<string, string> dict;dict.Insert(make_pair("sort", "排序"));dict.Insert(make_pair("string", "字符串"));auto kv = dict.Find("sort");cout << "Test2: " << endl;cout << kv->_kv.first << " " << kv->_kv.second << endl;}
}

 

五 Hash开散列模拟实现

1 HashTable.h

#pragma once
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 hash = 0;for (auto e : s){hash += e;hash *= 131;}return hash;}
};
namespace hash_bucket
{// T -> K// T -> pair<K, V>template<class T>struct HashNode{HashNode<T>* _next;T _data;HashNode(const T& data):_next(nullptr), _data(data){}};// 前置声明template<class K, class T, class KeyOfT, class Hash>class HashTable;template<class K, class T, class KeyOfT, class Hash>struct __HTIterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HTIterator<K, T, KeyOfT, Hash> Self;Node* _node;HT* _ht;__HTIterator(Node* node, HT* ht):_node(node), _ht(ht){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){if (_node->_next){// 当前桶还是节点_node = _node->_next;}else{// 当前桶走完了，找下一个桶KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) %_ht->_tables.size();// 找下一个桶hashi++;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}hashi++;}// 后面没有桶了if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}bool operator!=(const Self& s){return _node != s._node;}};template<class K, class T, class KeyOfT, class Hash>class HashTable{template<class K, class T, class KeyOfT, class Hash>friend struct __HTIterator;typedef HashNode<T> Node;public:typedef __HTIterator<K, T, KeyOfT, Hash> iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); i++){// 找到第一个桶的第一个节点if (_tables[i]){return iterator(_tables[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}HashTable(){_tables.resize(10, nullptr);_n = 0;}~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;}}pair<iterator, bool> Insert(const T& data){KeyOfT kot;iterator it = Find(kot(data));if (it != end())return make_pair(it, false);Hash hs;// 负载因子到1就扩容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 = hs(kot(cur->_data)) %newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), true);}iterator Find(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return iterator(nullptr, this);}bool Erase(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){// 删除if (prev){prev->_next = cur->_next;}else{_tables[hashi] = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables; // 指针数组size_t _n;};
}

2 unordered_map.h

#pragma once
#pragma once
#include"HashTable.h"namespace yf
{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;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}bool erase(const K& key){return _ht.Erase(key);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}iterator find(const K& key){return _ht.Find(key);}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};void test_map1(){unordered_map<string, string> dict;dict.insert(make_pair("sort", "grve"));dict.insert(make_pair("left", "egar"));dict.insert(make_pair("right", "jmh"));for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}cout << "Test erase" << endl;dict.erase("sort");for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}}
}

3 unordered_set .h

#pragma once
#pragma once
#include"HashTable.h"namespace yf
{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;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;};void test_set1(){unordered_set<int> us;us.insert(3);us.insert(1);us.insert(5);us.insert(15);us.insert(45);us.insert(7);unordered_set<int>::iterator it = us.begin();while (it != us.end()){//*it += 100;cout << *it << " ";++it;}cout << endl;for (auto e : us){cout << e << " ";}cout << endl;}}

总结: hash是很重要的数据结构, 理解原理和底层实现更为重要.  继续加油!


http://www.mrgr.cn/news/55351.html

相关文章：

  • 【STM32学习】PWM学习（四），散热风扇的控制，PWM调速调制，
  • 图像编辑大一统？多功能图像编辑框架Dedit:可基于图像、文本和掩码进行图像编辑。
  • 如何检查前端项目和 Node 项目中未被使用的依赖包
  • Vim使用与进阶
  • 解决IntelliJ IDEA启动失败的完整指南
  • c语言基础程序——经典100道实例。
  • 私域电商新纪元：消费增值模式引领业绩飞跃
  • stable diffusion WEBUI Brief summary
  • MATLAB深度学习工具箱——建议收藏！
  • CMA软件评测机构内部审核核查点清单，如何选择内审方法？
  • 本地和远程服务器连接
  • 什么是孤独症患者的表现？洞悉内心，感知世界的独特视角
  • 智慧型软件项目可行性研究报告模板案例（Word原件）
  • 雷池WAF自动化实现安全运营实操案例终极篇
  • 根据日志优化微调
  • 解决方案 | 系统开发更简单：TOSUN新能源汽车测试解决方案
  • SSH免密登录
  • 基于华为云CodeArts Repo和流水线门禁的分支合并与部署
  • 一起发现CMake太美-05-开启CMake之旅-模块化
  • 有同学问：拿到大厂JAVA OFFER，但是会不会不稳定，有失业风险？！
  • 【精准预测比分2-1】周一002 亚冠 多哈萨德VS波斯波利，拿捏主任 剧本已出 坐享其成
  • 十分钟安装部署大模型ChatGML-6B
  • 搭建分布式系统时通常要考虑的问题
  • HTTPS证书生成、验签-、证书链
  • 复杂形状微型零件超高精度加工，试试这款微纳加工中心
  • n9e categraf