【導(dǎo)讀】哈希表是一種高效的數(shù)據(jù)結(jié)構(gòu)。本文分五個(gè)部分：首先提出了哈希表的優(yōu)點(diǎn)，其次。介紹了它的基礎(chǔ)操作，接著從簡(jiǎn)單的例子中作了效率對(duì)比，指出其適用范圍以及特點(diǎn)，然后通過例子說明了如何在題目中運(yùn)用哈希表以及需要注意的問題，最后總結(jié)全文。哈希表的應(yīng)用近兩年才在NOI中出現(xiàn)，作為一種高效的數(shù)據(jù)結(jié)構(gòu)，它正在競(jìng)賽中發(fā)揮著越來越重要的作用。是常數(shù)時(shí)間；而代價(jià)僅僅是消耗比較多的內(nèi)存。然而在當(dāng)前可利用內(nèi)存越來越多的情況。下，用空間換時(shí)間的做法是值得的。另外，編碼比較容易也是它的特點(diǎn)之一。哈希表又叫做散列表，分為"開散列"和"閉散列"?？紤]到競(jìng)賽時(shí)多數(shù)人通常避免。我們使用一個(gè)下標(biāo)范圍比較大的數(shù)組來存儲(chǔ)元素。總的來說，"直接定址"與"解決沖突"是哈希表的兩大特點(diǎn)?？盏拇鎯?chǔ)單元為止（或者從頭到尾掃描一圈仍未發(fā)現(xiàn)空單元，這就是哈希表已經(jīng)滿了，注意到兩個(gè)程序的用時(shí)并不像我們期望的那樣，總是哈希表快。

　　

【正文】 i]=now then exit。 i:=next[i]。 end。 if q[i]=now then exit。 inc(qs)。 q[qs]:=now。 next[i]:=qs。 last[qs]:=nowlast。 id[qs]:=nowid。 end。 end。 begin init。 bit[1]:=1。 for i:=2 to 19 do bit[i]:=bit[i1]*3。 start:=0。 target:=0。 for i:=1 to 19 do begin start:=start+s[i]*bit[i]。 target:=target+t[i]*bit[i]。 end。 r:=0。 qs:=0。 step:=0。 insert(start)。 repeat l:=r+1。 r:=qs。 inc(step)。 for i:=l to r do for j:=1 to 7 do begin k:=change(q[i],j,1)。 nowlast:=i。 nowid:=j。 insert(k)。 k:=change(q[i],j,1)。 nowlast:=i。 nowid:=j。 insert(k)。 end。 until qs=r。 end. 5． 《方程的解》的程序 program equation。 const maxm=150。 max=4000037。 var k,p:array[1..6]of longint。 fin,fout:text。 n,m:integer。 ans:longint。 mi:array[1..maxm,1..30]of longint。 e:array[0..max1,1..2]of longint。 procedure init。 var i:integer。 begin assign(fin,39。39。)。 assign(fout,39。39。)。 reset(fin)。 rewrite(fout)。 read(fin,n)。 read(fin,m)。 for i:=1 to n do read(fin,k[i],p[i])。 close(fin)。 fillchar(e,sizeof(e),0)。 ans:=0。 end。 procedure prepute。 var i,j:integer。 tmp:longint。 begin for j:=1 to 30 do mi[1,j]:=1。 for i:=2 to m do begin tmp:=1。 for j:=1 to trunc(ln(maxlongint)/ln(i)) do begin tmp:=tmp*i。 mi[i,j]:=tmp。 end。 end。 end。 function locate(x:longint):longint。 var i,t:longint。 begin t:=abs(x) mod max。 i:=0。 while (e[(t+i)mod max,1]0)and(e[(t+i)mod max,1]x) do inc(i)。 locate:=(t+i) mod max。 end。 procedure ins(x:longint)。 var posi:longint。 begin posi:=locate(x)。 e[posi,1]:=x。 inc(e[posi,2])。 end。 procedure solve(a:integer。s:longint)。 var i:integer。 begin if a=n div 2 then begin for i:=1 to m do ins(s+k[a]*mi[i,p[a]])。 exit。 end。 for i:=1 to m do solve(a+1,s+k[a]*mi[i,p[a]])。 end。 procedure find(a:integer。s:longint)。 var i:integer。 tmp,posi:longint。 begin if a=n then begin for i:=1 to m do begin tmp:=1*(s+k[a]*mi[i,p[a]])。 posi:=locate(tmp)。 if e[posi,1]=tmp then inc(ans,e[posi,2])。 end。 exit。 end。 for i:=1 to m do find(a+1,s+k[a]*mi[i,p[a]])。 end。 procedure out。 begin writeln(fout,ans)。 close(fout)。 end。 procedure special。 var i:integer。 begin if n=1 then begin if p[1]=0 then writeln(fout,m) else writeln(fout,0)。 close(fout)。 halt。 end。 end。 begin init。 prepute。 special。 solve(1,0)。 find(n div 2+1,0)。 out。 end. 6． 《迷宮的墻》的程序 program the_100_tough_problems_0020_walls_in_the_maze。 const maxn=6001。 p=7499。 var fin,fout:text。 n,ans:integer。 data:array[1..maxn,1..4]of longint。 e:array[0..2,0..p1,1..4]of longint。 r:array[1..maxn]of longint。 procedure init。 var i,j:integer。 ch:char。 begin assign(fin,39。d:\test\39。)。 assign(fout,39。d:\test\39。)。 reset(fin)。 rewrite(fout)。 readln(fin,n)。 for i:=1 to n1 do begin read(fin,ch)。 case ch of 39。N39。:data[i,1]:=0。 39。Z39。:data[i,1]:=1。 39。C39。:data[i,1]:=2。 end。 for j:=2 to 4 do read(fin,data[i,j])。 readln(fin)。 end。 close(fin)。 ans:=n。 fillchar(e,sizeof(e),0)。 for i:=1 to n do r[i]:=i。 end。 function locate(var a,b,c,d:longint):longint。 var t:longint。 i:integer。 begin t:=r[b]*sqr(n)+r[c]*n+r[d]。 t:=t mod p。 i:=0。 while (e[a,(t+i)mod p,1]0)and(e[a,(t+i)mod p,1]r[b]) do if (e[a,(t+i)mod p,2]r[c])or(e[a,(t+i)mod p,3]r[d]) then inc(i)。 locate:=(t+i)mod p。 end。 procedure main。 var i,j,t,k:integer。 begin for i:=n1 downto 1 do begin t:=locate(data[i,1],data[i,2],data[i,3],data[i,4])。 if e[data[i,1],t,1]r[data[i,2]] then begin for j:=2 to 4 do e[data[i,1],t,j1]:=r[data[i,j]]。 e[data[i,1],t,4]:=i。 end else begin dec(ans)。 r[i]:=e[data[i,1],t,4]。 {for j:=1 to i1 do for k:=2 to 4 do if data[j,k]=i then data[j,k]:=e[data[i,1],t,4]。} end。 end。 end。 procedure out。 begin writeln({fout,}ans)。 close(fout)。 end。 begin init。 main。 out。 end.