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.

2 Whentheprogramruns,theprogramdatavectorc ontainstheobservationcurrentlybeingproce ssed. Data VectorPDV Example Softwareobjectsareconceptuallysimilartor eal-worldobjects.(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.

3 Statedmoresimply,itdoesn ttakeanylongertolookupavalueinahashtable with10millionentriesthanitdoestolookupav alueinahashtablewith1000entries. Justtobecompletelyclear, Youcanusehashesasalookuptable. Youcanusehashesforsorting. ,itisoftennotpossibletouseadatastepwitha mergestatement. JohnBlackwell sNESUG2010papersitesanexamplewhereanextr act, for hash Tables Forcomplexmanipulationsrequiringcontinuo usupdatingofintermediateresults. 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.)

4 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. CanbeaccomplishedusingIf_n_=1thendo;inaD ataStep Orintheinit()methodofaDS2programs LengthCustomer_Number$10 First_Name$20 Last_Name$30;Setting up hashes in SAS (cont.)

5 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.)

6 ,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.

7 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. 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.

8 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