哈希表

• 约束条件：

  • 元素 42、23 和 34 必须在 52 和 33 之前插入。
  • 元素 46 必须在 33 之前插入。

• 计算方式：
  $$ \text{不同序列总数} = 3! \times 5 = 30 $$

• 公式解析：

  • 3! 表示 42、23 和 34 可以以任意顺序插入（共 6 种排列）。
  • 5 表示 46 可以在满足约束的前提下插入到 5 个合法位置中。

简单均匀哈希函数是一种理想化的哈希函数，它能将元素均匀地分布到哈希表的各个槽位中。此外，每个待哈希元素被分配到任意槽位的概率相等，且与其他元素无关。前 3 次插入后第一个 3 个槽位未被填充的概率为：

• 第一个元素不放入前 3 个槽位的概率：$ \frac{97}{100} $
• 第二个元素不放入前 3 个槽位的概率：$ \frac{97}{100} $
• 第三个元素不放入前 3 个槽位的概率：$ \frac{97}{100} $

综合计算得：
$$ \left(\frac{97}{100}\right) \times \left(\frac{97}{100}\right) \times \left(\frac{97}{100}\right) = \frac{97^3}{100^3} $$

由于使用了 mod 10 操作，因此结果的最后一位数字是关键。如果对 0 到 9 的所有数字进行立方运算，得到的结果如下：

因此，从 0 到 2020 的所有数字会被均匀地分配到 10 个桶中。如果我们制作平方表，则无法获得均匀分布。在下表中，1、4、6 和 9 重复出现，因此这些桶会有更多条目，而 2、3、7 和 8 则为空。

另一种方法是利用幂次循环的概念：

• (a) (0,1,4,9,6,5,6,9,4,1,0) 循环
• (b) (0,1,8,7,4,5,6,3,2,9) 循环
• (c) (0,1,4,9,6,5,6,9,4,1,0) 循环
• (d) (0,2,4,6,8) 循环

因此，只有 h(i) =i³ mod 10 涵盖了 0 到 9 的所有数字。故选项 (C) 正确。

哈希函数被定义为任何可以将任意大小的数据映射到固定大小数据的函数。哈希函数返回的值称为哈希值、哈希码、摘要或简称为哈希：
陈述 1 正确

是的，哈希函数确实可能将不同的值映射到内存中的同一位置，这就是冲突发生的原因，我们有不同技术来处理这个问题：
陈述 3 正确

示例验证：

• 假设哈希函数 h(x) = x % 3
• 验证陈述 1：无论 ‘x’ 的值是什么，h(x) 都会生成一个固定的映射位置（0, 1, 或 2）
• 验证陈述 3：当 x=4 或 x=7 时，h(x)=1，在两种情况下都发生了冲突

结论：

• 陈述 I 和 III 成立
• 陈述 II 错误（哈希函数始终输出固定长度结果）

• 关键因素：冲突概率主要由两个因素决定：
  • 被哈希项的数量 $n$
  • 哈希表的大小 $m$
• 变化趋势：
  • 当 $n$ 增加时，冲突概率 上升
  • 当 $m$ 增大时，冲突概率 下降
• 数学表达式：因此，冲突概率可估计为 $ O\left(\frac{n}{m}\right) $

(a) 大小为 10 的哈希表索引范围是 0 到 9。哈希函数为 h(x) = ((ord(x) - ord(A) + 1)) mod 10。对于字符串 K R P C S N Y T J M：

• K 插入索引：(11-1+1) mod 10 = 1
• R 插入索引：(18-1+1) mod 10 = 8
• P 插入索引：(16-1+1) mod 10 = 6
• C 插入索引：(3-1+1) mod 10 = 3
• S 插入索引：(19-1+1) mod 10 = 9
• N 插入索引：(14-1+1) mod 10 = 4
• Y 插入索引：(25-1+1) mod 10 = 5
• T 插入索引：(20-1+1) mod 10 = 0
• J 插入索引：(10-1+1) mod 10 = 0 // 第一次冲突发生
• M 插入索引：(13-1+1) mod 10 = 3 // 第二次冲突发生

仅 J 和 M 导致冲突。

(b) 最终哈希表如下：

0 T  
1 K  
2 J  
3 C  
4 N  
5 Y  
6 P  
7 M  
8 R  
9 S  

