C++王牌结构hash：哈希表开散列(哈希桶)的实现与应用

2024-03-30 12:52
文章标签 c++ 实现 应用 哈希 结构 hash 散列 王牌 表开

本文主要是介绍C++王牌结构hash：哈希表开散列(哈希桶)的实现与应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、开散列的概念

1.1开散列与闭散列比较

二、开散列/哈希桶的实现

2.1开散列实现

哈希函数的模板构造

哈希表节点构造

开散列增容

插入数据

2.2代码实现

一、开散列的概念

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

fe028ef67fc447009dc9a8cfeb08e470.png

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

1.1开散列与闭散列比较

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

二、开散列/哈希桶的实现

2.1开散列实现

哈希函数的模板构造

当数据类型不是整数时，我们需要通过哈希函数将其转换为一个size_t类型的无符号整形然后%上哈希表的容量得出一个映射值，所以需要针对不同的数据类型，来构造不同的Hashfunc来将其转换为size_t类型，这时就要用到模板特化来处理数据，尤其是字符串类型。

哈希表节点构造

同时针对set和map的不同，我们需要将hash桶的模板可以满足两种不同类型的调用，所以在参数上也要设置两个参数，如果是set传参，就让两个参数都是K，如果是map传参，第一个参数是K，第二个参数则是pair<K,V>，而在构造哈希表的node时，不管是set还是map都只需要传第二个参数过去，而hashnode也只需要用一个template<class T>来进行接收就好，然后构造初始化出T _data和一个T* _next的指针来指向桶中下一个节点。

那为什么在传参时不直接只设置一个参数呢？因为在调用find时，需要传一个值进去查找，如果是set则直接查找，如果是map则需要取出hashnode中的first与之进行比较，所以必须设置两个模板参数。

开散列增容

桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。

插入数据

因为开散列每个位置都是一串单链表，所以在插入节点时，直接选择头插即可，头插的消耗和速度都是最小的。

2.2代码实现

#pragma once
#include<iostream>
using namespace std;
#include<vector>
#include<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 hash = 0;for (auto e : s){hash += e;hash *= 131;}return hash;}
};
namespace hash_bucket
{//如果是unordered_set的话T=K//如果是unordered_map的话T=pair<K,V>template<class T>struct HashNode{HashNode<T>* _next;T _data;HashNode(const T& data):_next(nullptr),_data(data){}};// 前置声明,因为编译器编译时会向上进行查找，而iterator要去调用哈希表，所以需要提前进行前置声明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;}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;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;}}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);}//插入节点bool insert(const T& data){Keyoft kot;if (Find(kot(data)))return 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();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 true;}//查找Node* Find(const K& key){Hash hs;Keyoft kot;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key)return cur;cur = cur->_next;}return nullptr;}Node* Erase(const K& key){Hash hs;Keyoft kot;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;}}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables;//指针数组size_t _n;};
}

这篇关于C++王牌结构hash：哈希表开散列(哈希桶)的实现与应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/861536。

相关文章

Vue ElementUI中Upload组件批量上传的实现代码

Vue ElementUI中Upload组件批量上传的实现代码

《VueElementUI中Upload组件批量上传的实现代码》ElementUI中Upload组件批量上传通过获取upload组件的DOM、文件、上传地址和数据,封装uploadFiles方法,使... ElementUI中Upload组件如何批量上传首先就是upload组件 <el-upl
阅读更多...
Docker部署Jenkins持续集成(CI)工具的实现

Docker部署Jenkins持续集成(CI)工具的实现

《Docker部署Jenkins持续集成(CI)工具的实现》Jenkins是一个流行的开源自动化工具,广泛应用于持续集成（CI）和持续交付（CD）的环境中,本文介绍了使用Docker部署Jenkins... 目录前言一、准备工作二、设置变量和目录结构三、配置 docker 权限和网络四、启动 Jenkins
阅读更多...
Python3脚本实现Excel与TXT的智能转换

Python3脚本实现Excel与TXT的智能转换

《Python3脚本实现Excel与TXT的智能转换》在数据处理的日常工作中,我们经常需要将Excel中的结构化数据转换为其他格式,本文将使用Python3实现Excel与TXT的智能转换,需要的可以... 目录场景应用：为什么需要这种转换技术解析：代码实现详解核心代码展示改进点说明实战演练：从Excel到
阅读更多...
如何使用CSS3实现波浪式图片墙

如何使用CSS3实现波浪式图片墙

《如何使用CSS3实现波浪式图片墙》：本文主要介绍了如何使用CSS3的transform属性和动画技巧实现波浪式图片墙，通过设置图片的垂直偏移量，并使用动画使其周期性地改变位置，可以创建出动态且具有波浪效果的图片墙，同时，还强调了响应式设计的重要性，以确保图片墙在不同设备上都能良好显示，详细内容请阅读本文，希望能对你有所帮助...
阅读更多...
C# string转unicode字符的实现

C# string转unicode字符的实现

《C#string转unicode字符的实现》本文主要介绍了C#string转unicode字符的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随... 目录1. 获取字符串中每个字符的 Unicode 值示例代码：输出：2. 将 Unicode 值格式化
阅读更多...
python安装whl包并解决依赖关系的实现

python安装whl包并解决依赖关系的实现

《python安装whl包并解决依赖关系的实现》本文主要介绍了python安装whl包并解决依赖关系的实现,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录一、什么是whl文件？二、我们为什么需要使用whl文件来安装python库？三、我们应该去哪儿下
阅读更多...
Python脚本实现图片文件批量命名

Python脚本实现图片文件批量命名

《Python脚本实现图片文件批量命名》这篇文章主要为大家详细介绍了一个用python第三方库pillow写的批量处理图片命名的脚本,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录前言源码批量处理图片尺寸脚本源码GUI界面源码打包成.exe可执行文件前言本文介绍一个用python第三方库pi
阅读更多...
Java中将异步调用转为同步的五种实现方法

Java中将异步调用转为同步的五种实现方法

《Java中将异步调用转为同步的五种实现方法》本文介绍了将异步调用转为同步阻塞模式的五种方法：wait/notify、ReentrantLock+Condition、Future、CountDownL... 目录异步与同步的核心区别方法一：使用wait/notify + synchronized代码示例关键
阅读更多...
MobaXterm远程登录工具功能与应用小结

MobaXterm远程登录工具功能与应用小结

《MobaXterm远程登录工具功能与应用小结》MobaXterm是一款功能强大的远程终端软件,主要支持SSH登录,拥有多种远程协议,实现跨平台访问,它包括多会话管理、本地命令行执行、图形化界面集成和... 目录1. 远程终端软件概述1.1 远程终端软件的定义与用途1.2 远程终端软件的关键特性2. 支持的
阅读更多...
Nginx实现动态封禁IP的步骤指南

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2