[MUZIKO Ludante] DOUG LLOYD: De nun vi scias multon pri arrays, kaj vi scias tre pri ligitaj listoj. Havas ni diskuti la avantaĝoj kaj contras, ni diskutis ke ligitaj listoj povas pligrandiĝi kaj pli malgranda, sed levu pli grandeco. Tabeloj estas multe pli simpla al uzi, sed ili estas limiga dum kiel ni devas agordi la grandecon de la tabelo ĉe la komenco kaj poste ni gluata kun ĝi. 

Sed tio, ni preskaux elĉerpita ĉiuj niaj temoj pri ligitaj listoj kaj tabeloj. Aŭ ni havas? Eble ni povas fari ion eĉ pli krea. Kaj tiaj pruntedonas la ideo de hash tablo. 

Do en hash tablo ni tuj provos kombini tabelo kun ligillisto. Ni tuj prenos la avantaĝojn de la tabelo, kiel hazarda aliro, povi ĝuste iri al tabelo elemento 4 aŭ tabelo elemento 8 sen devi persisti trans. Tio estas sufiĉe rapida, dekstra? 

Sed ni ankaŭ deziras havi niajn datumojn strukturo povi kreski kaj ŝrumpi. Ni ne bezonas, ni ne volas esti restriktita. Kaj ni volas povi aldoni kaj forigi aferojn tre facile, kaj se vi memoras, estas tre kompleksa kun tabelo. Kaj ni povas nomi ĉi nova afero hash tablo. 

Kaj se implementado korekte, ni ia prenante la avantaĝojn de ambaŭ datumoj strukturoj vi jam vidis, arrays kaj ligitaj listoj. Inserción povas komenci inklinas al theta de 1. Theta ni ne vere diskutis, sed theta estas simple la ordinara kazo, kio efektive okazos. Vi ne ĉiam tuj havi la plej malbona kazo scenaro, kaj vi ne ĉiam tuj devas la plej bona kazo scenaro, do kio estas la averaĝa scenaro? 

Nu mezumo inserción en hash tablo povas komenci alproksimigi al konstanta tempo. Kaj forigoj povas akiri fermi al konstanta tempo. Kaj lookup povas akiri fermi al konstanta tempo. That's-- ni ne havas datumojn strukturo tamen kiu povas tion fari, kaj tiel ĉi jam sonas kiel bela granda afero. Ni vere mildigis la malavantaĝoj de ĉiu en lia propra. 

Por ricevi ĉi agado ĝisdatigi kvankam ni bezonas rekonsideri kiel ni aldonu datumojn en la strukturo. Specife ni deziras la datumoj al diri nin kie devus iri en la strukturo. Kaj se ni tiam devas vidi se ĝi estas en la strukturon, se ni devas trovi ĝin, Ni volas rigardi la datumoj denove kaj povos efike, uzante la datumoj, hazarde aliras. Nur rigardante la datumojn ni devus havi ideon de kie ekzakte ni estas tuj trovi gxin en la hash tablo. 

Nun la malavantaĝo de hash tablo estas ke ili estas vere sufiĉe malbone ĉe ordigante aŭ ordigado de datumoj. Kaj fakte, se vi komencas uzi ilin ordigi aŭ varo datumoj vi perdas ĉiuj la avantaĝojn vi antaŭe devis en terminoj de inserción kaj forigo. La tempo iĝas pli proksime al theta de n, kaj ni esence regresis en ligillisto. Kaj tiel ni nur volas uzi hash tabloj se ni ne zorgas pri ĉu datumoj estas ordo. Por la kunteksto en kiu vi uzos ilin en CS50 vi probable ne zorgas ke la datumoj estas ordigitaj. 

Do hash tablo estas kombinaĵo el du distingaj pecoj kun kiu ni estas konataj. La unua estas funkcio, kiun ni kutime nomas hash funkcio. Kaj ke hash funkcio tuj reveni iu ne-negativa entjero, kiu ni kutime nomas hashcode, OK? La dua peco estas tabelo, kiu estas kapablaj de stoki datumojn de la tipo ni volas meti en la datumstrukturo. Ni teni ekstere sur la ligillisto elementon nuntempe kaj komencu kun la fundamentojn de hash tablo akiri vian kapon ĉirkaŭe, kaj tiam ni eble blovi via menso iomete kiam ni kombini arrays kaj karmo listojn kune. 

