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

数据结构 （30）计算式查找法——哈希法

news 来源：原创 2025/5/9 11:56:05

前言

       数据结构中的计算式查找法，特别是哈希法（又称散列法、杂凑法、关键字地址计算法），是一种高效的查找技术。

一、哈希法的基本概念

       哈希法是通过一个哈希函数将关键字映射到哈希表中的某个位置，从而实现快速查找的技术。哈希表是一种基于数组的数据结构，其中每个元素都与一个唯一的键值相关联。哈希函数根据关键字计算出在数组中的位置，这个位置称为哈希地址。

二、哈希函数的构造原则与方法

  1. 构造原则：

    • 函数本身便于计算。
    • 计算出来的地址分布均匀，以减少冲突。

  2. 构造方法：

    • 数字分析法：从关键字中选出分布均匀的若干位构成哈希地址。适用于关键字位数比哈希表地址位数多的情况。
    • 平方取中法：先求出关键字的平方值，然后取平方值中间的几位作为哈希地址。适用于无法确定关键字中哪几位分布较均匀的情况。
    • 分段叠加法：将关键字分成位数相等的几部分，然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
    • 除留余数法：假设哈希表的长度为m，p为小于等于m的最大素数，则哈希函数为H(key) = key mod p。其中，mod表示取余运算。这是最简单且常用的哈希函数构造方法。
    • 伪随机数法：采用一个随机函数作为哈希函数，即H(key) = random(key)。这种方法适用于需要较高随机性的场景。

三、哈希表的查找过程

  1. 计算哈希地址：根据哈希函数和关键字计算出哈希地址。
  2. 访问哈希表：直接访问哈希表中对应哈希地址的元素。
  3. 处理冲突：如果哈希地址上已有元素（即发生冲突），则采用适当的冲突解决方法进行处理。

四、冲突解决方法

  1. 开放定址法：当关键字key的初始哈希地址出现冲突时，以该地址为基础产生另一个地址，如果仍然冲突，则再以该新地址为基础产生下一个地址，直到找到一个不冲突的地址为止。这种方法包括线性探测再散列、二次探测再散列和伪随机数探测再散列等。
  2. 再哈希法：同时构造多个不同的哈希函数。当哈希地址冲突时，依次使用这些哈希函数进行计算，直到找到一个不冲突的地址为止。这种方法不易产生聚集，但增加了计算时间。
  3. 链地址法：将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中。查找、插入和删除操作主要在同义词链中进行。这种方法适用于哈希表较大且元素分布不均匀的情况。
  4. 建立公共溢出区：将哈希表分为基本表和溢出表两部分。凡是和基本表发生冲突的元素一律填入溢出表。这种方法简单易懂，但可能增加查找时间。

五、哈希法的优缺点

优点：

  1. 查找效率高：哈希查找的时间复杂度为O(1)，即常数时间。这使得哈希查找在大规模数据集合中具有很高的效率。
  2. 空间利用率高：哈希查找只需要存储关键字和对应的值，不需要额外的空间来存储指针等信息。
  3. 可扩展性强：哈希查找可以通过调整哈希函数和哈希表的大小来适应不同的数据集合。

缺点：

  1. 哈希冲突：当两个不同的关键字映射到同一个位置时，会发生哈希冲突。冲突会导致查找效率降低，需要额外的时间来解决。
  2. 哈希函数设计困难：设计一个好的哈希函数并不容易。一个好的哈希函数应该能够将关键字均匀地映射到哈希表中，以减少冲突的发生。然而，在实际应用中，很难找到一个完美的哈希函数来满足所有需求。
  3. 不支持范围查找：哈希查找只能支持精确查找，无法支持范围查找。如果需要查找某个范围内的元素，就需要使用其他数据结构或算法。
  4. 删除操作困难：在哈希表中删除元素时，需要确保删除后不会破坏哈希表的性质（如保持链表的完整性或重新计算哈希地址等）。这可能导致删除操作的时间复杂度变高。

总结

       综上所述，哈希法是一种高效的查找技术，具有查找效率高、空间利用率高和可扩展性强等优点。然而，它也存在哈希冲突、哈希函数设计困难、不支持范围查找和删除操作困难等缺点。在实际应用中，需要根据具体需求选择合适的哈希函数和解决冲突的方法来实现哈希查找。

 结语    

