C++哈希（链地址法）（二）详解

文章目录

  • 1.开放地址法
    • 1.1key不能取模的问题
      • 1.1.1将字符串转为整型
      • 1.1.2将日期类转为整型
  • 2.哈希函数
    • 2.1乘法散列法（了解）
    • 2.2全域散列法（了解）
  • 3.处理哈希冲突
    • 3.1线性探测（挨着找）
    • 3.2二次探测（跳跃着找）
    • 3.3双重散列（了解）
  • 4.链地址法
    • 4.1扩容
    • 4.2基本的框架
    • 4.3插入
    • 4.4查找
    • 4.5删除
  • 5.代码

1.开放地址法

1.1key不能取模的问题

当key是string/Date等类型时，key不能取模，那么我们需要给HashTable增加一个仿函数，这个仿函数支持把key转换成一个可以取模的整形，如果key可以转换为整形并且不容易冲突，那么这个仿函数就用默认参数即可，如果这个Key不能转换为整形，我们就需要自己实现一个仿函数传给这个参数，实现这个仿函数的要求就是尽量key的每个值都参与到计算中，让不同的key转换出的整形值不同。string做哈希表的key非常常见，所以我们可以考虑把string特化一下。

1.1.1将字符串转为整型

key如果是字符串，转为整形需要仿函数

// key / M , M哈希表的空间大小
size_t hash0 = hash(kv.first) % _tables.size();// 将key转为无符号的整形，因为key可能是负数
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 sum = 0;for (auto& ch : s){sum += ch;sum *= 131;// *131为了避免哈希冲突,每次的key都不一样}return sum;}
};int main()
{const char* a[] = { "abcd","def","gca" };HashTable<string, string> ha;// 类型+()是匿名对象// 哈希冲突了cout << HashFunc<string>()("abcd") << endl;cout << HashFunc<string>()("aadd") << endl;cout << HashFunc<string>()("acbd") << endl;for (auto& ch : a){ha.Insert({ ch,ch });}return 0;
}

1.1.2将日期类转为整型

struct Date
{int _year;int _month;int _day;Date(int year = 1,int month = 1,int day = 1):_year(year),_month(month),_day(day){}bool operator==(const Date& d){return _year == d._year&&_month == d._month&&_day == d._day;}
};struct DateHashFunc
{size_t operator()(const Date& d){size_t hash = 0;hash += d._year;hash *= 131;hash += d._month;hash *= 131;hash += d._day;hash *= 131;return hash;}
};int main()
{// 将日期类转化为整型HashTable<Date, int, DateHashFunc> ht;ht.Insert({ { 2024,12,10 }, 1 });ht.Insert({ { 2024,10,12 }, 1 });return 0;
}

2.哈希函数

设计哈希函数为了减少冲突，让更多的位参与运算，不管使用%不太接近2的幂次方的质数，还是用位运算计算都是可以的

2.1乘法散列法（了解）

  1. 乘法散列法对哈希表大小M没有要求，他的大思路第一步：用关键字 Key 乘上常数 A (0<A<1)，并抽
    取出 key * A 的小数部分。第二步：后再用M乘以key*A 的小数部分，再向下取整。
  2. h(key) = floor(M × ((A × key)%1.0)) ，其中floor表示对表达式进行下取整，A∈(0,1)，这里最重要的是A的值应该如何设定，Knuth认为 A = ( 5 − 1)/2 = 0.6180339887… (黄金分割点])比较好。
  3. 乘法散列法对哈希表大小M是没有要求的，假设M为1024，key为1234，A = 0.6180339887, A * key
    = 762.6539420558，取小数部分为0.6539420558, M×((A×key)%1.0) = 0.6539420558*1024 =669.6366651392，那么h(1234) = 669。

2.2全域散列法（了解）

  1. 如果存在一个恶意的对手，他针对我们提供的散列函数，特意构造出一个发生严重冲突的数据集，比如，让所有关键字全部落入同一个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。解决方法自然是见招拆招，给散列函数增加随机性，攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。
  2. hab (key) = ((a × key + b)%P)%M ，P需要选⼀个足够大的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了一个P*(P-1)组全域散列函数组。假设P=17，M=6，a = 3， b = 4, 则 h34 (8) = ((3 × 8 + 4)%17)%6 = 5 。
  3. 需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使用，后续增删查改都固定使用这个散列函数，否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数，查找又是另一个散列函数，就会导致找不到插入的key了。

在这里插入图片描述

3.处理哈希冲突

3.1线性探测（挨着找）

缺点：堆积

3.2二次探测（跳跃着找）

缺点：无法充分利用位置
3.1和3.2上一篇博客详细说明了

3.3双重散列（了解）

