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

哈希表-散列表数据结构


1、什么是哈希表?

哈希表也叫散列表,哈希表是根据关键码值(key value)来直接访问的一种数据结构,也就是将关键码值(key value)通过一种映射关系映射到表中的一个位置来加快查找的速度,这种映射关系称之为哈希函数或者散列函数,存放记录的数组称之为哈希表。

哈希表采用的是一种转换思想,其中一个中要的概念是如何将「Key」转换成数组下标?

在哈希表中,这个过程有哈希函数来完成,但是并不是每个「Key」都需要通过哈希函数来将其转换成数组下标,有些「Key」可以直接作为数组的下标。

举例:

用哈希表来存放员工信息,我们可以利用员工号作为「Key」就可以直接作为数据的下标,不需要通过哈希函数进行转化。

如果我们用员工姓名作为「Key」,这时候我们就需要哈希函数来帮我们转换成数组的下标。

换句话说,哈希函数是帮我们把 非int 的「Key」转化成 int,用来做数组的下标。

在 uthash 开源C代码中,哈希函数主要使用了以下几种:

详细可以参考 https://troydhanson.github.io/uthash/userguide.html

2、哈希表主要解决什么问题?
    

哈希表提供了快速的插入操作和查找操作,无论哈希表总中有多少条数据,插入和查找的时间复杂度都是为O(1),因为哈希表的查找速度非常快,所以在很多程序中都有使用哈希表,例如拼音检查器。

· 事先不需要排序。

· 搜寻速度与数据多少无关。


3、内核中哪些算法用的了哈希表?

 举例:

linux 跑起来的时候 有很多进程,那有很多 task_struct 怎么连接呢?

linux里面有三种数据结构来连接task_struct ,  链表(方便遍历的时候用),树(方便找父进程),哈希表(方便从pid 找到task_struct)。

4、C语言如何使用哈希表?

uthash 是用宏实现的一个头文件,即可实现哈希表的一些列操作。

https://troydhanson.github.io/uthash/userguide.html#_a_hash_in_c

GitHub - troydhanson/uthash: C macros for hash tables and more

参考:

图文并茂详解数据结构之哈希表 - 知乎

相关文章:

哈希表-散列表数据结构

1、什么是哈希表? 哈希表也叫散列表,哈希表是根据关键码值(key value)来直接访问的一种数据结构,也就是将关键码值(key value)通过一种映射关系映射到表中的一个位置来加快查找的速度,这种映射关系称之为哈希函数或者散列函数&…...

C# 强制类型转换和as区别和不同使用场景

文章目录 1.强制类型转换2. as 运算符3.实例总结: 在C#中,as 和 强制类型转换(例如 (T)value)的主要区别在于它们处理类型转换不成功时的行为和适用场景: 1.强制类型转换 使用语法:Type variable (Type)…...

什么是 DDoS 攻击

布式拒绝服务 (DDoS) 攻击是一种恶意尝试,通过大量互联网流量淹没目标或其周围基础设施,从而破坏目标服务器、服务或网络的正常流量。 DDoS 攻击通过利用多个受感染的计算机系统作为攻击流量源来实现有效性。被利用的机器可以包括计算机和其他网络资源。 从高层来看,DDoS 攻…...

c++隐式类型转换与explicit

我们知道,一个float与int做运算时,系统会首先个int类型转换为float类型之后再进行运算,这种隐式类型转换也会发生在类中 看以下例子,定义一个类 class myTime { public:int Hour;myTime() {};myTime(int h) :Hour(h) {}; }; 在…...

BERT Intro

继续NLP的学习,看完理论之后再看看实践,然后就可以上手去kaggle做那个入门的project了orz。 参考: 1810.04805.pdf (arxiv.org) BERT 论文逐段精读【论文精读】_哔哩哔哩_bilibili (强推!)2023李宏毅讲解大模型鼻祖BERT,一小时…...

“To-Do Master“ GPTs:重塑任务管理的趣味与效率

有 GPTs 访问权限的可以点击链接进行体验:https://chat.openai.com/g/g-IhGsoyIkP-to-do-master 部署私人的 To-Do Master 教程:https://github.com/Reborn14/To-Do-Master/tree/main 引言 在忙碌的日常生活中,有效地管理日常任务对于提高生…...

npm安装vue,添加淘宝镜像

如果是第一次使用命令栏可能会遇到权限问题。 解决vscode无法运行npm和node.js命令的问题-CSDN博客 安装 在vscode上面的导航栏选择terminal打开新的命令栏 另外可能会遇到网络或者其他的问题,可以添加淘宝镜像 npm install -g cnpm --registryhttps://registry.…...