清醒是知足常乐

而非奢望过多

！！！

相关文章：

数据结构 （30）计算式查找法——哈希法

前言 数据结构中的计算式查找法，特别是哈希法（又称散列法、杂凑法、关键字地址计算法），是一种高效的查找技术。 一、哈希法的基本概念 哈希法是通过一个哈希函数将关键字映射到哈希表中的某个位置，从而实现快速查找的技…...

编程日记 2025/5/9 11:56:05

电子商务人工智能指南 4/6 - 内容理解

介绍 81% 的零售业高管表示， AI 至少在其组织中发挥了中等至完全的作用。然而，78% 的受访零售业高管表示，很难跟上不断发展的 AI 格局。 近年来，电子商务团队加快了适应新客户偏好和创造卓越数字购物体验的需求。采用 AI 不再是一…...

编程日记 2025/5/4 18:57:22

交易系统：线上交易系统流程详解

大家好，我是汤师爷~ 今天聊聊线上交易系统流程详解。 线上交易系统为新零售连锁商家提供一站式线上交易解决方案。其核心目标是，通过数字化手段扩大商家的服务范围，突破传统门店的地理限制。系统支持电商、O2O等多种业务形态，为…...

编程日记 2025/5/9 11:06:18

如何通过自学成长为一名后端开发工程师？

大家好，我是袁庭新。最近，有星友向我提出了一个很好的问题：如何通过自学成为一名后端开发工程师？ 为了解答这个疑问，我特意制作了一个视频来详细分享我的看法和建议。 戳链接：如何通过自学成长为一名后端开…...

编程日记 2025/5/3 18:05:13

实际车辆行驶轨迹与预设路线偏离检测的Java实现

准备工作 本项目依赖于两个关键库：JTS Topology Suite（简称JTS），用于几何对象创建和空间分析；以及GeoTools，用于处理坐标转换和其他地理信息任务。确保开发环境中已经包含了这两个库，并且正确配…...

编程日记 2025/5/7 12:45:30

pci_resource相关函数

一、介绍 pci_resource_start函数用于获取PCI设备中指定Bar寄存器记录资源起始地址， 函数原型： resource_size_t pci_resource_start(struct pci_dev *dev, int bar) 参数： dev: PCI 设备结构体指针 bar: BAR 寄存器索引 (0-5) 返回&a…...

编程日记 2025/5/9 0:14:03

Android Studio 历史版本下载

Android Studio 历史版本下载 官方链接：https://developer.android.google.cn/studio/archive 通过gradle插件版本反查Android Studio历史版本 Android Studio Ladybug | 2024.2.1 October 1, 2024 【https://redirector.gvt1.com/edgedl/android/studio/ide-zip…...

编程日记 2025/5/9 5:31:07

Jupyter Lab打印日志

有时候在 jupyter 中执行运行时间较长的程序，且需要一直信息，但是程序执行到某些时候就不再打印了。 可以开启 日志控制台，将日志信息记录在控制台中。 参考：https://www.autodl.com/docs/jupyterlab/...

编程日记 2025/5/9 11:06:18

guava缓存的get方法的回调函数讲解一下

CacheBuilder.newBuilder()//设置缓存初始大小，应该合理设置，后续会扩容.initialCapacity(10)//最大值.maximumSize(100)//并发数设置.concurrencyLevel(5)//缓存过期时间，写入后10分钟过期.expireAfterWrite(600,TimeUnit.SECONDS)//统计缓存…...

编程日记 2025/5/9 11:24:59

【双分派小结】

双分派（Double Dispatch）是一种面向对象编程中的设计模式，通常用于实现多态性，尤其是在涉及多个对象交互时。它的基本思想是通过两个不同的对象来确定方法调用，而不仅仅是依赖于一个对象。 双分派的工作原理 在普通的…...

编程日记 2025/5/8 15:34:29

Python100道练习题

