Tere, Habr! Esitan teile artikli tõlke
"Kuidas toimib relaatsiooniline andmebaas".

Relaatsiooniliste andmebaaside kohta mõeldes ei saa ma jätta mõtlemata, et midagi on puudu. Need on kasutusel igal pool. On palju erinevaid andmebaase: alates väikesest ja kasulikust SQLite'ist kuni võimsa Teradatani. Kuid neid, mis selgitavad, kuidas andmebaas töötab, on vaid mõned artiklid. Saate ise otsida 'howdoesarelationaldatabasework' ("kuidas töötavad relaatsioonilised andmebaasid") ja näha, kui vähe tulemusi seal on. Veelgi enam, need artiklid on lühikesed. Kui aga otsite viimaseid moetehnoloogiaid (Big Data, NoSQL või JavaScript), leiate rohkem süvitsi minevaid artikleid, mis selgitavad, kuidas need töötavad.

Kas relaatsioonilised andmebaasid on liiga vanad ja igavad, et neid saaks selgitada väljaspool ülikooli kursusi, uurimistöid ja raamatuid?

Arendajana vihkan ma kasutada seda, mida ma ei mõista. Ja kui andmebaase on kasutatud rohkem kui 40 aastat, peab olema põhjus. Nende aastate jooksul olen kulutanud sadu tunde, et tõeliselt mõista neid kummalisi musti kaste, mida kasutan iga päev. Seotud andmebaasid on väga huvitavad, kuna need põhineb kasulikul ja korduvalt kasutataval kontseptsioonil. Kui teid huvitab andmebaasi mõistmine, kuid teil ei ole kunagi olnud aega või soovi selle ulatuslikku teemat süveneda, siis see artikkel peaks teile meeldima.

Kuigi selle artikli pealkiri on selge, ei ole selle artikli eesmärgiks andmebaasi kasutamine. Seetõttu peate juba teadma, kuidas kirjutada lihtne ühendusloend ja põhilised päringud CRUD; vastasel juhul ei pruugi te seda artiklit mõista. See on ainus, mida peate teadma; ma selgitan kõike muud.

Alustan mõningatest arvutiteaduse alustest, nagu algoritmide ajakompleksus (BigO). Tean, et mõned teist ei salli seda kontseptsiooni, kuid ilma selleta ei mõista te andmebaasi sisemisi nüansse. Kuna see on tohutu teema, fokuseerin sellele, mida pean oluliseks: kuidas andmebaas töötleb SQL palve. Esitan ainult põhialused andmebaasidest, et artikli lõpus oleks teil ettekujutus sellest, mis toimub sisemiselt.

Kuna see on pika- ja tehnilise sisuga artikkel, mis sisaldab mitmeid algoritme ja andmestruktuure, ärge kiirustage selle lugemisega. Mõned kontseptsioonid võivad olla keerulised ja te võite need vahele jätta, kuid ikkagi saada terviklikku arusaama.

Teie paremini informeerimiseks on see artikkel jagatud kolme ossa:

• Andmebaasi madala ja kõrge taseme komponentide ülevaade
• Küsimuste optimeerimise protsessi ülevaade
• Tehingute ja vahemälupanga haldamise ülevaade

Tagasi alustesse

Aastaid tagasi (kaugelt, kaugelt galaktikast...) pidid arendajad täpselt teadma nende kodeeritud operatsioonide arvu. Nad teadsid oma algoritme ja andmestruktuure peast, sest ei saanud lubada endale aeglaste arvutite CPU ja mälu raiskamist.

Selles osas meenutan ma teile mõningaid nendest kontseptsioonidest, kuna need on vajalikud andmebaasi mõistmiseks. Tutvustan ka mõistet andmebaasi indeks.

O(1) vs O(n2)

Praegu ei pööra paljud arendajad tähelepanu algoritmide ajakompleksusele... ja nad on õiged!

