Hej Habr! Mi prezentas al via atento la tradukon de la artikolo
"Kiel funkcias rilata datumbazo".

Se temas pri interrilataj datumbazoj mi ne povas ne pensi ke io mankas. Ili estas uzataj ĉie. Estas multaj malsamaj datumbazoj disponeblaj, de la malgranda kaj utila SQLite ĝis la potenca Teradata. Sed estas nur kelkaj artikoloj, kiuj klarigas kiel funkcias la datumbazo. Vi povas serĉi mem uzante "kiel estas rilata datumbazo" por vidi kiom malmultaj rezultoj estas. Krome, ĉi tiuj artikoloj estas mallongaj. Se vi serĉas la plej novajn zumajn teknologiojn (BigData, NoSQL aŭ JavaScript), vi trovos pli profundajn artikolojn klarigante kiel ili funkcias.

Ĉu interrilataj datumbazoj estas tro malnovaj kaj tro enuigaj por esti klarigitaj ekster universitataj kursoj, esplorartikoloj kaj libroj?

Kiel programisto, mi malamas uzi ion, kion mi ne komprenas. Kaj se datumbazoj estas uzataj dum pli ol 40 jaroj, devas esti kialo. Tra la jaroj, mi pasigis centojn da horoj por vere kompreni ĉi tiujn strangajn nigrajn skatolojn, kiujn mi uzas ĉiutage. Rilataj Datumbazoj tre interesa ĉar ili surbaze de utilaj kaj reuzeblaj konceptoj. Se vi interesiĝas pri kompreni datumbazon, sed neniam havis la tempon aŭ emon enprofundiĝi en ĉi tiun ampleksan temon, vi devus ĝui ĉi tiun artikolon.

Kvankam la titolo de ĉi tiu artikolo estas eksplicita, la celo de ĉi tiu artikolo ne estas kompreni kiel uzi la datumbazon. Tial, vi jam devus scii kiel skribi simplan konektopeton kaj bazajn demandojn KRUDA; alie vi eble ne komprenas ĉi tiun artikolon. Tio estas la nura afero, kiun vi bezonas scii, mi klarigos la ceterajn.

Mi komencos kun iuj bazaĵoj pri komputika, kiel tempa komplekseco de algoritmoj (BigO). Mi scias, ke kelkaj el vi malamas ĉi tiun koncepton, sed sen ĝi vi ne povos kompreni la komplikaĵojn ene de la datumbazo. Ĉar ĉi tio estas grandega temo, Mi fokusos kion mi opinias grava: kiel la datumbazo procesas SQL enketo. Mi nur prezentos bazaj datumbazaj konceptojpor ke ĉe la fino de la artikolo vi havu ideon pri tio, kio okazas sub la kapuĉo.

Ĉar ĉi tio estas longa kaj teknika artikolo, kiu implikas multajn algoritmojn kaj datumstrukturojn, prenu vian tempon por tralegi ĝin. Iuj konceptoj povas esti malfacile kompreneblaj; vi povas preterlasi ilin kaj ankoraŭ akiri la ĝeneralan ideon.

Por la pli spertaj inter vi, ĉi tiu artikolo estas dividita en 3 partojn:

• Superrigardo de malaltnivelaj kaj altnivelaj datumbazaj komponantoj
• Superrigardo de la Demando Optimumigo-Procezo
• Superrigardo de Transakcio kaj Buffer Pool Management

Reen al bazoj

Antaŭ jaroj (en galaksio malproksima, malproksime...), programistoj devis precize scii la nombron da operacioj, kiujn ili kodis. Ili konis siajn algoritmojn kaj datumstrukturojn parkere ĉar ili ne povis pagi malŝpari la CPU kaj memoron de siaj malrapidaj komputiloj.

En ĉi tiu parto, mi memorigos vin pri iuj el ĉi tiuj konceptoj, ĉar ili estas esencaj por kompreni la datumbazon. Mi ankaŭ enkondukos la koncepton datumbaza indekso.

O(1) vs O(n2)

Nuntempe multaj programistoj ne zorgas pri la tempokomplekseco de algoritmoj... kaj ili pravas!

