当前位置: 首页 > news >正文

c++ 散列表

散列表(Hash Table)是一种高效的数据结构,广泛用于实现快速的键值对存储

基本概念

散列表使用哈希函数将键映射到数组的索引。其主要优点在于平均情况下提供常数时间复杂度的查找、插入和删除操作。

  • 哈希函数: 将键映射到一个固定大小的数组索引。一个好的哈希函数应该具备:
    • 散列均匀性:不同的键应该尽量映射到不同的索引。
    • 计算简单:哈希值的计算应该高效。

冲突处理

由于多个键可能映射到同一个索引,必须采取措施处理冲突。常见的冲突解决方法包括:

  • 链地址法: 在每个数组索引处使用链表存储所有映射到该索引的键值对。
  • 开放寻址法: 在数组中查找下一个可用位置,例如线性探测、二次探测和双重散列等方法。

性能分析

时间复杂度:

  • 查找:O(1)(平均情况),O(n)(最坏情况,发生冲突时)
  • 插入:O(1)(平均情况),O(n)(最坏情况)
  • 删除:O(1)(平均情况),O(n)(最坏情况)

空间复杂度: O(n),即存储元素的数量。

负载因子(Load Factor): 定义为元素数量与表大小的比率。一般在负载因子超过一定阈值(如0.7)时进行扩容,以保持性能。

代码实现

链地址法