解析：
哈希表通过键值映射实现常数级时间复杂度 $O(1)$ 的查找操作。

• 二分查找需在有序数组中进行，时间复杂度为 $O(\log n)$
• 线性查找需遍历数据，时间复杂度为 $O(n)$
• AVL 树查找基于平衡二叉树结构，时间复杂度为 $O(\log n)$
  哈希函数的理想情况下能直接定位存储位置，因此具有最优的查找效率。

• 给定的哈希函数：h(K) = floor(m (K*A mod 1))
• 其中 $ A = \frac{\sqrt{5} - 1}{2} $
• 计算过程：
  $$ \begin{align*} h(123456) &= \left\lfloor 10000 \times \left(123456 \times \frac{\sqrt{5} - 1}{2} \mod 1 \right) \right\rfloor \\ &= \left\lfloor 10000 \times (76300.004115 \mod 1) \right\rfloor \\ &= \left\lfloor 10000 \times 0.004115 \right\rfloor \\ &= \left\lfloor 41.15 \right\rfloor = 41 \end{align*} $$
• 因此，选项 (B) 正确。

• 661 的哈希值：661 % 13 = 11 → 插入位置 11
• 182 的哈希值：182 % 13 = 0 → 插入位置 0
• 24 的哈希值：24 % 13 = 11（冲突）
  • 线性探测找到下一个可用位置 12
• 103 的哈希值：103 % 13 = 12（冲突）
  • 线性探测找到下一个可用位置 1
• 因此键值 103 最终插入位置为 1，对应选项 (B)

Ck(M) = (kM + 13) mod 26

此处，‘A’ = 0, ‘B’ = 1, …….‘Z’ = 25

• I 的加密过程

  • 明文字符 I 对应数值 8
  • 代入公式：$7 \times 8 + 13 = 69$
  • 取模运算：$69 \mod 26 = 17$
  • 数值 17 对应密文字符 R

• S 的加密过程

  • 明文字符 S 对应数值 18
  • 代入公式：$7 \times 18 + 13 = 139$
  • 取模运算：$139 \mod 26 = 9$
  • 数值 9 对应密文字符 J

• R 的加密过程

  • 明文字符 R 对应数值 17
  • 代入公式：$7 \times 17 + 13 = 132$
  • 取模运算：$132 \mod 26 = 2$
  • 数值 2 对应密文字符 C

• O 的加密过程

  • 明文字符 O 对应数值 14
  • 代入公式：$7 \times 14 + 13 = 105$
  • 取模运算：$105 \mod 26 = 7$
  • 数值 7 对应密文字符 H

综上，明文 ISRO 加密后得到密文 RJCH，因此选项 (A) 正确。

解析：

1. 哈希函数定义：
   $$ h(k) = \lfloor m(kA \bmod 1) \rfloor $$

2. 代入已知参数：

   • $ m = 100 $
   • $ k = 123456 $
   • 黄金比例常数 $ A \approx 0.618033 $

3. 计算过程：

   • 第一步：
     $$ 123456 \times 0.618033 = 76189.882048 $$
   • 第二步（取小数部分）：
     $$ 76189.882048 \bmod 1 = 0.882048 $$
   • 第三步（乘以表长）：
     $$ 100 \times 0.882048 = 88.2048 $$
   • 第四步（向下取整）：
     $$ \lfloor 88.2048 \rfloor = 88 $$

4. 结论：
   键值 123456 对应的哈希地址为 88，因此选项 (C) 正确。

• 分析思路

  • 情况一：当搜索从索引 0 开始时

    • 比较顺序：索引 0 → 索引 1 → 索引 2
    • 终止条件：在索引 2 发现空桶
    • 总比较次数：3 次

  • 情况二：当搜索从索引 8 开始时

    • 比较顺序：索引 8 → 索引 9 → 索引 0 → 索引 1 → 索引 2
    • 终止条件：在索引 2 发现空桶
    • 总比较次数：5 次

• 结论
  根据线性探测法的特性，搜索路径需连续探测直到遇到空桶。上述两种情况中，从索引 8 开始的搜索路径最长，因此最大比较次数为 5 次。
  正确答案为 (B)。

