软考-软件设计师：查找算法-散列表查找（哈希查找）

作者：马育民 • • 阅读：10042

散列表（哈希表）

散列表（Hash Table)，又称 哈希表。散列表是根据 关键字（Key） 直接计算出数据 存储地址 的存储结构

存储地址 = Hash(关键字)

其中 Hash() 称为 散列函数（哈希函数）

散列函数

散列函数构建了与 关键字（key）一一对应的 地址（address），不同的散列方法需要构造不同的散列函数，Hash（key） 就是散列函数。

目标

尽可能让不同关键字映射到不同地址（减少冲突）

散列函数的要求

  • 每一个 关键字（key） 只能有一个 地址（address） 与之对应。
  • 函数值域必须在表长范围之内。
  • 散列地址尽量均匀分布，尽可能的减少冲突。

散列地址

由散列函数的到的地址就是散列地址，address=Hash（key）

装填因子（负载因子）

负载因子是散列表中 已填充空间 与 总空间 的比例，即：已填充空间 / 总空间。

如果负载因子太高，冲突的概率就会增加，这就会影响ASL。一个合理的负载因子是 0.5-0.7

注意：不会避免冲突

查找时间复杂度

最优：O (1)（无冲突、一次定位）
平均：O (1)（α 合理时）
最坏：O (n)（全部冲突，线性探测 / 单链表）

查找效率取决于哪 3 点？

散列函数
冲突处理方法
装填因子 α

冲突

两个不同关键字（key1≠key2），具有相同地址（Hash（key1）==Hash（key2）），就叫发生冲突。

冲突解决

  • 线性探测，简单但可能聚集

  • 链地址法

同义词

计算结果一致的元素：Hash(key1) == Hash(key2)，则key1与key2互称为同义词。

线性探测法

关键字序列：(44,35,14,54)
存储空间 m=10，装填因子较小
p=4 (一般等于存储空间，这里是等于序列长度)
散列函数 h = key % p

处理冲突

当位置有元素时，就往后移一位，如果还有元素，继续往后移

提示：如果后面都放满，从索引是 0 的位置开始判断，如果没有元素，就放入

形成 聚集 现象

链地址法

链地址法通过在每个哈希位置上维护一个数据结构（通常是链表，但也可以是其他类型的数据结构如平衡二叉搜索树等），来存储所有映射到该位置的元素，从而解决这种冲突。

工作原理

  1. 哈希函数：首先，使用哈希函数将键映射到散列表的一个特定索引（或称为桶）。
  2. 存储结构：对于每个可能的哈希值，创建一个链表（或其他集合类型的数据结构）。如果多个键映射到了同一个索引，则这些键对应的值会被添加到这个索引对应的链表中。
  3. 查找操作：要查找某个键，首先计算其哈希值以确定它应该位于哪个桶内，然后遍历该桶中的链表，检查是否存在目标键。
  4. 插入和删除：类似地，插入新元素时，根据哈希值找到正确的桶，并将其添加到链表中；删除元素时，同样需要找到正确的桶并从链表中移除指定元素。

例子

假设我们有一个用于存储整数键的哈希表，使用简单的模运算作为哈希函数（例如，hash(key) = key % table_size），并且选择链表作为每个桶的数据结构。

假设哈希表大小为5 (table_size = 5)，则哈希函数为 key % 5。
初始状态：
0: []
1: []
2: []
3: []
4: []

插入键值对 (7, "apple"), (12, "banana"), (22, "cherry"):
- 7 % 5 = 2 -> 插入到索引2的链表
- 12 % 5 = 2 -> 插入到索引2的链表
- 22 % 5 = 2 -> 插入到索引2的链表

结果:
0: []
1: []
2: [(7, "apple"), (12, "banana"), (22, "cherry")]
3: []
4: []

在这个例子中，键7、12和22都映射到了索引2，因此它们都被放入了索引2对应的链表中。

链地址法的优点

  • 简单直观：实现起来相对简单，容易理解和实现。
  • 动态调整：可以自然地适应不同数量的元素，不需要重新分配整个哈希表的空间。
  • 性能稳定：理论上，在理想情况下（即哈希函数均匀分布且装填因子较小），平均查找时间复杂度接近O(1)。

链地址法的缺点

  • 额外空间开销：每个桶都需要额外的空间来存储链表节点，这增加了内存消耗。
  • 性能下降风险：如果哈希函数设计不当导致大量碰撞，或者装填因子过大，会导致链表过长，进而影响查找效率。

总的来说，链地址法是一种有效的哈希冲突解决方案，尤其适合于那些难以预测负载情况的应用场景。通过选择合适的哈希函数和控制装填因子，可以确保其高效运行。

题

用哈希表存储元素时，需要进行冲突（碰撞）处理，冲突是指
（ ）

A、关键字被依次映射到地址编号连续的存储位置
B、关键字不同的元素被映射到相同的存储位置
C、关键字相同的元素被映射到不同的存储位置
D、关键字被映射到哈希表之外的位置

答案

B

题

设散列函数为 H(key)=key%11，对于关键码序列(23,40,91,17,19,10,31，65，26），用 线性探查法 解决冲突构造的哈希表为（）

分析

通过上面 ABCD 4个选项中的哈希表，发现只有 索引是 0、10 有区别，所以只需要对这两个索引上的元素 10、65 计算就可以得出答案

  1. 由于元素 10 在 65 的前面，所以先算 10：10%11 = 10 ，所以元素 10 应该放在索引 10 的位置上

  2. 然后计算元素 65，65%11 = 10，由于元素 10 放在索引 10 的位置上，所以只能往后移一位，由于后面没有空间，所以从索引 0 开始，即：元素 65 放在索引 0 的位置上

答案

B

参考：
https://blog.csdn.net/Attract1206/article/details/107751927

原文出处：/show_1GWvkF4Wc8i.html

吉ICP备15003043号