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。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
水位雨量在线监测系统概述及应用介绍

水位雨量在线监测系统概述及应用介绍

在当今社会，随着科技的飞速发展，各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中，水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术，其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成，形成了一个完整的闭环系统。 数据采集单元：这是系统的“眼睛”，
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2