#include <iostream>
#include <vector>
#include <list>
#include <utility> // for std::pair
#include <functional> // for std::hashtemplate <typename Key, typename Value>
class HashTable {
public:HashTable(size_t size = 10) : table(size), current_size(0) {}void Insert(const Key& key, const Value& value) {size_t index = Hash_(key) % table.size();for (auto& pair : table[index]) {if (pair.first == key) {pair.second = value; // 更新值return;}}table[index].emplace_back(key, value); // 插入新键值对current_size++;if (current_size > table.size() * load_factor) {Resize_();}}bool Get(const Key& key, Value& value) const {size_t index = Hash_(key) % table.size();for (const auto& pair : table[index]) {if (pair.first == key) {value = pair.second;return true;}}return false; // 未找到}bool Remove(const Key& key) {size_t index = Hash_(key) % table.size();auto& cell = table[index];for (auto it = cell.begin(); it != cell.end(); ++it) {if (it->first == key) {cell.erase(it); // 删除current_size--;return true;}}return false; // 未找到}private:std::vector<std::list<std::pair<Key, Value>>> table; // 哈希表的数组size_t current_size; // 当前存储的元素数量const float load_factor = 0.7; // 负载因子size_t Hash_(const Key& key) const {return std::hash<Key>()(key); // 使用标准哈希函数}void Resize_() {std::vector<std::list<std::pair<Key, Value>>> old_table = table;table.resize(old_table.size() * 2); // 扩容current_size = 0;for (const auto& cell : old_table) {for (const auto& pair : cell) {Insert(pair.first, pair.second); // 重新插入}}}
};int main() {HashTable<std::string, int> hash_table;hash_table.Insert("apple", 1);hash_table.Insert("banana", 2);int value;if (hash_table.Get("apple", value)) {std::cout << "apple: " << value << std::endl; // 输出: apple: 1}hash_table.Remove("apple");if (!hash_table.Get("apple", value)) {std::cout << "apple not found" << std::endl; // 输出: apple not found}return 0;
}

代码解析

  1. 数据结构:
    • 使用 std::vector 存储链表,链表用于处理冲突。
    • 每个链表中的元素是 std::pair<Key, Value>,用于存储键值对。
  2. 插入操作:
    • 计算哈希值并确定索引。
    • 检查索引处是否存在相同的键,如果存在则更新值,否则插入新键值对。
    • 如果当前元素个数超过负载因子,则调用 Resize 扩容。
  3. 查找操作:
    • 计算索引,遍历链表查找对应的键。
  4. 删除操作:
    • 计算索引并在链表中查找键,找到后删除。
  5. 扩容:
    • 创建新的、更大的表,重新插入旧表中的元素以保证均匀分布。

开放寻址法

#include <iostream>
#include <vector>
#include <utility> // for std::pair
#include <stdexcept> // for std::out_of_rangetemplate <typename Key, typename Value>
class HashTable {
public:HashTable(size_t size = 10) : table(size), current_size(0), load_factor(0.7) {}void Insert(const Key& key, const Value& value) {if (current_size >= table.size() * load_factor) {Resize_();}size_t index = Hash_(key) % table.size();while (table[index].first != Key() && table[index].first != key) {index = (index + 1) % table.size(); // 线性探测}table[index] = { key, value };current_size++;}bool Get(const Key& key, Value& value) const {size_t index = Hash_(key) % table.size();while (table[index].first != Key()) {if (table[index].first == key) {value = table[index].second;return true;}index = (index + 1) % table.size(); // 线性探测}return false; // 未找到}bool Remove(const Key& key) {size_t index = Hash_(key) % table.size();while (table[index].first != Key()) {if (table[index].first == key) {table[index] = { Key(), Value() }; // 标记为删除current_size--;return true;}index = (index + 1) % table.size(); // 线性探测}return false; // 未找到}private:std::vector<std::pair<Key, Value>> table; // 散列表的数组size_t current_size; // 当前存储的元素数量const float load_factor; // 负载因子size_t Hash_(const Key& key) const {return std::hash<Key>()(key); // 使用标准哈希函数}void Resize_() {std::vector<std::pair<Key, Value>> old_table = table;table.resize(old_table.size() * 2, { Key(), Value() }); // 扩容current_size = 0;for (const auto& pair : old_table) {if (pair.first != Key()) {Insert(pair.first, pair.second); // 重新插入}}}
};int main() {HashTable<std::string, int> hash_table;hash_table.Insert("apple", 1);hash_table.Insert("banana", 2);int value;if (hash_table.Get("apple", value)) {std::cout << "apple: " << value << std::endl; // 输出: apple: 1}hash_table.Remove("apple");if (!hash_table.Get("apple", value)) {std::cout << "apple not found" << std::endl; // 输出: apple not found}return 0;
}

代码解析

  1. 数据结构:
    • 使用 std::vector<std::pair<Key, Value>> 存储键值对。未使用的槽位初始化为 Key()Value(),用于标记空槽。
  2. 插入操作:
    • 计算哈希值并确定初始索引。
    • 如果发生冲突,使用线性探测法查找下一个可用的索引。
    • 如果当前元素数量超过负载因子,则调用 Resize 方法进行扩容。
  3. 查找操作:
    • 计算索引并线性探测,直到找到对应的键或到达空槽。
  4. 删除操作:
    • 在查找过程中,如果找到目标键,则标记该位置为已删除。
  5. 扩容:
    • 创建一个更大的数组并重新插入旧表中的元素,以保持均匀分布。

总结

散列表是一种高效且灵活的数据结构,适合用于需要快速查找和存储的场景。通过合理设计哈希函数和冲突处理策略,可以实现良好的性能。

相关文章:

c++ 散列表

散列表&#xff08;Hash Table&#xff09;是一种高效的数据结构&#xff0c;广泛用于实现快速的键值对存储。 基本概念 散列表使用哈希函数将键映射到数组的索引。其主要优点在于平均情况下提供常数时间复杂度的查找、插入和删除操作。 哈希函数: 将键映射到一个固定大小的…...

Windows通过netsh控制安全中心防火墙和网络保护策略

Windows通过netsh控制安全中心防火墙和网络保护策略 1. 工具简介 【1】. Windows安全中心 【2】. netsh工具 netsh(Network Shell) 是一个Windows系统本身提供的功能强大的网络配置命令行工具。 2. 开启/关闭防火墙策略 在设置端口&#xff08;禁用/启用&#xff09;前&am…...

UML(Unified Modeling Language,统一建模语言)

UML&#xff08;Unified Modeling Language&#xff0c;统一建模语言&#xff09;是一种标准化的图形化语言&#xff0c;用于软件工程中的可视化建模。UML由Grady Booch、James Rumbaugh和Ivar Jacobson共同开发&#xff0c;他们各自的工作&#xff08;Booch方法、OMT方法和OOS…...

深⼊理解指针(2)

目录 1. 数组名的理解 2. 使⽤指针访问数组 3. ⼀维数组传参的本质 4. ⼆级指针 5. 指针数组 6. 指针数组模拟⼆维数组 1. 数组名的理解 我们在使⽤指针访问数组的内容时&#xff0c;有这样的代码&#xff1a; int arr[10] {1,2,3,4,5,6,7,8,9,10}; int *p &arr[…...

Ubuntu中MySQL远程登录设置

mysql单独放在一台Ubuntu服务器上&#xff0c;我远程连接不上。可能是安装的时候忘记设置远程登录了。事后补救措施如下&#xff1a; MySQL 绑定地址配置问题 MySQL 可能只绑定了 localhost&#xff0c;无法接受来自外部主机的连接。你需要检查 MySQL 的配置文件 /etc/mysql/…...

typescript 中封装一个 class 来解析接口响应数据

在TypeScript中&#xff0c;封装一个类来解析接口响应数据是一个常见的做法&#xff0c;它允许你将与接口响应相关的逻辑封装在一个可复用的单元中。下面是一个示例&#xff0c;展示了如何定义一个TypeScript类来解析一个假设的API接口响应数据。 首先&#xff0c;我们定义一个…...

[LeetCode] 21. 合并两个有序链表

题目描述&#xff1a; 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4]示例 2&#xff1a; 输入&#xff1a;l1 [], l2 […...

CTFHUB技能树之SQL——MySQL结构

开启靶场&#xff0c;打开链接&#xff1a; 先判断一下是哪种类型的SQL注入&#xff1a; 1 and 11# 正常回显 1 and 12# 回显错误&#xff0c;说明是整数型注入 判断一下字段数&#xff1a; 1 order by 2# 正常回显 1 order by 3# 回显错误&#xff0c;说明字段数是2列 知道…...

Git小知识:合理的分支命名约定

前言&#xff1a;创建新分支时&#xff0c;对 Git 分支进行合理的命名非常重要&#xff0c;应选择有描述性的名称&#xff0c;因为它可以帮助团队成员更好地理解分支的目的和内容&#xff0c;以便将来回顾时能立即明白分支的目的。以下是一些常见的分支命名约定&#xff1a; 功…...

Ubuntu如何显示pcl版本

终端输入&#xff1a; apt-cache show libpcl-dev可以看到&#xff0c;Ubuntu20.04&#xff0c;下载的pcl&#xff0c;应该都是1.10版本的...

wordcloud 字体报错

wordcloud 字体报错 词云库报错&#xff1a;Only supported for TrueType fonts字体文件问题pillow版本的问题wordcloud版本问题&#xff08;我的最终解决方案&#xff09; 词云库报错&#xff1a;Only supported for TrueType fonts 字体文件问题 解决方法 写绝对路径 &…...

使用Matplotlib绘制极轴散点图

散点图对于理解数据可视化中变量之间的相互作用至关重要。虽然散点图经常在笛卡尔坐标中创建&#xff0c;但我们也可以使用Matplotlib在极轴上创建散点图。有了这个功能&#xff0c;人们可以以创新的方式查看圆形或角形数据&#xff0c;例如周期性趋势或定向模式。在本文中&…...

Elasticsearch入门:增删改查详解与实用场景

引言 在我之前做社交架构设计的时候&#xff0c;我们有一项关键且必要的需求&#xff1a;需要存储并记录用户的所有聊天记录。这些记录不仅用于业务需求&#xff0c;也承担了风控审查的职责。因此&#xff0c;在架构设计中&#xff0c;我们需要考虑每天海量的聊天消息量&#…...

【AI论文精读6】SELF-RAG(23.10)附录

【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】 P1&#xff0c;P2&#xff0c;P3 附录 A SELF-RAG 细节 A.1 反思标记&#xff08;reflection tokens&#xff09; 反思标记的定义 下面我们提供了反思标记类型和输出标记的详细定义。前三个方面将在每个片段&#xf…...

sql-labs靶场第十七关测试报告

目录 一、测试环境 1、系统环境 2、使用工具/软件 二、测试目的 三、操作过程 1、寻找注入点 2、注入数据库 ①寻找注入方法 ②爆库&#xff0c;查看数据库名称 ③爆表&#xff0c;查看security库的所有表 ④爆列&#xff0c;查看users表的所有列 ⑤成功获取用户名…...

面试官:MySQL一次到底插入多少条数据合适啊?

前言 大家好&#xff01;在互联网时代&#xff0c;我们的每一个动作&#xff0c;无论是浏览网页、分享动态、点赞、购物或者搜索信息&#xff0c;都会在背后产生数据。这些数据&#xff0c;根据其用途和重要性&#xff0c;可能会被储存到不同的地方&#xff0c;其中最常见的存…...

WSL2 构建Ubuntu系统-轻量级AI运行环境

环境&#xff1a;Win11 软件&#xff1a;WSL2 安装环境&#xff1a;Ubuntu 22.04 检查电脑是否开启虚拟化 打开&#xff1a;任务管理器->性能->CPU CPU 开启虚拟化&#xff08;通常默认是开启的&#xff0c;如果没有开启需要BIOS开启&#xff09; 虚拟化设置&#xff0…...

什么是凸二次规划问题

我们从凸二次规划的基本概念出发&#xff0c;然后解释它与支持向量机的关系。 一、凸二次规划问题的详细介绍 凸二次规划问题是优化问题的一类&#xff0c;目标是最小化一个凸的二次函数&#xff0c;受一组线性约束的限制。凸二次规划是一类特殊的二次规划问题&#xff0c;其…...

解决 Elasticsearch cluster_block_exception 错误的终极指南

Elasticsearch 是一个功能强大的分布式搜索引擎&#xff0c;广泛应用于全文检索、实时分析等场景。 尽管如此&#xff0c;像任何复杂系统一样&#xff0c;它也会遇到一些运行问题&#xff0c;其中较为常见且影响较大的就是 cluster_block_exception 错误。 本文将深入解析这种错…...

QT sql驱动错误QMYSQL driver not loaded

引用文章QMYSQL driver not loaded 根据引用文章&#xff0c;到在编译QT mysql.pro的源码步骤时&#xff0c;构建没有报错&#xff0c;但是在对应的文件夹内没有找到编译好的dll文件&#xff0c;经过全电脑搜寻&#xff0c;找到在此文件夹内。 遇到同样错误的朋友可以找找QT安…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)

cd /home 进入home盘 安装虚拟环境&#xff1a; 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境&#xff1a; virtualenv myenv 3、激活虚拟环境&#xff08;激活环境可以在当前环境下安装包&#xff09; source myenv/bin/activate 此时&#xff0c;终端…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...

react-pdf(pdfjs-dist)如何兼容老浏览器(chrome 49)

之前都是使用react-pdf来渲染pdf文件&#xff0c;这次有个需求是要兼容xp环境&#xff0c;xp上chrome最高支持到49&#xff0c;虽然说iframe或者embed都可以实现预览pdf&#xff0c;但为了后续的定制化需求&#xff0c;还是需要使用js库来渲染。 chrome 49测试环境 能用的测试…...

21-Oracle 23 ai-Automatic SQL Plan Management(SPM)

小伙伴们&#xff0c;有没有迁移数据库完毕后或是突然某一天在同一个实例上同样的SQL&#xff0c; 性能不一样了、业务反馈卡顿、业务超时等各种匪夷所思的现状。 于是SPM定位开始&#xff0c;OCM考试中SPM必考。 其他的AWR、ASH、SQLHC、SQLT、SQL profile等换作下一个话题…...