212
Chapter5 Hashing
1
class CaseInsensitiveStringHash
2
{
3
public:
4
size_t operator( ) ) ( ( const string & s s ) ) const
5
{
6
static hash<string> > hf;
7
return hf( ( toLower( s ) );
// toLower implemented elsewhere
8
}
9
10
bool operator( ) ( ( const string g & lhs, const string g & & rhs ) ) const
11
{
12
return equalsIgnoreCase( ( lhs, rhs s ); ; // / equalsIgnoreCase is elsewhere
13
}
14
};
15
16
unordered_set<string,CaseInsensitiveStringHash,CaseInsensitiveStringHash> s;
Figure5.23 Creatingacase-insensitiveunordered_set
Theseunorderedclassescanbeusedifitisnotimportantfortheentriestobeviewable
insortedorder.Forinstance,intheword-changingexampleinSection4.8,therewere
threemaps:
1. Amapinwhichthekeyisawordlength,andthevalueisacollectionofallwordsof
thatwordlength.
2. Amapinwhichthekeyisarepresentative,andthevalueisacollectionofallwords
withthatrepresentative.
3. Amapinwhichthekeyisaword,andthevalueisacollectionofallwordsthatdiffer
inonlyonecharacterfromthatword.
Becausetheorderinwhichwordlengthsareprocesseddoesnotmatter,thefirstmap
canbean
unordered_map
.Becausetherepresentativesarenotevenneededafterthesecond
mapisbuilt,thesecondmap can bean
unordered_map
.The third map canalsobean
unordered_map
,unlesswewant
printHighChangeables
toalphabetically list thesubset of
wordsthatcanbechangedintoalargenumberofotherwords.
Theperformanceofan
unordered_map
canoftenbesuperiortoa
map
,butitishardto
knowforsurewithoutwritingthecodebothways.
5.7 HashTableswithWorst-CaseO(1)Access
Thehash tables that wehaveexaminedsofar allhave theproperty that withreason-
ableload factors,and appropriatehashfunctions,wecanexpectO(1)costonaverage
forinsertions,removes,andsearching.Butwhatistheexpectedworstcaseforasearch
assumingareasonablywell-behavedhashfunction?
How to convert pdf to ppt using - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
chart from pdf to powerpoint; convert pdf to powerpoint presentation
How to convert pdf to ppt using - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
copying image from pdf to powerpoint; how to change pdf to powerpoint
5.7 HashTableswithWorst-CaseO(1)Access
213
Forseparatechaining,assumingaloadfactorof1,thisisoneversionoftheclassic
ballsandbinsproblem:GivenNballsplacedrandomly(uniformly)inNbins,whatis
theexpectednumberofballsinthemostoccupiedbin?Theansweriswellknown to
beΘ(logN/loglogN),meaningthatonaverage,weexpectsomequeriestotakenearly
logarithmictime.Similartypesofboundsareobserved(orprovable)forthelengthofthe
longestexpectedprobesequenceinaprobinghashtable.
WewouldliketoobtainO(1)worst-casecost.Insomeapplications,suchashardware
implementationsoflookuptablesforroutersandmemorycaches,itisespeciallyimportant
thatthesearchhaveadefinite(i.e.,constant)amountofcompletiontime.Letusassume
thatNisknowninadvance,sonorehashingisneeded.Ifweareallowedtorearrangeitems
astheyareinserted,thenO(1)worst-casecostisachievableforsearches.
In theremainderofthissection we describetheearliestsolution tothisproblem,
namelyperfecthashing,andthentwomorerecentapproachesthatappeartoofferpromis-
ingalternativestotheclassichashingschemesthathavebeenprevalentformanyyears.
5.7.1 PerfectHashing
Suppose,forpurposesofsimplification,thatallNitemsareknowninadvance.Ifaseparate
chainingimplementationcouldguaranteethateachlisthadatmostaconstantnumberof
items,wewouldbedone.Weknowthataswemakemorelists,thelistswillonaverage
beshorter,sotheoreticallyifwehaveenoughlists,thenwithareasonablyhighprobability
wemightexpecttohavenocollisionsatall!
Buttherearetwofundamentalproblemswiththisapproach:First,thenumberoflists
mightbeunreasonablylarge;second,evenwithlotsoflists,wemightstillgetunlucky.
Thesecondproblemisrelativelyeasytoaddressinprinciple.Supposewechoosethe
numberofliststobeM(i.e.,TableSizeisM),whichissufficientlylargetoguaranteethat
withprobabilityatleast
1
2
,therewillbenocollisions.Thenifacollisionisdetected,we
simplyclearoutthetableandtryagainusingadifferenthashfunctionthatisindependent
ofthefirst.Ifwestillgetacollision,wetryathirdhashfunction,andsoon.Theexpected
numberoftrialswillbeatmost2(sincethesuccessprobabilityis
1
2
),andthisisallfolded
intotheinsertioncost.Section5.8discussesthecrucialissueofhowtoproduceadditional
hashfunctions.
So we are left with determining g how w large M,the number of lists, needs s to be.
Unfortunately,Mneedstobequitelarge;specificallyM=(N
2
).However,ifM=N
2
,we
canshowthatthetableiscollisionfreewithprobabilityatleast
1
2
,andthisresultcanbe
usedtomakeaworkablemodificationtoourbasicapproach.
Theorem5.2
IfNballsareplacedintoM=N
2
bins,theprobabilitythatnobinhasmorethanone
ballislessthan
1
2
.
Proof
Ifapair(i,j)ofballsareplacedinthesamebin,wecallthatacollision.LetC
i,j
bethe
expectednumberofcollisionsproducedbyanytwoballs(i,j).Clearlytheprobability
thatanytwospecifiedballscollideis1/M,andthusC
i,j
is1/M,sincethenumber
ofcollisionsthatinvolvethepair(i,j)iseither0or1.Thustheexpectednumberof
Online Convert PowerPoint to PDF file. Best free online export
Download Free Trial. Convert a PPTX/PPT File to PDF. Easy converting! We try to make it as easy as possible to convert your PPTX/PPT files to PDF.
how to change pdf to powerpoint on; convert pdf to ppt
How to C#: Convert PDF, Excel, PPT to Word
From MS-PPT and MS-PPTX to Word. RootPath + "\\" Output.docx"; // Load a PDF document PDFDocument doc = new PDFDocument(inputFilePath); // Convert it to Word
convert pdf to powerpoint slide; how to convert pdf into powerpoint presentation
214
Chapter5 Hashing
collisionsintheentiretableis
(i,j),i<j
C
i,j
.SincethereareN(N−1)/2pairs,thissum
isN(N−1)/(2M)=N(N−1)/(2N
2
)<
1
2
.Sincetheexpectednumberofcollisionsis
below
1
2
,theprobabilitythatthereisevenonecollisionmustalsobebelow
1
2
.
Ofcourse,usingN
2
listsisimpractical.However,theprecedinganalysissuggeststhefol-
lowingalternative:UseonlyNbins,butresolvethecollisionsineachbinbyusinghash
tablesinsteadoflinkedlists.Theideaisthatbecausethebinsareexpectedtohaveonlya
fewitemseach,thehashtablethatisusedforeachbincanbequadraticinthebinsize.
Figure5.24showsthebasicstructure.Here,theprimaryhashtablehastenbins.Bins1,3,
5,and7areallempty.Bins0,4,and8haveoneitem,sotheyareresolvedbyasecondary
hashtablewithoneposition.Bins2and6havetwoitems,sotheywillberesolvedintoa
secondaryhashtablewithfour(22)positions.Andbin9hasthreeitems,soitisresolved
intoasecondaryhashtablewithnine(32)positions.
Aswiththeoriginalidea,eachsecondaryhashtablewillbeconstructedusingadiffer-
enthashfunctionuntilitiscollisionfree.Theprimaryhashtablecanalsobeconstructed
severaltimesifthenumberofcollisionsthatareproducedishigherthanrequired.This
schemeisknownasperfecthashing.Allthatremainstobeshownisthatthetotalsizeof
thesecondaryhashtablesisindeedexpectedtobelinear.
Theorem5.3
IfNitemsareplacedintoaprimaryhashtablecontainingNbins,thenthetotalsizeof
thesecondaryhashtableshasexpectedvalueatmost2N.
Proof
UsingthesamelogicasintheproofofTheorem5.2,theexpectednumberofpairwise
collisionsisatmostN(N−1)/2N,or(N−1)/2.Letb
i
bethenumberofitemsthat
hashtopositioniintheprimaryhashtable;observethatb
2
i
spaceisusedforthiscell
0
1
2
3
4
5
6
2
2
= 4
7
8
9
2
2
= 4
3
2
= 9
Figure5.24 Perfecthashingtableusingsecondaryhashtables
C# TIFF: Learn to Convert MS Word, Excel, and PPT to TIFF Image
using RasterEdge.Imaging.PowerPoint; Load your PPT (.pptx) document null == doc) throw new Exception("Fail to load PowerPoint Document"); // Convert PPT to Tiff
how to convert pdf to ppt using; converting pdf to powerpoint slides
C# PDF Convert: How to Convert MS PPT to Adobe PDF Document
high performance PDF conversion from Microsoft PowerPoint (.ppt and .pptx). FILE_TYPE_UNSUPPORT: Console.WriteLine("Fail: can not convert to PDF, file type
how to convert pdf into powerpoint; convert pdf file to powerpoint
5.7 HashTableswithWorst-CaseO(1)Access
215
inthesecondaryhashtable,andthatthisaccountsforb
i
(b
i
−1)/2pairwisecollisions,
whichwewillcallc
i
.Thustheamountofspace,b
2
i
,usedfortheithsecondaryhash
tableis2c
i
+b
i
.Thetotalspaceisthen2
c
i
+
b
i
.Thetotalnumberofcollisionsis
(N−1)/2(fromthefirstsentenceofthisproof);thetotalnumberofitemsisofcourse
N,soweobtainatotalsecondaryspacerequirementof2(N−1)/2+N<2N.
Thus,theprobabilitythatthetotalsecondaryspacerequirementismorethan4Nisat
most
1
2
(since,otherwise,theexpectedvaluewouldbehigherthan2N),sowecankeep
choosinghashfunctionsfortheprimarytableuntilwegeneratetheappropriatesecondary
spacerequirement.Oncethatisdone,eachsecondaryhashtablewillitselfrequireonlyan
averageoftwotrialstobecollisionfree.Afterthetablesarebuilt,anylookupcanbedone
intwoprobes.
Perfect hashing works if the items are all known in advance. There are dynamic
schemesthatallowinsertionsanddeletions(dynamicperfecthashing),butinsteadwe
willinvestigatetwoneweralternativesthatappeartobecompetitiveinpracticewiththe
classichashingalgorithms.
5.7.2 CuckooHashing
From our previous s discussion, , we e know that in n the e balls and bins problem, , if N
items are randomly tossed into bins,the size of the largest bin is expected to be
Θ(logN/loglogN).Sincethisboundhasbeenknownforalongtime,andtheproblem
hasbeenwellstudiedbymathematicians,itwassurprisingwhen,inthemid1990s,itwas
shownthatif,ateachtoss,twobinswererandomlychosenandtheitemwastossedintothe
moreemptybin(atthetime),thenthesizeofthelargestbinwouldonlybeΘ(loglogN),
asignificantlylowernumber.Quickly,ahostofpotentialalgorithmsanddatastructures
aroseoutofthisnewconceptofthe“poweroftwochoices.”
Oneoftheideasiscuckoohashing.Incuckoohashing,supposewehaveNitems.
Wemaintaintwotables,eachmorethanhalfempty,andwehavetwoindependenthash
functionsthatcanassigneachitemtoapositionineachtable.Cuckoohashingmaintains
theinvariantthatanitemisalwaysstoredinoneofthesetwolocations.
Asanexample,Figure5.25showsapotentialcuckoohashtableforsixitems,with
twotablesofsize5(thesetablesaretoosmall,butservewellasanexample).Basedonthe
Table1
0
B
1
C
2
3
E
4
Table2
0
D
1
2
A
3
4
F
A:0,2
B:0,0
C:1,4
D:1,0
E:3,2
F:3,4
Figure5.25 Potentialcuckoohashtable.Hashfunctionsareshownontheright.For
thesesixitems,thereareonlythreevalidpositionsinTable1andthreevalidpositionsin
Table2,soitisnotclearthatthisarrangementcaneasilybefound.
VB.NET PowerPoint: Process & Manipulate PPT (.pptx) Slide(s)
the order of current PowerPoint slides using VB.NET control add-on can do PPT creating, loading powerful & profession imaging controls, PDF document, image to
adding pdf to powerpoint slide; how to change pdf file to powerpoint
VB.NET PowerPoint: Convert & Render PPT into PDF Document
VB.NET PowerPoint - Render PPT to PDF in VB.NET. How to Convert PowerPoint Slide to PDF Using VB.NET Code in .NET. Visual C#. VB.NET. Home > .NET Imaging SDK >
convert pdf file to powerpoint online; drag and drop pdf into powerpoint
216
Chapter5 Hashing
randomlychosenhashfunctions,itemAcanbeateitherposition0inTable1orposition
2inTable2.ItemFcanbeateitherposition3inTable1orposition4inTable2,and
soon.Immediately,thisimpliesthatasearchinacuckoohashtablerequiresatmosttwo
tableaccesses,andaremoveistrivial,oncetheitemislocated(lazydeletionisnotneeded
now!).
Butthereisanimportantdetail:Howisthetablebuilt?Forinstance,inFigure5.25,
thereareonlythreeavailablelocationsinthefirsttableforthesixitems,andthereare
onlythreeavailablelocationsinthesecondtableforthesixitems.Sothereareonlysix
availablelocationsforthesesixitems,andthuswemustfindanidealmatchingofslotsfor
oursixitems.Clearly,iftherewereaseventhitem,G,withlocations1forTable1and2for
Table2,itcouldnotbeinsertedintothetablebyanyalgorithm(thesevenitemswouldbe
competingforsixtablelocations).Onecouldarguethatthismeansthatthetablewould
simplybetooloaded(Gwouldyielda0.70loadfactor),butatthesametime,ifthetable
hadthousandsofitems,andwerelightlyloaded,butwehadA,B,C,D,E,F,Gwiththese
hashpositions,itwouldstillbeimpossibletoinsertallsevenofthoseitems.Soitisnotat
allobviousthatthisschemecanbemadetowork.Theanswerinthissituationwouldbeto
pickanotherhashfunction,andthiscanbefineaslongasitisunlikelythatthissituation
occurs.
Thecuckoohashingalgorithmitselfissimple:Toinsertanewitem,x,firstmakesureit
isnotalreadythere.Wecanthenusethefirsthashfunction,andifthe(first)tablelocation
isempty,theitemcanbeplaced.SoFigure5.26showstheresultofinsertingAintoan
emptyhashtable.
SupposenowwewanttoinsertB,whichhashashlocations0inTable1and0in
Table2.Fortheremainderofthealgorithm,wewilluse(h
1
,h
2
)tospecifythetwolocations,
soB’slocationsaregivenby(0,0).Table1isalreadyoccupiedinposition0.Atthispoint
therearetwooptions:OneistolookinTable2.Theproblemisthatposition0inTable2
couldalsobeoccupied.Ithappensthatinthiscaseitisnot,butthealgorithmthatthe
standardcuckoohashtableusesdoesnotbothertolook.Instead,itpreemptivelyplaces
thenewitemBinTable1.Inordertodoso,itmustdisplaceA,soAmovestoTable2,
usingitsTable2hashlocation,whichisposition2.TheresultisshowninFigure5.27.It
iseasytoinsertC,andthisisshowninFigure5.28.
Next we e want t to insert D, with h hash h locations (1, 0). But the e Table 1 1 location
(position1)isalreadytaken.NotealsothattheTable2locationisnotalreadytaken,but
wedon’tlookthere.Instead,wehaveDreplaceC,andthenCgoesintoTable2atposition
4,assuggestedbyitssecondhashfunction.TheresultingtablesareshowninFigure5.29.
Table1
0
A
1
2
3
4
Table2
0
1
2
3
4
A:0,2
Figure5.26 CuckoohashtableafterinsertionofA
VB.NET PowerPoint: Use PowerPoint SDK to Create, Load and Save PPT
This page mainly focuses on how users can get started by using this perfect VB.NET PPT document control with document pre-processing functions, including
pdf to ppt converter online for large; how to convert pdf file to powerpoint presentation
VB.NET PowerPoint: Extract & Collect PPT Slide(s) Using VB Sample
NET PPT slide extracting demo code using RasterEdge VB NET PPT slide adding/removing, PPT merging/splitting & profession imaging controls, PDF document, image
convert pdf to powerpoint using; pdf into powerpoint
5.7 HashTableswithWorst-CaseO(1)Access
217
Table1
0
B
1
2
3
4
Table2
0
1
2
A
3
4
A:0,2
B:0,0
Figure5.27 CuckoohashtableafterinsertionofB
Table1
0
B
1
C
2
3
4
Table2
0
1
2
A
3
4
A:0,2
B:0,0
C:1,4
Figure5.28 CuckoohashtableafterinsertionofC
Afterthisisdone,canbeeasilyinserted.Sofar,sogood,butcanwenowinsertF?
Figures5.30to5.33showthatthisalgorithmsuccessfullyinsertsF,bydisplacingE,then
A,andthenB.
Clearly,aswementionedbefore,wecannotsuccessfullyinsertGwithhashlocations
(1,2).Ifweweretotry,wewoulddisplaceD,thenB,thenA,E,F,andC,andthenC
Table1
0
B
1
D
2
3
E
4
Table2
0
1
2
A
3
4
C
A:0,2
B:0,0
C:1,4
D:1,0
E:3,2
Figure5.29 CuckoohashtableafterinsertionofD
Table1
0
B
1
D
2
3
F
4
Table2
0
1
2
A
3
4
C
A:0,2
B:0,0
C:1,4
D:1,0
E:3,2
F:3,4
Figure5.30 CuckoohashtablestartingtheinsertionofFintothetableinFigure5.29.
First,FdisplacesE.
218
Chapter5 Hashing
Table1
0
B
1
D
2
3
F
4
Table2
0
1
2
E
3
4
C
A:0,2
B:0,0
C:1,4
D:1,0
E:3,2
F:3,4
Figure5.31 Continuing the e insertion of into the table in Figure 5.29. Next, E
displacesA.
Table1
0
A
1
D
2
3
F
4
Table2
0
1
2
E
3
4
C
A:0,2
B:0,0
C:1,4
D:1,0
E:3,2
F:3,4
Figure5.32 Continuing the insertion n of into the table in n Figure e 5.29. Next, A
displacesB.
Table1
0
A
1
D
2
3
F
4
Table2
0
B
1
2
E
3
4
C
A:0,2
B:0,0
C:1,4
D:1,0
E:3,2
F:3,4
Figure5.33 CompletingtheinsertionofFintothetableinFigure5.29.Miraculously(?),
BfindsanemptypositioninTable2.
wouldtrytogobackintoTable1,position1,displacingGwhichwasplacedthereat
thestart.ThiswouldgetustoFigure5.34.SonowGwouldtryitsalternateinTable2
(location2)andthendisplaceA,whichwoulddisplaceB,whichwoulddisplaceD,which
woulddisplaceC,whichwoulddisplaceF,whichwoulddisplaceE,whichwouldnow
displaceGfromposition2.Atthispoint,Gwouldbeinacycle.
Thecentralissuethenconcernsquestionssuchaswhatistheprobabilityoftherebeing
acyclethatpreventstheinsertionfromcompleting,andwhatistheexpectednumberof
displacementsrequiredforasuccessfulinsertion?Fortunately,ifthetable’sloadfactoris
below0.5,ananalysisshowsthattheprobabilityofacycleisverylow,thattheexpected
numberofdisplacementsisasmallconstant,andthatitisextremelyunlikelythatasuc-
cessfulinsertionwouldrequiremorethanO(logN)displacements.Assuch,wecansimply
rebuildthetableswithnewhashfunctionsafteracertainnumberofdisplacementsare
5.7 HashTableswithWorst-CaseO(1)Access
219
Table1
0
B
1
C
2
3
E
4
Table2
0
D
1
2
A
3
4
F
A:0,2
B:0,0
C:1,4
D:1,0
E:3,2
F:3,4
G:1,2
Figure5.34 InsertingGintothetableinFigure5.33.GdisplacesD,whichdisplacesB,
whichdisplacesA,whichdisplacesE,whichdisplacesF,whichdisplacesC,whichdis-
placesG.ItisnotyethopelesssincewhenGisdisplaced,wewouldnowtrytheotherhash
table,atposition2.However,whilethatcouldbesuccessfulingeneral,inthiscasethere
isacycleandtheinsertionwillnotterminate.
detected.Moreprecisely,theprobabilitythatasingleinsertionwouldrequireanewsetof
hashfunctionscanbemadetobeO(1/N
2
);thenewhashfunctionsthemselvesgenerateN
moreinsertionstorebuildthetable,butevenso,thismeanstherebuildingcostisminimal.
However,ifthetable’sloadfactorisat0.5orhigher,thentheprobabilityofacyclebecomes
drasticallyhigher,andthisschemeisunlikelytoworkwellatall.
Afterthepublicationofcuckoohashing,numerousextensionswereproposed.For
instance,insteadoftwotables,wecanuseahighernumberoftables,such as3or4.
Whilethisincreasesthecostofalookup,italsodrasticallyincreasesthetheoreticalspace
utilization.Insomeapplicationsthelookupsthroughseparatehashfunctionscanbedone
inparallelandthuscostlittletonoadditionaltime.Anotherextensionistoalloweach
tabletostoremultiplekeys;again,thiscanincreasespaceutilizationandmakeiteasierto
doinsertionsandcanbemorecache-friendly.Variouscombinationsarepossible,asshown
inFigure5.35.Andfinally,oftencuckoohashtablesareimplementedasonegianttable
withtwo(ormore)hashfunctionsthatprobetheentiretable,andsomevariationsattempt
toplaceaniteminthesecondhashtableimmediatelyifthereisanavailablespot,rather
thanstartingasequenceofdisplacements.
CuckooHashTableImplementation
Implementing cuckoo hashing requires a a collection n of hash functions; ; simply using
hashCode
togeneratethecollectionofhashfunctionsmakesnosense,sinceany
hashCode
collisionswillresultincollisionsinallthehashfunctions.Figure5.36showsasimple
interfacethatcanbeusedtosendfamiliesofhashfunctionstothecuckoohashtable.
1itempercell
2itemspercell
4itemspercell
2hashfunctions
0.49
0.86
0.93
3hashfunctions
0.91
0.97
0.98
4hashfunctions
0.97
0.99
0.999
Figure5.35 Maximumloadfactorsforcuckoohashingvariations
220
Chapter5 Hashing
1
template <typename AnyType>
2
class CuckooHashFamily
3
{
4
public:
5
size_t hash( const AnyType & x, int t which ) ) const;
6
int getNumberOfFunctions( );
7
void generateNewFunctions( );
8
};
Figure5.36 GenericHashFamilyinterfaceforcuckoohashing
Figure5.37providestheclassinterfaceforcuckoohashing.Wewillcodeavariant
thatwillallowanarbitrarynumberofhashfunctions(specifiedbythe
HashFamily
template
parametertype)which uses asinglearray thatisaddressed by allthehash functions.
Thusourimplementation differsfromtheclassicnotionoftwoseparately addressable
hashtables.Wecanimplementtheclassicversionbymakingrelativelyminorchangesto
thecode;however,theversionprovidedinthissectionseemstoperformbetterintests
usingsimplehashfunctions.
In Figure5.37,wespecify that themaximumloadforthetableis0.4;iftheload
factor of thetable is about toexceed thislimit, an automatictable expansion is per-
formed.Wealsodefine
ALLOWED_REHASHES
,which specifies how many rehashes wewill
performifevictionstaketoolong.Intheory,
ALLOWED_REHASHES
canbeinfinite,sincewe
expectonlyasmallconstantnumberofrehashesareneeded;inpractice,dependingon
severalfactorssuchasthenumberofhashfunctions,thequalityofthehashfunctions,
andtheloadfactor,therehashescouldsignificantlyslowthingsdown,anditmightbe
worthwhiletoexpandthetable,eventhoughthiswillcostspace.Thedatarepresentation
forthecuckoohashtableisstraightforward:Westoreasimplearray,thecurrentsize,and
thecollectionsofhashfunctions,representedina
HashFamily
instance.Wealsomaintain
thenumberofhashfunctions,eventhoughthatisalwaysobtainablefromthe
HashFamily
instance.
Figure5.38showstheconstructorand
makeEmpty
methods,andthesearestraightfor-
ward.Figure5.39showsapairofprivatemethods.Thefirst,
myHash
,isusedtoselectthe
appropriatehashfunctionandthenscaleitintoavalidarrayindex.Thesecond,
findPos
,
consultsallthehashfunctionstoreturntheindexcontainingitem
x
,or−1if
x
isnot
found.
findPos
isthenusedby
contains
and
remove
inFigures5.40and5.41,respectively,
andwecanseethatthosemethodsareeasytoimplement.
Thedifficultroutineisinsertion.InFigure5.42,wecanseethatthebasicplanisto
checktoseeiftheitemisalreadypresent,returningifso.Otherwise,wechecktoseeifthe
tableisfullyloaded,andifso,weexpandit.Finallywecallahelperroutinetodoallthe
dirtywork.
ThehelperroutineforinsertionisshowninFigure5.43.Wedeclareavariable
rehashes
tokeeptrackofhowmanyattemptshavebeen madetorehashinthis insertion.Our
insertionroutineismutuallyrecursive:Ifneeded,
insert
eventuallycalls
rehash
,which
eventuallycallsbackinto
insert
.Thus
rehashes
isdeclared inanouterscopeforcode
simplicity.
5.7 HashTableswithWorst-CaseO(1)Access
221
1
template <typename AnyType, typename HashFamily>
2
class CuckooHashTable
3
{
4
public:
5
explicit CuckooHashTable( ( int size = 101 );
6
7
void makeEmpty( );
8
bool contains( const AnyType & & x x ) const;
9
10
bool remove( const AnyType & x x );
11
bool insert( const AnyType & x x );
12
bool insert( AnyType && x );
13
14
private:
15
struct HashEntry
16
{
17
AnyType element;
18
bool isActive;
19
20
HashEntry( const AnyType & & e e = AnyType( ( ), bool l a = false )
21
: element{ { e e }, isActive{ a } } { { }
22
HashEntry( AnyType && e, bool a a = = false e )
23
: element{ { std::move( e e ) }, isActive{ a a } } { }
24
};
25
26
bool insertHelper1( ( const t AnyType & & xx );
27
bool insertHelper1( ( AnyType && xx x );
28
bool isActive( int currentPos ) const;
29
30
size_t myhash( const AnyType & & x, , int which h ) ) const;
31
int findPos( const AnyType & x x ) ) const;
32
void expand( );
33
void rehash( );
34
void rehash( int t newSize );
35
36
static const double e MAX_LOAD D = = 0.40;
37
static const int t ALLOWED_REHASHES S = = 5;
38
39
vector<HashEntry> array;
40
int currentSize;
41
int numHashFunctions;
42
int rehashes;
43
UniformRandom r;
44
HashFamily hashFunctions;
45
};
Figure5.37 Classinterfaceforcuckoohashing
Documents you may be interested
Documents you may be interested