Hei Habr! Esitän huomionne artikkelin käännöksen
"Kuinka relaatiotietokanta toimii".

Mitä tulee relaatiotietokantoihin, en voi olla ajattelematta, että jotain puuttuu. Niitä käytetään kaikkialla. Saatavilla on monia erilaisia ​​tietokantoja pienestä ja hyödyllisestä SQLitesta tehokkaaseen Teradataan. Mutta vain muutama artikkeli selittää kuinka tietokanta toimii. Voit etsiä itseäsi käyttämällä "howdoesarelationaldatabasework" avulla nähdäksesi kuinka vähän tuloksia on. Lisäksi nämä artikkelit ovat lyhyitä. Jos etsit uusimpia buzzy-tekniikoita (BigData, NoSQL tai JavaScript), löydät tarkempia artikkeleita, joissa selitetään niiden toiminta.

Ovatko relaatiotietokannat liian vanhoja ja tylsiä selitettäviksi yliopistokurssien, tutkimuspapereiden ja kirjojen ulkopuolella?

Kehittäjänä vihaan käyttää jotain, jota en ymmärrä. Ja jos tietokantoja on käytetty yli 40 vuotta, siihen on oltava syy. Vuosien varrella olen käyttänyt satoja tunteja ymmärtääkseni todella näitä outoja mustia laatikoita, joita käytän päivittäin. Relaatiotietokannat erittäin mielenkiintoisia, koska ne perustuu hyödyllisiin ja uudelleenkäytettäviin käsitteisiin. Jos olet kiinnostunut ymmärtämään tietokantaa, mutta sinulla ei ole koskaan ollut aikaa tai halua syventyä tähän laajaan aiheeseen, sinun kannattaa nauttia tästä artikkelista.

Vaikka tämän artikkelin otsikko on selkeä, Tämän artikkelin tarkoitus ei ole ymmärtää tietokannan käyttöä. siksi, sinun pitäisi jo osata kirjoittaa yksinkertainen yhteyspyyntö ja peruskyselyt lika; muuten et ehkä ymmärrä tätä artikkelia. Se on ainoa asia, joka sinun on tiedettävä, minä selitän loput.

Aloitan joistakin tietojenkäsittelytieteen perusteista, kuten algoritmien aika monimutkaisuudesta (BigO). Tiedän, että jotkut teistä vihaavat tätä käsitettä, mutta ilman sitä ette voi ymmärtää tietokannan sisällä olevia monimutkaisia ​​asioita. Koska tämä on valtava aihe, Keskityn siihen mikä on mielestäni tärkeää: miten tietokanta käsittelee SQL tiedustelu. Esittelen vain tietokannan peruskäsitteetjotta artikkelin lopussa sinulla on käsitys siitä, mitä konepellin alla tapahtuu.

Koska tämä on pitkä ja tekninen artikkeli, joka sisältää paljon algoritmeja ja tietorakenteita, käytä aikaa sen lukemiseen. Joitakin käsitteitä voi olla vaikea ymmärtää; voit ohittaa ne ja silti saada yleiskäsityksen.

Tietävämmille teistä tämä artikkeli on jaettu kolmeen osaan:

• Yleiskatsaus matalan ja korkean tason tietokantakomponentteihin
• Yleiskatsaus kyselyn optimointiprosessiin
• Yleiskatsaus tapahtumien ja puskurivarannon hallinnasta

Takaisin perusasioihin

Vuosia sitten (kaukaisessa galaksissa...) kehittäjien piti tietää tarkasti koodaamiensa operaatioiden määrä. He tiesivät algoritmit ja tietorakenteet ulkoa, koska heillä ei ollut varaa hukata hitaan tietokoneidensa suoritinta ja muistia.

Tässä osassa muistutan sinua joistakin näistä käsitteistä, koska ne ovat välttämättömiä tietokannan ymmärtämisen kannalta. Esittelen myös konseptin tietokantahakemisto.

O(1) vs O(n2)

Nykyään monet kehittäjät eivät välitä algoritmien aikamonimutkaisuudesta... ja he ovat oikeassa!