La baza ideo kvankam Estas ni preni iujn datumojn. Ni kuras tra kiuj datumoj la hash funkcio. Kaj tial la datumoj procesas kaj ĝi kraĉas el kelkaj, OK? Kaj tiam kun tiu nombro ni nur stoki la datumojn ni volas konservi en la tabelo ĉe tiu loko. Do por ekzemplo havas eble tiu hash tablo de kordoj. Oni alvenis 10 elementoj en ĝi, do ni povas persvadi 10 kordoj en ĝi. 

Supozu ke ni volas hash Johano. Do Johanon la datumoj ni volas enmeti en tiu hash tablo ie. Kie ni metis ĝin? Nu tipe kun tabelo ĝis nun ni probable metus ĝin en tabelo ĉelo 0. Sed nun ni havas tiun novan hash funkcio. 

Kaj ni diras, ke ni kuras Johano tra ĉi hash funkcio kaj ĝin kraĉas el 4. Nu tio estas kie ni estas tuj volas Johanon. Ni volas meti John vicojn location 4, ĉar se ni hash John again-- diru poste ni volas serĉi kaj vidi se John ekzistas en tiu hash table-- ĉiuj ni devas fari kuras tra la sama hash funkcion, la numeron 4 el, kaj povos trovi Johano tuj en nia datumstrukturo. Tio estas sufiĉe bona. 

Supozu ke ni nun faras tiun denove, ni volas hash Paul. Ni volas aldoni Paul en tiu hash tablo. Diru ke ĉi tiu tempo ni kuras Paŭlo tra la krada funkcio, la hashcode kiu generas estas 6. Nu nun ni povas meti Paul en la tabelo situon 6. Kaj se ni bezonas serĉi ĉu Paul estas en ĉi hash tablo, ĉiuj ni devas fari estas kuri Paul tra la krada funkcio denove kaj ni tuj ricevas 6 reeliri. 

Kaj tiam ni simple rigardi ĉe tabelo situon 6. Paul tie? Se jes, li estas en la hash tablo. Paul ne? Li ne estas en la hash tablo. Ĝi estas bela simpla. 

Nun kiel vi difinas hash funkcio? Bone tie estas vere nenia limo al la nombro de eblaj kradaj funkcioj. Fakte ekzistas kelkaj vere, vere bona sur la interreto. Ekzistas kelkaj vere, vere malbonaj sur la interreto. Estas ankaŭ sufiĉe facila skribi malbongusta. 

Do kio konsistigas bonan hash funkcio, ĉu ne? Nu bona hash funkcio devus uzi nur la datumoj estanta hashed, kaj ĉiujn la datumoj estanta hashed. Do ni ne volas uzi ion ajn ni ne korpigi ion alia krom la datumoj. Kaj ni volas uzi ĉiujn de la datumo. Ni ne volas simple uzi peco de ĝi, ni volas uzi ĉiujn de ĝi. Hash funkcio devus ankaŭ determinisma. Kion tio signifas? Nu signifas ke ĉiufoje ni pasi la ĝusta sama peco de datumoj en la hash funkcio ni ĉiam atingi la saman hashcode eksteren. Se mi pasas Johanon en la hash funkcio mi liberiĝos el 4. Mi devus povi fari ke 10,000 fojojn kaj mi ĉiam ricevas 4. Do neniu hazardaj nombroj efike povas esti implikitaj en nia hash tables-- en nia kradaj funkcioj. 

Hash funkcio devus ankaŭ unuforme distribui datumojn. Se ĉiufoje kiam vi kuros datumoj tra la hash funkcio vi ricevas la hashcode 0, ke estas probable ne tiom granda, ĉu ne? Vi probable volas grandaj gamon de hash kodojn. Ankaŭ aĵoj povas disvastigi el ĉie en la tablo. Kaj ankaŭ ĝi estus granda se vere similajn datumojn, kiel John kaj Jonatan, eble estis etendantaj levar malsamaj lokoj en la hash tablo. Tio estus bela avantaĝon. 

