1、HASH函数及其应用函数及其应用雅礼 朱全民1ppt课件问题一 读入n个正整数，每个数小于109 查询某个数是否在这n个数中出现 一共查询m次 n=100000 m=1000002ppt课件in.txt5 - 5个数816353 - 询问3次369out.txtYESYESNO3ppt课件分析 这题可以先对n个数进行快速排序，然后对于每次询问，用二分查找解决。 有没有更快的做法？4ppt课件什么是HASH？ 哈希表是一种高效的数据结构 。 散列方法是使用函数h将U映射到表T0.m-1的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O
2、(1)时间内就可完成查找。5ppt课件一、整数的一、整数的Hash函数函数 构造方法（构造方法（1）1直接取余法直接取余法关键字关键字k除以除以m，取余数作为在，取余数作为在Hash表中表中的位置。函数表达式可以写成：的位置。函数表达式可以写成：h(k)=k mod m一般一般m选择为素数选择为素数6ppt课件一、整数的一、整数的Hash函数函数 构造方法（构造方法（2）2乘积取整法乘积取整法关键字关键字k乘以一个在乘以一个在(0,1)中的实数（最好是无理中的实数（最好是无理数），得到一个数），得到一个(0,1)之间的实数；取出其小数部之间的实数；取出其小数部分，乘以分，乘以m，再取整数部分，
3、即得，再取整数部分，即得K在在Hash表中表中的位置。函数表达式可以写成：的位置。函数表达式可以写成：例如例如 就是一个好的选择。就是一个好的选择。1mod)(kAMkh215 A7ppt课件一、整数的一、整数的Hash函数函数 构造方法（构造方法（3）3平方取中法平方取中法把关键字把关键字K平方，然后取中间的平方，然后取中间的 位作为位作为Hash函数值函数值返回。由于返回。由于K的每一位都会对其平方中间的若干位产生影的每一位都会对其平方中间的若干位产生影响，因此这个方法的效果也是不错的。但是对于比较小的响，因此这个方法的效果也是不错的。但是对于比较小的K值效果并不是很理想，实现起来也比较繁
4、琐。为了充分值效果并不是很理想，实现起来也比较繁琐。为了充分利用利用Hash表的空间，表的空间，M最好取最好取2的整数次幂。例如的整数次幂。例如,表容量表容量M=24=16，关键值，关键值K=100，那么，那么 h(k)=8M2log8ppt课件回到问题一n最多为100000flag数组不开到109，但可以开flag1.3000009ppt课件可用取余法可用取余法10ppt课件解决冲突 将数组改为链表11ppt课件问题二 问题一中的正整数改称字符串 （每个字符串的长度不超过20） 还是输入n个字符串，一共m次询问12ppt课件 in.txt 4 - 5个字符串 cat banana apple
5、 dog 3 - 询问3次 banana fruit pet out.txt YES NO NO13ppt课件二、字符串的二、字符串的Hash函数函数 构造方法构造方法 字符串本身就可以看成一个字符串本身就可以看成一个256进制（进制（ANSI字符字符串为串为128进制）的大整数，因此我们可以利用直接进制）的大整数，因此我们可以利用直接取余法，在线性时间内直接算出取余法，在线性时间内直接算出Hash函数值。函数值。 为了保证效果，仍然不能选择太接近为了保证效果，仍然不能选择太接近2n的数；尤的数；尤其是当我们把字符串看成一个其是当我们把字符串看成一个2p进制数的时候，进制数的时候，选择选择m=
6、 2p -1会使得该字符串的任意一个排列的会使得该字符串的任意一个排列的Hash函数值都相同。函数值都相同。 14ppt课件排列的Hash函数 让排列与数让排列与数1-A(m,n)之间建立一一对应的关系。之间建立一一对应的关系。 引理引理 从从0到到n!-1的任何自然数可唯一地表示为的任何自然数可唯一地表示为 全排列与自然数之一一对应全排列与自然数之一一对应不妨设不妨设n个元素为个元素为1,2,.,n。对应的规则如下。对应的规则如下:设序列设序列 (an-1 , a1) 对应的某一排列，其中对应的某一排列，其中ai可以看做是排列可以看做是排列p中数中数i+1所在位置右边比所在位置右边比i+1小
7、的数的个数。以排列小的数的个数。以排列4132为例，它为例，它是元素是元素1,2,3,4的一个排列。的一个排列。4的右边比的右边比4小的数的数目为小的数的数目为3，所以所以a3=3。3右边比右边比3小的数的数目为小的数的数目为0，即，即a2=0 。同理。同理a1=1 。所以排列所以排列4213对应于变进制的对应于变进制的301，也就是十进制的，也就是十进制的19；反；反过来也可以从过来也可以从19反推到反推到301，再反推到排列，再反推到排列4213。Nn11!1!nkkkn! 1!2!1121ananamnn15ppt课件Hash函数的冲突 冲突冲突 两个不同的关键字，由于散列函数值相同，因
8、而被映两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突射到同一表位置上。该现象称为冲突(Collision)或碰撞。或碰撞。 安全避免冲突的条件安全避免冲突的条件最理想的解决冲突的方法是安全避免冲突。要做到这一点最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：必须满足两个条件：其一是其一是|U|m其二是选择合适的散列函数。其二是选择合适的散列函数。 这只适用于这只适用于|U|较小，且关键字均事先已知的情况，此较小，且关键字均事先已知的情况，此时经过精心设计散列函数时经过精心设计散列函数h有可能完全避免冲突。有可能完全避免冲突。 影响冲突的因素影
9、响冲突的因素 冲突的频繁程度除了与冲突的频繁程度除了与h相关外，还与表的填满程度相关外，还与表的填满程度相关。相关。 设设m和和n分别表示表长和表中填人的结点数，则将分别表示表长和表中填人的结点数，则将=n/m定义为散列表的装填因子定义为散列表的装填因子(Load Factor)。越大，越大，表越满，冲突的机会也越大。通常取表越满，冲突的机会也越大。通常取1。16ppt课件解决冲突的方法 开散列方法开散列方法( open hashing，也称为拉链法，也称为拉链法，separate chaining ) 闭散列方法闭散列方法( closed hashing，也称为开地也称为开地址方法，址方法，
10、open addressing )。 这两种方法的不同之处在于：这两种方法的不同之处在于：开开散列法散列法把发生冲突的关键码存储在散列把发生冲突的关键码存储在散列表主表之外，表主表之外，而闭散列法把发生冲突的关键码存储在表而闭散列法把发生冲突的关键码存储在表中另一个槽内。中另一个槽内。17ppt课件拉链法拉链法 开散列方法的开散列方法的一种简单形式一种简单形式是把散列表中是把散列表中的每个槽定义的每个槽定义为一个为一个链表链表的的表头。散列到表头。散列到一个特定槽的一个特定槽的所有记录都放所有记录都放到这个槽的到这个槽的链链表表中。中。18ppt课件线性探查法(Linear Probing)
11、将散列表将散列表T0.m-1看成是一个循环向量，若初始探查的地看成是一个循环向量，若初始探查的地址为址为d(即即 h(key)=d)，则最长的探查序列为：，则最长的探查序列为：d，d+l，d+2，m-1，0，1，d-1 .即即:探查时从地址探查时从地址d开始，首开始，首先探查先探查Td，然后依次探查，然后依次探查Td+1，直到，直到Tm-1，此，此后又循环到后又循环到T0，T1，直到探查到，直到探查到 Td-1为止。探为止。探查过程终止于三种情况：查过程终止于三种情况：(1)若当前探查的单元为空，则表示查找失败（若是插入则将若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；写
12、入其中）；(2)若当前探查的单元中含有若当前探查的单元中含有key，则查找成功，但对于插入，则查找成功，但对于插入意味着失败；意味着失败；(3)若探查到若探查到Td-1时仍未发现空单元也未找到时仍未发现空单元也未找到key，则无论是，则无论是查找还是插入均意味着失败查找还是插入均意味着失败(此时表满此时表满)。19ppt课件思考题思考题1 ： distinct【试题描述】【试题描述】 陶陶为了给一道平面几何题出数据，需要产生陶陶为了给一道平面几何题出数据，需要产生 N N 个点个点 (x(xi i,y,yi i)。已知。已知x,yx,y是由伪随机函数顺序产生，即：是由伪随机函数顺序产生，即：
13、Xi+1 = (XXi+1 = (Xi i * *Ax+Bx+iAx+Bx+i) mod ) mod CxCx Yi+1 = (Y Yi+1 = (Yi i * *Ay+By+iAy+By+i) mod Cy) mod Cy X1, X1, Ax,Bx,Cx,YAx,Bx,Cx,Y1, 1, Ay,By,CyAy,By,Cy 是事先给定是事先给定最少要产生前多少项时，正好有最少要产生前多少项时，正好有 N N 个不相同的点。个不相同的点。【数据范围】【数据范围】 1=N=1,000,000, 1=N=1,000,000, 其它所有数据都在其它所有数据都在1.1,000,000,0001.1,0
14、00,000,000范围内。范围内。20ppt课件分析1. 数据最大为数据最大为106，O(N2)超时。每次要求查超时。每次要求查找某个数，由于是动态的，不好先排序。找某个数，由于是动态的，不好先排序。2. 用用O(NlogN)时间复杂度即可，可以用平衡时间复杂度即可，可以用平衡树之类。但现有编程复杂度高，时间系数树之类。但现有编程复杂度高，时间系数也大。也大。3. 对快速插入、查找操作，比较简洁有效的对快速插入、查找操作，比较简洁有效的方法是方法是hash表算法。表算法。21ppt课件 【试题描述】【试题描述】 农民约翰打算建一个新的矩形谷仓。但是农民约翰打算建一个新的矩形谷仓。但是,矩形谷
15、仓的矩形谷仓的4个个角落不能在落在软土路基上角落不能在落在软土路基上,只能落在一些固定点上。现只能落在一些固定点上。现在在,他已经找到地面上有他已经找到地面上有N（4 = N = 1,000）个点）个点,角落角落只可以落在这些点上。他想知道依次每加多一个点，可以只可以落在这些点上。他想知道依次每加多一个点，可以建立新谷仓的方法数量建立新谷仓的方法数量,请你帮助他找到答案。请你帮助他找到答案。【数据范围】【数据范围】 1 = N = 1,000 所有的所有的x,y都不会超过都不会超过16,000。 所有点都是不同的。所有点都是不同的。思考题思考题2：Allbarns22ppt课件分析1. 从样例
16、知道矩形是可以不平行于从样例知道矩形是可以不平行于X，Y轴的轴的。2. N 5000，但是，但是 262 5000 ），于是我们就选），于是我们就选取取3个位置上的字符。由于给定的字符串的长度从个位置上的字符。由于给定的字符串的长度从 1-12 都有可能，为了容易实现，选取最开始的都有可能，为了容易实现，选取最开始的1个字符和最末个字符和最末尾的尾的2个字符。让这个字符。让这3个字符组成个字符组成27进制的进制的3位数，则这个位数，则这个数的值就是这个字符串的编码。这样哈希函数就设计出来数的值就是这个字符串的编码。这样哈希函数就设计出来了！了！25ppt课件思考题思考题4：烦恼的设计师：烦恼的
17、设计师 给定两个正给定两个正6边形的花坛，要求求出从第一个变化到第二边形的花坛，要求求出从第一个变化到第二个的最小操作次数以及操作方式。个的最小操作次数以及操作方式。 一次操作是：选定不在边上的一盆花，将这盆花周围的一次操作是：选定不在边上的一盆花，将这盆花周围的6盆花按照顺时针或者逆时针的顺序依次移动一个单位。盆花按照顺时针或者逆时针的顺序依次移动一个单位。 一个花坛里摆放的不同种类的花不超过一个花坛里摆放的不同种类的花不超过3种，对于任意两种，对于任意两种花，数量多的花的盆数至少是数量少的花的种花，数量多的花的盆数至少是数量少的花的2倍。倍。26ppt课件 输入：输入：输入文件共输入文件共
18、11行，行，15行描述花坛的初始状态，行描述花坛的初始状态，711行表行表示花盆应摆放的位置。中间以空行分隔。示花盆应摆放的位置。中间以空行分隔。5行数字分别表行数字分别表示花坛的示花坛的5个行，其中第个行，其中第1、5两行有两行有3个整数，第个整数，第2、4两两行有行有4个整数，第个整数，第3行有行有5个整数，表示每一行的花的类型，个整数，表示每一行的花的类型，不同的数代表不同种类的花。不同的数代表不同种类的花。 输出：输出： 输出文件第一行包含一个整数输出文件第一行包含一个整数T即最少的操作数，数据保即最少的操作数，数据保证证20步之内有解。以下步之内有解。以下T行输出操作序列，每行代表一
19、次行输出操作序列，每行代表一次操作，包括操作，包括3个整数个整数Xi,Yi,Ki,（Xi,Yi）表示第）表示第i步转动第步转动第Xi行，第行，第Yi盆花下的转盘，当盆花下的转盘，当Ki为为0时表示向顺时针方向转时表示向顺时针方向转动，动，Ki为为1时表示向逆时针方向转动，如有多种方案，任时表示向逆时针方向转动，如有多种方案，任意输出其中一种即可。意输出其中一种即可。27ppt课件题意简述题意简述 本题要求将一个边长为本题要求将一个边长为3的六边形的六边形阵阵（共（共19个元素）通过一定的规则变换，从初始个元素）通过一定的规则变换，从初始状态转化为目标状态，并使变换的次数最状态转化为目标状态，并
20、使变换的次数最少。具体规则如下：每次选定除边缘之外少。具体规则如下：每次选定除边缘之外的的7个元素之一，将其周围的个元素之一，将其周围的6个元素沿顺个元素沿顺时针方向或逆时针方向移动一个位置。输时针方向或逆时针方向移动一个位置。输入初始状态和目标状态，输出最少变换次入初始状态和目标状态，输出最少变换次数以及一种是变换次数最少的变换方法。数以及一种是变换次数最少的变换方法。28ppt课件分析分析 首先确定本题可以用广度优先搜索处理，然首先确定本题可以用广度优先搜索处理，然后来看问题的规模。后来看问题的规模。 正正6边形共有边形共有19个格子可以用来放花，而且个格子可以用来放花，而且根据最后一句限
21、定条件根据最后一句限定条件一个花坛里摆放的不同种类的花不超过一个花坛里摆放的不同种类的花不超过3种种。对于任意两种花，数量多的花的盆数至少是数量对于任意两种花，数量多的花的盆数至少是数量少的花的少的花的2倍倍。 至多只能存在至多只能存在 C(2,19) * C(5,17) = 1058148 种状态，用宽搜完全可行。种状态，用宽搜完全可行。29ppt课件用用HASH表判重表判重 然而在广搜的时候，可以预料产生的重复然而在广搜的时候，可以预料产生的重复节点是相当多的，需要迅速判重才能在限节点是相当多的，需要迅速判重才能在限定时间内出解，因此想到了哈希表。定时间内出解，因此想到了哈希表。 那么这个
22、哈希函数如何设计呢？注意到那么这个哈希函数如何设计呢？注意到19个格子组成个格子组成6边形是有顺序的，而且每一个边形是有顺序的，而且每一个格子只有格子只有3种可能情况，那么用种可能情况，那么用3进制进制19位位数最大数最大 320-1=3486784400 ，完全可以承受。，完全可以承受。 于是我们将每一个状态与一个整数对应起于是我们将每一个状态与一个整数对应起来，使用除余法就可以了。来，使用除余法就可以了。 30ppt课件思考题思考题5：方程的解数：方程的解数 已知一个n元高次方程： 其中：x1, x2 xn是未知数， k1,k2 kn是系数， p1,p2 pn是指数，且方程中的所有数均为整
23、数。假设未知数1 xiM, i=1,2,n，求这个方程的整数解的个数。约束条件约束条件1n6；1M150；方程的整数解的个数小于23131ppt课件分析（1） 题目要求出给定的方程解的个数，这个方题目要求出给定的方程解的个数，这个方程在最坏的情况下可以有程在最坏的情况下可以有6个未知数，而且个未知数，而且次数由输入决定。这样就不能利用数学方次数由输入决定。这样就不能利用数学方法直接求出解的个数，而且注意到解的范法直接求出解的个数，而且注意到解的范围最多围最多150个数，因此恐怕只能使用枚举法个数，因此恐怕只能使用枚举法了。最简单的思路是穷举所有未知数的取了。最简单的思路是穷举所有未知数的取值，
24、这样时间复杂度是值，这样时间复杂度是 O(M6) ，无法承受。，无法承受。 否缩小枚举的范围呢？否缩小枚举的范围呢？32ppt课件分析(2) 我们再次注意到我们再次注意到M 的范围，若想不超时，似乎算法的复杂的范围，若想不超时，似乎算法的复杂度上限应该是度上限应该是 O(M3) 左右，这是因为左右，这是因为 1503 10000000 。这就启示我们能否仅仅通过枚举这就启示我们能否仅仅通过枚举3个未知数的值来找到答个未知数的值来找到答案呢？案呢？ 如果这样，前一半式子的值如果这样，前一半式子的值 S 可以确定，这时只要枚举可以确定，这时只要枚举后后3 个数的值，检查他们的和是否等于个数的值，检
25、查他们的和是否等于 -S 即可。这样只即可。这样只相当于在相当于在 O(M3) 前面加了一个系数，当然还需要预先算前面加了一个系数，当然还需要预先算出出 1 到到 150 的各个幂次的值。的各个幂次的值。 想到了这里，问题就是如何迅速的找到某个想到了这里，问题就是如何迅速的找到某个 S 是否曾经是否曾经出现过，以及出现过了多少次，于是又变成了出现过，以及出现过了多少次，于是又变成了“某个元素某个元素是否在给定集合中是否在给定集合中”这个问题。这个问题。 所以，我们还是使用哈希表解决这个问题。至于哈希函数，所以，我们还是使用哈希表解决这个问题。至于哈希函数，还是把还是把 S 的值作为关键字使用除余法即可。有一点需要的值作为关键字使用除余法即可。有一点需要注意，我们不仅需要纪录某个注意，我们不仅需要纪录某个 S 是否出现，出现的次数是否出现，出现的次数也很重要，所以需要加了一个存储出现次数的域。也很重要，所以需要加了一个存储出现次数的域。33ppt课件