Mutta kun käsittelet paljon dataa (en puhu tuhansista) tai jos kamppailet millisekunneissa, on tärkeää ymmärtää tämä käsite. Ja kuten voit kuvitella, tietokantojen on käsiteltävä molempia tilanteita! En pakota sinua käyttämään enempää aikaa kuin on tarpeen ymmärtääksesi asian. Tämä auttaa meitä ymmärtämään kustannusperusteisen optimoinnin käsitteen myöhemmin (maksaa perustua optimointi).

Käsite

Algoritmin aika monimutkaisuus käytetään näkemään, kuinka kauan algoritmin valmistuminen tietylle tietomäärälle kestää. Tämän monimutkaisuuden kuvaamiseksi käytämme matemaattista merkintää big O. Tätä merkintää käytetään funktion kanssa, joka kuvaa kuinka monta operaatiota algoritmi tarvitsee tietylle määrälle syötteitä.

Esimerkiksi, kun sanon "tämän algoritmin monimutkaisuus on O(jokin_funktio())", se tarkoittaa, että algoritmi vaatii jonkin_funktion(tiedon_määrä) -operaatioita käsitelläkseen tietyn määrän dataa.

Tässä tapauksessa Tietojen määrällä ei ole väliä**, muuten ** kuinka toimintojen määrä kasvaa datamäärän kasvaessa. Aikamonimutkaisuus ei tarjoa tarkkaa toimintojen määrää, mutta se on hyvä tapa arvioida suoritusaikaa.

Tässä kaaviossa näet operaatioiden lukumäärän verrattuna syötetyn datan määrään erityyppisille algoritmien aikakomplikaatioille. Käytin logaritmista asteikkoa niiden näyttämiseen. Toisin sanoen tiedon määrä kasvaa nopeasti yhdestä miljardiin. Näemme, että:

• O(1) eli jatkuva kompleksisuus pysyy vakiona (muuten sitä ei kutsuttaisi vakiokompleksisuudeksi).
• O(log(n)) pysyy alhaisena jopa miljardeista tiedoista huolimatta.
• Pahin vaikeus - O(n2), jossa operaatioiden määrä kasvaa nopeasti.
• Kaksi muuta komplikaatiota lisääntyvät yhtä nopeasti.

Примеры

Pienellä datamäärällä ero O(1):n ja O(n2):n välillä on mitätön. Oletetaan esimerkiksi, että sinulla on algoritmi, jonka täytyy käsitellä 2000 elementtiä.

• O(1)-algoritmi maksaa sinulle yhden operaation
• O(log(n))-algoritmi maksaa sinulle 7 operaatiota
• O(n)-algoritmi maksaa sinulle 2 000 operaatiota
• O(n*log(n))-algoritmi maksaa sinulle 14 000 operaatiota
• O(n2)-algoritmi maksaa sinulle 4 000 000 operaatiota

Ero O(1):n ja O(n2):n välillä näyttää suurelta (4 miljoonaa operaatiota), mutta menetät enintään 2 ms, vain aikaa räpytellä silmiäsi. Itse asiassa nykyaikaiset prosessorit voivat käsitellä satoja miljoonia operaatioita sekunnissa. Tästä syystä suorituskyky ja optimointi eivät ole ongelma monissa IT-projekteissa.

Kuten sanoin, on silti tärkeää tuntea tämä käsite, kun työskentelet valtavien tietomäärien kanssa. Jos tällä kertaa algoritmin on käsiteltävä 1 000 000 elementtiä (mikä ei ole niin paljon tietokannassa):

• O(1)-algoritmi maksaa sinulle yhden operaation
• O(log(n))-algoritmi maksaa sinulle 14 operaatiota
• O(n)-algoritmi maksaa sinulle 1 000 000 operaatiota
• O(n*log(n))-algoritmi maksaa sinulle 14 000 000 operaatiota
• O(n2)-algoritmi maksaa sinulle 1 000 000 000 000 operaatiota

En ole laskenut, mutta sanoisin, että O(n2)-algoritmilla ehdit juoda kahvin (jopa kaksi!). Jos lisäät datamäärään vielä nollan, sinulla on aikaa ottaa päiväunet.

Mennään syvemmälle

Tiedoksi:

• Hyvä hash-taulukon haku löytää elementin O(1):stä.
• Haku hyvin tasapainotetusta puusta tuottaa tulokset O(log(n)).
• Haku taulukosta tuottaa tulokset O(n).
• Parhaiden lajittelualgoritmien monimutkaisuus on O(n*log(n)).
• Huonon lajittelualgoritmin monimutkaisuus on O(n2).

Huomaa: Seuraavissa osissa näemme nämä algoritmit ja tietorakenteet.

Algoritmien aikamonimutkaisuutta on useita tyyppejä:

• keskimääräinen tapausskenaario
• paras tapaus
• ja pahimmassa tapauksessa

Aika monimutkaisuus on usein pahin skenaario.

Puhuin vain algoritmin aikamonimutkaisuudesta, mutta monimutkaisuus koskee myös:

• algoritmin muistinkulutus
• levyn I/O-kulutusalgoritmi

Tietenkin on komplikaatioita, jotka ovat pahempia kuin n2, esimerkiksi:

• n4: tämä on kauheaa! Joillakin mainituista algoritmeista on tämä monimutkaisuus.
• 3n: tämä on vielä pahempaa! Yhdellä tämän artikkelin keskellä näkevistä algoritmeista on tämä monimutkaisuus (ja sitä käytetään itse asiassa monissa tietokannoissa).
• factorial n: et koskaan saa tuloksia edes pienellä tietomäärällä.
• nn: Jos kohtaat tämän monimutkaisuuden, sinun tulee kysyä itseltäsi, onko tämä todella sinun toiminta-alasi...

Huomautus: En antanut sinulle suuren O-merkinnän todellista määritelmää, vain idean. Voit lukea tämän artikkelin osoitteessa wikipedia todellista (asymptoottista) määritelmää varten.

Yhdistä lajittelu

Mitä teet, kun sinun on lajiteltava kokoelma? Mitä? Kutsut sort()-funktiota... Ok, hyvä vastaus... Mutta tietokantaa varten sinun on ymmärrettävä, miten tämä sort()-funktio toimii.

Hyviä lajittelualgoritmeja on useita, joten keskityn tärkeimpiin: Yhdistä lajittelu. Et ehkä ymmärrä, miksi tietojen lajittelu on hyödyllistä juuri nyt, mutta sinun pitäisi tehdä se kyselyn optimointiosan jälkeen. Lisäksi yhdistämislajittelun ymmärtäminen auttaa meitä myöhemmin ymmärtämään yhteisen tietokannan liitosoperaation nimeltä yhdistää yhdistää (fuusioyhdistys).

Yhdistää

Kuten monet hyödylliset algoritmit, yhdistämislajittelu perustuu temppuun: kahden N/2-koon lajitellun taulukon yhdistäminen N-elementin lajiteltuun taulukkoon maksaa vain N operaatiota. Tätä toimintoa kutsutaan yhdistämiseksi.

Katsotaanpa, mitä tämä tarkoittaa yksinkertaisella esimerkillä:

Tämä kuva osoittaa, että luodaksesi lopullisen lajitellun 8 elementin taulukon sinun tarvitsee vain iteroida kerran kahden 2 elementin taulukon yli. Koska molemmat 4 elementin taulukot on jo lajiteltu:

• 1) vertaat molempia nykyisiä elementtejä kahdessa taulukossa (alkuvirta = ensimmäinen)
• 2) ota sitten pienin ja laita se 8 elementin taulukkoon
• 3) ja siirry taulukon seuraavaan elementtiin, josta otit pienimmän elementin
• ja toista 1,2,3, kunnes saavutat yhden taulukon viimeisen alkion.
• Sitten otat loput elementit toisesta taulukosta ja laitat ne 8 elementin taulukkoon.

Tämä toimii, koska molemmat 4-elementtiset taulukot lajitellaan, joten sinun ei tarvitse "palata" näissä taulukoissa.

Nyt kun ymmärrämme tempun, tässä on pseudokoodini yhdistämistä varten:

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;

Yhdistämislajittelu jakaa ongelman pienempiin ongelmiin ja etsii sitten pienempien ongelmien tulokset saadakseen alkuperäisen ongelman tuloksen (huomaa: tämän tyyppistä algoritmia kutsutaan jakaa ja hallitse). Jos et ymmärrä tätä algoritmia, älä huoli; En ymmärtänyt sitä ensimmäistä kertaa kun näin sen. Jos se voi auttaa sinua, näen tämän algoritmin kaksivaiheisena algoritmina:

• Jakovaihe, jossa taulukko jaetaan pienempiin matriisiin
• Lajitteluvaiheessa pienet taulukot yhdistetään (yhdistyksen avulla) suuremman taulukon muodostamiseksi.

Jakovaihe

Jakovaiheessa taulukko jaetaan yhtenäisiksi taulukoiksi 3 vaiheessa. Muodollinen askelmäärä on log(N) (koska N=8, log(N) = 3).

Mistä tiedän tämän?

Olen nero! Sanalla sanoen - matematiikka. Ajatuksena on, että jokainen askel jakaa alkuperäisen taulukon koon kahdella. Vaiheiden määrä on kuinka monta kertaa voit jakaa alkuperäisen taulukon kahteen osaan. Tämä on logaritmin tarkka määritelmä (kanta 2).

Lajitteluvaihe

Lajitteluvaiheessa aloitat yhtenäisillä (yksielementtisillä) taulukoilla. Kunkin vaiheen aikana käytät useita yhdistämistoimintoja ja kokonaiskustannukset ovat N = 8 operaatiota:

• Ensimmäisessä vaiheessa sinulla on 4 yhdistämistä, joista jokainen maksaa 2 operaatiota
• Toisessa vaiheessa sinulla on 2 yhdistämistä, joista kukin maksaa 4 operaatiota
• Kolmannessa vaiheessa sinulla on 1 yhdistäminen, joka maksaa 8 operaatiota

Koska on log(N) askelta, kokonaiskustannukset n * log(N)-operaatiot.

Yhdistelmälajittelun edut

Miksi tämä algoritmi on niin tehokas?

koska:

• Voit muuttaa sitä pienentääksesi muistin tilaa niin, että et luo uusia taulukoita, vaan muokkaat suoraan syöttötaulukkoa.

Huomautus: Tämän tyyppistä algoritmia kutsutaan in-paikka (lajittelu ilman lisämuistia).

• Voit muuttaa sen käyttämään levytilaa ja vähän muistia samanaikaisesti ilman merkittäviä levyn I/O-ylikustannuksia. Ajatuksena on ladata muistiin vain ne osat, joita parhaillaan käsitellään. Tämä on tärkeää, kun haluat lajitella usean gigatavun taulukon, jossa on vain 100 megatavun muistipuskuri.

Huomautus: Tämän tyyppistä algoritmia kutsutaan ulkoinen lajittelu.

• Voit muuttaa sen toimimaan useissa prosesseissa/säikeissä/palvelimissa.

Esimerkiksi hajautettu yhdistäminen on yksi avainkomponenteista Hadoop (joka on rakenne big datassa).

• Tämä algoritmi voi muuttaa lyijyn kullaksi (todellakin!).

Tätä lajittelualgoritmia käytetään useimmissa (jos ei kaikissa) tietokannoista, mutta se ei ole ainoa. Jos haluat tietää lisää, voit lukea tämän tutkimustyö, jossa käsitellään yleisten tietokantojen lajittelualgoritmien etuja ja haittoja.

Taulukko, puu ja tiivistetaulukko

Nyt kun ymmärrämme ajatuksen ajan monimutkaisuudesta ja lajittelusta, minun pitäisi kertoa teille kolmesta tietorakenteesta. Tämä on tärkeää, koska he ovat nykyaikaisten tietokantojen perusta. Esittelen myös konseptin tietokantahakemisto.

Массив

Kaksiulotteinen taulukko on yksinkertaisin tietorakenne. Taulukkoa voidaan pitää taulukona. Esimerkiksi:

Tämä 2-ulotteinen taulukko on taulukko, jossa on rivejä ja sarakkeita:

• Jokainen rivi edustaa kokonaisuutta
• Sarakkeet tallentavat entiteettiä kuvaavia ominaisuuksia.
• Jokainen sarake tallentaa tietyn tyyppisiä tietoja (kokonaisluku, merkkijono, päivämäärä...).

Tämä on kätevä tietojen tallentamiseen ja visualisointiin, mutta kun sinun on löydettävä tietty arvo, se ei sovellu.