Sed kiam vi traktas multajn datumojn (mi ne parolas milojn) aŭ se vi luktas en milisekundoj, fariĝas kritike kompreni ĉi tiun koncepton. Kaj kiel vi povas imagi, datumbazoj devas trakti ambaŭ situaciojn! Mi ne igos vin elspezi pli da tempo ol necese por komprenigi la aferon. Ĉi tio helpos nin kompreni la koncepton de kost-bazita optimumigo poste (kosto bazitaj optimumigo).

Koncepto

Tempokomplekseco de la algoritmo uzata por vidi kiom da tempo necesas por ekzekuti algoritmon por donita kvanto da datumoj. Por priskribi ĉi tiun kompleksecon, ni uzas matematikan notacion grandan O. Ĉi tiu notacio estas uzata kun funkcio kiu priskribas kiom da operacioj bezonas algoritmo por donita nombro da enigaĵoj.

Ekzemple, kiam mi diras "ĉi tiu algoritmo havas kompleksecon O(some_function())", tio signifas, ke la algoritmo postulas some_function(a_certain_amount_of_data) operacioj por prilabori certan kvanton da datumoj.

tiel Ne gravas la kvanto da datumoj**, alie ** kiel la nombro da operacioj pliiĝas kun pliiĝanta datumvolumo. Tempokomplekseco ne disponigas precizan nombron da operacioj, sed estas bona maniero taksi ekzekuttempon.

En ĉi tiu grafikaĵo vi povas vidi la nombron da operacioj kontraŭ la kvanto de eniga datumoj por malsamaj specoj de algoritmo tempokompleksaĵoj. Mi uzis logaritman skalon por montri ilin. Alivorte, la kvanto da datumoj rapide pliiĝas de 1 al 1 miliardo, ni povas vidi tion:

• O(1) aŭ konstanta komplekseco restas konstanta (alie ĝi ne estus nomita konstanta komplekseco).
• O(Log(n)) restas malalta eĉ kun miliardoj da datumoj.
• Plej malbona malfacileco - O(n2), kie la nombro da operacioj kreskas rapide.
• La aliaj du komplikaĵoj pliiĝas same rapide.

ekzemploj

Kun malgranda kvanto de datumoj, la diferenco inter O(1) kaj O(n2) estas nekonsiderinda. Ekzemple, ni diru, ke vi havas algoritmon, kiu bezonas prilabori 2000 elementojn.

• La algoritmo O(1) kostos al vi 1 operacion
• La algoritmo O(log(n)) kostos al vi 7 operaciojn
• La algoritmo O(n) kostos al vi 2 operaciojn
• La algoritmo O(n*log(n)) kostos al vi 14 operaciojn
• La algoritmo O(n2) kostos al vi 4 000 000 operaciojn

La diferenco inter O(1) kaj O(n2) ŝajnas granda (4 milionoj da operacioj) sed vi perdos maksimume 2 ms, nur tempo por palpebrumi. Efektive, modernaj procesoroj povas procesi centoj da milionoj da operacioj sekundo. Jen kial agado kaj optimumigo ne estas problemo en multaj IT-projektoj.

Kiel mi diris, estas ankoraŭ grave scii ĉi tiun koncepton kiam vi laboras kun grandegaj kvantoj da datumoj. Se ĉi-foje la algoritmo devas prilabori 1 000 000 elementojn (kio ne estas tiom por datumbazo):

• La algoritmo O(1) kostos al vi 1 operacion
• La algoritmo O(log(n)) kostos al vi 14 operaciojn
• La algoritmo O(n) kostos al vi 1 000 000 operaciojn
• La algoritmo O(n*log(n)) kostos al vi 14 000 000 operaciojn
• La algoritmo O(n2) kostos al vi 1 operaciojn

Mi ne faris la matematikon, sed mi dirus, ke per la algoritmo O(n2) oni havas tempon por trinki kafon (eĉ du!). Se vi aldonas alian 0 al la datumvolumo, vi havos tempon por dormeti.

Ni iru pli profunden

Por referenco:

• Bona hashtabelserĉo trovas elementon en O(1).
• Serĉi bone ekvilibran arbon produktas rezultojn en O(log(n)).
• Serĉi tabelon produktas rezultojn en O(n).
• La plej bonaj ordigaj algoritmoj havas kompleksecon O(n*log(n)).
• Malbona ordiga algoritmo havas kompleksecon O(n2).