Python100道练习题 BIlibili 1、两数之和 num1 20 num2 22result num1 num2print(result)2、一百以内的偶数 list1 []for i in range(1,100):if i % 2 0:list1.append(i) print(list1)3、一百以内的奇数 # 方法一 list1 [] for i in range(1,100):if i % 2 ! 0:lis…...

编程日记 2025/5/9 11:08:22

Scala—Slice（提取子序列）方法详解

Scala—Slice（提取子序列）方法详解 在 Scala 中，slice 方法用于从集合中提取一个连续的子序列（切片）。可以应用于多种集合类型，如 List、Array、Seq 等。 一、slice 方法的定义 slice 根据提供的起始索引…...

编程日记 2025/5/9 11:43:46

nginx根据报文里字段转发至不同地址

nginx接收到post请求.请求报文里是一个json字符串，字符串里有个字段id。 根据id不同，转发到不同地址。 如果idaaa,转发到www.aaa.com.test 如果idbbb,转发到www.bbb.com.test 如何配置,请提供一个nginx.conf 要在 Nginx 中根据 POST 请求的 JSON 负载中的…...

编程日记 2025/5/9 11:47:50

Kafka单机及集群部署及基础命令

目录 一、 Kafka介绍1、kafka定义2、传统消息队列应用场景3、kafka特点和优势4、kafka角色介绍5、分区和副本的优势6、kafka 写入消息的流程 二、Kafka单机部署1、基础环境2、iptables -L -n配置3、下载并解压kafka部署包至/usr/local/目录4、修改server.properties5、修改/etc…...

编程日记 2025/5/9 11:15:30

TCP Robot Send Recive

Function main String data$ 定义字符串变量 SetNet #205, "192.168.0.1", 2004, CRLF, NONE, 0 设置端口号IP地址 OpenNet #205 As Server 端口号对应pc机的端口号 Print "等待201端口连接" WaitNet #201 等待201网…...

编程日记 2025/5/3 19:28:23

旅游管理系统｜Java｜SSM｜VUE｜ 前后端分离

【重要1⃣️】前后端源码万字文档部署文档 【重要2⃣️】正版源码有问题包售后 【包含内容】 【一】项目提供非常完整的源码注释 【二】相关技术栈文档 【三】源码讲解视频 【其它服务】 【一】可以提供远程部署安装&#xf…...

编程日记 2025/5/9 11:20:49

qt-everywher交叉编译e-src-5.15.2

简化配置的方式： 你完全可以通过直接配置 安装目录、编译链 和 目标架构 来完成交叉编译，而不需要修改 mkspecs 配置。以下是如何通过简化配置来进行交叉编译 Qt 的步骤。 准备交叉编译工具链 首先，确保你已经安装了交叉编译工具链&#xff…...

编程日记 2025/5/3 4:10:55

Cursor vs VSCode：主要区别与优势分析

Cursor - The AI Code Editor 1. AI 集成能力 Cursor的优势 原生AI集成： # Cursor可以直接通过快捷键调用AI # 例如：按下 Ctrl K 可以直接获取代码建议 def complex_function():# 在这里，你可以直接询问AI如何实现功能# AI会直接在编辑器中…...

编程日记 2025/5/4 12:51:24

Qt 小项目 学生管理信息系统

主要是对数据库的增删查改的操作 登录/注册界面： 主页面： 添加信息： 删除信息： 删除第一行（支持多行删除） 需求分析： 用QT实现一个学生管理信息系统，数据库为MySQL 要求&#xf…...

编程日记 2025/5/9 11:33:22

Hadoop3集群实战：从零开始的搭建之旅

目录 一、概念 1.1 Hadoop是什么 1.2 历史 1.3 三大发行版本（了解） 1.4 优势 1.5 组成💗 1.6 HDFS架构 1.7 YARN架构 1.8 MapReduce概述 1.9 HDFS\YARN\MapReduce关系 二、环境准备 2.1 准备模版虚拟机 2.2 安装必要软件 2.3 安…...

编程日记 2025/5/9 9:58:40

软件工程复习记录

基本概念 软件工程三要素：方法、工具、过程 软件开发方法：软件开发所遵循的办法和步骤，以保证所得到的运行系统和支持的文档满足质量要求。 软件开发过程管理 软件生命周期：可行性研究、需求分析、概要设计、详细设计、编码、测…...