Jos esimerkiksi haluat löytää kaikki Yhdistyneessä kuningaskunnassa työskentelevät kaverit, sinun on tarkasteltava jokaista riviä selvittääksesi, kuuluuko kyseinen rivi Isoon-Britanniaan. Se maksaa sinulle N tapahtumaaMissä N - rivien määrä, mikä ei ole huono, mutta voisiko olla nopeampaa tapaa? Nyt meidän on aika tutustua puihin.

Huomautus: Useimmat nykyaikaiset tietokannat tarjoavat laajennettuja taulukoita taulukoiden tehokkaaseen tallentamiseen: pino- ja indeksiorganisoidut taulukot. Mutta tämä ei muuta ongelmaa löytää nopeasti tietty ehto sarakeryhmästä.

Tietokantapuu ja hakemisto

Binäärihakupuu on binääripuu, jolla on erityinen ominaisuus. Jokaisen solmun avaimen on oltava:

• suurempi kuin kaikki vasempaan alipuuhun tallennetut avaimet
• vähemmän kuin kaikki oikeaan alipuuhun tallennetut avaimet

Katsotaanpa, mitä tämä tarkoittaa visuaalisesti

Ajatus

Tässä puussa on N = 15 elementtiä. Oletetaan, että etsin 208:

• Aloitan juuresta, jonka avain on 136. Koska 136<208, katson solmun 136 oikeaa alipuuta.
• 398>208 siksi katson solmun 398 vasenta alipuuta
• 250>208 siksi katson solmun 250 vasenta alipuuta
• 200<208, siksi katson solmun 200 oikeaa alipuuta. Mutta 200:lla ei ole oikeaa alipuuta, arvoa ei ole olemassa (koska jos se on olemassa, se on oikeassa alipuussa 200).

Oletetaan nyt, että etsin 40

• Aloitan juuresta, jonka avain on 136. Koska 136 > 40, katson solmun 136 vasenta alipuuta.
• 80 > 40, joten katson solmun 80 vasenta alipuuta
• 40 = 40, solmu on olemassa. Haen rivitunnuksen solmun sisältä (ei näy kuvassa) ja etsin taulukosta annettua rivitunnusta.
• Kun tiedän rivitunnuksen, tiedän tarkalleen, missä tiedot ovat taulukossa, joten voin hakea ne välittömästi.

Lopulta molemmat haut maksavat minulle puun sisällä olevien tasojen määrän. Jos luet osion yhdistämislajittelusta huolellisesti, sinun pitäisi nähdä, että siellä on log(N) tasoja. Osoittautuu, hakukustannusloki (N), ei paha!

Palataan ongelmaamme

Mutta tämä on hyvin abstraktia, joten palataanpa ongelmaamme. Kuvittele yksinkertaisen kokonaisluvun sijasta merkkijono, joka edustaa jonkun edellisen taulukon maata. Oletetaan, että sinulla on puu, joka sisältää taulukon "maa"-kentän (sarake 3):

• Jos haluat tietää, kuka työskentelee Isossa-Britanniassa
• katsot puuta saadaksesi solmun, joka edustaa Iso-Britanniaa
• "UKnode":sta löydät Yhdistyneen kuningaskunnan työntekijätietueiden sijainnit.

Tämä haku maksaa log(N)-operaatioita N operaation sijaan, jos käytät taulukkoa suoraan. Se mitä juuri esititte, oli tietokantahakemisto.

Voit rakentaa hakemistopuun mille tahansa kenttäryhmälle (merkkijono, numero, 2 riviä, numero ja merkkijono, päivämäärä...) kunhan sinulla on avaimien (eli kenttäryhmien) vertailutoiminto, jotta voit määrittää järjestys avainten kesken (tämä koskee kaikkia tietokannan perustyyppejä).

B+TreeIndex

Vaikka tämä puu toimii hyvin tietyn arvon saamiseksi, tarvitaan SUURI ongelma saada useita elementtejä kahden arvon väliin. Tämä maksaa O(N), koska joudut tarkastelemaan puun jokaista solmua ja tarkistamaan, onko se näiden kahden arvon välissä (esim. puun järjestetyn läpikäynnin yhteydessä). Lisäksi tämä toiminto ei ole levy-I/O-ystävällinen, koska sinun on luettava koko puu. Meidän on löydettävä tapa tehokkaaseen toteuttamiseen aluepyyntö. Tämän ongelman ratkaisemiseksi nykyaikaiset tietokannat käyttävät muokattua versiota aiemmasta puusta nimeltä B+Tree. B+Tree-puussa:

• vain alimmat solmut (lehdet) varastoinformaatio (rivien sijainti vastaavassa taulukossa)
• loput solmut ovat täällä reititystä varten oikeaan solmuun haun aikana.

Kuten näet, tässä on enemmän solmuja (kahdesti). Sinulla on todellakin lisäsolmuja, "päätössolmuja", jotka auttavat sinua löytämään oikean solmun (joka tallentaa rivien sijainnin liittyvään taulukkoon). Mutta haun monimutkaisuus on edelleen O(log(N)) (on vain yksi taso lisää). Suuri ero on siinä alemman tason solmut ovat yhteydessä seuraajiinsa.

Jos etsit arvoja väliltä 40 ja 100 tällä B+Treella:

• Sinun tarvitsee vain etsiä 40 (tai lähin arvo 40:n jälkeen, jos 40:tä ei ole olemassa), kuten teit edellisen puun kanssa.
• Kerää sitten 40 perillistä suorien perillisten linkkien avulla, kunnes saavutat 100.

Oletetaan, että löydät M seuraajaa ja puussa on N solmua. Tietyn solmun löytäminen maksaa log(N) kuten edellinen puu. Mutta kun saat tämän solmun, saat M-operaatioissa M seuraajaa viittauksilla heidän seuraajiinsa. Tämä haku maksaa vain M+log(N) operaatioita verrattuna edellisen puun N operaatioon. Lisäksi sinun ei tarvitse lukea koko puuta (vain M+log(N) solmua), mikä tarkoittaa vähemmän levyn käyttöä. Jos M on pieni (esim. 200 riviä) ja N on suuri (1 000 000 riviä), ero on SUURI.

Mutta tässä on (taas!) uusia ongelmia. Jos lisäät tai poistat rivin tietokantaan (ja siten siihen liittyvään B+Tree-hakemistoon):

• sinun on ylläpidettävä järjestystä B+Puun sisällä olevien solmujen välillä, muuten et löydä solmuja lajittelemattoman puun sisältä.
• sinun on pidettävä mahdollisimman pieni määrä tasoja B+Puussa, muuten O(log(N))-aikakompleksisuudesta tulee O(N).

Toisin sanoen B+Treen tulee olla itsejärjestyvä ja tasapainoinen. Onneksi tämä on mahdollista älykkäillä poisto- ja lisäystoiminnoilla. Mutta tämä maksaa: lisäykset ja poistot B+-puussa maksavat O(log(N)). Siksi jotkut teistä ovat kuulleet sen Liian monien indeksien käyttäminen ei ole hyvä idea. Todella, hidastat nopeaa rivin lisäämistä/päivitystä/poistamista taulukkoonkoska tietokannan on päivitettävä taulukon indeksit käyttämällä kallista O(log(N))-operaatiota jokaiselle indeksille. Lisäksi indeksien lisääminen lisää työtaakkaa tapahtuman johtaja (kuvataan artikkelin lopussa).

Lisätietoja on Wikipedian artikkelissa B+Puu. Jos haluat esimerkin B+Treen toteuttamisesta tietokannassa, katso Tässä artikkelissa и Tässä artikkelissa johtavalta MySQL-kehittäjältä. Molemmat keskittyvät siihen, kuinka InnoDB (MySQL-moottori) käsittelee indeksejä.

Huomautus: Eräs lukija kertoi minulle, että matalan tason optimointien vuoksi B+-puun pitäisi olla täysin tasapainossa.

Hashtable

Viimeinen tärkeä tietorakenne on hash-taulukko. Tämä on erittäin hyödyllistä, kun haluat nopeasti etsiä arvoja. Lisäksi hash-taulukon ymmärtäminen auttaa meitä myöhemmin ymmärtämään yleisen tietokantaliitosoperaation, jota kutsutaan hash-liitoksi ( hash liittyä). Tätä tietorakennetta tietokanta käyttää myös joidenkin sisäisten asioiden tallentamiseen (esim. lukittava pöytä tai puskuriallas, näemme nämä molemmat käsitteet myöhemmin).