Noto: En la sekvaj partoj ni vidos ĉi tiujn algoritmojn kaj datumstrukturojn.

Estas pluraj specoj de algoritmo tempokomplekseco:

• meza kazo scenaro
• plej bona kazo
• kaj plej malbona kazo

Tempokomplekseco ofte estas la plej malbona kazo.

Mi nur parolis pri la tempokomplekseco de la algoritmo, sed komplekseco ankaŭ validas por:

• memorkonsumo de la algoritmo
• Diska I/O-konsuma algoritmo

Kompreneble, estas komplikaĵoj pli malbonaj ol n2, ekzemple:

• n4: ĉi tio estas terura! Iuj el la menciitaj algoritmoj havas ĉi tiun kompleksecon.
• 3n: ĉi tio estas eĉ pli malbona! Unu el la algoritmoj, kiujn ni vidos en la mezo de ĉi tiu artikolo, havas ĉi tiun kompleksecon (kaj ĝi estas fakte uzata en multaj datumbazoj).
• faktorialo n: vi neniam ricevos viajn rezultojn eĉ kun malgranda kvanto da datumoj.
• nn: Se vi renkontas ĉi tiun kompleksecon, vi devus demandi vin ĉu ĉi tio vere estas via agadkampo...

Notu: Mi ne donis al vi la realan difinon de la granda O-nomo, nur ideon. Vi povas legi ĉi tiun artikolon ĉe Vikipedio por la reala (asimptota) difino.

KunfandiOrdigi

Kion vi faras kiam vi bezonas ordigi kolekton? Kio? Vi nomas la funkcion sort()... Bone, bona respondo... Sed por datumbazo, vi devas kompreni kiel funkcias ĉi tiu funkcio sort().

Estas pluraj bonaj ordigaj algoritmoj, do mi koncentriĝos pri la plej grava: kunfandi ordigi. Vi eble ne komprenas kial ordigado de datumoj estas utila nun, sed vi devus post la demanda optimumigo parto. Plie, kompreno de merge sorto helpos nin poste kompreni la komunan datumbazan kunigoperacion nomitan iri aliĝi (fuzia asocio).

Kunfandi

Kiel multaj utilaj algoritmoj, kunfandi sorto dependas de ruzo: kombini 2 ordigitajn tabelojn de grandeco N/2 en N-elementan ordigitan tabelon kostas nur N operaciojn. Ĉi tiu operacio nomiĝas kunfandado.

Ni vidu, kion tio signifas per simpla ekzemplo:

Ĉi tiu figuro montras, ke por konstrui la finan ordigitan 8-elementan tabelon, vi nur bezonas ripeti unufoje super la 2 4-elementaj tabeloj. Ĉar ambaŭ 4-elementaj tabeloj jam estas ordigitaj:

• 1) vi komparas ambaŭ nunajn elementojn en du tabeloj (komence nuna = unue)
• 2) tiam prenu la plej malgrandan por meti ĝin en 8-elementan tabelon
• 3) kaj movu al la sekva elemento en la tabelo, kie vi prenis la plej malgrandan elementon
• kaj ripetu 1,2,3 ĝis vi atingos la lastan elementon de unu el la tabeloj.
• Tiam vi prenu la ceterajn elementojn de la alia tabelo por meti ilin en 8-elementan tabelon.

Ĉi tio funkcias ĉar ambaŭ 4-elementaj tabeloj estas ordigitaj kaj do vi ne devas "reiri" en tiuj tabeloj.

Nun kiam ni komprenas la lertaĵon, jen mia pseŭdokodo por kunfandi:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

Kunfandi ordigas problemon en pli malgrandajn problemojn kaj tiam trovas la rezultojn de la pli malgrandaj problemoj por ricevi la rezulton de la origina problemo (noto: ĉi tiu tipo de algoritmo nomiĝas dividi kaj konkeri). Se vi ne komprenas ĉi tiun algoritmon, ne maltrankviliĝu; Mi ne komprenis ĝin la unuan fojon, kiam mi vidis ĝin. Se ĝi povas helpi vin, mi vidas ĉi tiun algoritmon kiel dufazan algoritmon:

