Haai Habr! Ek bied die vertaling van die artikel aan u aandag
"Hoe werk 'n relasionele databasis".

Wanneer dit kom by relasionele databasisse kan ek nie help om te dink iets skort nie. Hulle word oral gebruik. Daar is baie verskillende databasisse beskikbaar, van die klein en nuttige SQLite tot die kragtige Teradata. Maar daar is net 'n paar artikels wat verduidelik hoe die databasis werk. Jy kan vir jouself soek deur gebruik te maak van "howdoesarelationaldatabasework" om te sien hoe min resultate daar is. Boonop is hierdie artikels kort. As jy op soek is na die nuutste buzzy-tegnologieë (BigData, NoSQL of JavaScript), sal jy meer in-diepte artikels vind wat verduidelik hoe dit werk.

Is relasionele databasisse te oud en te vervelig om buite universiteitskursusse, navorsingsreferate en boeke verduidelik te word?

As 'n ontwikkelaar haat ek dit om iets te gebruik wat ek nie verstaan ​​nie. En as databasisse al meer as 40 jaar gebruik word, moet daar 'n rede wees. Oor die jare het ek honderde ure spandeer om hierdie vreemde swart bokse wat ek elke dag gebruik, werklik te verstaan. Relasionele databasisse baie interessant omdat hulle gebaseer op nuttige en herbruikbare konsepte. As jy belangstel om 'n databasis te verstaan, maar nog nooit die tyd of lus gehad het om in hierdie breë onderwerp te delf nie, moet jy hierdie artikel geniet.

Alhoewel die titel van hierdie artikel eksplisiet is, die doel van hierdie artikel is nie om te verstaan ​​hoe om die databasis te gebruik nie... Vandaar, jy behoort reeds te weet hoe om 'n eenvoudige verbindingsversoek en basiese navrae te skryf GRUIS; anders verstaan ​​jy dalk nie hierdie artikel nie. Dit is die enigste ding wat jy moet weet, ek sal die res verduidelik.

Ek sal begin met 'n paar rekenaarwetenskap basiese beginsels, soos tyd kompleksiteit van algoritmes (BigO). Ek weet sommige van julle haat hierdie konsep, maar daarsonder sal jy nie die ingewikkeldhede binne die databasis kan verstaan ​​nie. Aangesien dit 'n groot onderwerp is, Ek sal fokus op wat ek dink belangrik is: hoe die databasis verwerk SQL navraag. Ek sal net voorstel basiese databasiskonseptesodat u aan die einde van die artikel 'n idee het van wat onder die enjinkap aangaan.

Aangesien dit 'n lang en tegniese artikel is wat baie algoritmes en datastrukture behels, neem jou tyd om dit deur te lees. Sommige konsepte kan moeilik wees om te verstaan; jy kan hulle oorslaan en steeds die algemene idee kry.

Vir die meer kundiges onder julle, is hierdie artikel in 3 dele verdeel:

• Oorsig van laevlak- en hoëvlakdatabasiskomponente
• Oorsig van die navraagoptimeringsproses
• Oorsig van transaksie- en bufferpoelbestuur

Terug na die beginsels