Hash-taulukko on tietorakenne, joka löytää nopeasti elementin avaimensa perusteella. Hajautustaulukon luomiseksi sinun on määritettävä:

• ключ elementeillesi
• hash-toiminto avaimia varten. Lasketut avaimen tiivisteet antavat elementtien sijainnin (kutsutaan segmenttejä ).
• toiminto avainten vertailuun. Kun olet löytänyt oikean segmentin, sinun on löydettävä etsimäsi elementti segmentistä tämän vertailun avulla.

Yksinkertainen esimerkki

Otetaanpa selkeä esimerkki:

Tässä hash-taulukossa on 10 segmenttiä. Koska olen laiska, kuvasin vain 5 osaa, mutta tiedän, että olet älykäs, joten annan sinun kuvitella loput 5 itse. Käytin avaimen hash-funktiota modulo 10. Toisin sanoen tallennan vain elementin avaimen viimeisen numeron löytääkseni sen segmentin:

• jos viimeinen numero on 0, elementti osuu segmenttiin 0,
• jos viimeinen numero on 1, elementti osuu segmenttiin 1,
• jos viimeinen numero on 2, elementti osuu alueelle 2,
• ...

Käyttämäni vertailufunktio on yksinkertaisesti kahden kokonaisluvun välinen tasa-arvo.

Oletetaan, että haluat saada elementin 78:

• Hajautustaulukko laskee hash-koodin 78:lle, joka on 8.
• Hajautustaulukko tarkastelee segmenttiä 8, ja ensimmäinen sen löytämä elementti on 78.
• Hän palauttaa sinulle tuotteen 78
• Haku maksaa vain 2 operaatiota (yksi hajautusarvon laskemiseen ja toinen segmentin elementin etsimiseen).

Oletetaan nyt, että haluat saada elementin 59:

• Hajautustaulukko laskee hash-koodin 59:lle, joka on 9.
• Hajautustaulukko etsii segmentistä 9, ensimmäinen löydetty elementti on 99. Koska 99!=59, elementti 99 ei ole kelvollinen elementti.
• Samaa logiikkaa käyttäen otetaan toinen elementti (9), kolmas (79), ..., viimeinen (29).
• Elementtiä ei löydy.
• Haku maksoi 7 operaatiota.

Hyvä hash-toiminto

Kuten näet, kustannukset eivät ole samat etsimäsi arvosta riippuen!

Jos nyt muutan avaimen tiivistefunktiota modulo 1 000 000 (eli otan viimeiset 6 numeroa), toinen haku maksaa vain 1 toiminnon, koska segmentissä 000059 ei ole elementtejä. Todellinen haaste on löytää hyvä hash-funktio, joka luo kauhoja, jotka sisältävät hyvin pienen määrän elementtejä.

Esimerkissäni hyvän hash-funktion löytäminen on helppoa. Mutta tämä on yksinkertainen esimerkki, hyvän hash-funktion löytäminen on vaikeampaa, kun avain on:

• merkkijono (esimerkiksi - sukunimi)
• 2 riviä (esimerkiksi - sukunimi ja etunimi)
• 2 riviä ja päivämäärä (esimerkiksi - sukunimi, etunimi ja syntymäaika)
• ...

Hyvällä hash-toiminnolla hash-taulukon haut maksavat O(1).

Array vs hash -taulukko

Mikset käytä taulukkoa?

Hmm, hyvä kysymys.

• Hash-taulukko voi olla ladattu osittain muistiin, ja loput segmentit voivat jäädä levylle.
• Taulukon kanssa on käytettävä vierekkäistä tilaa muistissa. Jos lataat suurta pöytää on erittäin vaikea löytää tarpeeksi jatkuvaa tilaa.
• Hajautustaulukossa voit valita haluamasi avaimen (esimerkiksi maan ja henkilön sukunimen).

Saat lisätietoja lukemalla artikkelin aiheesta JaavaHashMap, joka on hash-taulukon tehokas toteutus; sinun ei tarvitse ymmärtää Javaa ymmärtääksesi tässä artikkelissa käsitellyt käsitteet.

Lähde: will.com