• Dividadfazo, kie la tabelo estas dividita en pli malgrandajn tabelojn
• La ordiga fazo estas kie malgrandaj tabeloj estas kombinitaj (uzante union) por formi pli grandan tabelon.

Fazo de divido

En la divida stadio, la tabelo estas dividita en unuecajn tabelojn en 3 ŝtupoj. La formala nombro da paŝoj estas log(N) (ĉar N=8, log(N) = 3).

Kiel mi scias ĉi tion?

Mi estas geniulo! Unuvorte - matematiko. La ideo estas, ke ĉiu paŝo dividas la grandecon de la originala tabelo per 2. La nombro da paŝoj estas la nombro da fojoj kiam vi povas dividi la originan tabelon en du. Ĉi tiu estas la preciza difino de logaritmo (bazo 2).

Ordigofazo

En la ordiga fazo, oni komencas per unuecaj (unuelementaj) tabeloj. Dum ĉiu paŝo vi aplikas plurajn kunfandoperaciojn kaj la totalkosto estas N = 8 operacioj:

• En la unua etapo vi havas 4 kunfandiĝojn kiuj kostas po 2 operacioj
• En la dua paŝo vi havas 2 kunfandaĵojn, kiuj kostas po 4 operaciojn
• En la tria paŝo vi havas 1 kunfandi, kiu kostas 8 operaciojn

Ĉar estas log(N) paŝoj, totalkosto N * log(N) operacioj.

Avantaĝoj de merge sorto

Kial ĉi tiu algoritmo estas tiel potenca?

Ĉar:

• Vi povas ŝanĝi ĝin por redukti la memorpiedsignon, por ke vi ne kreu novajn tabelojn sed rekte modifu la enigan tabelon.

Noto: ĉi tiu tipo de algoritmo estas nomita in-loko (ordigo sen plia memoro).

• Vi povas ŝanĝi ĝin por uzi diskospacon kaj malgrandan kvanton da memoro samtempe sen altigi signifan diskan I/O-superkoston. La ideo estas ŝargi en memoron nur tiujn partojn, kiuj nuntempe estas prilaboritaj. Ĉi tio gravas kiam vi bezonas ordigi plurgigabajtan tabelon kun nur 100-megabajta memorbufro.

Noto: ĉi tiu tipo de algoritmo estas nomita ekstera speco.

• Vi povas ŝanĝi ĝin por funkcii per pluraj procezoj/fadenoj/serviloj.

Ekzemple, distribuita kunfanda varo estas unu el la ĉefaj komponantoj Hadoop (kiu estas strukturo en grandaj datumoj).

• Ĉi tiu algoritmo povas turni plumbon en oro (vere!).

Ĉi tiu ordiga algoritmo estas uzata en plej multaj (se ne ĉiuj) datumbazoj, sed ĝi ne estas la sola. Se vi volas scii pli, vi povas legi ĉi tion esplorlaboro, kiu diskutas la avantaĝojn kaj malavantaĝojn de oftaj datumbazaj ordigaj algoritmoj.

Array, Arbo kaj Hash Table

Nun kiam ni komprenas la ideon de tempokomplekseco kaj ordigo, mi devus diri al vi pri 3 datumstrukturoj. Ĉi tio estas grava ĉar ili estas la bazo de modernaj datumbazoj. Mi ankaŭ enkondukos la koncepton datumbaza indekso.

Array

Dudimensia tabelo estas la plej simpla datumstrukturo. Tablo povas esti konsiderata kiel tabelo. Ekzemple:

Ĉi tiu 2-dimensia tabelo estas tabelo kun vicoj kaj kolumnoj:

• Ĉiu linio reprezentas enton
• Kolumnoj stokas ecojn, kiuj priskribas la enton.
• Ĉiu kolumno konservas datumojn de specifa tipo (entjero, ĉeno, dato...).

Ĉi tio estas oportuna por stoki kaj bildigi datumojn, tamen, kiam vi bezonas trovi specifan valoron, ĉi tio ne taŭgas.