• 44：$ h(44) = 44 \bmod 7 = 2 $，直接存入位置 2
• 45：$ h(45) = 45 \bmod 7 = 3 $，直接存入位置 3
• 79：$ h(79) = 79 \bmod 7 = 2 $，位置 2 被占用 → 探测位置 3（被占用）→ 存入位置 4
• 55：$ h(55) = 55 \bmod 7 = 6 $，直接存入位置 6
• 91：$ h(91) = 91 \bmod 7 = 0 $，直接存入位置 0
• 18：$ h(18) = 18 \bmod 7 = 4 $，位置 4 被占用 → 探测位置 5（空闲）→ 存入位置 5
• 63：$ h(63) = 63 \bmod 7 = 0 $，位置 0 被占用 → 探测位置 1（空闲）→ 存入位置 1

最终哈希表状态：

因此键值 18 存储在位置 5，选项 (C) 正确。

• 已知条件

  • 表的大小：23
  • 键值 k = 90
  • 探测次数 i = 1（探测序列中的第 1 次探测）

• 双重哈希公式
  $$ \text{地址} = (h_1(k) + i \times h_2(k)) \mod (\text{表的大小}) $$

• 计算过程

  1. $ h_1(k) = 90 \mod 23 = 21 $
  2. $ h_2(k) = 1 + (90 \mod 19) = 15 $
  3. 代入公式：$ (21 + 15) \mod 23 = 36 \mod 23 = 13 $

• 结论
  选项 (A) 正确。

• 选项 (A) 中的序列不可能，因为包含键 4 (= 0100)，但最终哈希表中没有该键。
• 选项 (B) 中的序列不可能，因为键 1 (=0001) 和 9 (=1001) 在基于第三最低有效位的 0 侧解决冲突的方式与最终结果不符。
• 选项 (C) 是正确的序列，可得到给定的最终哈希表。
• 选项 (D) 中的序列不可能，因为在第三列中包含键 6 (=0110)、10 (=1010) 和 14 (=1110)，而这些键在最终哈希表中并未出现。

计算步骤：

1. 基础哈希值 h₁(k):
   $$ h₁(123456) = 123456 \mod 701 = 80 $$

2. 辅助哈希值 h₂(k):
   $$ h₂(123456) = 1 + (123456 \mod 700) = 1 + 256 = 257 $$

3. 第一次探测（i=1）:
   $$ h(123456, 1) = (80 + 1×257) \mod 701 = 337 $$

4. 第二次探测（i=2）:
   $$ h(123456, 2) = (80 + 2×257) \mod 701 = 594 $$

5. 两次探测的差值:
   $$ 594 - 337 = 257 $$

结论： 正确答案为选项 C。

• 在开放寻址方案中，当尝试删除一个元素时，如果在查找过程中遇到空桶（即未被占用的位置），可能会错误地认为该元素不存在，从而导致无法正确删除。
• 链式哈希表（外部哈希）通过将所有具有相同哈希值的元素存储在链表中，避免了这一问题，使得删除操作更加直接和可靠。
• 因此，选项 C 是正确答案。

• 键值集合：{1, 3, 8, 10}
• 哈希函数：h(x) = (7*x + 3) mod 4

计算过程：

1. h(1) = (7×1 + 3) mod 4 = 10 mod 4 = 2
2. h(3) = (7×3 + 3) mod 4 = 24 mod 4 = 0
3. h(8) = (7×8 + 3) mod 4 = 59 mod 4 = 3
4. h(10)= (7×10 + 3) mod 4 = 73 mod 4 = 1

哈希表构建：

因此，选项 (A) 正确。

开放寻址法（Open Addressing）是一种哈希表冲突解决方法。当发生哈希冲突时，通过在数组中按一定规则探测其他位置（称为探测序列），直到找到目标记录或空闲槽位。常见的探测方式包括：

• 线性探测：每次以固定步长（通常为 1）进行探测。
• 二次探测：探测间隔随线性增长（索引由二次函数描述）。
• 双重哈希：每个记录的探测间隔由另一个哈希函数计算得出。

本题中，所有键值均通过 h(k) = k mod 10 计算初始位置，并在线性探测下依次解决冲突，最终形成的哈希表对应选项 C。