Kuid kui tegelete suuri andmemahtudega (ma ei räägi tuhandetest) või kui võitlete millisekundite nimel, on ülioluline mõista seda kontseptsiooni. Ja nagu te aru saite, peavad andmebaasid tegelema mõlema olukorraga! Ma ei pane teid kulutama rohkem aega, kui on vajalik selle olemuse mõistmiseks. See aitab meil hiljem mõista kulu põhist optimeerimistkulu põhiste optimeerimine).

Kontseptsioon

Algoritmi ajakompleksus kasutatakse selleks, et näha, kui palju aega kulub algoritmi täitmiseks antud andmemahu puhul.Selle kompleksuse kirjeldamiseks kasutatakse suurte O matemaatilisi tähistusi. See märk on seotud funktsiooniga, mis kirjeldab, kui palju operatiivseid vajab algoritm määratud koguse sisendandmete töötlemiseks.

Näiteks, kui ma ütlen "see algoritm on keerukus O (some_function() )", tähendab see, et teatud andmemahtu töötlemiseks on algoritmil vaja some_function(a_certain_amount_of_data) operatsiooni.

Samal ajal Oluline ei ole andmete hulk**, vaid see, ** kuidas operatsioonide arv kasvab koos andmehulga suurenemisega.. Aja keerukus ei näita täpset operatsioonide arvu, kuid see on hea viis tööaja hindamiseks.

Sellel graafikul näete operatsioonide arvu sõltuvust sisendandmete mahust erinevat tüüpi algoritmide ajakeerukuse jaoks. Olen kasutanud logaritmilist skaalat nende kuvamiseks. Teisisõnu, andmete hulk suureneb kiiresti 1-st kuni 1 miljardini. Saame näha, et:

• O(1) ehk konstantne keerukus jääb muutumatuks (muul juhul ei saaks seda nimetada konstantseks keerukuseks).
• O(log(n)) jääb madalaks isegi miljardite andmete korral.
• Halvim keerukus on O(n2), kus operatsioonide arv kasvab kiiresti.
• Kahel teisel keerukusel on sama kiiresti suurenev jõudlus.

Näited

Väikese andmehulga korral on O(1) ja O(n2) vahe tühine. Oletame näiteks, et teie algoritm peab töötlema 2000 elementi.

• O(1) algoritm nõuab 1 operatsiooni
• O(log(n)) algoritm nõuab 7 operatsiooni
• O(n) algoritm nõuab 2 000 operatsiooni
• O(n * log(n)) algoritm nõuab 14 000 operatsiooni
• O(n2) algoritm nõuab 4 000 000 operatsiooni

O(1) ja O(n2) erinevus võib tunduda suur (4 miljonit operatsiooni), kuid te kaotate maksimaalselt 2 ms, vaid silmapilguga. Tõepoolest, tänapäeva protsessorid suudavad töödelda sadu miljoneid operatsioone sekundis. Seetõttu ei ole jõudlus ja optimeerimine paljude IT-projektide puhul probleem.

Nagu ma juba ütlesin, on selle mõiste teadmine endiselt oluline, kui töötate suure hulga andmetega. Kui seekord peab algoritm töötlema 1 000 000 elementi (mis ei ole päris palju andmebaasi jaoks):

• O(1) algoritm nõuab 1 operatsiooni
• O(log(n)) algoritm nõuab teilt 14 operatsiooni
• O(n) algoritm nõuab teilt 1 000 000 operatsiooni
• O(n * log(n)) algoritm nõuab teilt 14 000 000 operatsiooni
• O(n2) algoritm nõuab teilt 1 000 000 000 000 operatsiooni

Ma ei ole arvutusi teinud, kuid ma ütleksin, et O(n2) algoritmiga on teil aega kohvi juua (isegi kaks!). Kui lisate veel 0 andmete mahu juurde, on teil aega, et väike uinak teha.

Minu sügavamale minek

Viidates:

• Hea hajutustabeli otsimine leiab elemendi O(1) ajaga.
• Hästi tasakaalustatud puu otsimine annab tulemuse O(log(n)) ajaga.
• Massiivis otsimine annab tulemuse O(n) ajaga.
• Parimatel sortimisalgoritmidel on O(n * log(n)) keerukus.
• Halb süsteemi sorteerimisalgoritm on keerukusega O(n2).

