C++哈希

article/2025/8/26 10:21:37

一.哈希概念

哈希又叫做散列。本质就是通过哈希函数把关键字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.hkcw.cn/article/OaGhwoUCjH.shtml

相关文章

Java中的设计模式实战：单例、工厂、策略模式的最佳实践

Java中的设计模式实战：单例、工厂、策略模式的最佳实践

Java中的设计模式实战&#xff1a;单例、工厂、策略模式的最佳实践 在Java开发中&#xff0c;设计模式是构建高效、可维护、可扩展应用程序的关键。本文将深入探讨三种常见且实用的设计模式&#xff1a;单例模式、工厂模式和策略模式&#xff0c;并通过详细代码实例&#xff0…
阅读更多...
QT6搭建和使用MQTT

QT6搭建和使用MQTT

QT6搭建和使用MQTT 1.搭建MQTT环境1.下载源码2.CMake 编译 Qt MQTT 模块3.添加QT MQTT模块4.验证测试 2.MQTT的使用 1.搭建MQTT环境 1.下载源码 1.在GitHub下载对应qt版本的源码 git clone git://code.qt.io/qt/qtmqtt.git -b 6.5.3 这里以6.5.3版本的为例。 这里使用的是VS…
阅读更多...
深入了解 C# 异步编程库 AsyncEx

深入了解 C# 异步编程库 AsyncEx

在现代应用程序开发中&#xff0c;异步编程已经成为提升性能和响应能力的关键&#xff0c;尤其在处理网络请求、I/O 操作和其他耗时任务时&#xff0c;异步编程可以有效避免阻塞主线程&#xff0c;提升程序的响应速度和并发处理能力。C# 提供了内建的异步编程支持&#xff08;通…
阅读更多...
使用 Azure DevOps 管道部署到本地服务器

使用 Azure DevOps 管道部署到本地服务器

Azure DevOps 是一个帮助改进 SDLC（软件开发生命周期）的平台。 在本文中，我们将使用 Azure Pipelines 创建自动化部署。 Azure DevOps 团队将 Azure Pipelines 定义为“使用 CI/CD 构建、测试和部署，适用于任何语言、平台和云平台”。 在这里，我将解释如何在 Azure Dev…
阅读更多...
NSSCTF-[青海民族大学 2025 新生赛]wenshilou

NSSCTF-[青海民族大学 2025 新生赛]wenshilou

下载附件得到jpeg图片 放到kali里面用binwalk命令进行分离 分离之后得到文件 点击zip文件里面有个flag&#xff0c;打开得到base64编码 直接放到随波逐流里面解码 得到flag NSSCTF{welcometoQinhaiminzudaxue}
阅读更多...
React 编译器

React 编译器

&#x1f916; 作者简介&#xff1a;水煮白菜王&#xff0c;一位前端劝退师 &#x1f47b; &#x1f440; 文章专栏&#xff1a; 前端专栏 &#xff0c;记录一下平时在博客写作中&#xff0c;总结出的一些开发技巧和知识归纳总结✍。 感谢支持&#x1f495;&#x1f495;&#…
阅读更多...
【机器学习基础】机器学习入门核心算法：K均值（K-Means）

【机器学习基础】机器学习入门核心算法：K均值（K-Means）

机器学习入门核心算法&#xff1a;K均值&#xff08;K-Means&#xff09; 1. 算法逻辑2. 算法原理与数学推导2.1 目标函数2.2 数学推导2.3 时间复杂度 3. 模型评估内部评估指标外部评估指标&#xff08;需真实标签&#xff09; 4. 应用案例4.1 客户细分4.2 图像压缩4.3 文档聚类…
阅读更多...
力扣热题100之二叉树的最大深度

力扣热题100之二叉树的最大深度

题目 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 代码 方法一&#xff1a;递归 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightN…
阅读更多...
【C++编程】C++学习笔记【更新ing】

【C++编程】C++学习笔记【更新ing】

C学习笔记 作者&#xff1a;齐花Guyc(CAUC) 文章目录 C学习笔记Chapter.1 面向对象编程&#xff08;OOP&#xff09;1.类&#xff08;class&#xff09;2.对象&#xff08;object&#xff09;3.封装&#xff08;Encapsulation&#xff09;4.继承&#xff08;Inheritance&#…
阅读更多...
华为OD机试真题——矩形相交的面积（2025A卷：100分）Java/python/JavaScript/C/C++/GO最佳实现

华为OD机试真题——矩形相交的面积（2025A卷：100分）Java/python/JavaScript/C/C++/GO最佳实现

2025 A卷 100分 题型 本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式； 并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析； 本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分…
阅读更多...
STM32F407VET6学习笔记7：Bootloader跳转APP程序

