数据结构之<散列表>的介绍

2023-12-28 23:45:09

简介


散列表也叫做哈希表,是根据键值对 (key,value) 进行存储的一种数据结构。散列表利用哈希函数将给定的键映射到一个特定的位置(通常是数组索引),这个位置通常被称为哈希值或哈希地址。
这里可以举个微信好友列表的例子说明,存放好友首字母的表对应的就是散列表。

1.哈希函数


哈希函数是散列表的关键部分,它接收一个键作为输入并输出对应的哈希值。哈希函数应该尽可能地将键均匀地映射到散列表的位置上,以减少冲突的概率。一个好的哈希函数应该具有以下特性:

  • 唯一性:对于不同的键,应该生成不同的哈希值。
  • 一致性:对于相同的键,始终生成相同的哈希值。
  • 均匀性:尽可能地减少哈希冲突,即不同的键映射到相同的哈希值的情况。

2.碰撞处理


哈希函数并不总能保证完全避免冲突。当两个或多个键映射到相同的哈希值时,就会发生冲突。常见的处理冲突的方法有:

  • 开放寻址法:冲突发生时,尝试寻找散列表中的下一个位置。这包括线性探测二次探测等方法。这样,每个位置只能存储一个键值对。
  • 链地址法:每个散列表的位置维护一个链表,发生冲突时,新的键值对被插入到链表中。这样,每个位置都可以存储多个键值对。

3.装载因子


表示散列表中已经被占用的位置的比例。装载因子的增加会导致冲突的概率上升,影响散列表的性能。装载因子通常用 λ 表示,计算公式如下:

在这里插入图片描述

装载因子的影响

装载因子直接影响散列表的性能和效率。当装载因子较小时,散列表的空间利用率低,但是查找、插入和删除操作的性能可能会较好,因为冲突的可能性较小。而当装载因子较大时,散列表空间被更充分地利用,但是可能导致哈希冲突增多,降低了操作的效率。

装载因子的影响操作

  1. 插入操作:随着装载因子增大,哈希冲突的概率也增加,这会导致插入操作需要进行更多次的冲突解决,从而影响性能。

  2. 查找操作:装载因子增大,可能使得链表长度增加(如果使用链地址法解决冲突),从而增加了查找特定元素所需的比较次数,影响了查找操作的效率。

  3. 删除操作:装载因子较小时,删除操作可能较为简单快速,但在较大的装载因子下,删除操作可能会涉及到链表的重组,导致性能下降。

装载因子的控制

为了维护散列表的性能,需要对装载因子进行控制。通常,当装载因子达到某个阈值(例如 0.7 或 0.8)时,可以考虑进行散列表的重新哈希(即调整散列表的大小,重新分配存储空间并重新插入元素),以减小装载因子,避免性能下降。

4.性能分析


散列表在良好设计的情况下具有常数时间复杂度(O(1))的性能,但是在最坏情况下可能会退化到线性时间复杂度(O(n))。哈希函数的质量和冲突处理的方法都会影响散列表的性能。

5.应用


  • 字典:用于实现键值对的存储和检索。
  • 缓存:存储计算结果或者频繁访问的数据,以加快访问速度。
  • 数据库索引:用于加速数据库查询。
  • 编译器和解释器:用于符号表和标识符的快速查找。

推荐观看:【数据结构】散列表(哈希表)

文章来源:https://blog.csdn.net/WriteBug001/article/details/135279653
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。