Jen ekzemplo de hash funkcio. Mi skribis ĉi unu supren antaŭe. Ĝi ne estas aparte bona hash funkcio por kialoj kiuj ne vere elporti internigi nun. Sed ĉu vi vidas kio okazas ĉi tie? Ŝajnas kiel ni deklari variablon nomata sumo kaj fiksante ĝin egala al 0. Kaj tiam ŝajne mi faras ion tiel longe kiel strstr [j] estas ne egala por backslash 0. Kion mi faris? 

Tiu estas esence nur alia formo de apliko [? strl?] kaj detektante kiam vi havas atingis la finon de la ŝnuro. Do mi ne devas reale kalkuli la longecon de la kordo, Mi nur uzas kiam mi batis la backslash 0 karaktero Mi scias Mi jam atingis la finon de la ŝnuro. Kaj tiam mi tuj konservi ripetanta tra tiu ŝnuro, aldonante strstr [j] al sumo, kaj tiam ĉe la fino de la tago tuj revenos sumo mod HASH_MAX. 

Esence ĉiuj ĉi hash funkcio faras estas adicio ĉiuj ASCII valoroj de mian ŝnuron, kaj tiam estas reveninte iuj hashcode modded per HASH_MAX. Estas probable la grandeco de mia tabelo, dekstra? Mi ne volas esti akiranta hash kodoj se miaj tabelo estas de amplekso 10, Mi ne volas esti akiranta eksteren hash kodoj 11, 12, 13, mi ne povas meti aferojn en tiuj lokoj de la tabelo, ke estus kontraŭleĝa. Mi suferas segmentación kulpo. 

Nun tie estas alia rapida flanken. Ĝenerale vi probable ne tuj volas skribi viajn proprajn kradaj funkcioj. Estas efektive iom de arto, ne scienco. Kaj ekzistas multe kiu iras tra ili. La interreto, kiel mi diris, estas kompleta de vere bona kradaj funkcioj, kaj vi devus uzi la interreton trovi kradaj funkcioj ĉar estas vere nur speco de nenecesa tempoperdo krei vian propran. 

Vi povas skribi simplaj por testado. Sed kiam vi vere intencas komenci hashing datumoj kaj stokante ĝin en hash tablo vi estas probable tuj volas uzi iu funkcio kiu generis por vi, ke ekzistas sur la interreto. Se vi ĵus certi por citi viajn fontojn. Ekzistas neniu kialo por plagiar nenio ĉi tie. 

La komputiko komunumo estas sendube kreskas, kaj vere valoroj malfermita, kaj ĝi estas vere grava por citi viajn fontojn por ke homoj povas akiri atribuu laboro, kiun ili estas faras al la profito de la komunumo. Do ĉiam sure-- kaj ne nur por hash funkcioj, sed ĝenerale kiam vi uzi kodon de ekstera fonto, ĉiam citas vian fonton. Doni krediton al la persono kiu faris iuj de la laboro do vi ne devas. 

OK do ni reviziti ĉi hash tablo por dua. Tie estas kie ni maldekstre for post ni insertita John kaj Paul en tiu hash tablo. Ĉu vi vidas problemon tie? Vi povus vidi du. Sed precipe, ĉu vi vidu tiun eblan problemon? 

Kio se mi hash Ringo, kaj ĝi Rezultas ke post prilaborado ke datumoj tra la krada funkcio Ringo ankaŭ generis la hashcode 6. Mi jam akiris datumojn ĉe hashcode-- tabelo situon 6. Do ĝi estas probable tuj estos iom de problemo por mi nun, ĉu ne? 

Ni nomas tiun kolizion. Kaj la kolizio okazas kiam du datumerojn kuri tra la sama hash funkcio cedas la samaj hashcode. Supozeble ni ankoraŭ volas akiri ambaŭ datumerojn en la hash tablo, alie ni ne estus kuranta Ringo arbitre tra la krada funkcio. Ni supozeble volas ricevi Ringo en tiun tabelo. 

