C++哈希

一.哈希概念

哈希又叫做散列。本质就是通过哈希函数把关键字key和存储位置建立映射关系，查找时通过这个哈希函数计算出key存储的位置，进行快速查找。

上述概念可能不那么好懂，下面的例子可以辅助我们理解。

无论是数组还是链表，查找一个数都需要通过遍历的方式，假设用单向查找最坏的情况就是查找n次，假设双向查找最坏的情况是查找n/2次，在数据量很大的情况下查找一个数就变得比较困难。最好的情况就是希望一下子就可以找到目标数字，由此出现了哈希表。

什么是映射关系？

映射关系分为两种：一对一和一对多

一对一：假设有2 3 90 100这四个数据，那我就开100个空间，将每一个数存在对应下标的位置，这样查找数据的时候一下子就找到了。

一对一的弊端十分明显，就是当数据较为分散，例如存储1和1001，那就要开辟1001个空间，十分浪费。那么一对多的存储就会比较好。

一对多：就是一个空间对应着多个数据。按照概念存储数据的时候肯定会产生冲突，这就是哈希冲突。

二.除法散列法

针对冲突的情况可以用除法散列法来解决。顾名思义，假设哈希表大小为M，那么通过Key除以M的余数作为映射位置下标，也就是哈希函数为：h(key)=key%M

例如：假设数字为12，哈希表大小为10

12/10的余数是2，那么就将12映射到2的位置，但是如果还要存储32这个数据，不难发现32/10的余数仍然是2于是就产生了冲突，那该怎么解决呢？

2.1线性探测

从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则绕回到哈希表头的位置。

就像上面的例子，12已经映射到2的位置，那么32就需要向后线性探测，假如下标为3的位置没有数据存储 那么就将32存储到下标为3的位置。

我们最初的目标就是避免遍历，那如果数据一直冲突的话也就无法解决这个问题了，很简单通过扩容就可以解决这个问题。

2.1.1哈希因子

说到扩容就不得不提到哈希因子了，哈希因子就是有效数据个数/哈希表大小。

例如数据个数为2，哈希表大小为10，那么哈希因子就是0.2，一般来说当哈希因子到0.7时就需要开始扩容了。

2.1.2哈希桶

有时候扩容仍然无法解决冲突的问题，那么哈希桶就很好解决了这个问题。

哈希桶概念：哈希表中存储一个指针，当没有数据映射到这个位置时，这个指针为空；有多个数据映射到这个位置时，把冲突的数据连接成一个链表，挂在哈希表这个位置下面。

哈希桶的扩容：

 // 扩容函数void Resize() {size_t newSize = _tables.size() * 2;vector<Node*> newTables(newSize, nullptr);KeyOfT kot;Hash hs;// 重新哈希所有元素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)) % newSize;cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}}_tables.swap(newTables);}

 代码中出现KeyOfT是因为set和map取出key方式不一样，set可以直接取出key而map需要从pair中取出。

三.key不是整数的情况 

在计算位置的时候需要用到key来除以哈希表大小，当key不为整数时分两种情况：

  • double等可以直接强制类型转换为int
  • string不能强制类型转换成int