Märkus: järgmistes osades näeme neid algoritme ja andmestruktuure.

Algoritmi ajakulu on mitut tüüpi:

• keskmise juhtumi stsenaarium
• parim arengusenaarium
• ja halvim stsenaarium

Ajakulu on sageli halvim stsenaarium.

Rääkisin ainult algoritmi ajakulust, kuid keerukus kehtib ka:

• algoritmi mälutarbimise kohta
• algoritmi kettasisendi/väljundi kohta

Muidugi on olemas keerukusi, mis on halvemad kui n2, näiteks:

• n4: see on kohutav! Mõned mainitud algoritmid on sellise keerukusega.
• 3n: see on veel hullem! Üks algoritm, mida näeme selle artikli keskosas, omab seda keerukust (ja seda kasutatakse tõepoolest paljudes andmebaasides).
• faktoriaal n: te ei saa kunagi oma tulemusi isegi väikse andmemahu korral.
• nn: kui kohtate seda keerukust, peaksite endalt küsima, kas see tõeliselt kuulub teie valdkonda …

Märkus: andsin teile mitte õige määratlemise tähenduse „suur O”, vaid lihtsalt idee. Saate seda artiklit lugeda Vikipeediale reaalse (asümptootilise) määratlemise jaoks.

MergeSort (Merge Sort)

Mida teete, kui peate kogumit sorteerima? Mis? Te kutsute funktsiooni sort ()… Okei, hea vastus… Kuid andmebaasi puhul peate mõistma, kuidas see sort () funktsioon töötab.

On mitmeid häid sorteerimisalgoritme, seega peatun kõige olulisemal: merge sort. Võib-olla te ei mõista, miks andmete sorteerimine on kasulik, kuid peaksite seda mõistma pärast osakest, mis käsitleb päringute optimeerimist. Veelgi enam, merge sort'i mõistmine aitab meil hiljem mõista andmebaaside üldist operatsiooni join, mida nimetatakse merge liitu (merge join).

Merge (ühinemine)

Nagu paljude kasulike algoritmide puhul, põhineb merge sort nutikusel: 2 sorteeritud massiivi, mille suurus on N / 2, ühendamine N-elementseks sorteeritud massiiviks maksab vaid N toimingut. Seda toimingut nimetatakse ühinemiseks.

Vaatame, mida see lihtsa näite põhjal tähendab:

Selles joonises on näha, et kahe 4-elementilise massiivi abil saate koostada lõpliku järjestatud 8-elementilise massiivi, tehes vaid ühe iteratsiooni. Kuna mõlemad 4-elementilised massiivid on juba järjestatud:

• 1) võrrelge kahe massiivi jõudmisel praeguseid elemente (alguses praegune = esimesele)
• 2) seejärel võtke kõige väiksem, et paigutada see 8-elementilisse massiivi
• 3) ja minge järgmisele elemendile massiivis, kust te kõige väiksema elemendi võtsite
• ja korrake 1, 2, 3, kuni jõuate ühe massiivi viimase elemendini.
• Seejärel võtate teise massiivi ülejäänud elemendid, et paigutada need 8-elementilisse massiivi.

See töötab, sest mõlemad 4-elementilised massiivid on järjestatud ja seetõttu ei pea te nendes massiivides 'tagasi minema'.

Nüüd, kui oleme aru saanud sellest nippist, siin on minu pseudokood merge jaoks:

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

   //rekursiivsed kõned
   [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);

   // kahe väikese järjestatud massiivi ühendamine suureks
   array result := merge(new_left_array,new_right_array);
   return result;

Mergesort jagab ülesande väiksemateks ülesanneteks ning seejärel leiab väiksemate ülesannete tulemused, et saada algse ülesande tulemus (märkus: seda tüüpi algoritme nimetatakse jagamiseks ja valitsuseks). Kui te ei saa seda algoritmi aru, ärge muretsege; mina ei saanud ka esimesel korral aru. Kui see aitab, näen ma seda algoritmi kahefaasilise algoritmina:

• Jagamisfaas, kus massiiv jagatakse väiksemateks massiivideks
• Sorteerimisfaas, kus väiksed massiivid ühendatakse (kasutades ühendamist), et moodustada suurem massiiv.

Jagamisfaas

Jagamisetapis jagatakse massiiv üheüksikuteks massiivideks 3 sammus. Formaalne sammaste arv on log(N) (kuna N=8, log(N) = 3).

Kust ma seda tean?

Ma olen geenius! Ühesõnaga – matemaatika. Idee seisneb selles, et igal sammul jagatakse algse massiivi suurus 2. Sammaste arv on see, mitu korda saate algset massiivi kaheks jagada. See on logaritmi täpne määratlemine (alusel 2).

Sorteerimisfaas

Sorteerimisprotsessi alguses alustate üheinimeste (üheelemendiliste) massiividega. Iga etapi jooksul rakendate mitmeid sulandamiste operatsioone ning kogukulu on N = 8 operatsiooni:

• Esimeses etapis on Teil 4 sulandumist, millest igaühe maksumus on 2 operatsiooni
• Teises etapis on Teil 2 sulandumist, millest igaühe maksumus on 4 operatsiooni
• Kolmandas etapis on Teil 1 sulandumine, mille maksumus on 8 operatsiooni

Kuna on olemas log(N) sammu, kogukulu N * log(N) operatsiooni.

Sulandmise sortimise eelised

Miks on see algoritm nii võimas?

Sest:

• Saate seda muuta, et vähendada mälu kasutust, nii et Te ei loobu uutest massiividest, vaid muundate otse sisendmassii.

Märkus: seda tüüpi algoritmid nimetatakse in—place (sorteerimine ilma täiendava mäluta).

• Saate seda muuta, et kasutada ketta ruumi ja väikest mälumahtu samal ajal ilma oluliste kettasisendite ja -väljundita. Idee on laadida mällu ainult need osad, mida hetkel töödeldakse. See on oluline, kui peate sorteerima mitu gigabaiti andmeid ainult 100 megabaiti mälupuhvri mahuga.

Märkus: seda tüüpi algoritmid nimetatakse väline sortimine.

• Saate seda muuta, et see töötaks mitme protsessi / joone / serveriga.

Näiteks jaotatud sulatussortimine on üks peamisi komponente Hadoop (mis on struktureeritud suurtes andmetes).

• See algoritm suudab muuta pliidi kullaks (tõsiselt!).

Seda sortimisalgoritmi kasutatakse enamikus (kui mitte kõigis) andmebaasides, kuid see pole ainus. Kui soovite rohkem teada, võite lugeda seda uurimistööd, mis arutleb andmebaasi tavaliste sortimisalgoritmide plusse ja miinuseid.

Massiiv, Puud ja Hash-tabel

Nüüd, kui me mõistame ajalisest keerukusest ja sorteerimisest, pean ma teile rääkima kolmest andmestruktuurist. See on oluline, kuna need moodustavad tänapäevaste andmebaaside aluse.Tutvustan ka mõistet andmebaasi indeks.

Maatrikssüsteem

Kahemõõtmeline massiiv on kõige lihtsam andmestruktuur. Tabelit võib käsitleda kui massiivi. Näiteks:

See 2-mõõtmeline massiiv esindab tabelit ridade ja veergudega:

• Iga rida esindab mingit entiteeti.
• Veergudes hoitakse omadusi, mis kirjeldavad entiteeti.
• Iga veerg hoiab andmeid kindlas tüübis (täisarv, string, kuupäev …).

Kuigi on mugav andmeid hoida ja visualiseerida, ei sobi see, kui peate leidma kindla väärtuse.

Näiteks, kui soovite leida kõiki tüüpe, kes töötavad Suurbritannias, peate iga rida läbi vaatama, et määrata, kas see rida kuulub Suurbritanniale. See maksab teile N operatsiooni, kus N — ridade arv, mis on suhteliselt hea, kuid kas on kiiremat teed? Nüüd on aeg tutvuda puude struktureerimisega.