Kiel ni faru ĝin kvankam, se li kaj Paul ambaŭ rendimento hashcode 6? Ni ne volas anstataŭigi Paul, ni volas Paul esti tie ankaŭ. Do ni devas trovi manieron ricevi elementoj en la hash tablo ke ankoraŭ konservas nian rapida inserción kaj rapidan rigardon supren. Kaj unu maniero trakti ĝin estas fari iu nomita lineara tuŝoprobado. 

Uzante tiun metodon, se ni havas kolizio, nu, kion ni faru? Bone ni ne povas meti lin en tabelo location 6, aŭ kion ajn hashcode estis generita, ni metis lin ĉe hashcode plus 1. Kaj se tio estas plena let estas metis lin en hashcode plus 2. La profito de tiu estaĵo se li estas ne ĝuste kie ni kredas ke li estas, kaj ni devos ekserĉi, eble ni ne devas iri tro ege. Eble ni ne devas serĉi ĉiuj n elementoj de la hash tablo. Eble ni devas serĉi paro de ili. 

Kaj tial ni ankoraŭ strebanta al ke mezumo kazo estanta proksime al 1 vs proksime al n, do eble tio devos labori. Do ni vidu kiel ĉi povus eliri en realo. Kaj ni vidu, se eble ni povas detekti la problemo kiu povus okazi tie. 

Supozu ke ni hash Bart. Do nun ni tuj kuri nova aro de kordoj tra la krada funkcio, kaj ni kuras Bart tra la hash funkcio, ni preni hashcode 6. Ni rigardu, ni vidas 6 estas malplena, do ni povas meti Bart tie. 

Nun ni hash Lisa kaj ke ankaŭ generas hashcode 6. Nu nun ke ni uzas tiun lineara tuŝoprobado metodo ni starti je 6, ni vidas ke 6 estas plena. Ni ne povas meti Lisa en 6. Do kie ni iras? Ni iru al 7. 7 La malplena, por ke funkcias. Do ni metu Lisa tie. 

Nun ni hash Homer kaj ni preni 7. OK bone ni scias ke 7 plenas nun, tial ni ne povas meti Homero tie. Do ni iru al 8. Estas 8 havebla? Jes, kaj 8 proksimaj al 7, do se ni devos ekserĉi ni estas ne tuj devas iri tro ege. Kaj do ni metis Homero ĉe 8. 

Nun ni hash Maggie kaj Revenas 3, dank'al Dio ni povas nur meti Maggie tie. Ni ne devas fari ajnan ia tuŝoprobado por tio. Nun ni hash Marge, kaj Marge ankaŭ revenas 6. 

Nu 6 estas plena, 7 estas plena, 8 estas plena, 9, tute certe dankas Dion, 9 estas malplena. Mi povas meti Marge ĉe 9. Jam ni povas vidi ke ni startanta havi tiun problemon kie nun ni estas komencante por streĉi aferoj speco de fore de ilia hash kodojn. Kaj ke theta de 1, ke mezumo kazo de esti konstanta tempo, estas komencanta akiri malgrandan more-- komencantaj emas iom pli al theta de n. Ni komencas perdi tiun avantaĝon de hash tabloj. 

Tiu problemo kiun ni ĵus vidis Estas io nomita clustering. Kaj kio estas vere malbona pri clustering estas ke unufoje vi nun havas du elementojn kiuj flank bandola faras ankoraŭ pli verŝajna, vi havas duoblan hazardo, ke vi tuj havi alian kolizion kun tiu areto, kaj la areto kreskos post unu. Kaj Vi pli kaj kreskanta via verŝajneco de havado de kolizio. Kaj fine ĝi estas egale malbona kiel ne ordigado la datumoj ajn. 

