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

数据结构-散列表

news 2025/8/5 3:33:45

列表（Hash Table），又称哈希表，是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关
例：有一堆数据元素，关键字分别为｛19，14，23，1，68，20，84，27，55，11，10，79｝，散列函数H(key)=key%13
若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词”
通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”
image.png
用拉链法（又称链接法、链地址法）解决‘冲突’：把所有“同义词”存储在一个链表中

散列查找

image.png
image.png
image.png
image.png

image.png
image.png
image.png
image.png

常见的散列函数

设计目标–让不同关键字的冲突尽可能地少
除留余数法—H(key)=key%p
散列表表长为m，取一个不大于m但最接近或等于m的质数p
质数又称素数。指除了1和此整数自身外，不能被其他自然数整除的数
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

处理冲突的方法–开放定址法

image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

查找操作

image.png
image.png
image.png
image.png
image.png
image.png

删除操作

image.png
image.png
image.png

查找效率分析（ASL）

image.png
image.png
image.png

平方探测法

image.png
image.png
image.png
image.png

伪随机序列法

image.png
image.png
image.png
image.png

http://www.lryc.cn/news/229248.html

相关文章：

  • 一款IT团队都在用的私有化知识库，技术开放，还开源了！
  • 解决 docker compose 官方 MySQL 镜像在容器中不能输入中文的问题
  • 基于连续Hopfield神经网络优化——旅行商问题优化计算
  • SpringBoot整合Activiti7——定时器事件（九）
  • 轻量封装WebGPU渲染系统示例＜29＞- 深度模糊DepthBlur(源码)
  • LeetCode226. Invert Binary Tree
  • Java设计模式-创建型模式-建造者模式
  • PyQt中QFrame窗口中的组件不显示的原因
  • git 命令行回退版本
  • IntelliJ IDEA 安装 GitHub Copilot插件 （最新）
  • viewpage选择器
  • vue中如何将json数组指定的key赋值给el-form-item并均匀的分成2列
  • 笔记本分屏怎么操作？3个方法提高工作效率！
  • Android 使用poi生成Excel ,word并保存在指定路径内
  • 嵌入式杂记 -- MCU的大小端模式
  • 对这套BI零售数据分析方案心动，是零售人天性
  • vuekeyclock 集成
  • ARM Linux 基础学习 / 配置交叉编译工具链 / 编译 Linux 应用和驱动 / 编译内核
  • 通讯协议学习之路(实践部分)：SPI开发实践
  • 【系统安装】ubuntu20.04启动盘制作，正经教程，小白安装教程，百分百成功安装
  • 2023云计算发展趋势
  • C# .NET Core API Controller以及辅助专案
  • asp.net图书管理系统
  • 概念解析 | LoRA:低秩矩阵分解在神经网络微调中的作用
  • 前端---CSS的盒模型
  • Linux可以投屏到电视吗？用网页浏览器就能投屏到电视！
  • 云汇优想：抖音矩阵系统有哪些类型？
  • XSS 漏洞的理解
  • cocosCreator 之内存管理和释放
  • 飞天使-template模版相关知识