编程日记 2025/5/9 11:22:54

爬虫运行后数据如何存储？

爬虫运行后获取的数据可以存储在多种不同的存储系统中，具体选择取决于数据的规模、查询需求以及应用场景。以下是一些常见的数据存储方法： 1. 文件系统 对于小型项目或临时数据存储，可以直接将数据保存到本地文件中。常见的文件格式包括&…...

编程日记 2025/5/9 3:37:13

【C语言】C语言的潜规则：运行环境对C程序执行特性的影响

C语言的潜规则：C语言的执行会因为它的运行环境被赋予不同的特性 C语言是一种非常底层、高效、灵活的编程语言，但这种灵活性也带来了很多不确定性。C语言的行为在很大程度上依赖于其运行环境（编译器、操作系统、硬件架构等）。这也…...

编程日记 2025/5/9 11:38:32

Win11 24h2 不能正常ensp

Win11 24h2 不能正常ensp 因为Win11 24h2的内核大小更改，目前virtualbox在7.1.4中更新解决了。而ensp不支持5.2.44之后的virtualbox并已停止维护，不再进行5.2.44修复，virtualbox 5.2.24的ntdll文件sizeofimage问题，此问题导致ens…...

编程日记 2025/5/8 19:06:58

【认证法规】安全隔离变压器

文章目录 定义反激电源变压器 定义 安全隔离变压器（safety isolating transformer），通过至少相当于双重绝缘或加强绝缘的绝缘使输入绕组与输出绕组在电气上分开的变压器。这种变压器是为以安全特低电压向配电电路、电器或其它设备供电而设计…...

编程日记 2025/5/9 11:37:33

【北京迅为】iTOP-4412全能版使用手册-第六十七章 USB鼠标驱动详解

iTOP-4412全能版采用四核Cortex-A9，主频为1.4GHz-1.6GHz，配备S5M8767 电源管理，集成USB HUB,选用高品质板对板连接器稳定可靠，大厂生产，做工精良。接口一应俱全，开发更简单,搭载全网通4G、支持WIFI、蓝牙、…...

编程日记 2025/5/4 13:42:50

MFEM源码分析：代数库

数值计算引擎通常需要将表征物理模型的数学模型转化为线性/非线性方程组，进而求解这些线性/非线性方程组来获取数值解。因此，代数库自然成为数值计算引擎不可或取的模块。 而且，普遍认为，代数库的性能在很大程度上决定数值计算引…...

编程日记 2025/5/9 11:08:22

全景图相关算法学习笔记

目录 ldm3d CVPR 2024 Highlight 文本生360全景！PanFusion 全景图光流学习 一张2D全景图可合成高质量的360度3D场景 全景图生成3d ldm3d https://huggingface.co/Intel/ldm3d-pano CVPR 2024 Highlight 文本生360全景！PanFusion 文生图&#xff0…...

编程日记 2025/5/9 11:34:24

3D 目标检测：从萌芽到前沿的技术演进之路

亲爱的小伙伴们😘，在求知的漫漫旅途中，若你对深度学习的奥秘、JAVA 、PYTHON与SAP 的奇妙世界，亦或是读研论文的撰写攻略有所探寻🧐，那不妨给我一个小小的关注吧🥰。我会精心筹备，在…...

编程日记 2025/5/9 8:47:33

泷羽sec:shell编程(9)不同脚本的互相调用和重定向操作

声明： 学习视频来自B站up主 泷羽sec 有兴趣的师傅可以关注一下，如涉及侵权马上删除文章，笔记只是方便各位师傅的学习和探讨，文章所提到的网站以及内容，只做学习交流，其他均与本人以及泷羽sec团队无关&#…...

编程日记 2025/5/9 1:29:54

Java Web 3 Axios Vue组件库

一 Ajax 1 同步 异步 2 原生Ajax 比较繁琐 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Documen…...

编程日记 2025/5/6 17:31:47

探索未来驾驶：全面解析现代汽车高级辅助驾驶系统功能（APA 、SDA 、TBA、RPA、HPA、PEB）

