数据结构之＜散列表＞的介绍

简介

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

1.哈希函数

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

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

2.碰撞处理

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

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

3.装载因子

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

装载因子的影响

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

装载因子的影响操作

1. 插入操作：随着装载因子增大，哈希冲突的概率也增加，这会导致插入操作需要进行更多次的冲突解决，从而影响性能。
2. 查找操作：装载因子增大，可能使得链表长度增加（如果使用链地址法解决冲突），从而增加了查找特定元素所需的比较次数，影响了查找操作的效率。
3. 删除操作：装载因子较小时，删除操作可能较为简单快速，但在较大的装载因子下，删除操作可能会涉及到链表的重组，导致性能下降。

装载因子的控制

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

4.性能分析

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

5.应用

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

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