STM32F407VET6学习笔记7：Bootloader跳转APP程序

boot跳转APP的程序 目录 Flash分区设定&#xff1a; 工程文件地址设置&#xff1a; Bootloader工程文件&#xff1a; 测试的APP程序工程文件&#xff1a; Bootloader跳转程序&#xff1a; APP程序&#xff1a; Flash分区设定&#xff1a; 参考手册的分区&#xff1a; 工程文件…
阅读更多...
5.29 打卡

5.29 打卡

DAY 39 图像数据与显存 知识点回顾 图像数据的格式&#xff1a;灰度和彩色数据模型的定义显存占用的4种地方 模型参数梯度参数优化器参数数据批量所占显存神经元输出中间状态 batchisize和训练的关系 作业&#xff1a;今日代码较少&#xff0c;理解内容即可 # 打印一张彩色图像…
阅读更多...
关于scrapy在pycharm中run可以运行，但是debug不行的问题

关于scrapy在pycharm中run可以运行，但是debug不行的问题

关于scrapy在pycharm中run模式可以运行&#xff0c;但是debug模式不行的问题 文章目录 关于scrapy在pycharm中run模式可以运行&#xff0c;但是debug模式不行的问题查了下原因 点击run就可以运行&#xff0c;但是debug就是运行不了 一点击debug就报这个错&#xff0c;也不知道啥…
阅读更多...
第7讲、Odoo 18 源码深度分析

第7讲、Odoo 18 源码深度分析

Odoo 作为全球知名的开源 ERP 系统&#xff0c;其底层架构由众多核心 Python 文件共同支撑。本文将围绕 Odoo 18 版本中 的 api.py、exceptions.py、fields.py、http.py、loglevels.py、models.py、netsvc.py、release.py、sql_db.py 等关键文件&#xff0c;进行源码结构与实现…
阅读更多...
【春秋云镜】CVE-2022-26965 靶场writeup

【春秋云镜】CVE-2022-26965 靶场writeup

知识点 网站的主题或者模块位置一般是可以上传文件的&#xff0c;不过一般为压缩包形式主题或者模块可以上github上找到和cms匹配的源码主题被解压后会放到加入到对应的文件夹中&#xff0c;而且还会自动执行对应的info.php文件(需要主题和cms配套才行)我这里取巧了&#xff0…
阅读更多...
JUC多线程核心知识点深度解析

JUC多线程核心知识点深度解析

最近正在复习Java八股&#xff0c;所以会将一些热门的八股问题&#xff0c;结合ai与自身理解写成博客便于记忆 本文将从以上10个经典面试问题来做juc多线程的解析 一、线程状态与流转机制 1. 六种线程状态&#xff08;Java定义&#xff09; public enum State {NEW, …
阅读更多...
设计模式学习笔记

设计模式学习笔记

设计模式 一&#xff1a;分类&#xff1a; 创建型模式 用于描述“怎样创建对象”&#xff0c;它的主要特点是“将对象的创建与使用分离”。GoF&#xff08;四人组&#xff09;书中提供了单例、原型、工厂方法、抽象工厂、建造者等 5 种创建型模式。 结构型模式 用于描述如何将…
阅读更多...
【地图】腾讯地图页面卡顿问题解决

【地图】腾讯地图页面卡顿问题解决

目录 背景问题排查解决1. 页面是否使用 keep-alive 进行路由缓存2. 离开地图页面时&#xff0c;是否将地图清除 总结 背景 有的电脑没有显卡会出现如下问题&#xff1a; 系统打开有地图的页面&#xff0c;CPU 占用直线飙升到100%下不来&#xff0c;切到非地图页面&#xff0c;C…
阅读更多...
一起看 I/O | Android 性能相关最新动态

一起看 I/O | Android 性能相关最新动态

作者 / Ben Weiss 过去几年来&#xff0c;我们一直致力于让性能提升工作变得更易上手、回报更高。我们将在本文中分享这一领域的最新发展动态。为您介绍基准配置文件、Android Studio 中的工具改进、库&#xff0c;以及我们如何让这项技术更好地在后台为您服务。此外&#xff0…
阅读更多...
iPhone批量删除照片的方法

iPhone批量删除照片的方法

对于每一个iPhone用户来说&#xff0c;照片管理是一项日常而重要的任务。随着时间的积累&#xff0c;无数的照片快速填满了我们的存储空间&#xff0c;从美丽的风景到重要的家庭聚会&#xff0c;每一张照片都记录着我们生活中的瞬间。然而&#xff0c;当存储空间即将耗尽时&…
阅读更多...
推荐文章

Copyright @ 2022~2023