: Dictionaries and Hash Table Representation Dictionaries: Linear List Representation, Skip List Representation, Operations - Insertion, Deletion and Searching. Hash Table Representation: Hash Funetlons, Collision Resolution - Separate Chaining, Open Addressing - Linear Probing, Quadratle Probing, Double Hashing, Rehashing, Extendible Hashing. Introduction to Dictionaries Skip List and its Representation Yarlous Operations Performed on Skip List Concept of Ideal Hashing Various Hash Functions Various Collision Resolution Techniques Sages ON SS Concept of Extensible Hashing INTRODUCTION A dictionary consists of a group of keys and their associated values. It is of the form (K, V) where, *k’ denotes the key and ‘V’ denotes the value of the key ‘K'. These keys are unique. Various operations performed on dictionaries are find, insert and erase. A skip list Is a probabilistic data structure for storing an ordered list of items. It was developed by William Pugh in 1990. It Is based on a collection of linked lists. Hashing Isa technique that makes use of a hash function for mapping pairs to the corresponding {entries) positions in a hash table. Ideally a pair ‘P* with a key ‘K' Is stored at a position f(k) by the hash function ‘f’, Each hash table position can store one palr. Hash function is a function that fs used to mop the dictionary palrs to the corresponding entries in the hash table. The various Hashing functions include Division method, Mid square method, Folding Method and Digit Analysis, SPECTRUM ALL-IN-ONE JOURNAL FOR ENGINEERING STUDENTS. Se ee neoo Dron ADT wiv: 2.4 DICTIONARIES: Pte aDTiegeciiel Q1, Explain briefly about dictionaries with an ees fee a aah eh "Cty cm af ono nd the ato ott Fi “teensy a) emer eh ‘Etmnlep um cnae "he cmpey forte st ‘na diienny at coats pop ‘Shomer econ Woman ene ‘yutaetmlrot cle ede tinny, inp en an epee ese ‘Seanad et ed Rem ete oy beg ook mast ms) ‘Sey tay pe ee oc oh ‘oe cops denature on ‘copie acme ey wl ths Sa anemlyetee a ‘dca mh ie a ona at stews be ya edt mw. | Sn Milo poe Tie ours tt es ptm | at aye) o Soames inlA | etm aap "eke diy Te nhs fad snl‘ osama ios wipe Snel (0 Ping pi ht conn ti pei ey of {9) Dy fnga te pre snee ‘peli Sem rp mer eye on, sapwood rant a ih os "ie ein ‘Sneed tay Atom ‘o . snewvae ppt ey mocha sc Fo the ‘ens operation a mer mas ie which pire die om among al epi a ea ite deta pai rea dete al pts ot ‘Shoe wh te pce “Thin open find eines th pals ‘anon when key pode Same opis men jaca reeves Tete es hare ed for he nar 1 Sri Arey Uist Cas ‘ay mpeseninon aoa Ts solo ‘yee cigu. 85th fi operation sh ‘atin of Oona dtinsy coming rs |) Imerton:Aparsinerain ion os i othe aendy ex Vetting itn GDseTs Ta. TT ents ; mes aie esti eee ic, BE Swietcinncen salle banc tt ain mn nt dea tn ino inne pn nrg ee ete ample fr SriedChannted List Repeat (5, Whats skips How tis aterent rom inguin se? What sa skip ee Answer any 226) ‘Skip Lit [Askip ins roi en chihg aon tras tn kde ode Wi Bees Mishel es led ets come ncn are ieee SEs FS nt al he shoe aisle ip it tener nthe ft The as a ne kip tare sare pies ik ist wt wy cee bong The ey ews sce hed Batata oth yn seen ng ice nal Semen sen niet eh mt ea a ri i ee echelon or en spi tw cna Te mac pes sl edo phy oa irs ne, seta gl ar i pan or Mapes) pe one nts nh sos resi ing of cane sat eee een Besta cnc nae opts on ear cat nse ncening de ot 8 oe Gomes un Wir uc i pana ship rach ed cis sie umber of ier eds each eve we he TD ealnode dees regu any por ech nod sei 28 cent els be ule pier © FeldtGeyteetnonter) Tena eS Ut Ste SPECTRUM ALL-IN-ONE JOURNAL FOR ENGINEERING STUDENTSDATA STRUCTURES JNTUHYDERABAD) EALERTS LITDER UAT) a Wee, TW) imate iH Tate Resse in deta rerio ‘Wapeier he masini aambe of eels ha Be avin otal shou ship isivaae 48 encs.astotShipNode sued tastsisal | | reallowed ine pal chan, on! ar |] Seroqremensofthenedeswhichingvenas, | (1D. font uO For mover fr ot ‘template ‘tia used in deciding the number of the levels, Ne 8.05. osama on) > net Jo taney in alp trap SO™PsNGns canbe rascoa SkipNode SOR Ss, alr in skip it eer math wt sc aan Poa Bema pelea ihe, ls Ship Eira on a pantypes, t I ‘Ho at roresentaton of dna | Spode : “| te | pase: | ‘SkipNode(const pairTypet Pints) SkipNode * headerNode; ‘The oumber of comparisons, orney 240, a) o " ‘ShipNde * ute, Sek teed (+1 mpi tony (n= new Spade * (5) ‘ShigNode ** Lat (9 Manan poner ei yon ee , it lev te, mane By cmp pew ye ‘oat cut, ar ithe ide pu ‘Where Te sat “Sioe? , male oy pais ‘e=Blemet n= Neat lament a + G6) Foc stake pi seach ny Sele al eno he ned in PoP seSim, o | ‘uefa tae The pointer fields are denoted by the array ‘Example apes sn a cot sy a | ugg et SL a he ie -., Sinieoccmeaate |e Iida a stag, wel hn TT res on aa Pee Ngai! Asti wv ie pr, stash noherdicyconeen Spt Cae te dona Kis we ae Ne. IeStr tpg incre menos 7 “ePn Tnmb of cmpuos ae cd Maspairs i cass Sips. tis of pe int and dente tbe masinun ‘mambo paix ictonary canta, Hence | Gemaderlin | Prob : is ofpe Boa an dese the proba . "pars preset noth be ee and te ee nsrcone ir < ost KE & pi) (rea ‘The consrcorininins be StL clas da mente ah ‘Tiot compuvonscancvenbereeyfthr miingto prt pe ate ee he ‘4 ob * RAND MAX: tae pa ‘The da member of he Skint clas we as |. Hvelt= ‘town ize 0, ‘Shiphede *headeode tak = ghey, pei the pine te nero smanlevel = Git) clog (ot) mary ‘Spode *wlNode eae) Ty specie te one eine. headed ne side <, E> i Bios tsa tenants rece tom tants sasiocastp i Pc ary We noc seco wih tsa Ba Pesci {ert openon sero rang eax ets ph Ta prion nn see theft te tnd fl eee Sor ofthat elton chaps ane sql to The ee) en ca i Whe tpi = ey, [ae sip ln nmcday une bc pron por Attn mae rented ser rig Ins coms at sie he pce forte ew en which essen nar rn al Wart ow 03 a Per lanmear eer Tee ce ne [ested ee ects wtp tr mcg abr abe 03, cart be these nach hata dng each oes {iba yi pres Te wnhon pepe al baie Ba ee eat ras fom (co) acme by lnkig i eras pe: Te apie ‘Deol ee The osc compe The met ey en 0) ae Imei opr pete “SPECTRUM AILI-ONE JOURNAL FOR ENGINEERING STODERTS For sos te rel Octal de pac ee nhs ey sd pind el Tacos very fort pnd cone eens reps ee BAIS kip List operations - insertion, Deletion and 8, Exlan te nerton neh pron sp at wih an erp| a aa ee = eee pms tt ise owe ee | onan . ei} a mtn ee o s pd pst) _ mi se | “while rand) 12.40 wor | nl 7. is} far —_fa fas |_|] Tiree re ‘pose beforon) ae PeeHeHe HaHa aH as} fe | Stee ee | oA coy eae | eloteofotote tee odes pet * es ney ere L] sence i ie aa acer sn ascent rab i 6G] - : : in 2 a | Betrmspmecetere cerium tain ee op lprntna bso yg coy eo ae ee b ry j ‘Similar wo the insertion, the deletion ofan stem 1s made a the search moves down the skip list. The changed Be) itera acess recente 4 7 i] P= 1Sttom above pst sown blow ene - =e eo ue] 7 li | oct) =i) ow) ‘06) > owt =P Ent ice itty ‘Algorithm fr Deen ‘The algorithm fe deletion operon in sip it seston, ‘Algom SkpDeletotL kay) Dexia popes eta =tere:1>= 0,1) let = ky» orf paca emp. ert cement $8 (slot Ts Del sia pF Toe ww 0) mod =m 113-11 ee Tene ert MG)=Q2+0) nol 13=2med 12-9 9 poston sen iertthe semet 2, aT Tsao) : TT ee he oer 98 Wa)= 08 0) 08 13 94 od 1) =7 ‘AP polio s at cme tbe vale ie, Mai208+ "med Pinel 1-8 [As polionis ot cmp. cem a he ve e,2 H)=08+ 2) mo 13 =102 mol 13 = 11 Asti position sao mt en omen ey vase Ma}=(0h+ Py mol TRAP poston nt cy, creme te abe 4 Haj-04+ 8) nol 114 mal 1310 Ae IO portion ato cng rene he ae 3 Mai=O4= 2) 0413 12 mod = 6 Ase potions empoenhee Theresa uti “RICIVONE| (SURNAL FOR ENGINEERING STUDENTSDATA] RUCTURES JNTUHYDEPs, "oo er ~~) EB: Ditonafeb ond Mesh 382 Recresenaton We oor jms 9 ae i } ! ins f Metoratteary a ) oH se Free er sie vos) oe Pratt 1d ayy ( || sree tnt) mir Dee ef eter vale sec" tours Eset i”: sat HEA =e DIT aT sie indetea s reams: ar sex) ited} NULL) ) : Pr Benet ond inh unr hey it yun Poin ume aa { {shir end sl NULL chines) aux * ( (i Seon pnts as eminem tot | peed a= Pst le i shania: to ‘mind ? : os 2 Sepurate cat i lat. kyu ies NULL) = =. - ni “\nThe keys Of the array tion> mi(“Eleenent not founda"; Anne em | ad i ees Ape, a. we fied sens) viyy |e ii Mis ‘ 2 eg se) inner keys fash ble" his 1 for (roacrum) . i detent | nda pation Md" i | ha) = NULL) sex at rere finde Phes iT s}-(N hain 4 : edie eetNo Ean Hinf(aa-Open Adestng Methods i ine Poin Quai Mob al setts, te Goeryarcioer Ge salah viet) c ate: Pin Ener oho ble a sh Sean ("ANT sn, ‘wale iforke ‘oid main aie ‘ale>ner = NULL t ae : ittesay]— NULL) eye | ‘ex = ae; slo: ee ti) t hha: rinit-Separte Chaining Melodia Insert hltei->ex!=NULL) dopey) Seackat Extn you coe" (ueeainner nl" de facia han-NULL n-ne) PRIME yl ofs hb" peo"; sane) ” eps ue et" Ales node mats fcoturatnteys — |) SRS p=) Serge a TORE JOURNAL FOR ENGINEERING STUDER ———rs DATAS TRUCTURESLNTUYOERn | yg Deon HT epson a 2 Gaal otc ates = Petes i red oc at yin tna a ara eed bee ce feet nceaes and dere mesic odor poms ad eke ere = cfg below shows he peal cre fence hing as Mash pots [¢ | = ° —— Sse ‘rcak: wo. ae cS, i =r" eae tweak ta CT Prater Crest he 2.2.2 Exte jndible Hashing Excnible ashing isa yam hase tecnigie hat pate of ding te feces = ssbse pons amine them sick Ts ‘equres feo on of keen Bash bie moran |i bing tt id= Iheperfrmine ove ethan bene pei eopaniton ony © none ice tate. Ie eee the hh fen» bon hat that [aCe ui f+ Aedindonses. And itseaateaf wencsing ac Sierras of eabzownsebbiney oee ‘Thevalueofb usa: ly 32 Taf ea ee csmor andtilion tert However ack = etcrenteltoee a sed thy secret nema (steers aed oh ‘Win eaPheepa of Oak CANAL eBay ad | CABLE en ETAT Fier: om Srey te hig PR hak mts cvs tect sir al wich cuti pot ori et ive shows the hau re oop o bce aia le This yar net at's ash te ede od appropri cht em 'F Poe at nr cach kt on itr alec wi, bln fe — Ti fea the lengh of ommanhash ro tts poo rer cece ae ies wich oat a eke The nr of nie hat pt sbckt a enby 3 Shales on cxunpe tne sn chy valu meney wing een eig In hia Sha) od econ’ econ ash itn, jarred | ec =2, 3,57. 1117, 19,23.29 31 ofbcket= 3 et te ash as ech fhe gven seach ey va, Wa)=2 mol =2 3)=3 mob 3 Ks)=Smods~5 y= T 288° ‘ity=t1 ods =3 in)= 17 mod 8=1 119) 19 nod 8-3 1na3)=23 mod a9) =29 med 8-5 A31)=31 nod SSPECTROM ALLAF-ONE T SSORRAL FOR ENGINEERING STODERTS@ [DATA STRUCTURES LTULYDERAEAS, ee o Compute te binary vals foreach the Ee ae revues hava, s a2)=2=010 & ig)=3911 Ks) =5= 101 a=7=u1 wi=9 011 wod=7-111 ste eta ‘Compt etal dh vale nd pleco hetpf he backends abe oni s eed (0001010, 01, 10, 0, 11.11) “Guhl dep =3 These dincy=3 sts ns te ey vals in accordance this |.” Varale Number of ache: In extn nay acs He te manber fucker wee |" aig, bck ae ied en dab ‘rence five dferet ao aus a ror ey | ees weve, when date ee Naan ‘kc aed raced ow, come te imino th seat ey | 9, nue ember of uct Arche rt ‘shins eon ulie propty = ‘Se Se crpentiny ii 8s srepsscbeiaGnstaie eed Sete Wikre osainwy fenton Aer Sa ‘Erne sr nti on chonaseine de ee ‘address tule bucket 1. ooh 4 ae ini aos, ie remsinng iny| 5 year acm dented cence Dia ain wae Ince feeds ot degra —_ z Seer | ee 5 ‘the adres sos tothe respective buckets. This canbe | 1 The records are not accessed sequensaly Sais |) oe Seca eer | eee ee ee ee ‘he dramas of cede hahig a Conte ldap rach of etch 3 Dclonares and Hash Table Rereseraton SHORT QUESTIONS WITH SOLUTIONS (VSQS) erro) etry const popes nic sid alas ise em, he ees Pv der ar be SORE Shiki ens rotting rr i of em wa veep by Wom Pt es beed once of re a ri oben asec at isd ie typ i a i The er pron tf he dear pee yh of hah he repress by svete Bae ich rns Ose he i at is cid wh pen iy about midequre method. an expe or dig! sats meted. 34612 amc ihc aspen pater shel Ned colon eve mie a el SSPEETRUN ALLTONE JOURNAL FOR ENGINEERING STADENTS eee&4 DATA STRUCTURES (MTUHYDZes,,, ‘| FREQUENTLY ASKED QUESTIONS & IMPORTANT QUESTIONS | memento Q1. Explain briefly about dictionaries with an example. Answer: pon 0 Cetin For answer refer Unit-l, Page No. 42,01. Q2. Discuss the two classes that are used for the linear list representation metho. Answer : importer Cevmtne For answer refer Unit-l, Page No. 42, 04. 93. What Is skip list? How itis different from a linear linked list? Answer : er coet For answer refer Unit-IL, Page No. 43,05. Q4. Demonstrate ‘skip list representation of a dictionary. Answer: Peportant Question | Apriey-23°711, <4, For answer refer Unit-Il, Page No. 45, 08. Q5. Explain the operations of the skip list representation. f=. Answer : (March 220818), O30) Owc-tmn18).05)| 2 For answer refer Unit-ll, Page No. 48, O12. KJ Q6. Explain static hashing with examples. sh Answer : atone! Chmaten For answer refer Unit-Il, Page No. 49, 15. Q7. Discuss the hash functions. Answer: (important Goon | March-22° 18, a For answer refer Unit-Il, Page No. $0, Q17. Q8. Write the algorithm for calculating Hash function using division method. Answer: E sports Cuceen For answer refer Unit-ll, Page No. $1, Q18. Q9. What are different methods of collision resolution in hashing? Explain in brief. Answer: + Apathy TARA, C5 | Ageing ZUR, CAG) | March-221R18), 04>) fe March-21(R18), G2 | Dec ABPIE), G4 | Doc 151818), 21(0)) For answer refer Unit-Il, Page No. $2, 20. Q10, Insert the following list of elements into the hash table by using Quadratic probing (siz# Hash table is 13) 65, 34, 79, 114, 26, 85, 55, 89, 22, 98. dqrest; (important Question | Sep 21/812). For answer refer Unit-ll, Page No. $6,021. Q11, List and explain the advantages of extendible hashing. Answer: (Cesportart Gwatcm | Saver 221818)? For answer refer Unit-I1, Page No. 60,23. Tost ‘WARRING KerexIPhetocopying of this book is « CRIMINAL act Anyone ound pully & LIABLE ts toca LEGAL proceee=F