Introduction to Hash Tables

1 An Introduction to Hash TablesShaun KaufmannFarm Credit CanadaThispresentationwilladdressfourmai nquestions: Whatarehashesandhowdotheywork? Whatyoucanusethemfor? Whatkindofperformancegainscanhashesprovi de? HowdoIusehashesinSAS?AgendaBeforeweintro ducehashes(hashtables),therearethreeconc eptsthatarehelpfultofacilitateunderstand ing: Whatisadatastructure? WhatistheProgramDataVector? Whatisanobjectinregardtoobjectorientedpr ogramming?Before we adatastructureisaparticularwayofstoringa ndorganizingdatainacomputersothatitcanbe usedefficiently. Adatastructurecanbethoughtofasbeingiscon structedfromdatatypes.(numericandcharact er). Thesimplestdatastructureistheone-dimensi onal(linear)array, StructuresOne Dimensional Array Theprogramdatavectorisastorageplaceinmem orythatcontainsallofthevariablesencounte redbythedatastep. Whentheprogramruns,theprogramdatavectorc ontainstheobservationcurrentlybeingproce ssed. data VectorPDV Example Softwareobjectsareconceptuallysimilartor eal-worldobjects.

2 (adog,atoaster,you). Objectsconsistofthingsthattheycando,call edmethods,andinformationabouttheircurren tstate,calledpropertiesorattributes. Methodsandpropertiesarereferencedthought dot notation. ()orcolor= ;Objects Ahashtableisadatastructure. Residesinmemory,notondisklikeatable. Canbethoughtofasatypeofarray. Morespecifically,ahashtableimplementsana ssociativearraythatmapskeystovalues. Thismappingisaccomplishedthroughahashfun ction. Forexample, Are Hash Tables Foranappropriatelyimplementedhashdatastr ucture,thecostoflookupsisindependentofth enumberofelementsstoredinthetable. Statedmoresimply,itdoesn ttakeanylongertolookupavalueinahashtable with10millionentriesthanitdoestolookupav alueinahashtablewith1000entries. Justtobecompletelyclear, Youcanusehashesasalookuptable. Youcanusehashesforsorting. ,itisoftennotpossibletouseadatastepwitha mergestatement. JohnBlackwell sNESUG2010papersitesanexamplewhereanextr act, for Hash Tables Forcomplexmanipulationsrequiringcontinuo usupdatingofintermediateresults.

3 From personal experience, one such process resulted in a significant increase in performance: 3hoursfor30,000records(implementedinSASw ithouthashes) 3hoursfor300,000record(implementedinPL/S QLinOracleonamuchmorepowerfulserver withouthashes). 30secondsfor300,000records(implementedin SASusinghashing) for Hash Tables (cont.) HashesareimplementedinSASasObjects TheyhavemethodsandpropertiesandtheyuseDO Tnotation (); ( empid ); HashescanonlybeusedinaDataStepprocedureo rDS2program. InSAStheuserisshieldedfrommostoftheimple mentationdetails. Youdon tneedtoknowanythingaboutthehashfunctionu sedorcollisionresolutionapproaches. Hash table Implementation Hashesneedtobedeclared. Declarehashcustomer_hash(); Declarehashcustomer_hash(dataset: ); Thekey(s)needtobedefined: ( Customer_Number ); Thedataitemsneedtobedefined: ( First_Name , Last_Name ); TheDefinedone()methodiscalled. ();Setting up hashes in SAS Thedeclarationanddefinitionisdoneonlyonc e.

4 CanbeaccomplishedusingIf_n_=1thendo;inaD ataStep Orintheinit()methodofaDS2programs LengthCustomer_Number$10 First_Name$20 Last_Name$30;Setting up hashes in SAS (cont.) declarehashobj(dataset:'dataset_name',du plicate:'replace'|'error',hashexp:n,orde red:'a'|'d'|'no',suminc:'count_var'); dataset:loadsthehashobjectfromadataset. duplicate:controlshowduplicatekeysarehan dledwhenloadingfromadataset. hashexp:ndeclares2totheexponentnslotsfor thehashobject. ordered:specifiesakeysortorderwhenusinga hashiteratorortheoutputmethod. suminc:count_varcontainstheincrementvalu eforakeysummarythatisretrievedbythesumme thod. multidata:specifieswhethermultipledatait emsareallowedforeachkey. ,asaretheassociatedHAS_NEXT,FIND_NEXT,HA S_PREV, Hash Declaration Options rc= ('key_var1',..,'key_varN'); rc= ('data_var1',..,'data_varN'); Definesdata, ,tobestoredinthehashobject. rc= (); Hash Methods rc= (); rc= (key:key_val1,..,key:key_valN, data :data_ val1.)

5 , data :data_valN); Addsthespecifieddataassociatedwiththegiv enkeytothehashobject. rc= (); rc= (key:key_val1,..,key:key_valN); , , Hash Methods (cont.) rc= (); rc= (key:key_val1,..,key:key_valN, data :data_ val1,.., data :data_valN); rc= (); rc= (key:key_val1,..,key:key_valN); Hash Methods (cont.) rc= (); rc= (key:key_val1,..,key:key_valN); Removesthedataassociatedwiththegivenkey. rc= (); Hash Methods (cont.) rc= (dataset:'dataset_name'); Createsdatasetdataset_namewhichwillconta inthedatainthehashobject. rc= (sum:sum_var); rc= (key:key_val1,..,key:key_valN,sum:sum_va r); Hash Methods (cont.) rc= (); rc= (key:key_val1,..,key:key_valN); ,itwillbeadded. rc= (hash:'hash_obj',result:res_var); ,res_varissetto1,otherwiseitissettozero. rc= (); Hash Methods (cont.) i= ; Retrieves the number of elements in the hash object. sz= ; Obtains the item size, in bytes, for an item in the hash Hash Attributes Givesyoutheabilitytotraverseyourmemoryta blefromstarttoend,orviceversa.

6 Ahashiteratorisassociatedwithaspecificha shobjectandoperatesonlyonthathashobject. Hash Iterator declarehiteriterobj('hash_obj'); Createsahashiteratortoretrieveitemsfromt hehashobjectnamedhash_obj. rc= (); Copiesthedataforthefirstiteminthehashobj ectintothedatavariablesforthehashobject. rc= (); Iterator Methods rc= (); ,nextbeginswiththefirstitem. rc= (); , Iterator Methods (cont.) HashTablesareinmemorydatastructures. HashTablescanbeusedforlookups,sorting,me rgingandtofacilitatecomplexdatamanipulat ionsbyremovingthediskI/Oassociatedwithfr equentqueryandupdatestatements. HashTablescanprovidesignificantperforman cegainsincertaincircumstances. !UseMemoryTables(Hashing) ,DataSavantConsulting,Shawnee,KSFind()th epowerofHash-How,WhyandWhentousetheSAS , Hashing in SAS Robert Ray and Jason Secosky. SAS Global Forum :Key-Indexing Bitmapping