Jare gelede (in 'n sterrestelsel ver, ver ...), moes ontwikkelaars presies weet hoeveel bewerkings hulle kodeer. Hulle het hul algoritmes en datastrukture uit hul kop geken, want hulle kon nie bekostig om die SVE en geheue van hul stadige rekenaars te mors nie.

In hierdie deel sal ek jou herinner aan sommige van hierdie konsepte aangesien dit noodsaaklik is om die databasis te verstaan. Ek sal ook die konsep bekendstel databasis indeks.

O(1) vs O(n2)

Deesdae gee baie ontwikkelaars nie om oor die tydskompleksiteit van algoritmes nie ... en hulle is reg!

Maar wanneer jy met baie data te doen het (ek praat nie van duisende nie) of as jy in millisekondes sukkel, word dit van kritieke belang om hierdie konsep te verstaan. En soos jy jou kan voorstel, moet databasisse beide situasies hanteer! Ek sal jou nie meer tyd laat spandeer as wat nodig is om die kern daarvan te verstaan ​​nie. Dit sal ons later help om die konsep van koste-gebaseerde optimalisering te verstaan ​​(kos gebaseer optimization).

konsep

Tydskompleksiteit van die algoritme gebruik om te sien hoe lank 'n algoritme sal neem om te voltooi vir 'n gegewe hoeveelheid data. Om hierdie kompleksiteit te beskryf, gebruik ons ​​groot O wiskundige notasie Hierdie notasie word gebruik met 'n funksie wat beskryf hoeveel bewerkings 'n algoritme benodig vir 'n gegewe aantal insette.

Byvoorbeeld, as ek sê "hierdie algoritme het kompleksiteit O(sommige_funksie())", beteken dit dat die algoritme some_function(a_certain_amount_of_data)-bewerkings vereis om 'n sekere hoeveelheid data te verwerk.

In hierdie geval, Dit is nie die hoeveelheid data wat saak maak**, andersins ** hoe die aantal bewerkings toeneem met toenemende datavolume. Tydkompleksiteit verskaf nie 'n presiese aantal bewerkings nie, maar is 'n goeie manier om uitvoeringstyd te skat.

In hierdie grafiek kan jy die aantal bewerkings sien teenoor die hoeveelheid insetdata vir verskillende tipes algoritme-tydkompleksiteite. Ek het 'n logaritmiese skaal gebruik om hulle te vertoon. Met ander woorde, die hoeveelheid data neem vinnig toe van 1 tot 1 miljard. Ons kan sien dat:

• O(1) of konstante kompleksiteit bly konstant (anders sou dit nie konstante kompleksiteit genoem word nie).
• O(teken(n)) bly laag selfs met miljarde data.
• Ergste moeilikheid - O(n2), waar die aantal bewerkings vinnig groei.
• Die ander twee komplikasies neem net so vinnig toe.

voorbeelde

Met 'n klein hoeveelheid data is die verskil tussen O(1) en O(n2) weglaatbaar. Byvoorbeeld, kom ons sê jy het 'n algoritme wat 2000 elemente moet verwerk.

• Die O(1)-algoritme sal jou 1 bewerking kos
• Die O(log(n))-algoritme sal jou 7 bewerkings kos
• Die O(n)-algoritme sal jou 2 000 bewerkings kos
• Die O(n*log(n))-algoritme sal jou 14 000 bewerkings kos
• Die O(n2)-algoritme sal jou 4 000 000 bewerkings kos

Die verskil tussen O(1) en O(n2) lyk groot (4 miljoen bewerkings), maar jy sal 'n maksimum van 2 ms verloor, net tyd om jou oë te knip. Inderdaad, moderne verwerkers kan verwerk honderde miljoene operasies per sekonde. Dit is hoekom werkverrigting en optimalisering nie 'n probleem in baie IT-projekte is nie.

Soos ek gesê het, is dit steeds belangrik om hierdie konsep te ken wanneer jy met groot hoeveelhede data werk. As die algoritme hierdie keer 1 000 000 elemente moet verwerk (wat nie soveel vir 'n databasis is nie):

• Die O(1)-algoritme sal jou 1 bewerking kos
• Die O(log(n))-algoritme sal jou 14 bewerkings kos
• Die O(n)-algoritme sal jou 1 000 000 bewerkings kos
• Die O(n*log(n))-algoritme sal jou 14 000 000 bewerkings kos
• Die O(n2)-algoritme sal jou 1 000 000 000 000 bewerkings kos

Ek het nie die wiskunde gedoen nie, maar ek sou sê met die O(n2)-algoritme het jy tyd om 'n koffie te drink (selfs twee!). As jy nog 0 by die datavolume voeg, sal jy tyd hê om 'n middagslapie te neem.

Kom ons gaan dieper

Vir jou inligting:

• 'n Goeie hash-tabelopsoek vind 'n element in O(1).
• Deur 'n goed gebalanseerde boom te soek, lewer resultate in O(log(n)).
• Deur 'n skikking te soek, lewer resultate in O(n).
• Die beste sorteeralgoritmes het kompleksiteit O(n*log(n)).
• 'n Slegte sorteeralgoritme het kompleksiteit O(n2).

Let wel: In die volgende dele sal ons hierdie algoritmes en datastrukture sien.

Daar is verskeie tipes algoritme tyd kompleksiteit:

• gemiddelde geval scenario
• beste geval scenario
• en die ergste scenario

Tydskompleksiteit is dikwels die ergste scenario.

Ek het net gepraat oor die tydskompleksiteit van die algoritme, maar kompleksiteit is ook van toepassing op:

• geheueverbruik van die algoritme
• skyf I/O verbruik algoritme

Natuurlik is daar komplikasies erger as n2, byvoorbeeld:

• n4: dit is verskriklik! Sommige van die genoemde algoritmes het hierdie kompleksiteit.
• 3n: dit is nog erger! Een van die algoritmes wat ons in die middel van hierdie artikel sal sien, het hierdie kompleksiteit (en dit word eintlik in baie databasisse gebruik).
• faktoriale n: jy sal nooit jou resultate kry nie, selfs met 'n klein hoeveelheid data.
• nn: As jy hierdie kompleksiteit teëkom, moet jy jouself afvra of dit werklik jou aktiwiteitsveld is...

Let wel: Ek het jou nie die werklike definisie van die groot O-benaming gegee nie, net 'n idee. Jy kan hierdie artikel lees by Wikipedia vir die werklike (asimptotiese) definisie.

MergeSort

Wat doen jy wanneer jy 'n versameling moet sorteer? Wat? Jy noem die sort()-funksie... Ok, goeie antwoord... Maar vir 'n databasis moet jy verstaan ​​hoe hierdie sort()-funksie werk.

Daar is verskeie goeie sorteeralgoritmes, so ek sal op die belangrikste fokus: sorteer saamvoeg. Jy sal dalk nie verstaan ​​hoekom sortering van data op die oomblik nuttig is nie, maar jy moet na die navraagoptimeringsgedeelte. Boonop sal die verstaan ​​van samesmeltingssoort ons later help om die algemene databasisaansluitbewerking genoem te verstaan saamsmelt sluit (samesmeltingsvereniging).

Voeg saam

Soos baie bruikbare algoritmes, maak samesmeltingssortering staat op 'n truuk: die kombinasie van 2 gesorteerde skikkings van grootte N/2 in 'n N-element gesorteerde skikking kos slegs N bewerkings. Hierdie operasie word samesmelting genoem.

Kom ons kyk wat dit beteken met 'n eenvoudige voorbeeld:

Hierdie figuur wys dat om die finale gesorteerde 8-element skikking te bou, jy net een keer oor die 2 4-element skikkings hoef te herhaal. Aangesien beide 4-element skikkings reeds gesorteer is:

• 1) jy vergelyk beide huidige elemente in twee skikkings (aan die begin stroom = eerste)
• 2) neem dan die kleinste een om dit in 'n 8 element skikking te plaas
• 3) en beweeg na die volgende element in die skikking waar jy die kleinste element geneem het
• en herhaal 1,2,3 totdat jy die laaste element van een van die skikkings bereik.
• Dan neem jy die oorblywende elemente van die ander skikking om hulle in 'n 8 element skikking te plaas.

