个电acm课件152014版14hash及应用

ACM程序设计杭州电子科技大学刘春英

期末考试相关介绍日期：6月13号地点：待定内容：略第十四讲Hash及应用

(Hash&Application)导引问题

(HDOJ-1425sort)ProblemDescription给你n个整数，请按从大到小的顺序输出其中前m大的数。Input每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。Output对每组测试数据按从大到小的顺序输出前m大的数。初步分析题目特点：数据量大数据在一定范围

思考：常规算法的缺陷？是否可以将“数据值”和“存储位置”做某种对应？经典所在：存储完毕，则排序完毕！再思考（1425加强版）：原题描述： 第二行包含n个各不相同，且都处于区间[-500000,500000]的整数加强版(思考)： 如果整数允许相同怎么处理？Hash表简介——基本原理

哈希表（散列表）的基本原理： 使用一个下标范围比较大的数组来存储元素，一般通过设计一个函数（哈希函数，即散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，然后用该数组单元来存储对应元素。Hash表简介——函数构造无定式，方法很多最常见的方法：除余法 H(k)=kmodp

(p一般选取适当大的素数)常用的经典字符串Hash后面介绍Hash表简介——冲突由于不能够保证每个元素的关键字与函数值是一一对应的，因此很有可能出现如下情况：“对于不同的元素关键字，Hash函数计算出了相同的函数值”，这就是产生了所谓的“冲突”。换句话说，就是Hash函数把不同的元素分在了相同的下标单元。Hash表简介——冲突解决 方法很多～ 常用方法：线性探测再散列技术 即：当h(k)位置已经存储有元素的时候，依次探查(h(k)+i)modS,i=1,2,3…，直到找到空的存储单元为止。其中，S为数组长度。 特别地，如果将数组扫描一圈仍未发现空单元，则说明哈希表已满，这会带来麻烦，但是，该情况完全可以通过扩大数组范围来避免。Hash表简介——基本操作Hash表初始化（0或-1或其它）哈希函数运算插入元素（包含冲突解决）定位（需考虑可能冲突的情况）总结：Hash函数评价标准：低冲突率易于编码Hash函数特点：优点：数据存储和查找效率高 （几乎是常数时间）缺点：消耗较多内存（内存很便宜哪～）Hash主要应用：查找元素是否属于集合搜索中的状态表示Hash-应用基础第一部分整数Hash例1(HDOJ-1496Equations)Considerequationshavingthefollowingform:a*x12+b*x22+c*x32+d*x42=0

a,b,c,dareintegersfromtheinterval[-50,50]andanyofthemcannotbe0.Itisconsiderasolutionasystem(x1,x2,x3,x4)thatverifiestheequation,xiisanintegerfrom[-100,100]andxi!=0,anyi∈{1,2,3,4}.Determinehowmanysolutionssatisfythegivenequation.HDOJ-1496题目分析题意简单（类似“百钱买百鸡”问题）传统方法是（几重循环）？复杂度？上述方法如何判断两端相等？（查找？）可行方案（两重循环＋Hash存储查找）Hash表大小？HDOJ-1496参考代码（1）//bylinle#include"stdio.h"#include"memory.h"intpin[101];inthash[2000003];intmain(){inta,b,c,d;inti,j,sum;for(i=1;i<101;i++)pin[i]=i*i;while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){

……}}if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0)){printf("0\n");continue;}memset(hash,0,sizeof(hash));for(i=1;i<=100;i++)for(j=1;j<=100;j++)hash[a*pin[i]+b*pin[j]+1000000]++;sum=0;for(i=1;i<=100;i++)for(j=1;j<=100;j++)sum+=hash[-(c*pin[i]+d*pin[j])+1000000];printf("%d\n",sum*16);HDOJ-1496经验之谈“两层循环最多只可能产生10000个不同的结果,开200W的数组将会浪费很多初始化的时间,所以开小数组+处理冲突会比较好.”——byLaiLi具体见论坛讨论：

HDOJ-1496参考代码（2）//bylaili#include<stdio.h>#include<memory.h>#defineMAX50021intf[MAX],g[MAX];inthash(intk){intt=k%MAX;if(t<0)t+=MAX;while(f[t]!=0&&g[t]!=k)t=(t+1)%MAX;returnt;}intmain(){inta,b,c,d,p,i,j,s,n,t[101];for(i=1;i<=100;i++)t[i]=i*i;while(scanf("%d%d%d%d",&a,&b,&c,&d)>0){

……}}if(a>0&&b>0&&c>0&&d>0||a<0&&b<0&&c<0&&d<0){printf("0\n");continue;}memset(f,0,sizeof(f));n=0;for(i=1;i<=100;i++)for(j=1;j<=100;j++){s=a*t[i]+b*t[j];p=hash(s);g[p]=s;f[p]++;}for(i=1;i<=100;i++)for(j=1;j<=100;j++){s=-(c*t[i]+d*t[j]);p=hash(s);n+=f[p];}printf("%d\n",n*16);Hash-应用重点第二部分字符串Hash例2—(HDOJ-1800)FlyingtotheMarsHDOJ-1800题目分析除去马甲，本题的本质是——求相同级别（level）的人最多是几个。如果level的范围不大的话（64位整数可以表示）——本题很简单，简单贪心本题的难点：level的范围较大，需用大数或者字符串比较（去首0）效率较高、编程简单的方法：Hash!此外，字典树也是不错的选择参考源码(HDOJ-1800)//bylinle#include"stdio.h"#include"memory.h"#defineMAXN7003inlineintELFhash(char*key){unsignedlongh=0;unsignedlongg;while(*key){h=(h<<4)+*key++;g=h&0xf0000000L;if(g)h^=g>>24;h&=~g;}returnh;}inthash[MAXN],count[MAXN];intmaxit,n;inlinevoidhashit(char*str){intk,t;while(*str=='0')str++;k=ELFhash(str);t=k%MAXN;while(hash[t]!=k&&hash[t]!=-1)t=(t+10)%MAXN;if(hash[t]==-1)count[t]=1,hash[t]=k;elseif(++count[t]>maxit)maxit=count[t];}intmain(){charstr[100];while(scanf("%d",&n)!=EOF){memset(hash,-1,sizeof(hash));for(maxit=1,gets(str);n>0;n--){gets(str);hashit(str);}printf("%d\n",maxit);}}例3—(HDOJ-1043Eight)经典八数码问题：

123

x46

758

HDOJ-1043题目分析是否有解的判断：逆序数的奇偶性不变说明：上一行的确切说明应该是（略）算法主体：BFS本讲关注：搜索状态如何表示（哪些方法）？经典方法：排列数的Hash表示优点：存储状态的空间较小（多少足矣？）效率高编码方便八数码状态的Hash表示/*八数码的经典哈希求其排列数功能：求一个数组是第几个字典排列（假设每个元素都不同）*/intfact[9]={1,1,2,6,24,120,720,5040,40320};inthash(chars[]){ inti,j,n,c; for(i=n=0;i<8;++i) { c=0; for(j=i+1;j<9;++j) if(s[j]<s[i])++c; n+=c*fact[8-i]; } returnn;}经典提升避免字符串比较操作的方法：多次Hash~具体方法…参考：

相关练习HDOJ-1425 SortHDOJ-1800 FlyingtotheMarsHDOJ-1496 EquationsHDOJ-1228 A+BHDOJ-1043 Eight附：常用字符串Hash（1）inl