Märkus: enamik tänapäevaseid andmebaase pakuvad ulatuslikke massiive tõhusaks tabelite salvestamiseks: heap-organiseeritud tabelid ja indeksiga organiseeritud tabelid. Kuid see ei muuda kiire otsingu probleemi teatud tingimuste jaoks veergude grupis.

Andmebaasi puu ja indeks

Binaarne otsingupuu on binaarne puu, millel on eriline omadus: iga sõlme võtme peab olema:

• suurem kui kõik võtmed, mis on salvestatud vasakusse alampuusse
• väiksem kui kõik võtmed, mis on salvestatud paremasse alampuusse

Vaatame, mida see visuaalselt tähendab

Idee

See puu sisaldab N = 15 elementi. Oletame, et otsin 208:

• Alustan juurest, mille võtme väärtus on 136. Kuna 136 < 208, vaatan sõlme 136 paremat alampuud.
• 398 > 208, seetõttu vaatan sõlme 398 vasakut alampuud
• 250 > 208, seetõttu vaatan sõlme 250 vasakut alampuud
• 200 < 208, seetõttu vaatan sõlme 200 paremat alampuud. Kuid 200-l ei ole paremat alampuud, väärtust ei eksisteeri (sest kui see eksisteeriks, oleks see sõlme 200 paremas alampuus).

Nüüd oletame, et otsin 40

• Alustan juurest, mille võtme väärtus on 136. Kuna 136 > 40, vaatan sõlme 136 vasakut alampuud.
• 80 > 40, seega vaatan ma_node 80 vasakut alampuud
• 40= 40, node eksisteerib. Tõstan välja rea ID selle sõlme sees (seda pole joonisel) ning otsin selle rea ID põhjal tabelist.
• Rea ID teadmine võimaldab mul teada, kus andmed tabelis asuvad, ja seetõttu saan neid kohe kätte.

Kokkuvõttes maksavad mõlemad otsingud mulle tasemeid puu sees. Kui loete hoolikalt sulandumisjärjestuse osa, peaksite nägema, et siin on log (N) taset. Seega, otsingu maksumus log(N), mitte paha!

Naaseme meie probleemile

Aga see on väga abstraktne, seega naeme meie probleemile. Selle asemel et lihtsalt terve arvu, kujutage ette stringi, mis esindab kellegi riiki eelnevas tabelis. Eeldame, et teil on puu, mis sisaldab välja "country" (veeru 3) tabelist:

• Kui soovite teada, kes töötab Ühendkuningriigis
• vaatate puu suunas, et leida sõlm, mis esindab Ühendkuningriiki
• sõlmes "UKnode" leiate Ühendkuningriigi töötajate salvestuste asukoha.

See otsing maksab log(N) toimingut, mitte N toimingut, kui te ei kasuta otse massiivi. Just see, mida te tutvustasite — oli andmebaasi indeks.

Sa saad luua indeksipuu mistahes väljade rühma jaoks (string, number, 2 stringi, number ja string, kuupäev…) seni, kuni sul on võrdlemiseks funktsioon (st väljade rühm), et saaksid kehtestada järjestuse võtmete vahel (mis kehtib kõigi põhityüpide kohta andmebaasis).

B+TreeIndex

Kuigi see puu töötab hästi kindla väärtuse saamiseks, on olemas SUUR probleem, kui sul on vaja saada mitu elementi kahe väärtuse vahel. See maksab O(N), kuna sul tuleb iga puu sõlm läbi vaadata ja kontrollida, kas see on nende kahe väärtuse vahel (näiteks järjestatud puu läbimise kaudu). Veelgi enam, see operatsioon ei sobi diskivõimalustele, kuna sul tuleb lugeda terve puu. Peame leidma viisi, kuidas tõhusalt teostada vahe-küsimust. Selle probleemi lahendamiseks kasutavad kaasaegsed andmebaasid muutatud versiooni varasemast puust nimega B+Tree. B+Tree puus:

• ainult kõige alumised sõlmed (lehed) hoidvad teavet (ridade asukoht seotud tabelis)
• ülejäänud sõlmed asuvad siin õige sõlme suunamiseks otsimise ajal Kuidas näete, on siin rohkem sõlmi (kaks korda rohkem). Tõepoolest, teil on lisasõlmed, „otsuste tegemise sõlmed“, mis aitavad teil leida õige sõlme (mis hoiab ridade asukohta seotud tabelis). Kuid otsingu keerukus on endiselt O(log(N)) (seal on vaid veel üks tase). Suur vahe seisneb selles, et.

Nagu näete, on siin rohkem sõlme (kahe korra võrra). Tõeliselt, teil on lisasõlmed, "otsustuspunktid", mis aitavad teil leida õige sõlm (mis hoiab seostatud tabeli ridade asukohta). Kuid otsingu keerukus on endiselt O(log(N)) (olemas on vaid veel üks tase). Suur erinevus seisneb selles, et alumise taseme sõlmed on seotud oma järeltulijatega..

Selle B+Tree puhul, kui otsite väärtusi vahemikus 40 kuni 100:

• Peate lihtsalt otsima 40 (või lähimat väärtust, kui 40 ei eksisteeri), nagu te tegite varasema puuga.
• Seejärel koguge 40 järeltulijad, kasutades otseseid viiteid järeltulijatele, kuni jõuate 100.

Oletame, et leidsid M järglast ja puul on N sõlme. Konkreetse sõlme leidmine maksab log(N) nagu eelmises puus. Kuid kui oled saanud selle sõlme, saad M järglast M operatsiooni kaudu viidete juurde. See otsing maksab ainult M+log(N) operatsiooni, võrreldes N operatsiooniga eelmises puus. Veelgi enam, sul ei ole vaja lugeda kogu puu (ainult M + log(N) sõlme), mis tähendab väiksemat ketta kasutust. Kui M on väike (näiteks 200 rida) ja N suur (1 000 000 rida), on see SUUREM erinevus.

Aga siin on uusi probleeme (taas!). Kui lisad või eemaldad rea andmebaasis (ja seega seotud indeksis B+Tree):

• pead säilitama järjekorra sõlmede vahel B+Tree-s, vastasel juhul ei saa sa leida sõlme sorteerimata puus.
• pead hoidma minimaalset võimalikku tasemete arvu B+Tree-s, vastasel juhul muutub ajakulu O(log(N))-st O(N)-ks.

Teisisõnu, B+Tree peab olema isekorrastuv ja tasakaalustatud. Õnneks on see võimalik nutikate kustutamis- ja sisestamisoperatsioonidega. Kuid see on kulukas: sisestamine ja kustutamine B+ puus maksavad O(log(N)). Sellepärast olete võib-olla kuulnud, et liigne indeksite kasutamine ei ole hea mõte. Tõepoolest, te aeglustate kiiret sisestamist / värskendamist / kustutamist tabelis, kuna andmebaasis tuleb iga indeksi jaoks läbi viia kulukas O(log(N)) operatsioon indeksi uuendamiseks. Veelgi enam, indeksite lisamine tähendab suuremat koormust tehingute haldurile (sellest räägitakse artikli lõpus).

Kuna soovite rohkem teavet, saate vaadata Vikipeedia artiklit B+Puu. Kui soovite näidet B+Tree rakendamisest andmebaasis, vaadake selle artikli ja selle artikli maailmakuulsa MySQL arendaja juhendit. Need keskenduvad sellele, kuidas InnoDB (MySQL mootor) indekseid haldab.

Märkus: lugeja ütles mulle, et madala taseme optimeerimiste tõttu peab B+ puu olema täielikult tasakaalustatud.

HashTable (Räsi-tabel)

Meie viimane oluline andmestruktuur on hash-tabel. See on väga kasulik, kui soovite kiiresti väärtusi otsida. Veelgi enam, hash-tabeli mõistmine aitab meil hiljem mõista üldoperatsiooni, millega ühendatakse andmebaas, tuntud kui hash-ühendus ( hash join). See andmestruktuur on samuti andmebaasi sees mõningate sisestruktuuride (näiteks lukutabel või puuderiit, me näeme mõlemat neist kontseptsioonidest hiljem).