Dit werk omdat beide 4-element skikkings gesorteer is en dus hoef jy nie terug te gaan in daardie skikkings nie.

Noudat ons die truuk verstaan, hier is my pseudokode vir samesmelting:

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;

Merge sort breek 'n probleem in kleiner probleme op en vind dan die resultate van die kleiner probleme om die resultaat van die oorspronklike probleem te kry (let wel: hierdie tipe algoritme word verdeel en herwin genoem). As jy nie hierdie algoritme verstaan ​​nie, moenie bekommerd wees nie; Ek het dit nie verstaan ​​toe ek dit die eerste keer gesien het nie. As dit jou kan help, sien ek hierdie algoritme as 'n twee-fase algoritme:

• Delingsfase, waar die skikking in kleiner skikkings verdeel word
• Die sorteerfase is waar klein skikkings gekombineer word (met behulp van vereniging) om 'n groter skikking te vorm.

Afdelingsfase

In die verdelingstadium word die skikking in 3 stappe in unitêre skikkings verdeel. Die formele aantal stappe is log(N) (aangesien N=8, log(N) = 3).

Hoe weet ek dit?

Ek is geniaal! In 'n woord - wiskunde. Die idee is dat elke stap die grootte van die oorspronklike skikking deur 2 deel. Die aantal stappe is die aantal kere wat jy die oorspronklike skikking in twee kan verdeel. Dit is die presiese definisie van 'n logaritme (basis 2).

