hash表及其应用.ppt

分析（1） 题目要求出给定的方程解的个数，这个方程在最坏的情况下可以有6个未知数，而且次数由输入决定。这样就不能利用数学方法直接求出解的个数，而且注意到解的范围最多150个数，因此恐怕只能使用枚举法了。最简单的思路是穷举所有未知数的取值，这样时间复杂度是 O(M6) ，无法承受。 否缩小枚举的范围呢？ 分析(2) 我们再次注意到M 的范围，若想不超时，似乎算法的复杂度上限应该是 O(M3) 左右，这是因为 1503 。这就启示我们能否仅仅通过枚举3个未知数的值来找到答案呢？ 如果这样，前一半式子的值 S 可以确定，这时只要枚举后3 个数的值，检查他们的和是否等于 -S 即可。这样只相当于在 O(M3) 前面加了一个系数，当然还需要预先算出 1 到 150 的各个幂次的值。 想到了这里，问题就是如何迅速的找到某个 S 是否曾经出现过，以及出现过了多少次，于是又变成了“某个元素是否在给定集合中”这个问题。 所以，我们还是使用哈希表解决这个问题。至于哈希函数，还是把 S 的值作为关键字使用除余法即可。有一点需要注意，我们不仅需要纪录某个 S 是否出现，出现的次数也很重要，所以需要加了一个存储出现次数的域。 HASH函数及其应用 雅礼 朱全民 问题一 读入n个正整数，每个数小于109 查询某个数是否在这n个数中出现 一共查询m次 n=100000 m=100000 in.txt 5 ----- 5个数 8 1 6 3 5 3 ----- 询问3次 3 6 9 out.txt YES YES NO 分析 这题可以先对n个数进行快速排序，然后对于每次询问，用二分查找解决。 有没有更快的做法？ 什么是HASH？ 哈希表是一种高效的数据结构 。 散列方法是使用函数h将U映射到表T[0..m-1]的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。 一、整数的Hash函数 构造方法（1） 1．直接取余法 关键字k除以m，取余数作为在Hash表中的位置。函数表达式可以写成： h(k)=k mod m 一般m选择为素数 一、整数的Hash函数 构造方法（2） 2．乘积取整法 关键字k乘以一个在(0,1)中的实数（最好是无理数），得到一个(0,1)之间的实数；取出其小数部分，乘以m，再取整数部分，即得K在Hash表中的位置。函数表达式可以写成： 例如 就是一个好的选择。 一、整数的Hash函数 构造方法（3） 3．平方取中法 把关键字K平方，然后取中间的 位作为Hash函数值返回。由于K的每一位都会对其平方中间的若干位产生影响，因此这个方法的效果也是不错的。但是对于比较小的K值效果并不是很理想，实现起来也比较繁琐。为了充分利用Hash表的空间，M最好取2的整数次幂。例如,表容量M=24=16，，关键值K=100，那么 h(k)=8 回到问题一 n最多为100000 flag数组不开到109，但可以开flag[1..300000] 可用取余法 解决冲突 将数组改为链表 问题二 问题一中的正整数改称字符串 （每个字符串的长度不超过20） 还是输入n个字符串，一共m次询问 in.txt 4 ----- 5个字符串 cat banana apple dog 3 ----- 询问3次 banana fruit pet out.txt YES NO NO 二、字符串的Hash函数 构造方法 字符串本身就可以看成一个256进制（ANSI字符串为128进制）的大整数，因此我们可以利用直接取余法，在线性时间内直接算出Hash函数值。 为了保证效果，仍然不能选择太接近2n的数；尤其是当我们把字符串看成一个2p进制数的时候，选择m= 2p -1会使得该字符串的任意一个排列的Hash函数值都相同。 排列的Hash函数 让排列与数1--A(m,n)之间建立一一对应的关系。 引理 从0到n!-1的任何自然数可唯一地表示为 全排列与自然数之一一对应 不妨设n个元素为1,2,..,n。对应的规则如下:设序列 (an-1 ,…, a1) 对应的某一排列，其中ai可以看做是排列p中数i+1所在位置右边比i+1小的数的个数。以排列4132为例，它是元素1,2,3,4的一个排列。4的右边比4小的数的数目为3，所以a3=3。3右边比3小的数的数目为0，即a2=0 。同理a1=1 。所以排列4213对应于变进制的301，也就是十进制的19；反过来也可以从19反推到301，再反推到排列4213。 Hash函数的冲突 冲突??? 　两个不同的关键字