La alia problemo tamen estas ni ankoraŭ, kaj ĝis nun ĝis tiu punkto, ni ĵus estis ia komprenante kio hash tablo estas, ni ankoraŭ nur havas spacon por 10 kordoj. Se ni volas ri hash la civitanoj de Springfield, ni povas nur akiri 10 el ili en tie. Kaj se ni provu kaj aldoni 11a aŭ 12a, ni ne havas lokon por meti ilin. Ni povus simple esti turnadanta ĉirkaŭ en rondoj provanta trovi malplenan lokon, kaj ni eble akiri senmoviĝita en senfina buklo. 

Do tiu speco de pruntedonas al la ideo de iu nomita ĉenante. Kaj tio estas kie ni estas iranta alporti ligitaj listoj reen en la bildon. Kio se anstataŭ stoki nur la datumoj en la tabelo, ĉiu ero de la tabelo povis teni multnombraj pecoj de datumoj? Nu tio ne havas sencon, ĉu ne? Ni scias ke tabelo povas nur hold-- ĉiu elemento de tabelo povas nur teni unu peco de datumoj de tiu datumtipo. 

Sed kio se tiu datumtipo estas ligillisto, dekstra? Do kio se ĉiu elemento de la tabelo estis sagon al la kapo de ligitaj listo? Kaj tiam ni povus konstrui tiuj ligitaj lertaj kaj kreski ilin arbitre, ĉar ligitaj listoj permesi nin kreski kaj ŝrumpi multe pli flekse ol tabelo faras. Do kio se ni nun uzas, ni ekspluati tion, ĉu ne? Ni komencas kreski tiuj ĉenoj el tiuj tabelo lokoj. 

Nun ni povas persvadi malfinia kvanto de datumoj, aŭ ne senfina, arbitran kvanton de datumoj, en nia hash tablo sen iam alkuri la problemo de kolizio. Ni ankaŭ eliminita clustering farante tion. Kaj bone ni scias ke kiam ni enŝovu en ligillisto, se vi memoras de nia vídeo en ligitaj listoj, unuope ligitaj listoj kaj duoble ligitaj listoj, ĝi estas konstanta tempo operacio. Ni simple aldonante al la fronto. 

Kaj por rigardon supren, bone ni scias aspektantaj supren en ligillisto povas esti problemo, ĉu ne? Ni devas traserĉi ĝin de komenco al fino. Mankas hazarda aliro en ligillisto. Sed se anstataŭ havi kunligita lerta kie lookup estus O de n, Ni nun havas 10 ligitaj listoj, aŭ 1,000 ligitaj listoj, nun ĝi estas ho de n dividita per 10, aŭ O de n dividita per 1,000. 

Kaj dum ni parolis teorie pri komplekseco ni ignoru konstantoj, en la reala mondo tion vere gravas, dekstra? Ni efektive rimarkos ke tio okazas kuri 10 fojoj pli rapida, aŭ 1.000 fojoj pli rapida, ĉar ni distribui longa ĉeno trans 1.000 malgrandaj ĉenoj. Kaj tiel ĉiu tempo ni devas serĉi tra unu el tiuj ĉenoj eblan ignori la 999 ĉenojn ni ne zorgas pri, kaj nur serĉu tiu. 

Kiu estas averaĝe al esti 1,000 fojojn pli mallonga. Kaj tial ni ankoraŭ estas ia emanta al ĉi mezumo kazo esti konstanta tempo, sed nur ĉar ni laŭtigas dividante de iu grandega konstanta faktoro. Ni vidu kiom tio eble vere aspektas tamen. Do tio estis la hash tablo ni havis antaŭ ni deklaris hash tablo ke Estis kapabla de stoki 10 kordoj. Ni ne faros tion plu. Ni jam konas la limigoj de tiu metodo. Nun nia hash tablo tuj estos tabelo de 10 nodoj, punteros al kapoj de ligitaj listoj. 

Kaj ĝuste nun ĝi estas nula. Ĉiu el tiuj 10 punteros estas nula. Nenio en nia hash tablo nun. 

Nun ni komencu meti iun aferojn en tiu hash tablo. Kaj ni vidu kiel ĉi tiu metodo estas iranta profitigi nin iomete. Ni nun hash Joey. Ni kuros la kordo Joey tra hash funkcio kaj ni revenos 6. Nu kion ni faru nun? 

