【C++】哈希桶

ops/2024/9/23 16:13:55/

前言

哈希桶是哈希表中用于存储数据的基本单元,也称为哈希槽或存储桶。

  • 哈希桶(Hash Bucket)** 是哈希表数据结构中的一个概念。、
  • 哈希表通过哈希函数将输入数据映射到一个存储位置,而哈希桶就是这些存储位置中的一个单元。
  • 哈希桶用于存放哈希表中的元素,当不同的元素经过哈希函数映射到同一个桶时,通常通过链表或其他结构来存储这些元素。这种情况称为 哈希冲突

哈希桶的工作机制

  1. 哈希函数的作用:哈希函数根据输入元素计算出一个整数值,称为哈希值,然后根据哈希值来决定元素存储在哪个桶中。

    假设哈希表的桶数为 num_buckets,元素 key 的哈希值为 hash(key),则该元素将被存储在 hash(key) % num_buckets 这个桶中。

  2. 哈希冲突:由于哈希表的容量有限,而插入的元素可能很多,因此会有多个元素映射到同一个桶。这就是哈希冲突。

  3. 冲突解决方式:当发生哈希冲突时,哈希桶中的元素通常会存储在某种结构中。常见的冲突解决方式包括:

    • 拉链法:在每个哈希桶中维护一个链表,当多个元素映射到同一个桶时,这些元素会依次插入链表中。
    • 开放寻址法:当某个桶已经有元素时,寻找下一个空的桶来存储冲突的元素。参考

哈希桶示例

例如,一个哈希表有 5 个桶(编号为 0-4),通过简单的哈希函数 hash(key) = key % 5 来决定桶的位置。

//假设插入的元素为:12, 7, 5, 10, 15, 9
hash(12) = 12 % 5 = 2
hash(7) = 7 % 5 = 2
hash(5) = 5 % 5 = 0
hash(10) = 10 % 5 = 0
hash(15) = 15 % 5 = 0
hash(9) = 9 % 5 = 4

最终得到的哈希桶分布如下:

  • 桶 0:5 -> 10 -> 15
  • 桶 1:(空)
  • 桶 2:12 -> 7
  • 桶 3:(空)
  • 桶 4:9

其中:

  • 桶 0 通过拉链法存储了 5、10 和 15,使用链表处理冲突。
  • 桶 2 同样存储了 12 和 7。

哈希桶的实现

存储结构

  • 类似于链表,在顺序表中存储一个一个节点。’
template<class T>
struct defaultHashfunc
{size_t operator()(const T& data){return (size_t)data;}
};
  • table:使用 std::vector 存储多个链表,每个链表代表一个桶,链表中的元素是映射到这个桶的所有元素。
  • 记录_n进行负载因子的储存
template<class K,class T,class KeyofT,class HashFunc = defaultHashfunc<K>>
class HashTable
{public:...private:vector<Node*> _table;size_t _n = 0;
};

哈希函数

  1. 在函数的内容的不确定的时候进行返回。
  2. 针对string字符串的直接进行特模板化。
  3. 针对26字母有不同的组合,要进行字符串的哈希化处理,目的是针对哈希冲突 (本次采用 BKDR算法)参考:字符串哈希算法
template<class T>
struct defaultHashfunc
{size_t operator()(const T& data){return (size_t)data;}
};
//string特化
template<>
struct defaultHashfunc<string>
{size_t operator()(const string& str){size_t hash = 0;for (auto& ch : str){hash *= 131;hash += ch;}return hash;}
};

插入操作

哈希桶插入步骤

  • 计算哈希值: 使用哈希函数 hash(key) 将键值(key)映射为一个整数,称为 哈希值。这个哈希值决定了 key 应该被存储在哪个桶中。

  • 定位桶:根据哈希值和哈希表的大小(桶的数量),确定目标桶的位置。常用的方式是:bucket = hash(key) % num_buckets,其中 num_buckets 是哈希表的桶数量。

  • 检查冲突:定位到目标桶后,检查桶中是否已经存在与 key 相同的元素。如果已经存在,则插入操作可以直接结束(因为集合不允许重复元素),否则继续进行。

  • 插入元素: 如果目标桶中不存在相同的元素,直接将元素插入到该桶中。对于拉链法,目标桶通常使用链表(或类似结构)存储多个元素,因此新元素会被插入到链表末尾。

  • 哈希桶的扩容: 如果大小不够,一个桶的元素过于多,就需要进行扩容,创建一个新表进行插入操作。