Hash-tabel on andmestruktuur, mis leiab elemendi kiiresti selle võtme järgi. Hash-tabeli ehitamiseks peate määrama:

• võtme oma elementide jaoks
• hash-funktsiooni võtmete jaoks. Arvutatud võtmehassed annavad elementide asukoha (mida nimetatakse segmendiks ).
• võtmete võrdlemise funktsiooni. Kui olete leidnud õige segmendi, peate leidma elemendi, mida otsite, segmendi sees, kasutades seda võrdlust.

Lihtne näide

Võtame visuaalse näite:

See hash-tabelil on 10 segmenti. Kuna ma olen laisk, olen kujutanud vaid 5 segmenti, kuid tean, et olete nutikad, seega lasen teil ise 5 teist segmenti ette kujutada. Kasutasin võtme 10-modulo hash-funktsiooni. Teisisõnu, hoian alles ainult elemendi võtme viimast numbrit, et leida selle segment:

• kui viimane number on 0, siis element kuulub segmenti 0,
• kui viimane number on 1, siis element kuulub segmenti 1,
• kui viimane number on 2, siis element kuulub segmendi 2,
• …

Kasutatud võrdlev funktsioon on lihtsalt täisarvude võrdlemine.

Oletame, et soovite saada elementi 78:

• Hash-tabel arvutab 78 jaoks hash-koodi, mis on 8.
• Hash-tabel vaatab segmenti 8 ja esimene element, mille ta leiab, on 78.
• See tagastab teile elemendi 78
• Otsing maksab ainult 2 operatsiooni (üks hash-funktsiooni väärtuse arvutamiseks ja teine elementide otsimiseks segmendis).

Nüüd oletame, et soovite saada elementi 59:

• Hash-tabel arvutab 59 jaoks hash-koodi, mis on 9.
• Hästi laotud tabel otsib 9. segmendis, esimene leitud element on 99. Kuna 99!=59, pole 99 õige element.
• Sama loogikat kasutades võetakse teine element (9), kolmas (79), …, viimane (29).
• Elementi ei leitud.
• Otsing maksis 7 operatsiooni..

Hea hash-funktsioon.

Nagu näete, sõltub otsitava väärtuse põhjal hind erinev!

Kui ma nüüd muudan hash-funktsiooni modulaarselt 1 000 000 võtme järgi (st võtan viimased 6 numbrit), siis teine otsing maksab ainult 1 operatsiooni, kuna segmendis 000059 pole elemente. Reaalne ülesanne on leida hea hash-funktsioon, mis loob segmente, mis sisaldavad väga vähe elemente..

Minu näites on hea hash-funktsiooni leidmine lihtne. Kuid see on lihtne näide, hea hash-funktsiooni leidmine on keerulisem, kui võti on:

• string (nt perekonnanimi)
• 2 stringi (nt perekonnanimi ja eesnimi)
• 2 stringi ja kuupäev (nt perekonnanimi, eesnimi ja sünnipäev)
• …

Hea hash-funktsiooniga toimub otsing hash-tabelis O(1) ajal..

Massiiv vs hash-tabel.

Miks mitte kasutada massiivi?

Hmm, hea küsimus.

• Hash-tabel võib olla. osaliselt mälu koormatud., ja ülejäänud segmendid võivad jääda kettale.
• Massiivi jaoks peate kasutama järjepidevat mäluruumi. Kui laadite sisse suure tabeli, on väga raske leida piisavalt järjepidevat ruumi..
• Hash-tabeli jaoks saate valida vajaliku võtme (näiteks isiku riik ja perekonnanimi).

Lisainformatsiooni saamiseks võite lugeda artiklit JavaHashMap, mis on efektiivne hash-tabeli rakendus; te ei pea Java't mõistma, et mõista artiklis esitatud mõisteid.

Allikas: habr.com