Nu nun laboras kun ligitaj listoj, ni ne laboras per tabeloj. Kaj kiam ni laboras kun ligitaj listoj ni scias ni bezonas komenci dinamike asignante spaco kaj konstrumaterialoj ĉenoj. Tio estas speco de how-- tiuj estas la kerno elementoj de konstruado ligillisto. Do ni dinamike rezervu spacon por Joey, kaj tiam ni aldonu lin al la ĉeno. 

Do nun rigardas kion ni faris. Kiam ni hash Joey ni akiris la hashcode 6. Nun la montrilo ĉe tabelo situon 6 notas al la kapo de ligillisto, kaj ĝuste nun ĝi estas la sola elemento de ligitaj listo. Kaj la nodo en tiu ligillisto estas Joey. 

Do se ni bezonas serĉi Joey poste, ni nur hash Joey denove, ni ricevas 6 denove ĉar nia krada funkcio estas determinisma. Kaj tiam ni komencu ĉe la kapo de la ligillisto atentigis al per tabelo location 6, kaj ni povas persisti trans tiu provanta trovi Joey. Kaj se ni konstruas nian hash tablo efike, kaj nia hash funkcio efike distribui datumoj bone, averaĝe ĉiu de tiuj ligitaj listoj ĉe ĉiu tabelo location Estos 1/10 la grandeco de se ni nur havis ĝin kiel ununura grandega ligillisto kun ĉio en ĝi. 

Se ni disdoni ke grandega ligitaj lerta trans 10 ligitaj listoj ĉiu listo estos 1/10 la grandeco. Kaj tiel 10 fojoj pli rapida serĉi tra. Do ni faru ĉi denove. Ni nun hash Ross. 

Kaj diru Ross, kiam ni faru tion la hash kodo ni reiros estas 2. Nu nun ni dinamike rezervu nova nodo, ni metis Ross en tiu nodo, kaj ni diras nun tabelo location 2, anstataŭ montrante al nula, notas al la kapo de ligitaj lerta kies nura nodo estas Ross. Kaj ni povas fari tion pli tempo, ni povas hash Rahxel kaj akiri hashcode 4. malloc nova nodo, metu Rahxel en la nodo, kaj diri tabelo location 4 nun notas al la kapo de ligillisto kies nur elemento hazarde estas Rachel. 

OK sed kio okazas se ni havas kolizion? Ni vidu kiel ni pritrakti koliziojn uzante la apartaj ĉeni metodo. Ni hash Phoebe. Ni akiros la hashcode 6. En nia antaŭa ekzemplo ni estis ĵus stokante kordoj en la tabelo. Tiu estis problemo. 

Ni ne volas clobber Joey, kaj ni jam vidis ke ni povas akiri iom clustering problemoj se ni provas kaj paŝo tra kaj sondas. Sed kio se ni nur speco de trakti tiun sammaniere, dekstra? Estas nur kiel aldoni elementon al la kapo de ligitaj listo. Ni simple malloc spaco por Phoebe. 

Ni diru Phoebe venonta puntero punktoj al la malnova kapo de la ligillisto, kaj tiam 6 nur notas al la nova estro de la ligitaj listo. Kaj nun rigardu, ni ŝanĝis Phoebe en. Ni povas nun enteni du elementoj kun hashcode 6 kaj ni ne havas problemojn. 

Tio estas sufiĉe multe ĉiuj oni devas sinsekvon. Kaj ĉeni estas sendube la metodo tio tuj estos plej efika por vi se vi amasigas datumojn en hash tablo. Sed tiu kombino de arrays kaj ligitaj listoj kune formi hash tablo vere draste plibonigas vian kapablon stoki grandajn kvantojn de datumoj, kaj tre rapide kaj efike serĉi tra tiu datumo. 

Ekzistas ankoraŭ unu pli datumstrukturo tie kiuj povus eĉ esti iom bona en terminoj de garantiado ke nia inserción, forigo, kaj rigardi supren tempoj estas ankoraŭ pli rapida. Kaj ni vidos ke en video sur provoj. Mi Doug Lloyd, tiu estas CS50.