bool insert(const T& data)
{HashFunc hf;bool it = Find(kot(data));if (it){return false;}if (_n == _table.size()){size_t newsize = _table.size() * 2;vector<Node*> newtable;newtable.resize(newsize,nullptr);for (int i = 0; i < _table.size() ;i++){HashFunc hf;size_t hashi = 0;Node* cur = _table[i];while (cur){Node* next = cur->_next;hashi = hf(cur->_data) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}size_t hashi = hf(data) % _table.size();Node* newnode = new Node(data);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return true;
}

插入效率:

  • 时间复杂度:哈希桶的插入操作通常情况下的时间复杂度为 O(1),因为哈希函数能够在常数时间内定位到桶的位置。然而,最坏情况下(所有元素都被映射到同一个桶中),时间复杂度退化为 O(n),其中 n 是桶中元素的数量。
  • 空间复杂度:哈希表的空间复杂度与桶的数量和元素数量成正比,通常为 O(n)

删除操作

哈希桶删除步骤:

  • 计算哈希值: 使用哈希函数 hash(key) 计算出元素的哈希值,找到元素应该所在的桶。

  • 定位桶: 根据哈希值和哈希表的桶数量,确定目标桶的位置,通常通过:bucket = hash(key) % num_buckets 来找到对应的桶。

  • 遍历桶中的元素: 在找到的桶中,遍历桶中存储的所有元素(通常是通过链表存储),寻找需要删除的元素。

  • 删除元素: 一旦找到目标元素,将其从桶中删除(对于拉链法,通常是从链表中删除元素)。如果该元素不存在,则无需做任何操作。

bool Erase(const K& key)
{HashFunc hf;size_t hashi = hf(key) % _table.szie();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (cur->_data == key){if (prev == nullptr){_table[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;
}

时间复杂度分析

  • 最佳情况:每个桶中只有一个元素或哈希函数将元素均匀分布到桶中,删除操作的时间复杂度为 O(1),因为只需找到桶后直接删除即可。

  • 最坏情况:所有元素都被映射到同一个桶中,导致链表长度等于元素数量。在这种情况下,删除操作的时间复杂度为 O(n),其中 n 是链表中的元素数量。

  • 平均情况:如果哈希函数分布较好,链表的长度较短,删除操作的平均时间复杂度为 O(1)

查找操作

哈希桶查找步骤

  • 计算哈希值:使用哈希函数 hash(key) 计算出需要查找的元素的哈希值,找到元素应该存储的桶。
  • 定位桶:根据哈希值,计算出目标桶的索引。常用的方式是:bucket = hash(key) % num_buckets,其中 num_buckets 是哈希表的桶数量。
  • 在桶内查找: 如果该桶为空,直接返回元素不存在。如果桶内有元素,遍历桶中的链表或数组,逐个检查每个元素是否与要查找的键值相等。
  • 返回结果
    1. 如果找到与目标键相等的元素,则返回成功查找的结果。
    2. 如果遍历完整个桶(链表或数组)后,未找到目标元素,则返回查找失败。
bool Find(const K& key)
{HashFunc hf; size_t hashi = hf(key) % _table.size();Node* cur = _table[hashi];while (cur){if (kot(cur->_data) == key){return true;}cur = cur->_next;}return false;
}

http://www.ppmy.cn/ops/114853.html

相关文章

MyBatis XML映射文件编写【后端 18】

MyBatis XML映射文件编写 MyBatis 是一个优秀的持久层框架&#xff0c;它支持定制化 SQL、存储过程以及高级映射。MyBatis 避免了几乎所有的 JDBC 代码和手动设置参数以及获取结果集。MyBatis 可以使用简单的 XML 或注解用于配置和原始映射&#xff0c;将接口和 Java 的 POJOs …

Python办公自动化教程(002):PDF的拆分与合并

1、PyPDF2 介绍 介绍&#xff1a; PyPDF2是一个用于处理PDF文件的Python库&#xff0c;它提供了丰富的功能来读取、编辑、合并、拆分PDF文档&#xff0c;以及提取文本、图像和其他内容。 功能&#xff1a; 读取PDF&#xff1a;PyPDF2可以轻松地打开和读取PDF文件&#xff0c;获…

安卓13去掉下拉菜单的Dump SysUI 堆的选项 android13删除Dump SysUI 堆

总纲 android13 rom 开发总纲说明 文章目录 1.前言2.问题分析3.代码分析3.1 位置13.2 位置24.代码修改5.编译6.彩蛋1.前言 客户需要去掉下拉菜单里面的Dump SysUI 堆图标,不让使用这个功能。 2.问题分析 android的下拉菜单在systemui里面,这里我们只需要定位到对应的添加代…

CentOS:稳定的服务器操作系统选择

在当今的IT环境中&#xff0c;选择合适的操作系统对于服务器的稳定性和安全性至关重要。CentOS&#xff08;Community ENTerprise Operating System&#xff09;作为一个基于Red Hat Enterprise Linux&#xff08;RHEL&#xff09;的开源操作系统&#xff0c;因其稳定性和安全性…

TypeScript 类型断言

一、TypeScript 类型断言的语法 1. <Type>value let someValue: any "Hello"; let strLength: number (<string>someValue).length; 2. value as Type let someValue: any "Hello"; let strLength: number (someValue as string).lengt…

PostgreSQL 基础操作

PostgreSQL&#xff08;简称pgsql&#xff09;的基础命令行操作涉及多个方面&#xff0c;包括数据库和表的管理、数据操作以及系统信息的查询等。以下是一些常用的PostgreSQL基础命令行操作&#xff1a; 1. 数据库管理 创建数据库&#xff1a; CREATE DATABASE 数据库名;例如…

Elastic 的 OpenTelemetry PHP 发行版简介

作者&#xff1a;Pawel Filipczak 宣布 OpenTelemetry PHP 的 Elastic 发行版的第一个 alpha 版本。在本篇博文中了解使用 OpenTelemetry 来检测 PHP 应用程序是多么简单。 我们很高兴推出 OpenTelemetry PHP 的 Elastic Distribution 的第一个 alpha 版本。在这篇文章中&…

什么是CPQ?一文讲解什么是CPQ选型配置报价系统

什么是CPQ选型配置报价? CPQ&#xff0c;是英文名 Configure Price Quote的缩写&#xff0c;中文称为配置报价软件。该软件经常出现在销售行业。它是一种可以快速为企业报价的销售工具。企业在报价时&#xff0c;会综合考虑数量、折扣、产品可选功能等。CPQ软件能够整合企业的…