Sorteer fase

In die sorteerfase begin jy met unitêre (enkel-element) skikkings. Tydens elke stap pas jy veelvuldige samesmeltingsbewerkings toe en die totale koste is N = 8 bewerkings:

• In die eerste fase het jy 4 samesmeltings wat elk 2 bewerkings kos
• In die tweede stap het jy 2 samesmeltings wat elk 4 bewerkings kos
• In die derde stap het jy 1 samesmelting wat 8 bewerkings kos

Aangesien daar log(N) stappe is, totale koste N * log(N) bewerkings.

Voordele van merge sort

Hoekom is hierdie algoritme so kragtig?

Omdat:

• Jy kan dit verander om die geheue-voetspoor te verklein sodat jy nie nuwe skikkings skep nie, maar die invoerskikking direk verander.

Let wel: hierdie tipe algoritme word genoem in-plek (sorteer sonder bykomende geheue).

• Jy kan dit verander om skyfspasie en 'n klein hoeveelheid geheue terselfdertyd te gebruik sonder om aansienlike skyf-I/O-bokoste aan te gaan. Die idee is om slegs die dele wat tans verwerk word, in die geheue te laai. Dit is belangrik wanneer jy 'n multi-gigagreep-tabel met slegs 'n 100-megagreep-geheuebuffer moet sorteer.

Let wel: hierdie tipe algoritme word genoem eksterne soort.

• U kan dit verander om op verskeie prosesse/drade/bedieners te loop.