Ekzemple, se vi volus trovi ĉiujn ulojn kiuj laboras en Britio, vi bezonus rigardi ĉiun vicon por determini ĉu tiu vico apartenas al la UK. Ĝi kostos al vi N transakciojkie N - nombro da linioj, kio ne estas malbona, sed ĉu povus esti pli rapida maniero? Nun estas tempo por ni konatiĝi kun la arboj.

Notu: Plej modernaj datumbazoj disponigas plilongigitajn tabelojn por konservi tabelojn efike: amaso-organizedtables kaj indekso-organizedtables. Sed ĉi tio ne ŝanĝas la problemon rapide trovi specifan kondiĉon en grupo de kolumnoj.

Datumbaza arbo kaj indekso

Duuma serĉarbo estas duuma arbo kun speciala propraĵo, la ŝlosilo ĉe ĉiu nodo devas esti:

• pli granda ol ĉiuj ŝlosiloj konservitaj en la maldekstra subarbo
• malpli ol ĉiuj ŝlosiloj stokitaj en la dekstra subarbo

Ni vidu, kion tio signifas vide

Ideo

Ĉi tiu arbo havas N = 15 elementojn. Ni diru, ke mi serĉas 208:

• Mi komencas ĉe la radiko, kies ŝlosilo estas 136. Ekde 136<208, mi rigardas la dekstran subarbon de nodo 136.
• 398>208 do mi rigardas la maldekstran subarbon de la nodo 398
• 250>208 do mi rigardas la maldekstran subarbon de la nodo 250
• 200<208, tial mi rigardas la ĝustan subarbon de nodo 200. Sed 200 ne havas ĝustan subarbon, valoro ne ekzistas (ĉar se ĝi ekzistas, ĝi estos en la dekstra subarbo 200).

Nun ni diru, ke mi serĉas 40

• Mi komencas ĉe la radiko, kies ŝlosilo estas 136. Ekde 136 > 40, mi rigardas la maldekstran subarbon de nodo 136.
• 80 > 40, tial mi rigardas la maldekstran subarbon de la nodo 80
• 40= 40, nodo ekzistas. Mi prenas la vicon ID ene de la nodo (ne montrita en la bildo) kaj serĉas en la tabelo la donita vico ID.
• Koni la vicon ID permesas al mi scii precize kie la datumoj estas en la tabelo, do mi povas preni ĝin tuj.

Fine, ambaŭ serĉoj kostos al mi la nombron da niveloj ene de la arbo. Se vi atente legas la parton pri kunfanda ordigo, vi devus vidi ke ekzistas log(N) niveloj. Rezultas, serĉokostoprotokolo (N), ne malbona!

Ni revenu al nia problemo

Sed ĉi tio estas tre abstrakta, do ni revenu al nia problemo. Anstataŭ simpla entjero, imagu ĉenon, kiu reprezentas la landon de iu en la antaŭa tabelo. Ni diru, ke vi havas arbon, kiu enhavas la kampon "lando" (kolumno 3) de la tabelo:

• Se vi volas scii, kiu laboras en Britio
• vi rigardas la arbon por ricevi la nodon kiu reprezentas Brition
• ene de "UKnode" vi trovos la lokon de britaj laboristaj registroj.

Ĉi tiu serĉo kostos log(N) operaciojn anstataŭ N operaciojn se vi uzas la tabelon rekte. Tio, kion vi ĵus prezentis, estis datumbaza indekso.

Vi povas konstrui indeksarbon por iu ajn grupo de kampoj (ŝnuro, nombro, 2 linioj, nombro kaj ĉeno, dato...) kondiĉe ke vi havas funkcion por kompari klavojn (te kampogrupoj) por ke vi povu agordi ordo inter la ŝlosiloj (kio estas la kazo por iuj bazaj tipoj en la datumbazo).

B+ArbaIndekso

Dum ĉi tiu arbo funkcias bone por akiri specifan valoron, estas GRANDA problemo kiam vi bezonas akiri plurajn elementojn inter du valoroj. Ĉi tio kostos O(N) ĉar vi devos rigardi ĉiun nodon en la arbo kaj kontroli ĉu ĝi estas inter ĉi tiuj du valoroj (ekz. kun ordigita krucado de la arbo). Plie, ĉi tiu operacio ne amikas al disko I/O ĉar vi devas legi la tutan arbon. Ni devas trovi manieron efike ekzekuti intervalpeto. Por solvi ĉi tiun problemon, modernaj datumbazoj uzas modifitan version de la antaŭa arbo nomata B+Tree. En arbo B+Arbo:

• nur la plej malaltaj nodoj (folioj) vendej informoj (loko de vicoj en la rilata tabelo)
• la resto de la nodoj estas ĉi tie por vojigo al la ĝusta nodo dum serĉado.

Kiel vi povas vidi, estas pli da nodoj ĉi tie (dufoje). Efektive, vi havas pliajn nodojn, "decidnodojn", kiuj helpos vin trovi la ĝustan nodon (kiu konservas la lokon de la vicoj en la rilata tabelo). Sed la serĉkomplekseco ankoraŭ estas O(log(N)) (estas nur unu plia nivelo). La granda diferenco estas tio nodoj ĉe la pli malalta nivelo estas konektitaj al siaj posteuloj.

Kun ĉi tiu B+Arbo, se vi serĉas valorojn inter 40 kaj 100:

• Vi nur bezonas serĉi 40 (aŭ la plej proksiman valoron post 40 se 40 ne ekzistas) kiel vi faris kun la antaŭa arbo.
• Poste kolektu 40 heredantojn uzante rektajn heredantajn ligilojn ĝis vi atingos 100.

Ni diru, ke vi trovas M posteulojn kaj la arbo havas N nodojn. Trovi specifan nodon kostas log(N) kiel la antaŭa arbo. Sed post kiam vi ricevas ĉi tiun nodon, vi ricevos M-posteulojn en M-operacioj kun referencoj al iliaj posteuloj. Ĉi tiu serĉo kostas nur M+log(N) operacioj kompare kun N operacioj sur la antaŭa arbo. Plie, vi ne devas legi la plenan arbon (nur M+log(N) nodoj), kio signifas malpli da diskuzado. Se M estas malgranda (ekz. 200 vicoj) kaj N estas granda (1 vicoj), estos GRANDA diferenco.

Sed estas novaj problemoj ĉi tie (denove!). Se vi aldonas aŭ forigas vicon en la datumbazo (kaj do en la rilata B+Arba indekso):

• vi devas konservi ordon inter la nodoj ene de B+Arbo, alie vi ne povos trovi la nodojn ene de neordigita arbo.
• vi devas konservi la minimuman eblan nombron da niveloj en B+Arbo, alie la tempokomplekseco de O(log(N)) fariĝas O(N).

Alivorte, B+Tree devas esti mem-orda kaj ekvilibra. Feliĉe, ĉi tio eblas per inteligentaj operacioj por forigi kaj enmeti. Sed tio kostas: enmetoj kaj forigoj en B+-arbo kostas O(log(N)). Tial kelkaj el vi aŭdis tion uzi tro da indeksoj ne estas bona ideo. Vere, vi malrapidigas rapidan enmeton/ĝisdatigon/forigon de vico en tabeloĉar la datumbazo bezonas ĝisdatigi la indeksojn de la tabelo uzante multekostan O(log(N)) operacion por ĉiu indekso. Plie, aldoni indeksojn signifas pli da laborŝarĝo por administranto de transakcioj (estos priskribita fine de la artikolo).

Por pliaj detaloj, vi povas vidi la artikolon pri Vikipedio B+arbo. Se vi volas ekzemplon de efektivigo de B+Tree en datumbazo, rigardu ĉi tiu artikolo и ĉi tiu artikolo de gvida MySQL-programisto. Ili ambaŭ fokusiĝas pri kiel InnoDB (la MySQL-motoro) pritraktas indeksojn.

Noto: Leganto diris al mi, ke pro malaltnivelaj optimumoj, la B+-arbo devus esti tute ekvilibrigita.

Hashtable

Nia lasta grava datumstrukturo estas la hashtabelo. Ĉi tio estas tre utila kiam vi volas rapide serĉi valorojn. Plie, kompreno de hashtabelo helpos nin poste kompreni oftan datumbazan kunigoperacion nomitan hash join ( hash join). Ĉi tiu datumstrukturo ankaŭ estas uzata de la datumbazo por stoki iujn internajn aferojn (ekz. ŝlosi tablon aŭ bufrolaĝejo, ni vidos ambaŭ ĉi tiujn konceptojn poste).