随着科技的不断进步&#xff0c;汽车行业正在经历一场革命&#xff0c;自动驾驶技术逐渐成为现实。从自适应巡航控制到完全自动驾驶&#xff0c;各种高级驾驶辅助系统&#xff08;ADAS&#xff09;正在改变我们的驾驶方式。今天&#xff0c;我们将深入探讨几种关键的高级驾驶辅…...

编程日记 2025/5/6 20:57:01

MYSQL - 索引详解

一 什么是索引&#xff1f; 实际上在上一篇介绍MYSQL的体系结构当中我们稍微提及了一点&#xff0c;在引擎层&#xff0c;我们提到不同的引擎对应的索引的实现方式&#xff0c;选择是不一样的。 简单理解&#xff0c;索引&#xff08;index&#xff09;其实就是一种帮助MYSQL高…...

编程日记 2025/5/1 22:49:31

AI智能体Prompt预设词指令大全+GPTs应用使用

AI智能体使用指南 直接复制在AI工具助手中使用&#xff08;提问前&#xff09; 可前往SparkAi系统用户官网进行直接使用 SparkAI系统介绍文档&#xff1a;Docs 常见AI智能体GPTs应用大全在线使用 自定义添加制作AI智能体进行使用&#xff1a; 文章润色器 你是一位具有敏锐洞察…...

编程日记 2025/5/8 19:45:17

美团一面，有点难度

前几天分享过一篇训练营的朋友在阿里的一面面经&#xff0c;挺简单的她也是很轻松的过了&#xff0c;感兴趣的可以看一下我之前发的文章。 今天要分享的还是她的面经&#xff0c;美团的一面&#xff0c;感觉比阿里的难一些&#xff0c;各位观众老爷你怎么看&#xff1f; 自我介…...

编程日记 2025/5/8 17:26:04

axios取消请求

Axios 使用 cancel token 取消请求 1、先在axios请求中加上cancelToken import request from ../utils/request // 配置过的Axios 对象 import axios from axios export function getDetail(params, that) { return request({url: /api/indexlineage/detail, method: get,par…...

编程日记 2025/5/6 15:38:22

Spark简介

Spark简介 菜鸟弹性分布式数据集 (RDDs)参考 Spark通过两种方式使用Hadoop&#xff1a;一种是存储&#xff0c;另一种是处理。由于Spark具有自己的集群管理计算&#xff0c;因此仅将Hadoop用于存储目的。 Spark 的关键思想是- [Resilient Distributed Datasets&#xff08;RDD…...

编程日记 2025/5/7 17:41:40

visual studio2017版本的安装下载

绝绝子&#xff0c;官网找了半天都不知道在哪里下载的&#xff0c;和当初下载旧版本的qt一样难受&#xff0c;还是用百度云吧&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 参考文章&#xff1…...

编程日记 2025/5/7 4:15:53

【Linux】ubuntu下一键配置vim

&#x1f525;个人主页&#x1f525;&#xff1a;孤寂大仙V &#x1f308;收录专栏&#x1f308;&#xff1a;Linux &#x1f339;往期回顾&#x1f339;&#xff1a;Linux权限&#xff08;超详细彻底搞懂Linux的权限&#xff09; &#x1f516;流水不争&#xff0c;争的是滔滔…...

编程日记 2025/5/1 22:03:09

[光源控制] UI调节光源亮度参数失效

📢博客主页：https://loewen.blog.csdn.net📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！📢本文由 丶布布原创，首发于 CSDN，转载注明出处🙉📢现在的付出，都会是一种沉淀，只为让你成为更好的人✨文章预览： 一. 前言二. 串口调试助手辅助排查接线问题二. …...

编程日记 2025/5/9 0:42:43

C语言学习：速通指针（2）

这里要学习的有以下内容 1. const修饰指针 2. 野指针 3. assert断⾔ 4. 指针的使⽤和传址调⽤ 那么从这里开始 1. const 修饰指针 const修饰变量 首先我们知道变量是可以修改的&#xff0c;如果把变量的地址交给⼀个指针变量&#xff0c;通过指针变量的也可以修改这个变…...

编程日记 2025/5/8 11:54:30

