This page intentionally left blank 
Converting pdf to powerpoint - 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
conversion of pdf to ppt online; how to convert pdf to ppt
Converting pdf to powerpoint - 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
convert pdf to powerpoint online; conversion of pdf into ppt
C H A P P T E R
5
Hashing
InChapter4wediscussedthesearchtreeADT,whichallowedvariousoperationsonaset
ofelements.Inthischapter,wediscussthehashtableADT,whichsupportsonlyasubset
oftheoperationsallowedbybinarysearchtrees.
Theimplementationofhashtablesisfrequentlycalledhashing.Hashingisatech-
niqueusedforperforminginsertions,deletions,andfindsinconstantaveragetime.Tree
operationsthatrequireanyorderinginformationamongtheelementsarenotsupported
efficiently.Thus,operationssuchas
findMin
,
findMax
,andtheprintingoftheentiretablein
sortedorderinlineartimearenotsupported.
Thecentraldatastructureinthischapteristhehashtable.Wewill...
Seeseveralmethodsofimplementingthehashtable.
Comparethesemethodsanalytically.
Shownumerousapplicationsofhashing.
Comparehashtableswithbinarysearchtrees.
5.1 GeneralIdea
Theidealhashtabledatastructureismerelyanarrayofsomefixedsizecontainingthe
items.AsdiscussedinChapter4,generallyasearchisperformedonsomepart(thatis,
datamember)oftheitem.Thisiscalledthekey.Forinstance,anitemcouldconsistofa
string(thatservesasthekey)andadditionaldatamembers(forinstance,anamethatispart
ofalargeemployeestructure).WewillrefertothetablesizeasTableSize,withtheunder-
standingthatthisispartofahashdatastructureandnotmerelysomevariablefloating
aroundglobally.Thecommonconventionistohavethetablerunfrom0toTableSize−1;
wewillseewhyshortly.
Eachkey ismappedintosomenumberintherange0toTableSize−1andplaced
intheappropriatecell.Themappingiscalledahashfunction,whichideallyshouldbe
simpletocomputeandshouldensurethatanytwodistinctkeysgetdifferentcells.Since
thereareafinitenumberofcellsandavirtuallyinexhaustiblesupplyofkeys,thisisclearly
impossible,andthusweseekahashfunctionthatdistributesthekeysevenlyamongthe
cells.Figure5.1istypicalofaperfectsituation.Inthisexample,johnhashesto3,phil
hashesto4,davehashesto6,andmaryhashesto7.
193
C# powerpoint - PowerPoint Conversion & Rendering in C#.NET
This PowerPoint document converting library component offers reliable C#.NET PowerPoint document rendering APIs for developers PowerPoint to PDF Conversion.
convert pdf to powerpoint online no email; converting pdf to powerpoint
C# powerpoint - Convert PowerPoint to PDF in C#.NET
Online C# Tutorial for Converting PowerPoint to PDF (.pdf) Document. PowerPoint Why do we need this PowerPoint to PDF converting library? In
how to add pdf to powerpoint; how to convert pdf into powerpoint slides
194
Chapter5 Hashing
john25000
phil31250
dave27500
mary28200
0
1
2
3
4
5
6
7
8
9
Figure5.1 Anidealhashtable
Thisisthebasicideaofhashing.Theonlyremainingproblemsdealwithchoosinga
function,decidingwhattodowhentwokeyshashtothesamevalue(thisisknownasa
collision),anddecidingonthetablesize.
5.2 HashFunction
Iftheinputkeysareintegers,thensimplyreturningKeymodTableSizeisgenerallyarea-
sonablestrategy,unlessKeyhappenstohavesomeundesirableproperties.Inthiscase,the
choiceofhashfunctionneedstobecarefullyconsidered.Forinstance,ifthetablesize
is10andthekeysallendinzero,thenthestandardhashfunctionisabadchoice.For
reasonsweshallseelater,andtoavoidsituationsliketheoneabove,itisoftenagoodidea
toensurethatthetablesizeisprime.Whentheinputkeysarerandomintegers,thenthis
functionisnotonlyverysimpletocomputebutalsodistributesthekeysevenly.
Usually,thekeysarestrings;inthiscase,thehashfunctionneedstobechosencarefully.
Oneoptionistoaddupthe
ASCII
valuesofthecharactersinthestring.Theroutinein
Figure5.2implementsthisstrategy.
ThehashfunctiondepictedinFigure5.2issimpletoimplementandcomputesan
answerquickly.However,ifthetablesizeislarge,thefunctiondoesnotdistributethekeys
well.Forinstance,supposethatTableSize=10,007(10,007isaprimenumber).Suppose
allthekeysareeightorfewercharacterslong.Sincean
ASCII
characterhasanintegervalue
thatisalwaysatmost127,thehashfunctiontypicallycanonlyassumevaluesbetween0
and1,016,whichis127∗8.Thisisclearlynotanequitabledistribution!
AnotherhashfunctionisshowninFigure5.3.ThishashfunctionassumesthatKeyhas
atleastthreecharacters.Thevalue27representsthenumberoflettersintheEnglishalpha-
bet,plustheblank,and729is27
2
.Thisfunctionexaminesonlythefirstthreecharacters,
butifthesearerandomandthetablesizeis10,007,asbefore,thenwewouldexpecta
Online Convert PowerPoint to PDF file. Best free online export
Then just wait until the conversion from Powerpoint to PDF is complete and download the file Creating a PDF from PPTX/PPT has never been so easy Easy converting!
change pdf to ppt; how to convert pdf to powerpoint on
C# PDF Convert to HTML SDK: Convert PDF to html files in C#.net
Best C#.NET PDF Converter SDK for converting PDF to HTML in Visual Studio .NET. This is a C# programming example for converting PDF to HTML.
pdf to powerpoint converter online; convert pdf slides to powerpoint online
5.2 HashFunction
195
1
int hash( ( const string g & key, int tableSize )
2
{
3
int hashVal l = = 0;
4
5
for( char ch : key )
6
hashVal += = ch;
7
8
return hashVal % % tableSize;
9
}
Figure5.2 Asimplehashfunction
1
int hash( ( const string g & key, int tableSize )
2
{
3
return ( ( key[ 0 0 ] + + 27 7 * * key[ [ 1 ] + + 729 9 * * key[ 2 2 ] ) % % tableSize;
4
}
Figure5.3 Anotherpossiblehashfunction—nottoogood
reasonablyequitabledistribution.Unfortunately,Englishisnotrandom.Althoughthere
are26
3
= 17,576possiblecombinationsofthreecharacters(ignoringblanks),acheck
ofareasonablylargeonlinedictionaryrevealsthatthenumberofdifferentcombinations
isactuallyonly2,851.Evenifnoneofthesecombinationscollide,only28percentofthe
tablecanactuallybehashedto.Thusthisfunction,althougheasilycomputable,isalsonot
appropriateifthehashtableisreasonablylarge.
Figure5.4 shows athird attemptat ahash function.This hash function involves
allcharactersinthekeyandcan generally beexpected todistributewell(itcomputes
KeySize−1
i=0
Key[KeySizei−1]·37
i
andbringstheresultintoproperrange).Thecode
computesapolynomialfunction(of37)byuseofHorner’srule.Forinstance,anotherway
ofcomputingh
k
=k
0
+37k
1
+37
2
k
2
isbytheformulah
k
=((k
2
)∗37+k
1
)∗37+k
0
.
Horner’sruleextendsthistoannthdegreepolynomial.
1
/**
2
* A A hash routine for r string g objects.
3
*/
4
unsigned int t hash( ( const string g & & key, int t tableSize e )
5
{
6
unsigned int t hashVal = 0;
7
8
for( char ch : key )
9
hashVal = = 37 7 * * hashVal + ch;
10
11
return hashVal % % tableSize;
12
}
Figure5.4 Agoodhashfunction
VB.NET PDF Converter Library SDK to convert PDF to other file
This guide give a series of demo code directly for converting MicroSoft Office Word, Excel and PowerPoint document to PDF file in VB.NET application.
pdf picture to powerpoint; convert pdf into powerpoint
VB.NET PowerPoint: Complete PowerPoint Document Conversion in VB.
Converting PowerPoint document to PDF file can be quite simple provided that this VB.NET PowerPoint Converting SDK is correctly installed and utilized.
how to convert pdf to ppt online; convert pdf document to powerpoint
196
Chapter5 Hashing
The hash h function takes s advantage of the fact that overflow is allowed and uses
unsigned int
toavoidintroducinganegativenumber.
ThehashfunctiondescribedinFigure5.4isnotnecessarilythebestwithrespectto
tabledistribution,butitdoeshavethemeritofextremesimplicityandisreasonablyfast.If
thekeysareverylong,thehashfunctionwilltaketoolongtocompute.Acommonpractice
inthiscaseisnottouseallthecharacters.Thelengthandpropertiesofthekeyswouldthen
influencethechoice.Forinstance,thekeyscouldbeacompletestreetaddress.Thehash
functionmightincludeacoupleofcharactersfromthestreetaddressandperhapsacouple
ofcharactersfromthecitynameand
ZIP
code.Someprogrammersimplementtheirhash
functionbyusingonlythecharactersintheoddspaces,withtheideathatthetimesaved
computingthehashfunctionwillmakeupforaslightlylessevenlydistributedfunction.
The main n programming detailleft is s collision resolution. If,when n an n element t is
inserted,ithashestothesamevalueasanalreadyinsertedelement,thenwehaveacollision
andneedtoresolveit.Thereareseveralmethodsfordealingwiththis.Wewilldiscusstwo
ofthesimplest:separatechainingandopenaddressing;thenwewilllookatsomemore
recentlydiscoveredalternatives.
5.3 SeparateChaining
Thefirststrategy,commonlyknownasseparatechaining,istokeepalistofallelements
thathashtothesamevalue.WecanusetheStandardLibrarylistimplementation.Ifspace
istight,itmightbepreferabletoavoidtheiruse(sincetheselistsaredoublylinkedand
wastespace).Weassumeforthissectionthatthekeysarethefirst10perfectsquaresand
thatthehashingfunctionissimplyhash(x)=xmod10.(Thetablesizeisnotprimebut
isusedhereforsimplicity.)Figure5.5showstheresultingseparatechaininghashtable.
Toperforma
search
,weusethehashfunctiontodeterminewhichlisttotraverse.We
thensearchtheappropriatelist.Toperforman
insert
,wechecktheappropriatelisttosee
whethertheelementisalreadyinplace(ifduplicatesareexpected,anextradatamemberis
0
81
1
64
4
25
36
16
49
9
0
1
2
3
4
5
6
7
8
9
Figure5.5 Aseparatechaininghashtable
C# PDF Converter Library SDK to convert PDF to other file formats
Free C#.NET SDK library and components for converting PDF file in .NET Windows applications, ASP.NET web programs and .NET console application.
images from pdf to powerpoint; pdf to ppt
C# PDF Convert to Word SDK: Convert PDF to Word library in C#.net
Word in C#.NET. Online C#.NET Tutorial for Converting PDF to Word (.doc/ .docx) Document with .NET XDoc.PDF Library in C#.NET Class.
export pdf to powerpoint; pdf to powerpoint conversion
5.3 SeparateChaining
197
1
template <typename e HashedObj>
2
class HashTable
3
{
4
public:
5
explicit HashTable( int size e = = 101 );
6
7
bool contains( ( const t HashedObj & x ) ) const;
8
9
void makeEmpty( );
10
bool insert( const HashedObj j & & x );
11
bool insert( HashedObj j && x x );
12
bool remove( const HashedObj j & & x );
13
14
private:
15
vector<list<HashedObj>> theLists;
// The e array y of Lists
16
int currentSize;
17
18
void rehash( );
19
size_t myhash( const t HashedObj & x ) ) const;
20
};
Figure5.6 Typedeclarationforseparatechaininghashtable
usuallykept,andthisdatamemberwouldbeincrementedintheeventofamatch).Ifthe
elementturnsouttobenew,itcanbeinsertedatthefrontofthelist,sinceitisconvenient
andalsobecausefrequentlyithappensthatrecentlyinsertedelementsarethemostlikely
tobeaccessedinthenearfuture.
TheclassinterfaceforaseparatechainingimplementationisshowninFigure5.6.The
hashtablestoresanarrayoflinkedlists,whichareallocatedintheconstructor.
Theclassinterfaceillustratesasyntax point:PriortoC
++
11,inthe declaration of
theLists
,aspacewasrequiredbetweenthetwo
>
s;since
>>
isaC
++
token,andbecauseit
islongerthan
>
,
>>
wouldberecognizedasthetoken.InC
++
11,thisisnolongerthecase.
Justasthebinarysearchtreeworksonlyforobjectsthatare
Comparable
,thehashtables
inthischapterworkonlyforobjectsthatprovideahashfunctionandequalityoperators
(
operator==
or
operator!=
,orpossiblyboth).
Insteadofrequiringhashfunctionsthattakeboth theobjectand thetablesizeas
parameters,wehaveourhashfunctionstakeonlytheobjectastheparameterandreturn
anappropriateintegraltype.Thestandardmechanismfordoingthisusesfunctionobjects,
andtheprotocolforhashtableswasintroducedinC
++
11.Specifically,inC
++
11,hash
functionscanbeexpressedbythefunctionobjecttemplate:
template <typename Key>
class hash
{
public:
size_t operator() ( const Key y & & k ) ) const;
};
C# PDF Convert to SVG SDK: Convert PDF to SVG files in C#.net, ASP
and WinForms applications. Support converting PDF document to SVG image within C#.NET project without quality loss. C# sample code
pdf to ppt converter; convert pdf into powerpoint online
198
Chapter5 Hashing
Defaultimplementationsofthistemplateareprovidedforstandardtypessuchas
int
and
string
;thus,thehashfunctiondescribedinFigure5.4couldbeimplementedas
template <>
class hash<string>
{
public:
size_t operator()( ( const t string g & & key y )
{
size_t hashVal l = = 0;
for( char ch : : key y )
hashVal = = 37 * hashVal + ch;
return hashVal;
}
};
Thetype
size_t
isan unsigned integraltypethat representsthesizeofanobject;
therefore,itisguaranteedtobeabletostoreanarrayindex.Aclassthatimplementsa
hashtablealgorithmcanthenusecallstothegenerichashfunctionobjecttogeneratean
integraltype
size_t
andthenscaletheresultintoasuitablearrayindex.Inourhashtables,
thisismanifestedinprivatememberfunction
myhash
,showninFigure5.7.
Figure 5.8 illustrates s an
Employee
class that can be stored in the generic hash
table,usingthe
name
memberasthekey.The
Employee
class implementsthe
HashedObj
requirementsbyprovidingequalityoperatorsandahashfunctionobject.
Thecodetoimplement
makeEmpty
,
contains
,and
remove
isshowninFigure5.9.
Nextcomestheinsertionroutine.Iftheitemtobeinsertedisalreadypresent,thenwe
donothing;otherwise,weplaceitinthelist(seeFig.5.10).Theelementcanbeplaced
anywhereinthelist;using
push_back
ismostconvenientinourcase.
whichList
isareference
variable;seeSection1.5.2foradiscussionofthisuseofreferencevariables.
Anyschemecouldbeusedbesideslinkedliststoresolvethecollisions;abinarysearch
treeorevenanotherhashtablewouldwork,butweexpectthatifthetableislargeandthe
hashfunctionisgood,allthelistsshouldbeshort,sobasicseparatechainingmakesno
attempttotryanythingcomplicated.
Wedefinetheloadfactor,λ,ofahashtabletobetheratioofthenumberofelements
inthehashtabletothetablesize.Intheexampleabove,λ=1.0.Theaveragelengthofa
listisλ.Theeffortrequiredtoperformasearchistheconstanttimerequiredtoevaluate
thehashfunctionplusthetimetotraversethelist.Inanunsuccessfulsearch,thenumber
1
size_t myhash( const HashedObj & & x x ) const
2
{
3
static hash<HashedObj> hf;
4
return hf( ( x ) ) % % theLists.size( );
5
}
Figure5.7 myHashmemberfunctionforhashtables
5.3 SeparateChaining
199
1
// Example of an Employee class
2
class Employee
3
{
4
public:
5
const string g & getName( ) const
6
{ return name; ; }
7
8
bool operator==( ( const t Employee & rhs ) const
9
{ return getName( ( ) ) == = rhs.getName( ( ); }
10
bool operator!=( ( const t Employee & rhs ) const
11
{ return !( *this s == = rhs; ; }
12
13
// Additional public members s not t shown
14
15
private:
16
string name;
17
double salary;
18
int
seniority;
19
20
// Additional private members not t shown
21
};
22
23
template<>
24
class hash<Employee>
25
{
26
public:
27
size_t operator()( const t Employee e & & item m )
28
{
29
static hash<string> hf;
30
return hf( item.getName( ) ) );
31
}
32
};
Figure5.8 ExampleofaclassthatcanbeusedasaHashedObj
ofnodestoexamineisλonaverage.Asuccessfulsearchrequiresthatabout1+(λ/2)
linksbetraversed.Toseethis,noticethatthelistthatisbeingsearchedcontainstheone
nodethatstoresthematchpluszeroormoreothernodes.Theexpectednumberof“other
nodes”inatableofNelementsandMlistsis(N−1)/M=λ−1/M,whichisessentiallyλ,
sinceMispresumedlarge.Onaverage,halfthe“othernodes”aresearched,socombined
withthematchingnode,weobtainanaveragesearchcostof1+λ/2nodes.Thisanalysis
showsthatthetablesizeisnotreallyimportantbuttheloadfactoris.Thegeneralrule
forseparatechaininghashingistomakethetablesizeaboutaslargeasthenumberof
elementsexpected(inotherwords,letλ ≈ ≈ 1).InthecodeinFigure5.10,iftheload
factorexceeds1,weexpandthetablesizebycalling
rehash
atline10.
rehash
isdiscussed
inSection5.5.Itisalsoagoodidea,asmentionedbefore,tokeepthetablesizeprimeto
ensureagooddistribution.
200
Chapter5 Hashing
1
void makeEmpty( ( )
2
{
3
for( auto & thisList : theLists )
4
thisList.clear( );
5
}
6
7
bool contains( ( const t HashedObj j & x ) ) const
8
{
9
auto & whichList t = = theLists[ myhash( x x ) ) ];
10
return find( begin( ( whichList t ), , end( ( whichList ), x ) ) != end( whichList t );
11
}
12
13
bool remove( const t HashedObj j & & x )
14
{
15
auto & whichList t = = theLists[ myhash( x x ) ) ];
16
auto itr r = = find( ( begin( ( whichList ), end( whichList t ), x x );
17
18
if( itr == end( whichList ) ) )
19
return false;
20
21
whichList.erase( itr r );
22
--currentSize;
23
return true;
24
}
Figure5.9 makeEmpty,contains,andremoveroutinesforseparatechaininghashtable
1
bool insert( const HashedObj & x )
2
{
3
auto & whichList = theLists[ myhash( x ) ];
4
if( find( begin( whichList ), end( whichList ), x ) != end( whichList ) )
5
return false;
6
whichList.push_back( x );
7
8
// Rehash; see Section 5.5
9
if( ++currentSize > theLists.size( ) )
10
rehash( );
11
12
return true;
13
}
Figure5.10 insertroutineforseparatechaininghashtable
5.4 HashTableswithoutLinkedLists
201
5.4 HashTableswithoutLinkedLists
Separatechaining hashing hasthe disadvantageofusinglinked lists.Thiscould slow
thealgorithmdown abitbecauseofthetimerequiredtoallocatenew cells(especially
inotherlanguages)andessentiallyrequirestheimplementationofaseconddatastruc-
ture.Analternativetoresolvingcollisionswithlinkedlistsistotryalternativecellsuntil
anemptycellisfound.Moreformally,cellsh
0
(x),h
1
(x),h
2
(x),...aretriedinsuccession,
whereh
i
(x)= (hash(x)+f(i)) ) modTableSize,withf(0)=0.Thefunction,f,isthecol-
lisionresolutionstrategy.Becauseallthedatagoinsidethetable,abiggertableisneeded
insuchaschemethanforseparatechaininghashing.Generally,theloadfactorshouldbe
belowλ = = 0.5forahashtablethatdoesn’tuseseparatechaining.Wecallsuchtables
probinghashtables.Wenowlookatthreecommoncollisionresolutionstrategies.
5.4.1 LinearProbing
Inlinearprobing,fisalinearfunctionofi,typicallyf(i)=i.Thisamountstotryingcells
sequentially(withwraparound)insearchofanemptycell.Figure5.11showstheresultof
insertingkeys{89,18,49,58,69}intoahashtableusingthesamehashfunctionasbefore
andthecollisionresolutionstrategy,f(i)=i.
Thefirstcollisionoccurswhen49isinserted;itisputinthenextavailablespot,namely,
spot0,whichisopen.Thekey58collideswith18,89,andthen49beforeanemptycell
isfoundthreeaway.Thecollisionfor69ishandledinasimilarmanner.Aslongasthe
tableisbigenough,afreecellcanalwaysbefound,butthetimetodosocangetquite
large.Worse,evenifthetableisrelativelyempty,blocksofoccupiedcellsstartforming.
Thiseffect,knownasprimaryclustering,meansthatanykeythathashesintothecluster
willrequireseveralattemptstoresolvethecollision,andthenitwilladdtothecluster.
Althoughwewillnotperformthecalculationshere,itcanbeshownthattheexpected
numberofprobesusinglinearprobingisroughly
1
2
(1+1/(1−λ)
2
)forinsertionsand
EmptyTable
After89
After18
After49
After58
After69
0
49
49
49
1
58
58
2
69
3
4
5
6
7
8
18
18
18
18
9
89
89
89
89
89
Figure5.11 Hashtablewithlinearprobing,aftereachinsertion
Documents you may be interested
Documents you may be interested