此处使用哈希函数 h(k)=k mod 10 和线性探测。仔细分析所有选项：

分析所有选项后，(C) 是正确的可能插入顺序：

• (A) 不成立，因为序列中 52 出现在 23 之前。

  • 根据线性探测规则，23 的哈希位置为 3（23 mod 10 = 3），而 52 的哈希位置为 2（52 mod 10 = 2）。若先插入 52，则 23 在探测时会占据位置 3，导致后续插入冲突逻辑不一致。

• (B) 不成立，因为序列中 33 出现在 46 之前。

  • 33 的哈希位置为 3（33 mod 10 = 3），而 46 的哈希位置为 6（46 mod 10 = 6）。若先插入 33，则 46 插入时应直接放置于位置 6，但实际表中 46 位于位置 6，与插入顺序矛盾。

• (C) 成立，因为：

  • 42（42 mod 10 = 2）→ 直接插入位置 2
  • 34（34 mod 10 = 4）→ 直接插入位置 4
  • 42 已存在，23（23 mod 10 = 3）→ 插入位置 3
  • 52（52 mod 10 = 2）→ 冲突后探测至位置 5
  • 33（33 mod 10 = 3）→ 冲突后探测至位置 7
  • 所有插入操作均符合线性探测规则。

• (D) 不成立，因为序列中 33 出现在 23 之前。

  • 33 插入时会占据位置 3，导致 23 插入时需从位置 3 开始探测，最终插入位置 4 或 5，但实际表中 23 位于位置 4，与插入顺序不符。

对于均匀哈希函数而言，无论使用多少个哈希函数，每个槽位中关键字的期望数量始终等于 关键字总数 ÷ 槽位总数。
具体分析如下：

• 哈希函数的均匀性保证了每个关键字被分配到任意槽位的概率相等
• 即使采用多个哈希函数（如本题的 $h_1$ 和 $h_2$），只要它们都满足均匀分布特性
• 最终每个槽位的期望负载仍为 $\frac{n}{m}$
  因此，选项 B 是正确答案。

哈希的组成部分主要有三个：

• 键（Key）：键可以是字符串或整数等任何输入到哈希函数中的内容，该技术用于确定数据结构中存储项目的索引或位置。
• 哈希函数（Hash Function）：哈希函数接收输入键，并返回一个称为哈希表的数组中元素的索引。该索引称为哈希索引。
• 哈希表（Hash Table）：哈希表是一种使用哈希函数将键映射到值的数据结构。它以关联方式在数组中存储数据，每个数据值都有其唯一的索引。
  因此，选项 (D) 是正确答案。

线性探测法是一种哈希冲突处理技术，当发生冲突时，算法会在哈希表中寻找下一个可用的存储位置。其应用包括：

• 缓存
  线性探测法可用于缓存系统，将频繁访问的数据存储在内存中。

  • 当发生缓存未命中时，数据可通过线性探测法加载到缓存中
  • 当发生冲突时，使用缓存中的下一个可用位置存储数据

• 数据库
  线性探测法可用于数据库中存储记录及其关联键值。

  • 当发生冲突时，通过线性探测法查找下一个可用位置存储记录

• 编译器设计
  线性探测法可用于实现：

  1. 符号表管理
  2. 错误恢复机制
  3. 语法分析过程

因此选项 (D) 是正确答案。

• 主要的冲突处理方法有两种：
  • 独立链接法（Separate Chaining）
  • 开放寻址法（Open Addressing）
• 因此 选项 C 是正确答案

让我们将值 1, 3, 8, 10 插入大小为 7 的哈希表中：

初始时哈希表为空：

插入 1

• 哈希计算：(3×1 + 4) mod 7 = 7 mod 7 = 0
• 直接放入索引 0

插入 3

• 哈希计算：(3×3 + 4) mod 7 = 13 mod 7 = 6
• 直接放入索引 6

插入 8

• 哈希计算：(3×8 + 4) mod 7 = 28 mod 7 = 0
• 索引 0 被占用，使用线性探测找到下一个可用位置 1

插入 10

• 哈希计算：(3×10 + 4) mod 7 = 34 mod 7 = 6
• 索引 6 被占用，使用线性探测找到下一个可用位置 2

最终哈希表状态为：1, 8, 10, _, _, _, 3