麻省理工大学算法导论lecture08

《麻省理工大学算法导论lecture08》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntroductiontoAlgorithms6.046J/18.401J/SMA5503Lecture8Prof.CharlesE.LeisersonAweaknessofhashingProblem:Foranyhashfunctionh,asetofkeysexiststhatcancausetheaverageaccesstimeofahashtabletoskyrocket.•Anadversarycanpickallkeysfrom{k∈U:h(k)=i}forsomesloti.IDEA:Choosethehashf

2、unctionatrandom,independentlyofthekeys.•Evenifanadversarycanseeyourcode,heorshecannotfindabadsetofkeys,sinceheorshedoesn’tknowexactlywhichhashfunctionwillbechosen.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay12L8.2UniversalhashingDefinition.LetUbeauniverseofkeys

3、,andletHbeafinitecollectionofhashfunctions,eachmappingUto{0,1,…,m–1}.WesayHisuniversalifforallx,y∈U,wherex≠y,wehave

4、{h∈H:h(x)=h(y)}

5、=

6、H

7、/m.Thatis,thechanceHofacollision{h:h(x)=h(y)}betweenxandyis1/mifwechooseh

8、H

9、randomlyfromH.m©2001byCharlesE.LeisersonIntroductiontoAlg

10、orithmsDay12L8.3UniversalityisgoodTheorem.Lethbeahashfunctionchosen(uniformly)atrandomfromauniversalsetHofhashfunctions.SupposehisusedtohashnarbitrarykeysintothemslotsofatableT.Then,foragivenkeyx,wehaveE[#collisionswithx]

11、rithmsDay12L8.4ProofoftheoremProof.LetCbetherandomvariabledenotingxthetotalnumberofcollisionsofkeysinTwithx,andlet1ifh(x)=h(y),c=xy0otherwise.Note:E[cxy]=1/mandCx=∑cxy.y∈T−{x}©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay12L8.5Proof(continued)E[Cx]=E∑cxy•Take

12、expectationy∈T−{x}ofbothsides.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay12L8.6Proof(continued)E[Cx]=E∑cxy•Takeexpectationy∈T−{x}ofbothsides.=∑E[cxy]•Linearityofy∈T−{x}expectation.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay12L8.7Proof(cont

13、inued)E[Cx]=E∑cxy•Takeexpectationy∈T−{x}ofbothsides.=∑E[cxy]•Linearityofy∈T−{x}expectation.=∑1/m•E[cxy]=1/m.y∈T−{x}©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay12L8.8Proof(continued)E[Cx]=E∑cxy•Takeexpectationy∈T−{x}ofbothsides.=∑E[cxy]•Linearity

14、ofy∈T−{x}expectation.=∑1/m•E[cxy]=1/m.y∈T−{x}n−1=.•Algebra.m©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay12L8.