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

数据结构:哈希表

1.哈希表

哈希表(hash table),又称散列表,它通过建立键 key 与值 value 之间的映射,实现高效的元素查询。具体而言,我们向哈希表中输入一个键 key ,则可以在 O(1) 时间内获取对应的值 value 。

2.哈希表实现

我们先考虑最简单的情况,仅用一个数组来实现哈希表。在哈希表中,我们将数组中的每个空位称为桶(bucket),每个桶可存储一个键值对。因此,查询操作就是找到 key 对应的桶,并在桶中获取 value 。

3.哈希冲突与扩容

从本质上看,哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间,而输入空间往往远大于输出空间。因此,理论上一定存在“多个输入对应相同输出”的情况。

通常情况下哈希函数的输入空间远大于输出空间,因此理论上哈希冲突是不可避免的。比如,输入空间为全体整数,输出空间为数组容量大小,则必然有多个整数映射至同一桶索引。

哈希冲突会导致查询结果错误,严重影响哈希表的可用性。为了解决该问题,每当遇到哈希冲突时,我们就进行哈希表扩容,直至冲突消失为止。此方法简单粗暴且有效,但效率太低,因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率,我们可以采用以下策略。

  1. 改良哈希表数据结构,使得哈希表可以在出现哈希冲突时正常工作。
  2. 仅在必要时,即当哈希冲突比较严重时,才执行扩容操作。

哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。

(1)链式地址

在原始哈希表中,每个桶仅能存储一个键值对。链式地址(separate chaining)将单个元素转换为链表,将键值对作为链表节点,将所有发生冲突的键值对都存储在同一链表中。

原文地址:https://blog.csdn.net/niikkoo/article/details/142064540
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/297174.html

相关文章:

  • java后端保存的本地图片通过ip+端口直接访问
  • LG AI研究开源EXAONE 3.0:一个7.8B双语语言模型,擅长英语和韩语,在实际应用和复杂推理中表现出色
  • vim常用快捷键
  • 数据库的操作:数据完整性约束是什么?
  • linux-基础知识3
  • Arduino IDE的安装
  • springcloud间通信的方式
  • 非标金属零件加工的质量与效率是如何体现的?
  • Figma如何给设计的UI套样机
  • RK3562 NPU供电要求
  • wordpress做后台的资讯类小程序源码
  • Anaconda Prompt 安装paddle2.6报错
  • 线程池实现服务端
  • Linux Runtime PM(运行时电源管理)框架API
  • 97.游戏的启动与多开-共享内存多开检测
  • 九,自定义转换器详细操作(附+详细源码解析)
  • c语言--力扣简单题目(移除链表元素)讲解
  • UE4_后期处理_后期处理材质及后期处理体积一
  • 从Milvus迁移DashVector
  • 久久派安装启用USB摄像头(基于mjpg-streamer)