缺点：虽然可以充分利用位置，但是还是要解决冲突的问题

  • h1 (key) = hash0 = key % M , hash0位置冲突了，则双重探测公式为：hc(key, i) = hashi =
    (hash0 + i ∗ h2 (key)) % M， i = {1, 2, 3, …, M}
  • 要求 h2 (key) < M 且 h2 (key) 和M互为质数，有两种简单的取值方法：
    1、当M为2整数幂时，h2 (key) 从[0，M-1]任选一个奇数；
    2、当M为质数时， h2 (key) = key % (M − 1) + 1
  • 反例：保证 h2 (key) 与M互质是因为根据固定的偏移量所寻址的所有位置将形成一个群，若最大公约数说无法充分利用整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表大小为12，那么所能寻址的位置为{1, 4, 7, 10}，寻址个数为p = gcd(M, h1 (key)) > 1 ，那么所能寻址的位置的个数为 M/P < M ，使得对于一个关键字来
    12/gcd(12, 3) = 4
  • 下面演示 {19,30,52,74} 等这一组值映射到M=11的表中，设 h2 (key) = key%10 + 1
  • 本质是跳跃探测，减少冲突堆积
  • 双重散列就是让数据更加地分散，不容易产生哈希冲突

在这里插入图片描述

4.链地址法

开放地址法的问题是你占别人位置，别人来了又占其他人的位置，链地址法就不用占别人的位置，自己位置可以存多个位置，用了链表挂了多个数据

4.1扩容

  • 开放地址法的负载因子必须小于1，链地址法的负载因子没有这种规定，可以大于1，但是unordered_xxx中最大负载因子基本控制在1，大于1就会扩容。
    在这里插入图片描述

4.2基本的框架

namespace hash_bucket
{template<class K,class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K,V>& kv):_kv(kv),_next(nullptr){}};template<class K,class V,class Hash = HashFunc<K>>class HashTable{typedef HashTable<K, V> Node;public:// 构造HashTable():_tables(__stl_next_prime(0)),_n(0){}private:vector<Node*> _tables;// 指针数组size_t _n;// 表示存了多少个数据};
}

4.3插入

头插，尾插都可以，这里用了头插
在这里插入图片描述

// 插入
bool Insert(const pair<K,V>& kv)
{// 负载因子 == 1时扩容if (_n == _tables.size()){// 这种方法每个节点都要拷贝,影响效率// 并且原数组释放完后,不会自动析构每个节点,因为是内置类型// 还要自己写析构函数,比较麻烦//HashTable<K, V> newht;//newht._tables.resize(_stl_next_prime(tables.size() + 1));////for(size_t i = 0;i < _tables.size();i++)//{//	// 旧表的数据扩容后可能不冲突,必须一个一个取//	Node* cur = _tables[i];//	while (cur)//	{//		newht.Insert(cur->_kv);//		cur = cur->_next;//	}//}//_tables.swap(newht._tables);vector<Node*> newTable(_tables.size() * 2);for(size_t i = 0;i < _tables.size();i++){// 表旧表中的数据插入到新表中Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 算cur在新表中的位置size_t hashi = cur->_kv.first % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTable);}size_t hashi = kv.first % _tables.size();// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}int main()
{int a2[] = { 19,30,5,36,13,20,21,12,24,96 };hash_bucket::HashTable<int, int> ht;for (auto e : a2){ht.Insert({ e,e });}ht.Insert({ 100,100 });ht.Insert({ 200,200 });return 0;
}

4.4查找

// 查找
Node* Find(const K& key)
{size_t hashi = key % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;
}

4.5删除

删除分为三种情况：

  1. 头删，让下一个节点变为头节点
  2. 删除中间的节点，保留前一个节点的指针指向后一个节点的指针
  3. 尾删，让最后一个节点的前一个节点的指针指向空
  4. 2和3可以归为一类，删除中间的节点可以是前一个节点指向空
    在这里插入图片描述
// 删除
bool Erase(const K& key)
{size_t hashi = key % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev == nullptr){// 头删_tables[hashi] = cur->_next;}else{// 删除中间的节点prev->_next = cur->_next;}delete cur;--_n;return true;}else{prev = cur;cur = cur->_next;}}return false;
}

5.代码

namespace hash_bucket
{template<class K,class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K,V>& kv):_kv(kv),_next(nullptr){}};template<class K,class V,class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:// 构造HashTable():_tables(__stl_next_prime(0)),_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;}}// 插入bool Insert(const pair<K,V>& kv){Hash hash;// 如果插入的值存在冗余了返回falseif (Find(kv.first)){return false;}// 负载因子 == 1时扩容if (_n == _tables.size()){// 这种方法每个节点都要拷贝,影响效率// 并且原数组释放完后,不会自动析构每个节点,因为是内置类型// 还要自己写析构函数,比较麻烦//HashTable<K, V> newht;//newht._tables.resize(_stl_next_prime(tables.size() + 1));////for(size_t i = 0;i < _tables.size();i++)//{//	// 旧表的数据扩容后可能不冲突,必须一个一个取//	Node* cur = _tables[i];//	while (cur)//	{//		newht.Insert(cur->_kv);//		cur = cur->_next;//	}//}//_tables.swap(newht._tables);vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));for(size_t i = 0;i < _tables.size();i++){// 表旧表中的数据插入到新表中Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 算cur在新表中的位置size_t hashi = hash(cur->_kv.first) % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTable);}size_t hashi = hash(kv.first) % _tables.size();// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}// 查找Node* Find(const K& key){Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}// 删除bool Erase(const K& key){size_t hashi = key % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (cur->_kv.first == key){if (prev == nullptr){// 头删_tables[hashi] = cur->_next;}else{// 删除中间的节点prev->_next = cur->_next;}delete cur;--_n;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector<Node*> _tables;// 指针数组size_t _n;// 表示存了多少个数据};
}

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

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