方案拆解 | 打击矩阵新规频出！2025矩阵营销该怎么玩？

社媒平台的矩阵营销又要“变天”了&#xff1f;&#xff01; 11月18日&#xff0c;小红书官方发表了被安全薯 称为“小红书史上最严打击黑灰产专项”新规&#xff0c;其中就包括黑灰产矩阵号的公告。 ▲ 图源&#xff1a;小红书 实际上&#xff0c;不包括这次&#xff0c;今年…...

编程日记 2025/5/7 17:41:43

Ubuntu22.04深度学习环境安装【cuda+cudnn】

为了复现一篇深度学习论文&#xff0c;特意安装了Linux系统。前一天已经安装Linux显卡驱动&#xff0c;现在需要安装cuda、cudnn等。 论文代码 论文PDF 确定包版本&#xff1a; 根据论文提供的代码。在requirements.txt中发现cuda版本为11.7,cudnn为8.5.0&#xff0c;python没…...

编程日记 2025/5/5 21:24:15

etcd分布式存储系统快速入门指南

在分布式系统的复杂世界中&#xff0c;确保有效的数据管理至关重要。分布式可靠的键值存储在维护跨分布式环境的数据一致性和可伸缩性方面起着关键作用。 在这个全面的教程中&#xff0c;我们将深入研究etcd&#xff0c;这是一个开源的分布式键值存储。我们将探索其基本概念、特…...

编程日记 2025/5/7 2:06:52

dataTable

在 C# 中&#xff0c;DataTable 是 .NET Framework 中用于处理数据表格的一个类&#xff0c;属于 System.Data 命名空间。它是一种内存中表示数据表的结构&#xff0c;通常用于临时存储和操作数据&#xff0c;类似于数据库中的表。DataTable 的主要特点是行列结构&#xff0c;其…...

编程日记 2025/5/4 7:20:08

Flink学习连载文章11--双流Join

双流 Join 和两个流合并是不一样的 两个流合并&#xff1a;两个流变为 1 个流 union connect 双流 join: 两个流 join&#xff0c;其实这两个流还是原来的&#xff0c;只是满足条件的数据会变为一个新的流。 可以结合 sql 语句中的 union 和 join 的区别。 在离线 Hive 中&…...

编程日记 2025/5/9 3:50:55

RayLink远程控制技术助力教育领域的创新应用研究

远程控制技术在教育领域的应用确实改变了传统教学模式。想象一下&#xff0c;无论身处何地&#xff0c;只要有网络连接&#xff0c;就能通过远程软件加入课堂&#xff0c;这种体验是不是很吸引人&#xff1f;虽然远程控制听起来很技术化&#xff0c;但别担心&#xff0c;小编今…...

编程日记 2025/5/6 17:56:48

【Qt移植LVGL】QWidget手搓LVGL软件仿真模拟器（非直接运行图形库）

【Qt移植LVGL】QWidget手搓LVGL软件仿真模拟器&#xff08;非直接运行图形库&#xff09; 打包开源地址&#xff1a; Qt函数库gitee地址 更新以gitee为准 移植后的demo工程&#xff1a; gitee 有些没实现的 后续我会继续优化 文章目录 别碰瓷看清楚&#xff1a;是移植&#…...

编程日记 2025/5/6 6:38:22

PostgreSQL UNION 操作符

PostgreSQL UNION 操作符 引言 PostgreSQL 是一种功能强大的开源对象关系型数据库管理系统，它以其稳定性、可靠性和先进的特性而闻名。在处理数据库查询时，我们经常需要合并来自不同表的数据，或者合并同一表的不同查询结果。这时，UNION 操作符就变得非常有用。本文将详细…...

编程日记 2025/5/6 11:40:17

spring boot 测试 mybatis mapper类

spring boot 测试 mybatis mapper类 针对 mybatis plus不启动 webserver指定加载 xml 【过滤 “classpath*:/mapper/**/*.xml” 下的xml】, mapper xml文件名和mapper java文件名称要一样&#xff0c;是根据文件名称过滤的。默认情况加载和解析所有mapper.xml 自定义 MapperT…...

编程日记 2025/5/8 0:02:50