Hashtabelo estas datumstrukturo, kiu rapide trovas elementon per sia ŝlosilo. Por konstrui hashtabelon vi devas difini:

• pardonu por viaj elementoj
• hash funkcio por ŝlosiloj. La komputitaj ŝlosilaj haŝoj donas la lokon de la elementoj (nomitaj segmentoj ).
• funkcio por kompari klavojn. Post kiam vi trovis la ĝustan segmenton, vi devas trovi la elementon, kiun vi serĉas en la segmento, uzante ĉi tiun komparon.

Simpla ekzemplo

Ni prenu klaran ekzemplon:

Ĉi tiu hashtabelo havas 10 segmentojn. Ĉar mi estas maldiligenta, mi bildigis nur 5 segmentojn, sed mi scias, ke vi estas saĝa, do mi lasos vin bildigi la aliajn 5 memstare. Mi uzis hash-funkcion modulo 10 de la ŝlosilo. Alivorte, mi stokas nur la lastan ciferon de la ŝlosilo de la elemento por trovi ĝian segmenton:

• se la lasta cifero estas 0, la elemento falas en segmenton 0,
• se la lasta cifero estas 1, la elemento falas en segmenton 1,
• se la lasta cifero estas 2, la elemento falas en areon 2,
• ...

La kompara funkcio, kiun mi uzis, estas simple egaleco inter du entjeroj.

Ni diru, ke vi volas akiri elementon 78:

• La hashtabelo kalkulas la hashkodon por 78, kio estas 8.
• La hashtabelo rigardas segmenton 8, kaj la unua elemento, kiun ĝi trovas, estas 78.
• Ŝi resendas eron 78 al vi
• Serĉo kostas nur 2 operaciojn (unu por kalkuli la hash-valoron kaj la alia por serĉi la elementon ene de la segmento).

Nun ni diru, ke vi volas akiri elementon 59:

• La hashtabelo kalkulas la hashkodon por 59, kio estas 9.
• La hashtabelo serĉas en segmento 9, la unua elemento trovita estas 99. Ĉar 99!=59, elemento 99 ne estas valida elemento.
• Uzante la saman logikon, la dua elemento (9), la tria (79), ..., la lasta (29) estas prenita.
• Elemento ne trovita.
• La serĉo kostis 7 operaciojn.

Bona hash-funkcio

Kiel vi povas vidi, depende de la valoro, kiun vi serĉas, la kosto ne estas la sama!

Se mi nun ŝanĝas la hash-funkcion modulo 1 de la ŝlosilo (tio estas, prenante la lastajn 000 ciferojn), la dua serĉo kostas nur 000 operacion ĉar ne estas elementoj en segmento 6. La vera defio estas trovi bonan hash-funkcion, kiu kreos sitelojn enhavantajn tre malgrandan nombron da elementoj.

En mia ekzemplo, trovi bonan hashfunkcion estas facila. Sed ĉi tio estas simpla ekzemplo, trovi bonan hashfunkcion estas pli malfacila kiam la ŝlosilo estas:

• ĉeno (ekzemple - familia nomo)
• 2 linioj (ekzemple - familia nomo kaj antaŭnomo)
• 2 linioj kaj dato (ekzemple - familia nomo, antaŭnomo kaj dato de naskiĝo)
• ...

Kun bona hashfunkcio, hashtabelserĉoj kostas O(1).

Array vs hash-tabelo

Kial ne uzi tabelon?

Hmm, bona demando.

• La hashtabelo povas esti parte ŝarĝita en memoron, kaj la ceteraj segmentoj povas resti sur la disko.
• Kun tabelo vi devas uzi apudan spacon en memoro. Se vi ŝarĝas grandan tablon estas tre malfacile trovi sufiĉe da kontinua spaco.
• Por hashtabelo, vi povas elekti la ŝlosilon, kiun vi volas (ekzemple, lando kaj familia nomo de persono).

Por pliaj informoj, vi povas legi la artikolon pri javaHashMap, kiu estas efika efektivigo de hashtabelo; vi ne bezonas kompreni Javan por kompreni la konceptojn kovritajn en ĉi tiu artikolo.

fonto: www.habr.com