LeetCode 2707. 字符串中的额外字符

一、题目 1、题目描述 给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串,每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。 请你采取最优策略分割 s &#xff…...

Js进阶31-DOM 操作专题

1. JavaScript 的组成部分: ECMAScript:简称 ES,它是欧洲计算机协会,大概每年的六月中旬定制语法规范。DOM:全称 Document Object Model,即为文档对象类型。BOM:全称 Browser Object Model&…...

Hive之set参数大全-4

F 指定在使用 FETCH 命令提取查询结果时的序列化/反序列化器 hive.fetch.output.serde 是 Hive 的一个配置参数,用于指定在使用 FETCH 命令提取查询结果时的序列化/反序列化器。 以下是一个示例: -- 设置 hive.fetch.output.serde 为 org.apache.had…...

竞赛保研 基于深度学习的人脸识别系统

前言 🔥 优质竞赛项目系列,今天要分享的是 基于深度学习的人脸识别系统 该项目较为新颖,适合作为竞赛课题方向,学长非常推荐! 🧿 更多资料, 项目分享: https://gitee.com/dancheng-senior/…...

9.建造者模式

文章目录 一、介绍二、代码三、实际使用总结 一、介绍 建造者模式旨在将一个复杂对象的构建过程和其表示分离,以便同样的构建过程可以创建不同的表示。这种模式适用于构建对象的算法(构建过程)应该独立于对象的组成部分以及它们的装配方式的…...

简单的MOV转MP4方法

1.下载腾讯的QQ影音播放器, 此播放器为绿色视频播放器, 除了播放下载好的视频外没有臃肿无用功能 官网 QQ影音 百度网盘链接:https://pan.baidu.com/s/1G0kSC-844FtRfqGnIoMALA 提取码:dh4w 2.用QQ影音打开MOV文件 3.右下角打开影音工具箱 , 选择截取…...

YOLOv8改进 | Neck篇 | 利用ASF-YOLO改进特征融合层(适用于分割和目标检测)

一、本文介绍 本文给大家带来的改进机制是ASF-YOLO(发布于2023.12月份的最新机制),其是特别设计用于细胞实例分割。这个模型通过结合空间和尺度特征,提高了在处理细胞图像时的准确性和速度。在实验中,ASF-YOLO在2018年数据科学竞赛数据集上取得了卓越的分割准确性和速度,…...

基于模块自定义扩展字段的后端逻辑实现(一)

目录 一:背景介绍 二:实现过程 三:字段标准化 四:数据存储 五:数据扩展 六:表的设计 一:背景介绍 最近要做一个系统,里面涉及一个模块是使用拖拉拽的形式配置模块使用的字段表…...

力扣:18.四数之和

一、做题链接:18. 四数之和 - 力扣(LeetCode) 二、题目分析 1.做这一道题之前本博主建议先看上一篇《三数之和》 2.题目分析 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重…...

.netcore 6 ioc注入的三种方式

1、定义接口 public interface MyInterceptorInterface 2、实现接口 public class MyInterceptorImpl : MyInterceptorInterface 在构造中增加以下代码&#xff0c;便于观察 static ConcurrentDictionary<string, string> keyValues new ConcurrentDictionary<s…...

Python轴承故障诊断 (十)基于VMD+CNN-Transfromer的故障分类

目录 1 变分模态分解VMD的Python示例 2 轴承故障数据的预处理 2.1 导入数据 2.2 故障VMD分解可视化 3 基于VMDCNN-Transformer的轴承故障诊断分类 3.1 定义VMD-CNN-Transformer分类网络模型 3.2 设置参数&#xff0c;训练模型 3.3 模型评估 代码、数据如下&#xff1a…...

【复习】人工智能 第7章 专家系统与机器学习

专家系统就是让机器人当某个领域的专家&#xff0c;但这章专家系统不咋考&#xff0c;主要靠书上没有的机器学习。 一、专家系统的基本组成 二、专家系统与传统程序的比较 &#xff08;1&#xff09;编程思想&#xff1a; 传统程序 数据结构 算法 专家系统 知识 推理 &…...

使用 Apache PDFBox 操作PDF文件

简介 Apache PDFBox库是一个开源的Java工具&#xff0c;专门用于处理PDF文档。它允许用户创建全新的PDF文件&#xff0c;编辑现有的PDF文档&#xff0c;以及从PDF文件中提取内容。此外&#xff0c;Apache PDFBox还提供了一些命令行实用工具。 Apache PDFBox提供了创建、渲染、…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...