相关文章

29.Word：公司本财年的年度报告【13】

29.Word：公司本财年的年度报告【13】

目录 NO1.2.3.4 NO5.6.7​ NO8.9.10​ NO1.2.3.4 另存为F12&#xff1a;考生文件夹&#xff1a;Word.docx选中绿色标记的标题文本→样式对话框→单击右键→点击样式对话框→单击右键→修改→所有脚本→颜色/字体/名称→边框&#xff1a;0.5磅、黑色、单线条&#xff1a;点…
阅读更多...
深入理解Java引用传递

深入理解Java引用传递

先看一段代码&#xff1a; public static void add(String a) {a "new";System.out.println("add: " a); // 输出内容&#xff1a;add: new}public static void main(String[] args) {String a null;add(a);System.out.println("main: " a);…
阅读更多...
Python从零构建macOS状态栏应用(仿ollama)并集成AI同款流式聊天 API 服务（含打包为独立应用）

Python从零构建macOS状态栏应用(仿ollama)并集成AI同款流式聊天 API 服务（含打包为独立应用）

在本教程中，我们将一步步构建一个 macOS 状态栏应用程序，并集成一个 Flask 服务器，提供流式响应的 API 服务。 如果你手中正好持有一台 MacBook Pro，又怀揣着搭建 AI 聊天服务的想法，却不知从何处迈出第一步，那么这篇文章绝对是你的及时雨。 最终，我们将实现以下功能： …
阅读更多...
Qt之数据库操作三

Qt之数据库操作三

主要介绍qt框架中对数据库的增加&#xff0c;删除和修改功能。 软件界面如下 程序结构 tdialogdata.h中代码 #ifndef TDIALOGDATA_H #define TDIALOGDATA_H#include <QDialog> #include<QSqlRecord> namespace Ui { class TDialogData; }class TDialogData : pub…
阅读更多...
neo4j入门

neo4j入门

文章目录 neo4j版本说明部署安装Mac部署docker部署 neo4j web工具使用数据结构图数据库VS关系数据库 neo4j neo4j官网Neo4j是用ava实现的开源NoSQL图数据库。Neo4作为图数据库中的代表产品&#xff0c;已经在众多的行业项目中进行了应用&#xff0c;如&#xff1a;网络管理&am…
阅读更多...
JVM-运行时数据区

JVM-运行时数据区

JVM的组成 运行时数据区-总览 Java虚拟机在运行Java程序过程中管理的内存区域&#xff0c;称之为运行时数据区。 《Java虚拟机规范》中规定了每一部分的作用 运行时数据区-应用场景 Java的内存分成哪几部分&#xff1f; Java内存中哪些部分会内存溢出&#xff1f; JDK7 和J…
阅读更多...
Java篇之继承

Java篇之继承

目录 一. 继承 1. 为什么需要继承 2. 继承的概念 3. 继承的语法 4. 访问父类成员 4.1 子类中访问父类的成员变量 4.2 子类中访问父类的成员方法 5. super关键字 6. super和this关键字 7. 子类构造方法 8. 代码块的执行顺序 9. protected访问修饰限定符 10. 继承方式…
阅读更多...
leetcode——验证二叉搜索树（java）

leetcode——验证二叉搜索树（java）

给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左子树只包含小于当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1&#xff1a; 输入…
阅读更多...
家居EDI：Hom Furniture EDI需求分析

家居EDI：Hom Furniture EDI需求分析

HOM Furniture 是一家成立于1977年的美国家具零售商&#xff0c;总部位于明尼苏达州。公司致力于提供高品质、时尚的家具和家居用品&#xff0c;满足各种家庭和办公需求。HOM Furniture 以广泛的产品线和优质的客户服务在市场上赢得了良好的口碑。公司经营的产品包括卧室、客厅…
阅读更多...
Spring Boot + Facade Pattern : 通过统一接口简化多模块业务

