是什么

  • 定义:散列表(Hash Table)是根据关键字码值(Key)通过散列函数直接计算出数据元素的存储位置的一种数据结构,开放寻址法是当发生冲突时通过系统性的探测序列在表中寻找下一个空闲槽位的冲突解决技术。

  • 大白话:算个公式直接知道东西该放第几个格子;如果这个格子被人占了,就按既定规则(比如往后数步长或平方步长)挨个找下一个空位塞进去。

核心内容

1. 关键指标与计算公式

  • 装填因子 :衡量散列表饱和程度的指标。

    ==注意:分母 必须是散列表的总长度,而不是除留余数法的模数 ==。

  • 平均查找长度(ASL):

    • (分母为==记录总数 ==)

    • (408中分母通常为==散列函数模数 ==,对应各个入口)

2. 开放寻址法的探测与终止逻辑

  • 探测公式:

    其中 为初始散列地址, 为增量序列。

    • 线性探测:

    • 标准平方探测(二次探测):(其中 )

    • 自定义探测:以题干给定公式为准(如只含加法项)。

  • 查找终止条件(核心考点):

    1. 查找成功:。

    2. 查找失败:==探测到首个空单元()立即判定失败==。因为若该关键字存在,建表时就应该填入该空位,绝不会越过空单元探测。

例题

例题一(自定义公式题型)

  • 题目: 将关键字 依次存储到长度为 11 的散列表 中,散列函数为 , 为初始散列地址,、、、、 分别为第 1 次冲突、第 2 次冲突、、第 次冲突时探测的地址。。 (1) 画出所构造的 并计算 的装填因子。 (2) 给出在 中查找关键字 14 的关键字比较序列。 (3) 在 中查找关键字 8,确认查找失败时的散列地址是多少?

  • 分析:

    • 核心在于遵循题目的探测公式 (只有加法项)。

    • 查找 8 失败时,需从 开始依次模拟探测,直至遇到第一个空单元,该空单元地址即为最终确认失败的地址。

  • 答案:

    (1)

    依次计算并插入各关键字:

    • 20: (存入 5)

    • 3: (存入 9)

    • 11: (存入 0)

    • 18: (存入 10)

    • 9: (冲突),(存入 6)

    • 14: (冲突),(冲突),(存入 2)

    • 7: (冲突),(冲突),(存入 3)

    散列表 存储状态如下表:

    下标012345678910
    关键字11空147空209空空318

    装填因子公式与计算:

    (2)

    查找关键字 14 的过程:

    • ,取出

    • ,取出

    • ,取出 ,查找成功

    关键字比较序列为:3,18,14。

    (3)

    查找关键字 8 的过程:

    • ,

    • ,

    • ,

    • ,

    • , 为空,终止查找

    确认查找失败时的散列地址是 7。

例题二(标准平方探测法题型)

  • 题目:

    将关键字序列 存入表长为 11 的散列表中,散列函数为 。采用==标准二次探测法(平方探测法,增量序列为 )==解决冲突。

    (1) 画出所构造的散列表 。

    (2) 分别计算查找成功和查找失败时的平均查找长度( 与 )。

  • 分析:

    • 标准平方探测增量为 。遇到负数取模时,必须先加表长化为正数再计算,即 。

    • 的分子为每个元素找到时的比较次数之和,分母为元素个数 10。

    • 考察以每个可能余数入口()进行查找,探测直到遇到空单元的比较次数。

  • 答案:

    (1)

    依次计算并插入各元素(括号内为探测次数):

    • 19: (1次,存入 8)

    • 14: (1次,存入 3)

    • 23: (1次,存入 1)

    • 1: (冲突)

      • (2次,存入 2)

    • 68: (冲突)

      • (冲突)

      • (冲突)

      • (4次,存入 6)

    • 20: (1次,存入 9)

    • 84: (1次,存入 7)

    • 27: (1次,存入 5)

    • 55: (1次,存入 0)

    • 11: (冲突)

      • (冲突)

      • (3次,存入 10)

    散列表存储状态如下表:

    下标012345678910
    关键字5523114空276884192011
    查找成功比较次数1121-141113

    (2)

    查找成功时的平均查找长度:

    查找失败时的平均查找长度(从余数入口 开始探测直到空单元下标 4):

    • 入口 0: 探测 0, 1, 10, 4(遇空停),比较 4 次

    • 入口 1: 探测 1, 2, 0, 5, 8, 10, 3(遇非空继续),经计算至空位共比较 9 次

    • 入口 2: 探测 2, 3, 1, 6, 9, 7, 4(遇空停),比较 7 次

    • 入口 3: 探测 3, 4(遇空停),比较 2 次

    • 入口 4: 为空,比较 1 次

    • 入口 5: 探测 5, 6, 4(遇空停),比较 3 次

    • 入口 6: 探测 6, 7, 5, 10, 2, 8, 4(遇空停),比较 7 次

    • 入口 7: 探测 7, 8, 6, 0, 3, 9, 4(遇空停),比较 7 次

    • 入口 8: 探测 8, 9, 7, 1, 4(遇空停),比较 5 次

    • 入口 9: 探测 9, 10, 8, 2, 5, 4(遇空停),比较 6 次

    • 入口 10: 探测 10, 0, 9, 3, 6, 5, 4(遇空停),比较 7 次

⚠️ 易错点

Warning

  • 套用死公式 课本标准平方探测为 ,但考题若显式定义了探测公式(如只定义了 ),必须以题目公式为唯一执行依据。

  • 负数取模计算错误 采用标准平方探测时, 出现负数项,计算结果为负必须==加上表长 转为正数后再取模==(例:)。

  • 混淆“关键字比较序列”与“探测地址序列” 题目问“比较序列”必须写具体比对的数字(如 3, 18, 14),写成地址下标(如 9, 10, 2)直接判错。

  • 查找失败判定时机 开放寻址法中,只有碰到空槽位(EMPTY)才确认查找失败,而不是比对到最后一个非空元素就停下;失败时的散列地址必定是该空槽位的下标。

  • 取模对象搞混 冲突探测更新地址时,==外层取模始终是对表长 取模==,切勿误用散列函数的质数 。