template<class K>
struct HashFunc {size_t operator()(const K& key) {return (size_t)key; // 默认实现：适用于整数类型}
};// 字符串类型特化
template<>
struct HashFunc<string> {size_t operator()(const string& key) {size_t hash = 0;for (char c : key) {hash = hash * 131 + c; // 使用BKDR哈希算法处理字符串}return hash;}
};

完整代码：

#pragma once
#include<vector>
#include<iostream>
using namespace std;
// 通用哈希函数模板（默认使用类型转换）
template<class K>
struct HashFunc {size_t operator()(const K& key) {return (size_t)key; // 默认实现：适用于整数类型}
};// 字符串类型特化
template<>
struct HashFunc<string> {size_t operator()(const string& key) {size_t hash = 0;for (char c : key) {hash = hash * 131 + c; // 使用BKDR哈希算法处理字符串}return hash;}
};
namespace hash_bucket {template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>class HashTable {typedef HashNode<T> Node;public:// 构造函数HashTable() {_tables.resize(10, nullptr);}// 析构函数：释放所有节点内存~HashTable() {for (auto& bucket : _tables) {Node* cur = bucket;while (cur) {Node* next = cur->_next;delete cur;cur = next;}bucket = nullptr;}_n = 0;}// 插入元素bool Insert(const T& data) {KeyOfT kot;Hash hs;const K& key = kot(data); // 提取键// 检查键是否已存在if (Find(key)) return false;// 负载因子超过1时扩容if (_n >= _tables.size()) {Resize();}// 计算哈希值并插入size_t hashi = hs(key) % _tables.size();Node* newNode = new Node(data);newNode->_next = _tables[hashi];_tables[hashi] = newNode;++_n;return true;}// 查找元素bool Find(const K& key) {Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur) {if (kot(cur->_data) == key) {return true;}cur = cur->_next;}return false;}// 删除元素bool Erase(const K& key) {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 == nullptr) {_tables[hashi] = cur->_next;}else {prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:// 扩容函数void Resize() {size_t newSize = _tables.size() * 2;vector<Node*> newTables(newSize, nullptr);KeyOfT kot;Hash hs;// 重新哈希所有元素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)) % newSize;cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}}_tables.swap(newTables);}private:vector<Node*> _tables;size_t _n = 0;};} // namespace hash_bucket

四.unordered_set和unordered_map的封装

1.unordered_set

#define _CRT_SECURE_NO_WARNINGS
#include"hashi.h"
namespace happy
{template<class K>class unorder_set{struct SetKeyOfT{ const K& operator()(const K& key) {return key;}};public://取类模板的内嵌类型需要typenametypedef typename hash_bucket::HashTable<K, const K, SetKeyOfT>::Iterator iterator;typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT>::const_Iterator Citerator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}Citerator begin()const{return _ht.begin();}Citerator end()const{return _ht.end();}pair<iterator,bool> insert(const K& key){return _ht.Insert(key);}private:hash_bucket::HashTable<K, const K,SetKeyOfT> _ht;};void print(const unorder_set<int>& s){unorder_set<int>::Citerator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}
}

2.unordered_map

#pragma once
#include"hashi.h"
#include <utility> // pair
#include <iostream>
using namespace std;
namespace happy
{template<class K, class V, class Hash = HashFunc<K>>class unorder_map{struct MapKeyOfT{const K& operator() (const pair<const K, V>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, 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();}pair<iterator, bool> insert(const pair<const K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert({ key, V() });return ret.first->second;}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};void test_unordered_map(){unorder_map<string, string> dict;dict.insert({ "string", "字符串" });dict.insert({ "left", "左边" });unorder_map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;// 测试 operator[]dict["right"] = "右边";cout << "dict[\"right\"]: " << dict["right"] << endl;}
}

3.hashi 

#pragma once
#include<vector>
#include<iostream>
using namespace std;
// 通用哈希函数模板（默认使用类型转换）
template<class K>
struct HashFunc {size_t operator()(const K& key) {return (size_t)key; // 默认实现：适用于整数类型}
};// 字符串类型特化
template<>
struct HashFunc<string> {size_t operator()(const string& key) {size_t hash = 0;for (char c : key) {hash = hash * 131 + c; // 使用BKDR哈希算法处理字符串}return hash;}
};
namespace hash_bucket {template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K, class T, class KeyOfT, class Hash >class HashTable;template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash = HashFunc<K>>struct HTIterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef HTIterator<K, T,Ref,Ptr, KeyOfT, Hash> iterator;Node* _node;//结点指针const HT* _ht;//哈希表指针HTIterator(Node*node,const HT*ht):_node(node),_ht(ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const iterator& s){return _node != s._node;}bool operator==(const iterator& s){return _node == s._node;}iterator& 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;}else{++hashi;}}//所有桶走完if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}};template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>class HashTable {typedef HashNode<T> Node;//友元声明template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash >friend struct HTIterator;public:typedef HTIterator<K, T,T&,T*, KeyOfT, Hash> Iterator;typedef HTIterator<K, T,const T&,const T*, KeyOfT, Hash> const_Iterator;Iterator begin(){for (size_t hashi = 0; hashi < _tables.size(); hashi++){if (_tables[hashi]){return Iterator(_tables[hashi],this);}}return end();}Iterator end(){return Iterator(nullptr, this);}const_Iterator begin()const{for (size_t hashi = 0; hashi < _tables.size(); hashi++){if (_tables[hashi]){return const_Iterator(_tables[hashi], this);}}return end();}const_Iterator end()const{return const_Iterator(nullptr, this);}// 构造函数HashTable() {_tables.resize(10, nullptr);}// 析构函数：释放所有节点内存~HashTable() {for (auto& bucket : _tables) {Node* cur = bucket;while (cur) {Node* next = cur->_next;delete cur;cur = next;}bucket = nullptr;}_n = 0;}// 插入元素pair<Iterator,bool> Insert(const T& data) {KeyOfT kot;Hash hs;Iterator it = Find(kot(data));const K& key = kot(data); // 提取键// 检查键是否已存在if (it != end()) return { it,false };// 负载因子超过1时扩容if (_n >= _tables.size()) {Resize();}// 计算哈希值并插入size_t hashi = hs(key) % _tables.size();Node* newNode = new Node(data);newNode->_next = _tables[hashi];_tables[hashi] = newNode;++_n;return { {newNode,this},true };}// 查找元素Iterator Find(const K& key) {Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur) {if (kot(cur->_data) == key) {return Iterator(cur, nullptr);}cur = cur->_next;}return end();}// 删除元素bool Erase(const K& key) {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 == nullptr) {_tables[hashi] = cur->_next;}else {prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:// 扩容函数void Resize() {size_t newSize = _tables.size() * 2;vector<Node*> newTables(newSize, nullptr);KeyOfT kot;Hash hs;// 重新哈希所有元素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)) % newSize;cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}}_tables.swap(newTables);}private:vector<Node*> _tables;size_t _n = 0;};} // namespace hash_bucket

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.pswp.cn/pingmian/82912.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

iOS 使用CocoaPods 添加Alamofire 提示错误的问题

iOS 使用CocoaPods 添加Alamofire 提示错误的问题

Sandbox: rsync(59817) deny(1) file-write-create /Users/aaa/Library/Developer/Xcode/DerivedData/myApp-bpwnzikesjzmbadkbokxllvexrrl/Build/Products/Debug-iphoneos/myApp.app/Frameworks/Alamofire.framework/Alamofire.bundle把这个改成 no 2 设置配置文件
阅读更多...
mysql的Memory引擎的深入了解

mysql的Memory引擎的深入了解

目录 1、Memory引擎介绍 2、Memory内存结构 3、内存表的锁 4、持久化 5、优缺点 6、应用 前言 Memory 存储引擎 是 MySQL 中一种高性能但非持久化的存储方案&#xff0c;适合临时数据存储和缓存场景。其核心优势在于极快的读写速度&#xff0c;需注意数据丢失风险和内存占…
阅读更多...
若依项目AI 助手代码解析

若依项目AI 助手代码解析

基于 Vue.js 和 Element UI 的 AI 助手组件 一、组件整体结构 这个 AI 助手组件由三部分组成&#xff1a; 悬浮按钮&#xff1a;点击后展开 / 收起对话窗口对话窗口&#xff1a;显示历史消息和输入框API 调用逻辑&#xff1a;与 AI 服务通信并处理响应 <template><…
阅读更多...
Vue2的diff算法

Vue2的diff算法

diff算法的目的是为了找出需要更新的节点&#xff0c;而未变化的节点则可以复用 新旧列表的头尾先互相比较。未找到可复用则开始遍历&#xff0c;对比过程中指针逐渐向列表中间靠拢&#xff0c;直到遍历完其中一个列表 具体策略如下&#xff1a; 同层级比较 Vue2的diff算法只…
阅读更多...
mongodb集群之分片集群

mongodb集群之分片集群

目录 1. 适用场景2. 集群搭建如何搭建搭建实例Linux搭建实例(待定)Windows搭建实例1.资源规划2. 配置conf文件3. 按顺序启动不同角色的mongodb实例4. 初始化config、shard集群信息5. 通过router进行分片配置 1. 适用场景 数据量大影响性能 数据量大概达到千万级或亿级的时候&…
阅读更多...
DEEPSEEK帮写的STM32消息流函数，直接可用.已经测试

DEEPSEEK帮写的STM32消息流函数，直接可用.已经测试

#include "main.h" #include "MessageBuffer.h"static RingBuffer msgQueue {0};// 初始化队列 void InitQueue(void) {msgQueue.head 0;msgQueue.tail 0;msgQueue.count 0; }// 检查队列状态 type_usart_queue_status GetQueueStatus(void) {if (msgQ…
阅读更多...
华为欧拉系统中部署FTP服务与Filestash应用：实现高效文件管理和共享

华为欧拉系统中部署FTP服务与Filestash应用：实现高效文件管理和共享

华为欧拉系统中部署FTP服务与Filestash应用：实现高效文件管理和共享 前言一、相关服务介绍1.1 Huawei Cloud EulerOS介绍1.2 Filestash介绍1.3 华为云Flexus应用服务器L实例介绍二、本次实践介绍2.1 本次实践介绍2.2 本次环境规划三、检查云服务器环境3.1 登录华为云3.2 SSH远…
阅读更多...
React---day5

React---day5

4、React的组件化 组件的分类&#xff1a; 根据组件的定义方式&#xff0c;可以分为&#xff1a;函数组件(Functional Component )和类组件(Class Component)&#xff1b;根据组件内部是否有状态需要维护&#xff0c;可以分成&#xff1a;无状态组件(Stateless Component )和…
阅读更多...
测试策略：AI模型接口的单元测试与稳定性测试

测试策略：AI模型接口的单元测试与稳定性测试

测试策略：AI模型接口的单元测试与稳定性测试 在构建支持AI能力的系统中，开发者不仅要关注业务逻辑的正确性，也必须保障AI模型接口在各种环境下都能稳定运行。这就要求我们在开发阶段制定清晰的测试策略，从功能验证到性能保障，逐步推进系统可用性、可维护性与可扩展性的提…
阅读更多...
UniApp 生产批次管理模块技术文档

UniApp 生产批次管理模块技术文档

UniApp 生产批次管理模块技术文档 1. 运行卡入站页面 (RunCardIn) 1.1 页面结构 <template><!-- 页面容器 --><view class"runCardIn" :style"{ paddingTop: padding }"><!-- 页头组件 --><pageHeader :title"$t(MENU:…
阅读更多...
针对Helsinki-NLP/opus-mt-zh-en模型进行双向互翻的微调

针对Helsinki-NLP/opus-mt-zh-en模型进行双向互翻的微调

引言  题目听起来有点怪怪的&#xff0c;但是实际上就是对Helsinki-NLP/opus-mt-en-es模型进行微调。但是这个模型是单向的&#xff0c;只支持中到英的翻译&#xff0c;反之则不行。这样的话&#xff0c;如果要做中英双向互翻就需要两个模型&#xff0c;那模型体积直接大了两倍…
阅读更多...
Object转Map集合

Object转Map集合

对象与 Map 转换详解&#xff1a; Object.entries() 和 Object.fromEntries() 1&#xff0c;Object.fromEntries() 的主要用途就是将键值对集合&#xff08;如 Map&#xff09;转换为普通对象。 2&#xff0c;Object.entries() 返回一个二维数组&#xff0c;其中每个子数组包…
阅读更多...
优先队列用法

优先队列用法

第 5 行定义了一个队首是最大值的优先队列,第 10 行的输出如下: 27 - wuhan 21 - shanghai 11 - beijing 第 13 行定义了一个队首是最小值的优先队列,第 19 行的输出如下: 11 - beijing 21 - shanghai 27 - wuhan #include <bits/stdc.h> using namespace std; int…
阅读更多...
Spring Boot3.4.1 集成redis

Spring Boot3.4.1 集成redis

Spring Boot3.4.1 集成redis 第一步 引入依赖 <!-- redis 缓存操作 --> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId> </dependency> <!-- pool 对象池 …
阅读更多...
Replacing iptables with eBPF in Kubernetes with Cilium

Replacing iptables with eBPF in Kubernetes with Cilium

source: https://archive.fosdem.org/2020/schedule/event/replacing_iptables_with_ebpf/attachments/slides/3622/export/events/attachments/replacing_iptables_with_ebpf/slides/3622/Cilium_FOSDEM_2020.pdf 使用Cilium&#xff0c;结合eBPF、Envoy、Istio和Hubble等技术…
阅读更多...
英一真题阅读单词笔记 05年

英一真题阅读单词笔记 05年

2005 年 Text 1 第一段 序号 单词 音标 词义 1 fat [ft] a. 丰厚的&#xff0c;巨额的&#xff1b;肥胖的 2 pay [peɪ] n. 薪水 3 rise [raɪz] n. 上涨&#xff0c;增加&#xff1b;斜坡 4 pleasure [pleʒə(r)] n. 快乐&#xff1b;乐事 5 pleasure a…
阅读更多...
FastAPI集成APsecheduler的BackgroundScheduler+mongodb(精简)

FastAPI集成APsecheduler的BackgroundScheduler+mongodb(精简)

项目架构&#xff1a; FastAPI(folder) >app(folder) >core(folder) >models(folder) >routers(folder) >utils(folder) main.py(file) 1 utils文件夹下新建schedulers.py from apscheduler.schedulers.background import BackgroundScheduler from apschedu…
阅读更多...
聊一聊接口测试中耗时请求如何合理安排？

聊一聊接口测试中耗时请求如何合理安排？

目录 一、异步处理与轮询机制 轮询检查机制 二、 并行化测试执行 三、模拟与桩技术&#xff08;Mock/Stub&#xff09; 四、动态超时与重试策略 五、测试架构设计优化 分层测试策略 并行化执行 网络优化 六、测试用例分层管理 金字塔策略 七、 缓存与数据复用 响应…
阅读更多...
深入详解DICOMweb：WADO与STOW-RS的技术解析与实现

深入详解DICOMweb：WADO与STOW-RS的技术解析与实现

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家、CSDN平台优质创作者&#xff0c;高级开发工程师&#xff0c;数学专业&#xff0c;10年以上C/C, C#, Java等多种编程语言开发经验&#xff0c;拥有高级工程师证书&#xff1b;擅长C/C、C#等开发语言&#xff0c;熟悉Java常用开…
阅读更多...
Splunk Validated Architecture (SVA)：构建企业级可观测性与安全的基石

Splunk Validated Architecture (SVA)：构建企业级可观测性与安全的基石

Splunk Validated Architecture (SVA) 是 Splunk 官方提供的一套经过严格测试、性能验证和最佳实践指导的参考架构蓝图。它并非单一固定方案&#xff0c;而是根据企业数据规模、性能需求、高可用性目标和合规要求&#xff0c;提供一系列可落地的部署模型。SVA 的核心价值在于为…
阅读更多...
最新文章

Copyright @ 2022~2023