Byvoorbeeld, verspreide samesmeltingssorteer is een van die sleutelkomponente Hadoop (wat 'n struktuur in groot data is).

• Hierdie algoritme kan lood in goud verander (regtig!).

Hierdie sorteeralgoritme word in die meeste (indien nie alle) databasisse gebruik, maar dit is nie die enigste nie. As jy meer wil weet, kan jy dit lees navorsingswerk, wat die voor- en nadele van algemene databasissorteringalgoritmes bespreek.

Skikking, Boom en Hash Tabel

Noudat ons die idee van tydskompleksiteit en sortering verstaan, moet ek jou vertel van 3 datastrukture. Dit is belangrik omdat hulle is die basis van moderne databasisse. Ek sal ook die konsep bekendstel databasis indeks.

Reeks

'n Tweedimensionele skikking is die eenvoudigste datastruktuur. 'n Tabel kan as 'n skikking beskou word. Byvoorbeeld:

Hierdie 2-dimensionele skikking is 'n tabel met rye en kolomme:

• Elke lyn verteenwoordig 'n entiteit
• Kolomme stoor eienskappe wat die entiteit beskryf.
• Elke kolom stoor data van 'n spesifieke tipe (heelgetal, string, datum...).

Dit is gerieflik vir die stoor en visualisering van data, maar wanneer jy 'n spesifieke waarde moet vind, is dit nie geskik nie.

Byvoorbeeld, as jy al die ouens wil vind wat in die VK werk, sal jy na elke ry moet kyk om te bepaal of daardie ry aan die VK behoort. Dit sal jou N transaksies kosWaar N - aantal lyne, wat nie sleg is nie, maar kan daar 'n vinniger manier wees? Nou is dit tyd dat ons met die bome kennis maak.

Let wel: Die meeste moderne databasisse bied uitgebreide skikkings vir die doeltreffende stoor van tabelle: hoop-georganiseerde tabelle en indeks-georganiseerde tabelle. Maar dit verander nie die probleem om vinnig 'n spesifieke toestand in 'n groep kolomme te vind nie.

Databasis boom en indeks

'n Binêre soekboom is 'n binêre boom met 'n spesiale eienskap, die sleutel by elke nodus moet wees:

• groter as al die sleutels wat in die linker subboom gestoor is
• minder as alle sleutels wat in die regte subboom gestoor is

Kom ons kyk wat dit visueel beteken

Idee

Hierdie boom het N = 15 elemente. Kom ons sê ek soek 208:

• Ek begin by die wortel waarvan die sleutel 136 is. Sedert 136<208 kyk ek na die regter subboom van nodus 136.
• 398>208 daarom kyk ek na die linker subboom van nodus 398
• 250>208 daarom kyk ek na die linker subboom van nodus 250
• 200<208, daarom kyk ek na die regte subboom van node 200. Maar 200 het geen regte subboom nie, waarde bestaan ​​nie (want as dit bestaan, sal dit in die regte subboom 200 wees).

Kom ons sê nou ek soek 40

• Ek begin by die wortel waarvan die sleutel 136 is. Sedert 136 > 40 kyk ek na die linker subboom van nodus 136.
• 80 > 40, daarom kyk ek na die linker subboom van node 80
• 40= 40, nodus bestaan. Ek haal die ry-ID binne-in die nodus (nie in die prentjie gewys nie) en soek in die tabel vir die gegewe ry-ID.
• Om die ry-ID te ken, laat my toe om presies te weet waar die data in die tabel is, sodat ek dit onmiddellik kan herwin.

Op die ou end sal albei soektogte my die aantal vlakke binne die boom kos. As jy die deel oor merge sort sorgvuldig lees, behoort jy te sien dat daar log(N) vlakke is. Dit blyk, soek kostelog(N), nie sleg nie!

Kom ons keer terug na ons probleem

Maar dit is baie abstrak, so kom ons keer terug na ons probleem. In plaas van 'n eenvoudige heelgetal, stel 'n string voor wat die land van iemand in die vorige tabel verteenwoordig. Kom ons sê jy het 'n boom wat die "land"-veld (kolom 3) van die tabel bevat:

• As jy wil weet wie werk in die Verenigde Koninkryk
• jy kyk na die boom om die nodus te kry wat Groot-Brittanje verteenwoordig
• binne "UKnode" sal jy die ligging van Britse werkerrekords vind.

Hierdie soektog sal log(N) bewerkings kos in plaas van N bewerkings as jy die skikking direk gebruik. Wat jy sopas aangebied het, was databasis indeks.

Jy kan 'n indeksboom bou vir enige groep velde (string, nommer, 2 reëls, nommer en string, datum...) solank jy 'n funksie het om sleutels (dws veldgroepe) te vergelyk sodat jy kan stel orde tussen die sleutels (wat die geval is vir enige basiese tipes in die databasis).

B+boom-indeks

Alhoewel hierdie boom goed werk om 'n spesifieke waarde te kry, is daar 'n GROOT probleem wanneer jy nodig het kry veelvuldige elemente tussen twee waardes. Dit sal O(N) kos, want jy sal na elke nodus in die boom moet kyk en kyk of dit tussen hierdie twee waardes is (bv. met 'n geordende deurkruising van die boom). Boonop is hierdie bewerking nie skyf I/O vriendelik nie, aangesien jy die hele boom moet lees. Ons moet 'n manier vind om doeltreffend uit te voer reeks versoek. Om hierdie probleem op te los, gebruik moderne databasisse 'n gewysigde weergawe van die vorige boom genaamd B+Tree. In 'n B+boomboom:

• slegs die laagste nodusse (blare) inligting stoor (ligging van rye in die verwante tabel)
• die res van die nodusse is hier vir roetering na die regte nodus tydens soektog.

Soos u kan sien, is daar meer nodusse hier (twee keer). Inderdaad, jy het bykomende nodusse, "besluitnodes", wat jou sal help om die korrekte nodus te vind (wat die ligging van die rye in die gepaardgaande tabel stoor). Maar die soekkompleksiteit is steeds O(log(N)) (daar is net nog een vlak). Die groot verskil is dit nodusse op die laer vlak is gekoppel aan hul opvolgers.

Met hierdie B+Tree, as jy waardes tussen 40 en 100 soek:

• Jy hoef net vir 40 te soek (of die naaste waarde na 40 as 40 nie bestaan ​​nie) soos jy met die vorige boom gedoen het.
• Versamel dan 40 erfgename deur direkte erfgename skakels te gebruik totdat jy 100 bereik.

Kom ons sê jy vind M opvolgers en die boom het N nodusse. Om 'n spesifieke nodus te vind kos log(N) soos die vorige boom. Maar sodra jy hierdie nodus kry, sal jy M-opvolgers in M-bedrywighede kry met verwysings na hul opvolgers. Hierdie soektog kos slegs M+log(N) bewerkings in vergelyking met N bewerkings op die vorige boom. Boonop hoef jy nie die volle boom te lees nie (slegs M+log(N) nodusse), wat minder skyfgebruik beteken. As M klein is (bv. 200 rye) en N groot is (1 000 000 rye), sal daar 'n GROOT verskil wees.

Maar hier is nuwe probleme (weer!). As jy 'n ry in die databasis byvoeg of uitvee (en dus in die geassosieerde B+Tree-indeks):

• jy moet orde tussen die nodusse binne 'n B+Tree handhaaf, anders sal jy nie die nodusse binne 'n ongesorteerde boom kan vind nie.
• jy moet die minimum moontlike aantal vlakke in B+Tree hou, anders word die O(log(N)) tydkompleksiteit O(N).

Met ander woorde, B+Tree moet selfordenend en gebalanseerd wees. Gelukkig is dit moontlik met slim verwydering en invoegbewerkings. Maar dit kom teen 'n prys: invoegings en skrappings in 'n B+-boom kos O(log(N)). Dis hoekom sommige van julle dit gehoor het om te veel indekse te gebruik is nie 'n goeie idee nie. Regtig, jy vertraag vinnige invoeging/opdatering/skrap van 'n ry in 'n tabelomdat die databasis die tabel se indekse moet opdateer deur 'n duur O(log(N))-bewerking vir elke indeks te gebruik. Boonop beteken die byvoeging van indekse meer werklas vir transaksiebestuurder (sal aan die einde van die artikel beskryf word).

Vir meer besonderhede, kan jy die Wikipedia-artikel sien oor B+Tree. As jy 'n voorbeeld wil hê van die implementering van B+Tree in 'n databasis, kyk gerus hierdie artikel и hierdie artikel van 'n toonaangewende MySQL-ontwikkelaar. Hulle fokus albei op hoe InnoDB (die MySQL-enjin) indekse hanteer.

Let wel: 'n Leser het vir my gesê dat, as gevolg van laevlak-optimalisasies, die B+-boom heeltemal gebalanseer moet wees.

Hashtable

Ons laaste belangrike datastruktuur is die hash-tabel. Dit is baie nuttig wanneer jy vinnig waardes wil opsoek. Verder, as ons 'n hash-tabel verstaan, sal dit ons later help om 'n algemene databasisverbindingsbewerking genaamd 'n hash-verbinding te verstaan ​​( hash aansluit). Hierdie datastruktuur word ook deur die databasis gebruik om sommige interne dinge te stoor (bv. slot tafel of buffer swembad, ons sal albei hierdie konsepte later sien).

'n Hash-tabel is 'n datastruktuur wat vinnig 'n element deur sy sleutel vind. Om 'n hash-tabel te bou, moet jy definieer:

• sleutel vir jou elemente
• hash funksie vir sleutels. Die berekende sleutelhase gee die ligging van die elemente (genoem segmente ).
• funksie om sleutels te vergelyk. Sodra jy die regte segment gevind het, moet jy die element waarna jy soek binne die segment vind deur hierdie vergelyking te gebruik.

Eenvoudige voorbeeld

Kom ons neem 'n duidelike voorbeeld:

Hierdie hash-tabel het 10 segmente. Omdat ek lui is, het ek net 5 segmente afgebeeld, maar ek weet jy is slim, so ek sal jou die ander 5 op jou eie laat afbeeld. Ek het 'n hash-funksie modulo 10 van die sleutel gebruik. Met ander woorde, ek stoor net die laaste syfer van die element se sleutel om sy segment te vind:

• as die laaste syfer 0 is, val die element in segment 0,
• as die laaste syfer 1 is, val die element in segment 1,
• as die laaste syfer 2 is, val die element in area 2,
• ...

Die vergelykingsfunksie wat ek gebruik het, is bloot gelykheid tussen twee heelgetalle.

Kom ons sê jy wil element 78 kry:

• Die hash-tabel bereken die hash-kode vir 78, wat 8 is.
• Die hash-tabel kyk na segment 8, en die eerste element wat dit vind, is 78.
• Sy gee item 78 aan jou terug
• Soektog kos slegs 2 operasies (een om die hash-waarde te bereken en die ander om die element binne die segment op te soek).

Kom ons sê nou jy wil element 59 kry:

• Die hash-tabel bereken die hash-kode vir 59, wat 9 is.
• Die hash-tabel soek in segment 9, die eerste element wat gevind is, is 99. Aangesien 99!=59 is element 99 nie 'n geldige element nie.
• Deur dieselfde logika te gebruik, word die tweede element (9), die derde (79), ..., die laaste (29) geneem.
• Element nie gevind nie.
• Die soektog het 7 operasies gekos.

Goeie hash-funksie

Soos u kan sien, afhangende van die waarde waarna u soek, is die koste nie dieselfde nie!

As ek nou die hash-funksie modulo 1 van die sleutel verander (dit wil sê, met die laaste 000 syfers), kos die tweede opsoek net 000 bewerking aangesien daar geen elemente in segment 6 is nie. Die werklike uitdaging is om 'n goeie hash-funksie te vind wat emmers sal skep wat 'n baie klein aantal elemente bevat.

In my voorbeeld is dit maklik om 'n goeie hash-funksie te vind. Maar dit is 'n eenvoudige voorbeeld, om 'n goeie hash-funksie te vind is moeiliker as die sleutel is:

• string (byvoorbeeld - van)
• 2 reëls (byvoorbeeld - van en voornaam)
• 2 reëls en datum (byvoorbeeld - van, voornaam en geboortedatum)
• ...

Met 'n goeie hash-funksie kos hash-tabel-opsoeke O(1).

Skikking vs hash tabel

Hoekom nie 'n skikking gebruik nie?

Hmm, goeie vraag.

• Die hash-tabel kan wees gedeeltelik in die geheue gelaai, en die oorblywende segmente kan op die skyf bly.
• Met 'n skikking moet jy aaneenlopende spasie in geheue gebruik. As jy 'n groot tafel laai dit is baie moeilik om genoeg aaneenlopende spasie te kry.
• Vir 'n hash-tabel kan jy die sleutel kies wat jy wil hê (byvoorbeeld land en persoon se van).

Vir meer inligting, kan jy die artikel oor lees JavaHashMap, wat 'n doeltreffende implementering van 'n hash-tabel is; jy hoef nie Java te verstaan ​​om die konsepte wat in hierdie artikel behandel word, te verstaan ​​nie.

Bron: will.com