Spring Boot + Facade Pattern : 通过统一接口简化多模块业务

文章目录 Pre概述在编程中&#xff0c;外观模式是如何工作的&#xff1f;外观设计模式 UML 类图外观类和子系统的关系优点案例外观模式在复杂业务中的应用实战运用1. 项目搭建与基础配置2. 构建子系统组件航班服务酒店服务旅游套餐服务 3. 创建外观类4. 在 Controller 中使用外…
阅读更多...
八、Spring Boot 日志详解

八、Spring Boot 日志详解

目录 一、日志的用途 二、日志使用 2.1 打印日志 2.1.1 在程序中获取日志对象 2.1.2 使用日志对象打印日志 2.2、日志框架介绍 2.2.1 门面模式(外观模式) 2.2.2 门面模式的实现 2.2.3 SLF4J 框架介绍 2.3 日志格式的说明 2.4 日志级别 2.4.1 日志级别的分类 2.4.2…
阅读更多...
创建前端项目的方法

创建前端项目的方法

目录 一、创建前端项目的方法 1.前提&#xff1a;安装Vue CLI 2.方式一&#xff1a;vue create项目名称 3.方式二&#xff1a;vue ui 二、Vue项目结构 三、修改Vue项目端口号的方法 一、创建前端项目的方法 1.前提&#xff1a;安装Vue CLI npm i vue/cli -g 2.方式一&…
阅读更多...
(leetcode 213 打家劫舍ii)

(leetcode 213 打家劫舍ii)

代码随想录&#xff1a; 将一个线性数组换成两个线性数组&#xff08;去掉头&#xff0c;去掉尾&#xff09; 分别求两个线性数组的最大值 最后求这两个数组的最大值 代码随想录视频 #include<iostream> #include<vector> #include<algorithm> //nums:2,…
阅读更多...
【Python】第七弹---Python基础进阶：深入字典操作与文件处理技巧

【Python】第七弹---Python基础进阶：深入字典操作与文件处理技巧

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】【MySQL】【Python】 目录 1、字典 1.1、字典是什么 1.2、创建字典 1.3、查找 key 1.4、新增/修改元素 1.5、删除元素 1.6、遍历…
阅读更多...
本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操

本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操

本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操 Janus-Pro-7B介绍 Janus-Pro-7B 是由 DeepSeek 开发的多模态 AI 模型&#xff0c;它在理解和生成方面取得了显著的进步。这意味着它不仅可以处理文本&#xff0c;还可以处理图像等其他模态的信息。 模型主要特点:Permalink…
阅读更多...
BW AO/工作簿权限配置

BW AO/工作簿权限配置

场景&#xff1a; 按事业部配置工作簿权限&#xff1b; 1、创建用户 事务码&#xff1a;SU01&#xff0c;用户主数据的维护&#xff0c;可以创建、修改、删除、锁定、解锁、修改密码等 用户设置详情页 2、创建权限角色 用户的权限菜单是通过权限角色分配来实现的 2.1、自定…
阅读更多...
jstat命令详解

jstat命令详解

jstat 用于监视虚拟机运行时状态信息的命令&#xff0c;它可以显示出虚拟机进程中的类装载、内存、垃圾收集、JIT 编译等运行数据。 命令的使用格式如下。 jstat [option] LVMID [interval] [count]各个参数详解&#xff1a; option&#xff1a;操作参数LVMID&#xff1a;本…
阅读更多...
3.Spring-事务

3.Spring-事务

一、隔离级别&#xff1a; 脏读&#xff1a; 一个事务访问到另外一个事务未提交的数据。 不可重复读&#xff1a; 事务内多次查询相同条件返回的结果不同。 幻读&#xff1a; 一个事务在前后两次查询同一个范围的时候&#xff0c;后一次查询看到了前一次查询没有看到的行。 二…
阅读更多...
MYSQL--一条SQL执行的流程,分析MYSQL的架构

MYSQL--一条SQL执行的流程,分析MYSQL的架构

文章目录 第一步建立连接第二部解析 SQL第三步执行 sql预处理优化阶段执行阶段索引下推 执行一条select 语句中间会发生什么&#xff1f; 这个是对 mysql 架构的深入理解。 select * from product where id 1;对于mysql的架构分层: mysql 架构分成了 Server 层和存储引擎层&a…
阅读更多...
ReentrantReadWriteLock源码分析

ReentrantReadWriteLock源码分析

文章目录 概述一、状态位设计二、读锁三、锁降级机制四、写锁总结 概述 ReentrantReadWriteLock&#xff08;读写锁&#xff09;是对于ReentranLock&#xff08;可重入锁&#xff09;的一种改进&#xff0c;在可重入锁的基础上&#xff0c;进行了读写分离。适用于读多写少的场景…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023