国内单页网站,wordpress 点餐主题,房价查询官网,企业型网站建设咨询电话1、动态集合结构#xff0c;它至少要支持 INSERT、SEARCH 和 DELETE字典操作
散列表 是实现字典操作的 一种有效的数据结构。尽管 最坏情况下#xff0c;散列表中 查找一个元素的时间 与链表中 查找的时间相同#xff0c;达到了 Θ(n)。在实际应用中#xff0c;散列表的性…1、动态集合结构它至少要支持 INSERT、SEARCH 和 DELETE字典操作
散列表 是实现字典操作的 一种有效的数据结构。尽管 最坏情况下散列表中 查找一个元素的时间 与链表中 查找的时间相同达到了 Θ(n)。在实际应用中散列表的性能 是极好的。在一些 合理的假设下在 散列表中 查找一个元素的平均时间是 O(1)
2、散列表是 普通数组概念的推广。如果 存储空间允许可以 提供一个数组为每个可能的 关键字 保留一个位置以利用 直接寻址的技术优势
当 实际存储的 关键字数目 比全部的可能关键字 总数要小时采用 散列表就成为 直接数组寻址的 一种有效替代因为 散列表使用一个 长度与实际存储的 关键字数目 成比例的数组来 存储
在散列表中不是 直接把关键字 作为 数组的下标而是 根据关键字 计算出 相应的下标
1、直接寻址表
1、当关键字的全域U 比较小时直接寻址 是一种简单而有效的技术
2、用一个数组或 称为 直接寻址表记为T[0…m-1]。其中 每个位置或称为槽对应全域U中的一个关键字。槽k指向集合中 一个关键字为k的元素。如果 该集合中没有关键字为k 的元素则 T[k] NIL 几个字典操作
DIRECT-ADDRESS-SEARCH(T, k)return T[k]DIRECT-ADDRESS-INSERT(T, x)T[x.key] xDIRECT-ADDRESS-DELETE(T, x)T[x.key] NIL直接寻址表本身就可以 存放动态集合中的元素。直接 把该对象存放在表的槽中从而节省了空间。我们使用 对象内的一个特殊关键字 来表明该槽为空槽比如-1
3、假设一动态集合S 用一个长度为m的直接寻址表T 来表示。给出 一个查找S中最大元素的过程
DIRECT-ADDRESS-MAXIMUM(T)max -∞for i 1 to mif T[i] ≠ NIL and T[i].key maxmax T[i].keyj ireturn T[j]过程 在最坏情况下的运行时间是 O(m)
4、位向量 是一个仅包含0和1的数组
2、散列表
1、直接寻址技术的缺点如果 全域U很大要存储大小为 |U| 的一张表T 也许不太实际
如果 实际存储的关键字集合K 相对U来说可能很小使得 分配给T的大部分空间 都将被浪费掉
2、当存储在字典中的 关键字集合K 比所有可能的关键字的全域U 要小许多时散列表 需要的存储空间 要比直接寻址表 少得多。将散列表的存储需求 降至 Θ(|K|)同时 散列表中查找一个元素的优势 仍得到保持只需要 O(1)的时间。问题是 这个界 是针对 平均情况时间的而对于 直接寻址 来说它是 适用于 最坏情况时间的
3、在 直接寻址 方式下具有 关键字k的元素 被存放在 槽k中。在 散列方式下该元素 被放在h(k)中即 利用 散列函数h由关键字k 计算出 槽的位置。函数h 将关键字的全域U 映射到 散列表 T[0…m - 1]的槽位上 可以说 一个具有关键字k的元素 被散列到 槽 h(k) 上也可以说 h(t) 是关键字的散列值。即 减少了 数组的大小使其 由|U|减少为m 4、两个关键字 可能映射到 同一个槽中我们称 这种情形为冲突
可以试图 选择一个适合的散列函数h 来做到 避免冲突 一个想法就是 使h尽可能的“随机”。但是 |U|m故至少 有两个关键字 其散列值 相同所以 要想完全 避免冲突 是不可能的
一方面 可以通过 精心设计的散列函数 来尽量减少 冲突的次数另一方面 仍需要 有解决 可能出现冲突的方法
5、最简单的冲突解决方法链接法
在 链接法中把 散列到 同一槽中的所有元素 都放在 一个链表中槽j中有 一个指针它指向 存储所有散列到j的元素的 链表的表头如果 不存在 这样的元素则 槽j中为NIL
CHAINED-HASH-INSERT(T, x)insert x at the head of list T[h(x.key)]CHAINED-HASH-SEARCH(T, k)search for an element with key k in list T[h(k)]CHAINED-HASH-DELETE(T, x)delete x from the list T[h(x.key)]插入操作的最坏情况 运行时间为 O(1)。查找操作的最坏情况运行时间 与表的长度成正比
6、如果散列表中的链表是 双向链接的则删除一个元素x的操作 可以在 O(1) 时间内完成
CHAINED-HASH-DELETE 以元素x 而不是它的关键字k 作为输入所以无需 先搜索x。如果散列表支持 删除操作则为了能够更快地删除 某一元素应该将其链表设计为 双向链接的可以直接 找到前驱 如果表是 单链接的则为了删除元素x我们首先 必须在表 T[h(x.key)] 中找到元素x然后通过 更改x前驱元素的next属性把x从链表中删除 7、链接法 散列分析给定 一个能存放n个元素的、具有 m个槽位的散列表T定义T的装载因子α为 n/m即 一个链的平均存储元素数
用链接法散列的最坏情况 性能很差所有的两个关键字 都散列到同一个槽中从而产生出 一个长度为n的链表。这时最坏情况下 查找的时间为 Θ(n)再加上 计算散列函数的时间
8、散列方法的平均性能 依赖于 所选取的散列函数h将所有的关键字集合 分布在m个槽位上的均匀程度
先假定 任何一个给定元素 等可能地散列到m个槽位中的 任何一个等可能且与 其他元素被散列到什么位置上 无关独立我们称这个假设为 简单均匀散列
列表 T[j] 的长度 用nj表示有 并且 nj 的期望值为 E[nj] a n/m
假定可以在 O(1) 时间内 计算出散列值 h(k)从而 查找关键字为k的元素的时间线性地依赖于 表T[A(k)] 的长度 nh(k) 分两种情况来考虑。在第一种情况中查找不成功表中没有一个元素的关键字为k。在第二种情况中成功地查找到 关键字为k的元素
9、在简单均匀散列的假设下对于 用链接法解决冲突的散列表一次不成功查找的平均时间为 Θ(1α) 证明当查找一个关键字时在不成功的情况下查找的期望时间 就是查找至 链表 T[h(k)] 末尾的期望时间这一时间的期望长度为E[nh(k)] α于是一次不成功的查找 平均要检查α个元素并且所需要的总时间包括计算 h(k) 的时间为 Θ(1α
对于成功的查找来说情况略有不同这是因为每个链表 并不是等可能地被查找到的。某个链表被查找到的概率与它所包含的元素数成正比 期望的查找时间仍然是 Θ(1α
10、在简单均匀散列的假设下对于 用链接法解决冲变的散列表一次成功查找 所需的平均时间为 Θ(1α) 证明在对元素x的 一次成功查找中所检查的元素数 就是x所在的链表中x前面的元素 多1。新的元素 都是在表头插入的所以 出现在x之前的元素 都是在x之后插入的。在 简单均匀散列的假设下有 Pr{h(ki) h(kj)} 1/m有 E[Xij] 1/m
于是在一次成功的查找中所检查元素的期望数目 为 一次成功的查找 所需要的全部时间包括计算散列函数的时间为 Θ(2 α / 2 - α / 2n) Θ(1 α)
如果散列表中 槽数 至少与表中的元素数 成正比则有 nO(m)从而 a n / m O(m) / m O(1) 。所以查找操作平均需要常数时间。当链表采用双向链接时插入操作 在最坏情况下 需要 O(1时间删除操作 最坏情况下 也需要 O(1) 时间因而全部的字典操作 平均情况下 都可以在 O(1) 时间内完成
11、假设 采用的是 简单均匀散列对关键字k和l定义指示器随机变量 Xkl Ⅰ{h(k)h(l)}。在简单均匀散列的假设下有Pr{h(k)h(l)}1/m从而 有E[Xkl] 1/m。于是集合{{kl}k≠l且h(k)h(l)}基的期望值是 12、假设将n个关键字存储到一个大小为m 且通过链接法解决冲突的散列表中关键字 均源于 全域U且 |U| nm 因为 |U| nm所以当将全域U中的所有关键字存储到一个大小为 m 的散列表中时每个槽位中至少有 n 个关键字。因此U中有一个大小为n的子集其由散列到 同一槽位中的所有关键字构成使得链接法散列的查找时间 最坏情况下为 Θ(n)
3、散列函数
1、其中的两种方法 用除法进行散列和用乘法进行散列本质上 属于启发式方法而第三种方法全域散列则利用了 随机技术 来提供 可证明的良好性能
2、好的散列函数的特点一个好的 散列函数应近似地满足 简单均匀散列假设 遗憾的是一般 无法检查这一条件 是否成立因为 很少能知道 关键字散列 所满足的概率分布而且 各关键字 可能并不是完全独立的
常常 可以运用启发式方法 来构造 性能好的散列函数。设计过程中可以利用 关键字分布的有用信息 一些很相近的符号 经常会出现在 同一个程序中如 pt 和 pts。好的散列函数 应能将这些相近符号 散列到 相同槽中的可能性 最小化
一种好的方法导出的 散列值在 某种程度上 应独立于 数据可能存在的任何模式 注意到 散列函数的某些应用 可能会 要求比简单均匀散列更强的性质。例如可能希望 某些很近似的关键字 具有截然不同的散列值
3、将关键字 转换为 自然数多数散列函数 都假定关键字的全域为 自然数集 N {012…}。因此如果所给关键字不是自然数就需要 找到一种方法来 将它们转换为自然数。例如一个字符串 可以被 转换为按适当的基数符号表示的整数
这样就可以将标识符pt 转换为 十进制整数对112116这是因为 在 ASCII字符集中p 112t 116。然后以128为基数二进制转十进制 就是以2为基数的 来表示pt 即为112×128116 14452 假定所给的关键字都是自然数
3.1 除法散列法
1、通过 k除以m的余数将关键字k 映射到m个槽中的某一个上即散列函数为 当应用除法散列法时要避免选择m的某些值。例如m 不应为2的幂因为如果m2p则h(k)就是 k的p个最低位数字除非 已知各种最低p位的排列形式 为等可能的
当 k是一个按基数2p表示的字符串时选 m 2p - 1 可能是一个槽糕的选择 如果 串x可 由串y通过其自身的字符置换排列 导出则 x和y具有 相同的散列值
证明 用 除法散列表 来计算 一个字符串的散列值如何 才能在除了 该串本身 占用的空间外只利用 常数个机器字 在 模运算下加法和乘法 都满足分配律这样 可以在乘法过程中 保持结果的大小 在合适范围内
设字符串x表示成以2p为基数的数为 k a1 a2 … ar根据上一题的结果 因为 ai 在 0~2p-2 之间所以 mod(2p-1) 可以直接去
2、一个 不太接近2的整数幂的素数常常 是m的一个较好的选择。例如假定 我们要分配—张散列表 并用链接法解决冲突表中 大约要存放2000个字符串其中的每个字符 有8位。如果我们 不介意一次不成功的查找 需要平均检查3个元素这样分配散列表的大小为 m701它是一个 接近 2000/3 但又不接近2的任何次幂的素数
散列函数为h(k) k mod 701
3.2 乘法散列法
1、乘法散列法 包含两个步骤第一步用关键字k乘上常数A(0A1并提取 kA 的小数部分。第二步用m乘以这个值再向下取整 乘法散列法 的一个优点是 对m的选择不是特别关键一般选择它 为2的某个幂次m2pp为某个整数这是因为我们可以在大多数计算机上 按下面所示方法 较容易地实现 散列函数
假设 某计算机的字长为w位而k正好可用 一个单字表示。限制A为形如 s/2w 的一个分数其中s是一个 取自 0s2w 的整数 先用w位整数 s A * 2w 左移一个字长乘上k其结果 是一个 2w 位的值 r1*2w r0这里 r1 为乘积的高位字r0 为乘积的低位字。所求的 p位散列值中包含了 r0的p个最高有效位m 2p
虽然这个方法 对任何的A值 都适用但对 某些值的效果更好。最佳选择 与 待散列的数据的特征有关 假设 k 123456p 14m 214 16384且 w 32。取A为形如 s/232 的分数它与 (√5-1) / 2 最为接近于是 A 2654435769 / 2 s 2654435769那么k x s 327706022297664 (76300 X 232) 17612864从而有 r1 76300 和 r0 17612864。r0 的 14个最高位 产生了 散列值 h(k) 67将17612864转成 二进制并在前面加上7个零 凑够32位取前14位 就是67
3.3 全域散列法
1、将 n个关键字 全部 散列到 同一个槽中使得平均的检索时间为 Θ(x)。任何一个特定的散列函数 都可能出现 这种令人恐怖的最坏情况。唯一有效的改进方法是 随机地选择散列函数使之独立于 要存储的关键字。这种方法称为全域散列不管 选择了怎么样的关键字其平均性能都很好
2、全域散列法 在执行开始时 就从一组精心设计的函数中随机地选择一个 作为散列函数。就像 在快速排序中 一样随机化 保证了 没有哪一种输入 会始终导致 最坏情况性能 算法 在每一次执行时 都会有所不同甚至对于相同的输入 都会如此。这样就可以确保 对于任何输入算法都具有 较好的平均情况性能
设 H为一组 有限散列函数它将给定的关键字的全域U 映射到 {0, 1, …, m-1} 中这样的一个函数组 为全域的。如果 从H中 随机地选择 一个散列函数当 关键字 k!l 时两者发生冲突的概率 不大于 1/m这也是 正好从集合 {01…m - 1} 中 独立地随机选择 h(k) 和 h(l) 时 发生冲突的概率
3、ni 表示链表 T[i] 的长度。h选自 一组全域散列函数。如果 关键字k不在表中则 k被散列至 其中的链表的期望长度 E[nh(k)] 至多为 α n/m。如果 关键字k在表中则 包含关键字k的链表的 期望长度 E[nh(k)] 至多为 1α
证明期望值 与 散列函数的选择有关且 不依赖于 任何有关 关键字分布的假设。因为 由 全域散列函数的定义一对 关键字发生冲突的概率 至多为 1/m有 Pr{h(k) h(l)} 1/m所以有 E[Xkl] 1/m 对于 每个关键字k定义 随机变量Yk它表示 与k散列到 同一槽位中的 非k的 其他关键字的数目 余下部分 按关键字k是否在表T中分情况讨论
如果 k!∈T则 nh(k) Yk并且 |{ll∈T 且 l!k}| n。于是E[nh(k)] E[Yk] n / m α如果 k∈T由于 关键字k出现在 链表 T[h(k)] 中且 计数Yk中 并没有包括关键字k所以 nh(k) Yk 1并且 |{ll∈T 且 l ! k}| n - 1。于是 E[nh(k)] E[Yk] 1 (n - 1) / m 1 1 α - 1/m 1 α
已经无法通过选择一个操作序列 来迫使达到 最坏情况运行时间了
4、对于 一个具有m个槽位且初始时为空的表利用 全域散列法 和 链接法解决冲突需要 Θ(n) 的期望时间 来处理任何包含了n个 INSERT、SEARCH和DELETE的操作序列其中 该序列包含了 O(m) 个INSERT操作
证明 在全域散列法和链接法中解决冲突的时间复杂度取决于散列函数的质量和表的装载因子。在这种情况下我们假设 散列函数是良好设计的并且在平均情况下能够均匀地将元素分布到表的不同槽位中。 表的装载因子是 Θ(1) 的即元素数量与表的大小之比是常数。 在这样的假设下全域散列法和链接法解决冲突的平均时间复杂度是 Θ(1)。
对于链接法也称为开放地址法 在平均情况下对于一个给定的槽位搜索或删除一个元素的时间复杂度是 Θ(1)因为每个槽位是一个链表查找或删除一个元素只需要遍历链表 在 INSERT 操作中我们需要计算元素的哈希值然后将其插入到对应槽位的链表中。由于散列函数是均匀的每个槽位的链表平均长度为 Θ(n/m)因此插入的平均时间复杂度是 Θ(1)。 因此链接法的平均时间复杂度是 Θ(1)
对于全域散列法 在平均情况下搜索或删除一个元素的时间复杂度也是 Θ(1)因为我们可以直接计算出元素所在的槽位 在 INSERT 操作中我们需要计算元素的哈希值并找到对应的槽位。由于散列函数是均匀的每个槽位平均只包含 Θ(n/m) 个元素因此插入的平均时间复杂度是 Θ(1)。 因此全域散列法的平均时间复杂度也是 Θ(1)
综上所述无论是链接法还是全域散列法对于一个具有 m 个槽位的哈希表在平均情况下处理包含了 n 个 INSERT、SEARCH 和 DELETE 操作的序列的时间复杂度都是 Θ(1)所以 整个n个操作序列的期望时间 为 Θ(n)
5、设计一个全域散列函数类设 Zp 表示集合 {01…p - 1}Zp* 表示集合 {12…p - 1}由于 p是一个素数 对于 任何 a∈Zp* 和 任何 b∈Zp定义 散列函数 hab 散列函数 构成的 函数簇为 这个函数簇 是全域的
一个散列函数被称为全域散列函数如果它满足以下两个性质 1均匀性对于任意不同的输入键散列函数产生的哈希值在哈希表中的每个槽位中出现的概率相等。换句话说对于任意两个不同的键 1 和 2如果哈希函数 ℎ是全域散列函数则满足Pr[h(k1) h(k2)] 1/m 其中 m 是哈希表的大小Pr[⋅] 表示概率
2独立性全域散列函数的输出 在给定一个键的情况下是不可预测的并且 与其他键的哈希值无关。换句话说对于一个给定的键 k 和任意给定的哈希值 如果哈希函数 ℎ是全域散列函数则满足Pr[h(k) y] 1 / m 其中 是哈希表的大小
全域散列函数的均匀性和独立性保证了在散列过程中每个键被哈希到哈希表的每个槽位的概率是相等的并且每个键的哈希值都是不可预测的。这样可以最大程度地减少冲突提高哈希表的性能
证明这个函数簇 是全域的 可以导出 r ! s因为 p是素数且 a和(k - l)模p的结果不为0所以 它们乘积模p后 也不为0。所以 计算任何 hab∈Hpm不同的输入k和l会被映射到 不同的值r和s模p(r ! s)在模p层次上不会产生冲突线性函数一一对应此外数对(a, b)(a ! 0) 有 p(p - 1)中可能的选择。其中的每一种 都会产生一个 不同的结果数对 (r, s) (r ! s) 解出 a和b 因为 (r, s) 有p(p - 1)种可能所以 数对(a, b) 和 数对(r, s)之间 存在一一对应的关系。对 任意给定的输入对 k和l如果 从 Zp* × Zp 中均匀地 随机选择(a, b)则 结果数对 (r, s) 就等可能地 为任何不同的数值对模p 当 r和s为 随机选择的不同的值模p时不同的关键字k和l发生冲突的概率 等于 r ≡ s(mod m) 的概率。对于 某个给定的r值s的可能取值 就为余下的 p - 1 种其中 满足 s ! r 且 s ≡ r(mod m) 的s值的数目至多为s与r之差 正好是m的倍数 当模m进行 归约时s与r发生冲突的概率 至多为 ((p - 1) / m) / (p - 1) 1 / m 6、查找的时候 怎么确定关键字使用的是 哈希函数族中的哪个哈希函数 在构建好哈希表后可以使用 相同的哈希函数来 执行查找操作。由于哈希函数在构建哈希表时 已经确定了在构建的时候 参数的值 会随着一起保存因此在查找时 不需要再确定关键字 使用的是哪个哈希函数。相反只需根据哈希函数的定义 将关键字哈希到哈希表中的相应槽位上然后执行相应的查找操作即可 在全域散列法中参数 a 和 b 通常是选定一个固定的范围并且对于每个不同的关键字都随机选择一组 a 和 的值。换句话说对于哈希函数族中的每个哈希函数 h(a, b)都会为 每个不同的关键字选择不同的 a 和 b 的值
4、开放寻址法
1、在 开放寻址法中所有的元素 都存放在 散列表里。每个表项 或包含动态集合的一个元素或包含 NIL其 装载因子α绝对不会超过1
也可以 将用作 链接的链表 存放在 散列表未用的槽中但 开放寻址法的好处 就是 它不用使用指针而是 计算出 要存取的槽序列。不用 存储指针 而节省空间使得 可以用 同样的空间 来提供更多的槽潜在地减小了冲突提高了 检索速度
2、为了 使用开放寻址法 插入一个元素需要 连续地检查 散列表或 称为探查直到 找到一个空槽 来放置 待插入的关键字为止 对于 每一个关键字k使用开放寻址法的探查序列 h(k, 1) 为第一个备用… 使得 当散列表 逐渐填满时每一个表位 最终都可以 被考虑为用来 插入新关键字的槽 查找过程中碰到一个空槽时查找算法 就非成功地停止因为 如果在表中它就应该在此处而不会 在探查序列随后的位置上 从开放寻址法的散列表中 删除操作元素 比较困难。当我们从槽i中 删除关键字时不能仅将 NIL置于 其中来标识它为空如果这样做就会有问题在插人关键字k时发现槽i被占用了则就被插人到后面的位置上此时将i中的关键字删除后就无法检索到关键字了到空就停 在槽i中置一个特定的值DELETED替代NIL来标记该槽这样 就要对过程HASH-INSERT做相应的修改将这样的一个槽当做空槽使得在此 仍然可以插人新的关键字。对HASH-SEARCH无需做什么改动因为它在搜索时会绕过DELETED标识。但是当我们使用特殊的值DELETED时查找时间就 不再依赖于装载因子了为此在必须删除关键字的应用中更常见的做法是采用链接法来解决冲突
由于删除操作 不会改变表的大小因此装载因子 不再影响 查找操作的性能。在使用开放寻址法时查找操作的性能 取决于 表中空槽位的数量而不仅仅是 已插入元素的数量。它取决于表中空槽位的数量即 1−a因为空槽位的数量越多冲突的可能性就越小查找操作的性能就越好
3、做一个均匀散列 的假设每个关键字的探查序列 等可能地为01…m-1的m!种排列中 的任一种。均匀散列 将前面定义过的简单均匀散列的概念 加以了一般化推广到散列函数的结果 不只是一个数而是 一个完整的探查序列
有三种技术 常用来 计算开放定址法中的探查序列线性探查、二次探查 和 双重探查
这些技术 都不能满足 均匀散列的假设因为 他们能产生的 不同探查序列数 都不超过m2个均匀散列 要求有 m! 个探查序列。双重散列 产生的探查序列数最多似乎能 给出最好的结果
4.1 线性探查
1、给定 一个普通的散列函数 h’U-{0, 1, …, m - 1}称之为 辅助散列函数线性探查 采用的散列函数为 对于 关键字k首先 探查槽 T[h’(k)]即由 辅助散列函数 所给出的槽位再 探查槽 T[h’(k) 1]依次类推直到槽 T[m - 1]。然后又绕到槽 T[0]T[1]…直到 最后探查到槽 T[h’(k) - 1]。在 线性探查方法中初始探查位置 决定了 整个序列故 只有m种 不同的探查序列
2、线性探查 存在一个问题称为 一次群集。随着 连续被占用的槽 不断增加平均查找时间 也随之不断增加。因为 当一个空槽前 有i个满的槽该空槽 下一个将被占用的概率是 (i 1) / m。连续被占用的槽 就会变得越来越长因而 平均查找时间 也会越来越大
4.2 二次探查
1、散列函数 h’ 是 一个辅助散列函数c1和c2 为正的辅助常数i 01…m - 1。初始的探查位置为 T[h’(k)]。后续的探查位置 要加上一个偏移量该偏移量以二次的方式 依赖于探查序号i。这种探查方法的效果 要比 线性探查好得多连续被占用的槽 就会变得越来越长的情况 会缓解
2、如果 两个关键字的初始探查位置 相同那么它们的探查序列 也是相同的这是因为 h(k1, 0) h(k2, 0蕴涵着 h(k1, i) h(k2, i)。 这一性质 可导致 一种轻度的群集称为二次群集。像在线性探查中一样初始探查位置 决定了 整个序列这样 也仅有m个不同的探查序列被用到
4.3 双重散列
1、双重散列 是用于 开放寻址法的最好方法之一因为 它所产生的排列 具有随机选择排列的许多特性。散列函数 初始探查位置为 T[h1(k)]后续的探查位置 是前一个位置 加上偏移量h2(k)模m。因此不像 线性探查 或 二次探查这里的探查序列 以两种不同方式 依赖于关键字k因为 初始探查位置、偏移量 或者 二者 都可能发生变化
2、为了 能查找整个散列表值h2(k) 必须要 与表的大小m 互素两个整数的最大公约数为1。有一种简便的方法 确保这个条件成立就是取m为2的幂并设计 一个总产生奇数的h2。另一种方法是 取m为素数并设计一个 总是返回较m小的正整数的函数h2
如果 k 123456m 701m’ 700则有 h1(k) 80h2(k) 257 当m为素数 或者 2的幂时双重散列法中 用到了 Θ(m2) 种探查序列而 线性探查 或 二次探查中 用了 Θ(m) 种 因为 每一对可能的 (h1(k), h2(k)) 都会产生 一个不同的探查序列。因此对于m的每一种可能取值双重散列的性能 看起来 就非 常接近“理想的”均匀散列的性能
尽管 除素数和2的幂以外的m值 在理论上 也能用于双重散列中但是在实际中要高效 地产生 h2(k) 确保使其与m互素 很困难。部分原因是 这些数的相对密度 ɸ(m) / m 可能比较小
3、开放寻址散列的分析像在链接法中的分析 一样开放寻址法的分析 也是 以散列表的装载因子 α n / m 来表达的 当然使用开放寻址法每个槽中 至多只有一个元素因而 n m也就意味着 α ≤ 1
每一种 探查序列 都是等可能的 给定一个装载因子为 a n/m ≤ 1 的开放寻址散列表并假设 是均匀散列的则 对于一次不成功的查找其期望的探查次数 至多为 1 / (1 - a)
证在不成功的查找中除了 最后一次探查每一次 探查都要检查 一个被占用 但并不包含 所求关键字的槽最后检查的槽 是空的。先定义 随机变量X 为一次不成功的探查次数再定义事件 Aii 1, 2, …) 为 第i次探查 且探查到的是 一个已经被占用的槽。事件 {Xi} 即为 事件 A1∩A2∩…∩Ai - 1的交集 由于 有n个元素和m个槽所以 Pr{A1} n / m。在前j - 1次探查到的 都是已经占用槽的前提下第j次探查 且探查到的仍是 已占用槽的概率是 (n - j 1) / (m - j 1)。因为要在 (m - (j - 1)) 个未探查的槽中查找 余下的 (n - (j - 1)) 个元素中的某一个。注意到 nm对于 所有j0 j m就有 (n - j) / (m - j) n/m。 等比计算公式 4、假设 采用的是 均匀散列平均情况下向一个装载因子为α的开放寻址散列表中 插入一个元素 至多需要做 1/(1 - α) 次探查
证明只有当表中 有空槽时才可以 插入新元素故 α1。插入一个关键字 要先做一次 不成功的查找然后 将该关键字置入 第一个遇到的空槽中所以 跟不成功的查找一样期望的探查次数 至多为 1/(1 - α)
5、对于一个装载因子 为 α1 的开放寻址散列表一次成功查找中的探查期望数 至多为 假设采用均匀散列且表中的每个关键字被查找的可能性 是相同的 证明根据4如果 k是第 i1 个被插入表中的关键字则 对k的一次查找中探查的期望次数 至多为 1/(1 - i / m) m / (m - i)对散列表中 所有n个关键字 求平均则得到一次成功查找的 探查期望次数为 综合 35 当装载因子为3/4 和 7/8 时一次不成功查找 的探查期望数上界 分别为4和8一次成功查找 的探查期望数上界 分别为 4/3 ln4 和 8/7 ln8
6、写出 HASH-DELETE 的伪代码修改 HASH-INSERT使之能处理特殊值 DELETED
HASH-DELETE(T, k)for i 0 to m-1j h(k, i)if T[j] kT[j] DELETEDreturnHASH-INSERT(T, k)i 0repeatj h(k, i)if T[j] NIL or T[j] DELETED // 区别T[j] kreturn jelse i i 1until i merror hash table overflow5、完全散列
1、使用散列技术 通常 是个好的选择不仅是 因为它有优异的平均情况性能而且 当关键字集合是静态时散列技术 也能提供出色的最坏情况性能。所谓静态就是指 一旦各关键字 存入表中关键字集合 就不再变化了
2、一种散列方法 称为完全散列如果 该方法进行查找时能在 最坏情况下 用 O(1) 次访存完成
采用两级的散列方法 来设计完全散列方案在每级上 都使用全域散列 第一级与 带链接的散列表基本上是一样的利用 从某一全域散列函数族中 仔细选出的一个 散列函数h将n个关键字 散列到 m个槽中 然后 采用了 一个较小的二次散列表 Sj 及 相关的散列函数 hj利用 精心选择的散列函数hj可以确保 在第二级上 不出现冲突
为了确保 在第二级上 不出现冲突需要 让散列表 Sj 的大小 mj 为散列到槽j中的关键字数 nj 的平方尽管 mj 对 nj 的这种二次依赖 看上去可能使得总体存储需求很大通过 适当地选择 第一级散列函数可以将 预期使用的总体存储空间 限制为 O(n)
3、如果 从一个全域散列函数类中 随机选出 散列函数h将 n个关键字 存储在 一个大小为 m n2 的散列表中那么表中 出现冲突的概率 小于 1/2
证明 共有 Cn2 对关键字 可能发生冲突如果A 是从一个全域散列函数类H 中随机选出那么 每一对关键字冲突的概率为 1 / m。当 m n2 时期望的冲突次数为 运用 马尔可夫不等式 4、下面的定理 和 一个推论给出了所有二级散列表的大小加起来后 的期望值的界第二个推论 给出了所有二级散列表的大小加起来后超过线性时的概率的一个上界(实际上后面的证明中超过线性是指等于或大于4n
1定理如果 从某一个全域散列函数类中 随机选出 散列函数h用它将n个关键字 存储到 一个大小为 m n 的散列表中则有 这里 nj 为散列 到槽j中的关键字数
证明从下面的恒等式开始这个等式 对任何非负的整数a成立 所以有 里面涉及到 加法原理
2推论1如果 从某一全域散列函数类中 随机选出散列函数h用它 将n个关键字 存储到 一个大小为 m n 的散列表中并将每个二次散列表的大小 设置为 mj (nj)2j 01…m-1则 在一个完全散列方案中存储 所有二次散列表 所需的存储总量的期望值 小于2n
证明由 (1) 3推论2如果 从某一全域散列函数类中 随机选出散列函数h用它 将n个关键字 存储到 一个大小为 m n 的散列表中并将 每个二级散列表的大小 置为 mj (nj)2 (j 0, 1, …, m - 1)则 用于存储 所有二级散列表的存储总量 等于 或 大于 4n的概率小于 1/2 证明用 马尔可夫不等式即 Pr{X t} E[X] / t。并将 入 推论1中 不等式 从 推论2 可得只需 从全域散列函数类中 随机选出 几个散列函数尝试几次 就可以快速找到 一个所需存储量 较为合理的函数
