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。

相关文章

Redis客户端连接机制的实现方案

Redis客户端连接机制的实现方案

《Redis客户端连接机制的实现方案》本文主要介绍了Redis客户端连接机制的实现方案,包括事件驱动模型、非阻塞I/O处理、连接池应用及配置优化,具有一定的参考价值,感兴趣的可以了解一下... 目录1. Redis连接模型概述2. 连接建立过程详解2.1 连php接初始化流程2.2 关键配置参数3. 最大连
阅读更多...
Python实现网格交易策略的过程

Python实现网格交易策略的过程

《Python实现网格交易策略的过程》本文讲解Python网格交易策略,利用ccxt获取加密货币数据及backtrader回测,通过设定网格节点,低买高卖获利,适合震荡行情,下面跟我一起看看我们的第一... 网格交易是一种经典的量化交易策略，其核心思想是在价格上下预设多个“网格”，当价格触发特定网格时执行买
阅读更多...
Python标准库之数据压缩和存档的应用详解

Python标准库之数据压缩和存档的应用详解

《Python标准库之数据压缩和存档的应用详解》在数据处理与存储领域,压缩和存档是提升效率的关键技术,Python标准库提供了一套完整的工具链,下面小编就来和大家简单介绍一下吧... 目录一、核心模块架构与设计哲学二、关键模块深度解析1.tarfile：专业级归档工具2.zipfile：跨平台归档首选3.
阅读更多...
使用IDEA部署Docker应用指南分享

使用IDEA部署Docker应用指南分享

《使用IDEA部署Docker应用指南分享》本文介绍了使用IDEA部署Docker应用的四步流程：创建Dockerfile、配置IDEADocker连接、设置运行调试环境、构建运行镜像,并强调需准备本... 目录一、创建 dockerfile 配置文件二、配置 IDEA 的 Docker 连接三、配置 Do
阅读更多...
深入浅出SpringBoot WebSocket构建实时应用全面指南

深入浅出SpringBoot WebSocket构建实时应用全面指南

《深入浅出SpringBootWebSocket构建实时应用全面指南》WebSocket是一种在单个TCP连接上进行全双工通信的协议,这篇文章主要为大家详细介绍了SpringBoot如何集成WebS... 目录前言为什么需要 WebSocketWebSocket 是什么Spring Boot 如何简化 We
阅读更多...
Java Stream流之GroupBy的用法及应用场景

Java Stream流之GroupBy的用法及应用场景

《JavaStream流之GroupBy的用法及应用场景》本教程将详细介绍如何在Java中使用Stream流的groupby方法,包括基本用法和一些常见的实际应用场景,感兴趣的朋友一起看看吧... 目录Java Stream流之GroupBy的用法1. 前言2. 基础概念什么是 GroupBy？Stream
阅读更多...
python设置环境变量路径实现过程

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法：临时设置（Windows用`set`,Linux/macOS用`export`）、永久设置（系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量（适用于当前会话）永久设置环境变量（Windows系统
阅读更多...
python中列表应用和扩展性实用详解

python中列表应用和扩展性实用详解

《python中列表应用和扩展性实用详解》文章介绍了Python列表的核心特性：有序数据集合,用[]定义,元素类型可不同,支持迭代、循环、切片,可执行增删改查、排序、推导式及嵌套操作,是常用的数据处理... 目录1、列表定义2、格式3、列表是可迭代对象4、列表的常见操作总结1、列表定义是处理一组有序项目的
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2