哈尔滨市第三中学 刘翀

5. 总结

　　本文介绍了有关哈希表方面的内容，分析了它的特点和优点，指出了应用需要注意的问题，并且重点举了几个例子来说明它在竞赛中的应用。希望读者读完本文能够对哈希表有更全面的了解，并能在竞赛中应用自如！

参考文献：

　　1． 《算法与数据结构（第二版）》 付清祥 王晓东 编著
　　2． 《奥赛兵法信息学（计算机）》 朱全民 主编
　　3． 《SGOI-8 烦恼的设计师 解题报告》 曙光网信息学
　　4． 《Data Structures》 USACO Training Gate

附录：

　　这是我第一次写论文，水平很有限，希望大家指出我的缺点和不足！
　　我的邮箱 iliuchong@sohu.com

　　下面是所有前面提到的程序。其中只有 SGOI-8 Flowers 的程序是网上提供的标程，其余的都是我自己写的，并且已经通过所有测试数据。

1． 哈希表的程序

　　program subset;
　　　const max=15889;
　　　var fin,fout:text;
　　　　　a,b,s,j:longint;
　　　　　index:array[0..max-1]of longint;
　　　　　t:real;
　　　function locate(t:longint):longint;
　　　　var tmp:longint;
　　　　begin
　　　　　tmp:=t mod max;
　　　　　while (index[tmp]<>0)and(index[tmp]<>t) do
　　　　　　tmp:=(tmp+1) mod max;
　　　　　locate:=tmp;
　　　　end;
　　　procedure int(t:longint);
　　　　begin
　　　　　index[locate(t)]:=t;
　　　　end;
　　function member(t:longint):boolean;
　　　begin
　　　　if index[locate(t)]=t then member:=true
　　　　　　　　　　　　　　　　　else member:=false;
　　　end;
　　procedure init;
　　　var shu,i:longint;
　　　begin
　　　　assign(fin,'subset.in');
　　　　assign(fout,'subset.out');
　　　　reset(fin);
　　　　rewrite(fout);
　　　　close(fout);
　　　　fillchar(index,sizeof(index),0);
　　　　read(fin,a);
　　　　for i:=1 to a do
　　　　　begin
　　　　　　read(fin,shu);
　　　　　　int(shu);
　　　　　end;
　　　end;
　　procedure main;
　　　var i,shu:longint;
　　　begin
　　　　read(fin,b);
　　　　s:=0;
　　　　for i:=1 to b do
　　　　　begin
　　　　　　read(fin,shu);
　　　　　　if not member(shu) then inc(s);
　　　　　end;
　　　end;
　　procedure out;
　　　begin
　　　　writeln(s);
　　　　close(fin);
　　　end;
　　begin
　　　t:=meml[$40:$6C];
　　　for j:=1 to 50 do
　　　　begin
　　　init;
　　　main;
　　　out;
　　　　end;
　　　t:=meml[$40:$6C]-t;
　　　writeln(t/18.181818:0:8);
　　end.

2． 快速排序+二分查找的程序

　　program subset;
　　　const max=16101;
　　　var a,b,s,j:longint;
　　　　　da:array[1..max]of longint;
　　　　　fin:text;
　　　　　t:real;
　　　procedure init;
　　　　var i:longint;
　　　　begin
　　　　　assign(fin,'subset.in');
　　　　　reset(fin);
　　　　　read(fin,a);
　　　　　for i:=1 to a do
　　　　　　read(fin,da[i]);
　　　end;
　　procedure sort(m,n:longint);
　　　var p:longint;
　　　function locate:longint;
　　　　var value,i,j,temp:longint;
　　　　begin
　　　　　value:=da[(m+n) div 2];
　　　　　i:=m-1;
　　　　　j:=n+1;
　　　　　while true do
　　　　　　begin
　　　　　　　repeat
　　　　　　　　inc(i);
　　　　　　　until da[i]>=value;
　　　　　　　repeat
　　　　　　　　dec(j);
　　　　　　　until da[j]<=value;
　　　　　　　if i<j then begin
　　　　　　　　　　　temp:=da[i];
　　　　　　　　　　　da[i]:=da[j];
　　　　　　　　　　　da[j]:=temp;
　　　　　　　　　　end
　　　　　　　　else begin
　　　　　　　　　　if I<>j then locate:=j
　　　　　　　　　　　　　　　else locate:=j-1;;
　　　　　　　　　　exit;
　　　　　　　　　end;
　　　　　end;
　　　end;
　　begin
　　　if m<n then begin
　　　　　　　　　　　　p:=locate;
　　　　　　　　　　　　sort(m,p);
　　　　　　　　　　　　sort(p+1,n);
　　　　　　　　　　　end;
　　　end;
　　procedure main;
　　　var i,x:longint;
　　　function member(x:longint):boolean;
　　　　var p,e,mid:longint;
　　　　begin
　　　　　p:=1;
　　　　　e:=a;
　　　　　mid:=(p+e) div 2;
　　　　　while (p<>mid)and(e<>mid)and(da[mid]<>x) do
　　　　　　begin
　　　　　　　if x=da[mid] then begin
　　　　　　　　　　　　　　　　　　　member:=true;
　　　　　　　　　　　　　　　　　　　exit;
　　　　　　　　　　　　　　　　　　end;
　　　　　　　if x<da[mid] then begin
　　　　　　　　　　　　　　　　　　　e:=mid;
　　　　　　　　　　　　　　　　　　　mid:=(p+e)div 2;
　　　　　　　　　　　　　　　　　　end
　　　　　　　　　　　　　　else begin
　　　　　　　　　　　　　　　　　　p:=mid;
　　　　　　　　　　　　　　　　　　mid:=(p+e)div 2;
　　　　　　　　　　　　　　　　　end;
　　　　　　　end;
　　　　　　if (da[p]=x)or(da[e]=x)or(da[mid]=x) then member:=true
　　　　　　　　　　　　　　　　　　　　　　　　　　else member:=false;
　　　　　end;
　　　　begin
　　　　　read(fin,b);
　　　　　s:=0;
　　　　　for i:=1 to b do
　　　　　　begin
　　　　　　　read(fin,x);
　　　　　　　if not member(x) then inc(s);
　　　　　　end;
　　　end;
　　procedure out;
　　　begin
　　　　writeln(s);
　　　　close(fin);
　　　end;
　　begin
　　　t:=meml[$40:$6C];
　　　for j:=1 to 50 do
　　　　begin
　　　init;
　　　sort(1,a);
　　　main;
　　　out;
　　　　end;
　　　t:=meml[$40:$6C]-t;
　　　writeln(t/18.181818:0:8);
　　end.

　　　　　　　　　　　　　　　　　　　　　　相关链接：浅谈竞赛中哈希表的应用（一）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（二）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（三）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（四）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（五）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（六）
　　　　　　　　　　　　　　　　　　　　　　　　　　　浅谈竞赛中哈希表的应用（七）