Hallo, Habr! Ik presenteer onder uw aandacht een vertaling van het artikel
"Hoe werkt een relationele database".

Als het om relationele databases gaat, kan ik niet anders dan denken dat er iets ontbreekt. Ze worden overal gebruikt. Er zijn veel verschillende databases beschikbaar, van het kleine en handige SQLite tot het krachtige Teradata. Maar er zijn slechts een paar artikelen die uitleggen hoe de database werkt. U kunt zelf zoeken met "howdoesarelationaldatabasework" om te zien hoe weinig resultaten er zijn. Bovendien zijn deze artikelen kort. Als u op zoek bent naar de nieuwste buzzy-technologieën (BigData, NoSQL of JavaScript), vindt u meer diepgaande artikelen waarin wordt uitgelegd hoe ze werken.

Zijn relationele databases te oud en te saai om buiten universitaire cursussen, onderzoekspapers en boeken te worden uitgelegd?

Als ontwikkelaar haat ik het om iets te gebruiken dat ik niet begrijp. En als databases al meer dan veertig jaar worden gebruikt, moet daar een reden voor zijn. Door de jaren heen heb ik honderden uren besteed aan het echt begrijpen van deze vreemde zwarte dozen die ik elke dag gebruik. relationele databases erg interessant omdat ze gebaseerd op bruikbare en herbruikbare concepten. Als je geïnteresseerd bent in het begrijpen van een database, maar nooit de tijd of de neiging hebt gehad om je in dit brede onderwerp te verdiepen, dan zul je dit artikel leuk vinden.

Hoewel de titel van dit artikel expliciet is, Het doel van dit artikel is niet om te begrijpen hoe u de database moet gebruiken. Vandaar, u zou al moeten weten hoe u een eenvoudig verbindingsverzoek en basisquery's schrijft WREED; anders begrijpt u dit artikel mogelijk niet. Dat is het enige wat je moet weten, de rest leg ik uit.

Ik zal beginnen met enkele basisbeginselen van de computerwetenschappen, zoals de tijdscomplexiteit van algoritmen (BigO). Ik weet dat sommigen van jullie dit concept haten, maar zonder dit concept zul je de fijne kneepjes van de database niet kunnen begrijpen. Omdat dit een groot onderwerp is, Ik zal me concentreren op wat ik belangrijk vind: hoe de database verwerkt SQL navraag. Ik zal het even voorstellen basisdatabaseconceptenzodat je aan het eind van het artikel een idee hebt van wat er zich onder de motorkap afspeelt.

Aangezien dit een lang en technisch artikel is waarbij veel algoritmen en datastructuren betrokken zijn, neem je de tijd om het door te lezen. Sommige concepten kunnen moeilijk te begrijpen zijn; je kunt ze overslaan en toch het algemene idee krijgen.

Voor de meer deskundige onder jullie is dit artikel verdeeld in 3 delen:

• Overzicht van databasecomponenten op laag en hoog niveau
• Overzicht van het query-optimalisatieproces
• Overzicht van transactie- en bufferpoolbeheer

Terug naar de basis

Jaren geleden (in een sterrenstelsel ver, ver weg...) moesten ontwikkelaars precies weten hoeveel bewerkingen ze codeerden. Ze kenden hun algoritmen en datastructuren uit hun hoofd, omdat ze het zich niet konden veroorloven de CPU en het geheugen van hun trage computers te verspillen.

In dit deel zal ik u aan enkele van deze concepten herinneren, omdat ze essentieel zijn voor het begrijpen van de database. Ik zal het concept ook introduceren database-index.

O(1) versus O(n2)

Tegenwoordig geven veel ontwikkelaars niets om de tijdscomplexiteit van algoritmen... en ze hebben gelijk!

Maar als je te maken hebt met veel data (ik heb het niet over duizenden) of als je met milliseconden worstelt, wordt het van cruciaal belang om dit concept te begrijpen. En zoals u zich kunt voorstellen, hebben databases met beide situaties te maken! Ik zal u niet meer tijd laten besteden dan nodig is om het punt duidelijk te maken. Dit zal ons later helpen het concept van op kosten gebaseerde optimalisatie te begrijpen (kosten gebaseerde optimalisatie).

Concept

Tijdcomplexiteit van het algoritme gebruikt om te zien hoe lang het duurt voordat een algoritme is voltooid voor een bepaalde hoeveelheid gegevens. Om deze complexiteit te beschrijven, gebruiken we de wiskundige notatie grote O. Deze notatie wordt gebruikt met een functie die beschrijft hoeveel bewerkingen een algoritme nodig heeft voor een bepaald aantal invoer.

Als ik bijvoorbeeld zeg: "dit algoritme heeft complexiteit O(een_functie())", betekent dit dat het algoritme een_functie(een_bepaalde_hoeveelheid_gegevens) bewerkingen nodig heeft om een ​​bepaalde hoeveelheid gegevens te verwerken.

In dit geval Het gaat niet om de hoeveelheid gegevens**, anders ** hoe het aantal bewerkingen toeneemt naarmate het datavolume toeneemt. Tijdcomplexiteit levert geen exact aantal bewerkingen op, maar is een goede manier om de uitvoeringstijd te schatten.

In deze grafiek ziet u het aantal bewerkingen versus de hoeveelheid invoergegevens voor verschillende typen tijdcomplexiteiten van algoritmen. Ik heb een logaritmische schaal gebruikt om ze weer te geven. Met andere woorden: de hoeveelheid data neemt snel toe van 1 naar 1 miljard. We zien dat:

• O(1) of constante complexiteit blijft constant (anders zou het geen constante complexiteit worden genoemd).
• O(inloggen(n)) blijft laag, zelfs met miljarden data.
• Grootste moeilijkheid - O(n2), waarbij het aantal operaties snel groeit.
• De andere twee complicaties nemen net zo snel toe.

Примеры

Met een kleine hoeveelheid gegevens is het verschil tussen O(1) en O(n2) verwaarloosbaar. Stel dat u een algoritme heeft dat 2000 elementen moet verwerken.

• Het O(1)-algoritme kost u 1 bewerking
• Het O(log(n))-algoritme kost u 7 bewerkingen
• Het O(n)-algoritme kost u 2 bewerkingen
• Het O(n*log(n))-algoritme kost u 14 bewerkingen
• Het O(n2)-algoritme kost u 4 bewerkingen

Het verschil tussen O(1) en O(n2) lijkt groot (4 miljoen bewerkingen), maar je verliest maximaal 2 ms, net tijd om met je ogen te knipperen. Moderne processors kunnen inderdaad verwerken honderden miljoenen bewerkingen per seconde. Daarom zijn prestaties en optimalisatie bij veel IT-projecten geen issue.

Zoals ik al zei, is het nog steeds belangrijk om dit concept te kennen als je met grote hoeveelheden gegevens werkt. Als het algoritme deze keer 1 elementen moet verwerken (wat niet zoveel is voor een database):

• Het O(1)-algoritme kost u 1 bewerking
• Het O(log(n))-algoritme kost u 14 bewerkingen
• Het O(n)-algoritme kost u 1 bewerkingen
• Het O(n*log(n))-algoritme kost u 14 bewerkingen
• Het O(n2)-algoritme kost u 1 bewerkingen

Ik heb de wiskunde niet gedaan, maar ik zou zeggen dat je met het O(n2)-algoritme tijd hebt om een ​​kopje koffie te drinken (zelfs twee!). Als u nog eens 0 toevoegt aan het datavolume, heeft u tijd om een ​​dutje te doen.

Laten we dieper gaan

Voor uw informatie:

• Een goede hashtabelzoekopdracht vindt een element in O(1).
• Het doorzoeken van een goed uitgebalanceerde boom levert resultaten op in O(log(n)).
• Het doorzoeken van een array levert resultaten op in O(n).
• De beste sorteeralgoritmen hebben complexiteit O(n*log(n)).
• Een slecht sorteeralgoritme heeft complexiteit O(n2).

Opmerking: in de volgende delen zullen we deze algoritmen en datastructuren zien.

Er zijn verschillende soorten algoritme-tijdcomplexiteit:

• gemiddeld gevalscenario
• in het gunstigste geval
• en worstcasescenario

Tijdcomplexiteit is vaak het slechtste scenario.

Ik had het alleen over de tijdscomplexiteit van het algoritme, maar complexiteit geldt ook voor:

• geheugengebruik van het algoritme
• algoritme voor schijf-I/O-verbruik

Natuurlijk zijn er complicaties die erger zijn dan n2, bijvoorbeeld:

• n4: dit is verschrikkelijk! Sommige van de genoemde algoritmen hebben deze complexiteit.
• 3n: dit is nog erger! Een van de algoritmen die we in het midden van dit artikel zullen zien, heeft deze complexiteit (en wordt feitelijk in veel databases gebruikt).
• faculteit n: u zult nooit uw resultaten krijgen, zelfs niet met een kleine hoeveelheid gegevens.
• nn: Als je deze complexiteit tegenkomt, moet je jezelf afvragen of dit echt jouw werkterrein is...

Opmerking: ik heb je niet de daadwerkelijke definitie van de grote O-aanduiding gegeven, het is slechts een idee. Dit artikel kun je lezen op Wikipedia voor de echte (asymptotische) definitie.

SamenvoegenSorteren

Wat doe je als je een collectie moet sorteren? Wat? Je roept de functie sort() aan... Oké, goed antwoord... Maar voor een database moet je begrijpen hoe deze functie sort() werkt.

Er zijn verschillende goede sorteeralgoritmen, dus ik zal me concentreren op de belangrijkste: samenvoegen sorteren. U begrijpt misschien niet waarom het sorteren van gegevens op dit moment nuttig is, maar dat zou u wel moeten doen na het gedeelte voor het optimaliseren van de zoekopdrachten. Bovendien zal het begrijpen van merge sort ons later helpen de gemeenschappelijke operatie voor het samenvoegen van databases te begrijpen samensmelten mee (fusievereniging).

Samenvoegen

Zoals veel nuttige algoritmen berust het samenvoegen en sorteren op een truc: het combineren van twee gesorteerde arrays van grootte N/2 tot een gesorteerde array met N-elementen kost slechts N bewerkingen. Deze bewerking wordt samenvoegen genoemd.

Laten we eens kijken wat dit betekent met een eenvoudig voorbeeld:

Deze afbeelding laat zien dat u, om de uiteindelijk gesorteerde array met 8 elementen te bouwen, slechts één keer over de twee arrays met 2 elementen hoeft te itereren. Omdat beide arrays met 4 elementen al zijn gesorteerd:

• 1) je vergelijkt beide huidige elementen in twee arrays (aan het begin actueel = eerst)
• 2) Neem vervolgens de kleinste om deze in een array van 8 elementen te plaatsen
• 3) en ga naar het volgende element in de array waar je het kleinste element hebt genomen
• en herhaal 1,2,3 totdat je het laatste element van een van de arrays bereikt.
• Vervolgens neem je de resterende elementen van de andere array om ze in een array van 8 elementen te plaatsen.

Dit werkt omdat beide arrays met vier elementen zijn gesorteerd en u dus niet "terug" hoeft te gaan in die arrays.

Nu we de truc begrijpen, is hier mijn pseudocode voor samenvoegen:

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 verdeelt een probleem in kleinere problemen en vindt vervolgens de resultaten van de kleinere problemen om het resultaat van het oorspronkelijke probleem te krijgen (let op: dit type algoritme wordt verdeel en heers genoemd). Als u dit algoritme niet begrijpt, hoeft u zich geen zorgen te maken; De eerste keer dat ik het zag, begreep ik het niet. Als het je kan helpen, zie ik dit algoritme als een tweefasig algoritme:

• Divisiefase, waarbij de array in kleinere arrays wordt verdeeld
• In de sorteerfase worden kleine arrays gecombineerd (met behulp van unie) om een ​​grotere array te vormen.

Divisie fase

In de delingsfase wordt de array in 3 stappen in unitaire arrays verdeeld. Het formele aantal stappen is log(N) (aangezien N=8, log(N) = 3).

Hoe weet ik dit?

Ik ben geniaal! In één woord: wiskunde. Het idee is dat elke stap de grootte van de originele array door 2 deelt. Het aantal stappen is het aantal keren dat je de originele array in tweeën kunt delen. Dit is de exacte definitie van een logaritme (basis 2).

Sorteerfase

In de sorteerfase begin je met unitaire arrays (enkele elementen). Tijdens elke stap past u meerdere samenvoegbewerkingen toe en de totale kosten bedragen N = 8 bewerkingen:

• In de eerste fase heb je 4 samenvoegingen die elk 2 bewerkingen kosten
• In de tweede stap heb je 2 samenvoegingen die elk 4 bewerkingen kosten
• In de derde stap heb je 1 samenvoeging die 8 bewerkingen kost

Omdat er log(N) stappen zijn, totale kosten N * log(N)-bewerkingen.

Voordelen van samenvoegen sorteren

Waarom is dit algoritme zo krachtig?

Omdat:

• U kunt dit wijzigen om de geheugenvoetafdruk te verkleinen, zodat u geen nieuwe arrays maakt, maar de invoerarray rechtstreeks wijzigt.

Let op: dit type algoritme wordt genoemd in-plaats (sorteren zonder extra geheugen).

• U kunt dit wijzigen om tegelijkertijd schijfruimte en een kleine hoeveelheid geheugen te gebruiken zonder dat er aanzienlijke schijf-I/O-overhead ontstaat. Het idee is om alleen die delen in het geheugen te laden die momenteel worden verwerkt. Dit is belangrijk als u een tabel van meerdere gigabytes moet sorteren met slechts een geheugenbuffer van 100 megabyte.

Let op: dit type algoritme wordt genoemd externe sortering.

• U kunt het wijzigen zodat het op meerdere processen/threads/servers kan worden uitgevoerd.

Gedistribueerde samenvoegsortering is bijvoorbeeld een van de belangrijkste componenten Hadoop (wat een structuur is in big data).

• Dit algoritme kan lood in goud veranderen (echt waar!).

Dit sorteeralgoritme wordt in de meeste (zo niet alle) databases gebruikt, maar het is niet de enige. Als je meer wilt weten, kun je dit lezen onderzoekswerk, waarin de voor- en nadelen van algemene algoritmen voor het sorteren van databases worden besproken.

Array-, boom- en hashtabel

Nu we het idee van tijdscomplexiteit en -sortering begrijpen, zou ik je over 3 datastructuren moeten vertellen. Dit is belangrijk omdat zij vormen de basis van moderne databases. Ik zal het concept ook introduceren database-index.

rangschikking

Een tweedimensionale array is de eenvoudigste datastructuur. Een tabel kan worden gezien als een array. Bijvoorbeeld:

Deze tweedimensionale array is een tabel met rijen en kolommen:

• Elke lijn vertegenwoordigt een entiteit
• Kolommen slaan eigenschappen op die de entiteit beschrijven.
• In elke kolom worden gegevens van een specifiek type opgeslagen (geheel getal, tekenreeks, datum...).

Dit is handig voor het opslaan en visualiseren van gegevens, maar als u een specifieke waarde moet vinden, is dit niet geschikt.

Als je bijvoorbeeld alle jongens wilt vinden die in Groot-Brittannië werken, moet je naar elke rij kijken om te bepalen of die rij tot Groot-Brittannië behoort. Het kost u N transactiesWaar N - aantal regels, wat niet slecht is, maar kan het sneller? Nu is het tijd om kennis te maken met de bomen.

Opmerking: De meeste moderne databases bieden uitgebreide arrays voor het efficiënt opslaan van tabellen: heap-georganiseerde tabellen en index-georganiseerde tabellen. Maar dit verandert niets aan het probleem van het snel vinden van een specifieke voorwaarde in een groep kolommen.

Databaseboom en index

Een binaire zoekboom is een binaire boom met een speciale eigenschap; de sleutel op elk knooppunt moet zijn:

• groter dan alle sleutels die in de linker subboom zijn opgeslagen
• minder dan alle sleutels die in de rechter subboom zijn opgeslagen

Laten we eens kijken wat dit visueel betekent

Idee

Deze boom heeft N = 15 elementen. Laten we zeggen dat ik op zoek ben naar 208:

• Ik begin bij de wortel waarvan de sleutel 136 is. Omdat 136<208, kijk ik naar de rechter subboom van knooppunt 136.
• 398>208 Daarom kijk ik naar de linker subboom van knooppunt 398
• 250>208 Daarom kijk ik naar de linker subboom van knooppunt 250
• 200<208, daarom kijk ik naar de rechter deelboom van knooppunt 200. Maar 200 heeft geen juiste deelboom, waarde bestaat niet (want als het bestaat, zal het in de rechter subboom 200 staan).

Laten we zeggen dat ik op zoek ben naar 40

• Ik begin bij de wortel waarvan de sleutel 136 is. Omdat 136 > 40, kijk ik naar de linker subboom van knooppunt 136.
• 80 > 40, daarom kijk ik naar de linker subboom van knooppunt 80
• 40= 40, knooppunt bestaat. Ik haal de rij-ID binnen het knooppunt op (niet weergegeven in de afbeelding) en zoek in de tabel naar de opgegeven rij-ID.
• Als ik de rij-ID ken, weet ik precies waar de gegevens zich in de tabel bevinden, zodat ik deze onmiddellijk kan ophalen.

Uiteindelijk zullen beide zoekopdrachten mij het aantal niveaus in de boom kosten. Als je het gedeelte over samenvoegen en sorteren zorgvuldig leest, zou je moeten zien dat er log(N)-niveaus zijn. Het blijkt, zoekkostenlogboek(N), niet slecht!

Laten we terugkeren naar ons probleem

Maar dit is heel abstract, dus laten we teruggaan naar ons probleem. Stel je in plaats van een eenvoudig geheel getal een string voor die het land van iemand in de vorige tabel vertegenwoordigt. Stel dat u een boomstructuur heeft die het veld 'land' (kolom 3) van de tabel bevat:

• Als je wilt weten wie er in Groot-Brittannië werkt
• je kijkt naar de boom om het knooppunt te vinden dat Groot-Brittannië vertegenwoordigt
• binnen "UKnode" vindt u de locatie van Britse werknemersrecords.

Deze zoekopdracht kost log(N)-bewerkingen in plaats van N-bewerkingen als u de array rechtstreeks gebruikt. Wat je net presenteerde was database-index.

U kunt een indexboom bouwen voor elke groep velden (tekenreeks, getal, 2 regels, getal en tekenreeks, datum...) zolang u maar een functie hebt om sleutels te vergelijken (dat wil zeggen veldgroepen), zodat u orde onder de sleutels (wat het geval is voor alle basistypen in de database).

B+BoomIndex

Hoewel deze boom goed werkt om een ​​specifieke waarde te verkrijgen, is er een GROOT probleem als je dat nodig hebt krijg meerdere elementen tussen twee waarden. Dit kost O(N), omdat je naar elk knooppunt in de boom moet kijken en moet controleren of deze tussen deze twee waarden ligt (bijvoorbeeld bij een geordende verplaatsing van de boom). Bovendien is deze bewerking niet schijf-I/O-vriendelijk, aangezien u de hele boomstructuur moet lezen. We moeten een manier vinden om dit efficiënt uit te voeren bereik verzoek. Om dit probleem op te lossen, gebruiken moderne databases een aangepaste versie van de vorige boom genaamd B+Tree. In een B+Tree-boom:

• alleen de laagste knooppunten (bladeren) informatie opslaan (locatie van rijen in de gerelateerde tabel)
• de rest van de knooppunten zijn hier voor routering naar het juiste knooppunt tijdens het zoeken.

Zoals je kunt zien, zijn er hier meer knooppunten (twee keer). Je hebt inderdaad extra knooppunten, "beslissingsknooppunten", die je zullen helpen het juiste knooppunt te vinden (waarin de locatie van de rijen in de bijbehorende tabel wordt opgeslagen). Maar de zoekcomplexiteit is nog steeds O(log(N)) (er is nog maar één niveau). Het grote verschil is dat knooppunten op het lagere niveau zijn verbonden met hun opvolgers.

Met deze B+Tree, als je waarden zoekt tussen 40 en 100:

• Je hoeft alleen maar te zoeken naar 40 (of de dichtstbijzijnde waarde na 40 als 40 niet bestaat) zoals je deed met de vorige boom.
• Verzamel vervolgens 40 erfgenamen met behulp van directe erfgenamenlinks totdat je 100 hebt bereikt.

Laten we zeggen dat je M opvolgers vindt en dat de boom N knooppunten heeft. Het vinden van een specifiek knooppunt kost log(N), net als de vorige boom. Maar zodra je dit knooppunt krijgt, krijg je M opvolgers in M-bewerkingen met verwijzingen naar hun opvolgers. Deze zoekopdracht kost slechts M+log(N) bewerkingen vergeleken met N bewerkingen in de vorige boom. Bovendien hoeft u niet de volledige boomstructuur te lezen (alleen M+log(N)-nodes), wat minder schijfgebruik betekent. Als M klein is (bijvoorbeeld 200 rijen) en N groot is (1 rijen), zal er een GROOT verschil zijn.

Maar er zijn hier (alweer!) nieuwe problemen. Als u een rij toevoegt of verwijdert in de database (en dus in de bijbehorende B+Tree-index):

• je moet de orde handhaven tussen de knooppunten in een B+Boom, anders kun je de knooppunten in een ongesorteerde boom niet vinden.
• je moet het minimaal mogelijke aantal niveaus in B+Tree behouden, anders wordt de tijdcomplexiteit O(log(N)) O(N).

Met andere woorden: B+Tree moet zelfordend en evenwichtig zijn. Gelukkig is dit mogelijk met slimme verwijder- en invoegbewerkingen. Maar dit brengt kosten met zich mee: invoegingen en verwijderingen in een B+ boom kosten O(log(N)). Daarom hebben sommigen van jullie dat gehoord het gebruik van te veel indexen is geen goed idee. Echt, u vertraagt ​​het snel invoegen/bijwerken/verwijderen van een rij in een tabelomdat de database de indexen van de tabel moet bijwerken met behulp van een dure O(log(N))-bewerking voor elke index. Bovendien betekent het toevoegen van indexen meer werklast voor transactiebeheerder (wordt aan het einde van het artikel beschreven).

Voor meer details kunt u het Wikipedia-artikel raadplegen op B+Boom. Als je een voorbeeld wilt van de implementatie van B+Tree in een database, kijk dan eens dit artikel и dit artikel van een toonaangevende MySQL-ontwikkelaar. Ze richten zich allebei op hoe InnoDB (de MySQL-engine) omgaat met indexen.

Opmerking: een lezer vertelde me dat, vanwege optimalisaties op laag niveau, de B+ boom volledig in balans zou moeten zijn.

Hashtabel

Onze laatste belangrijke datastructuur is de hashtabel. Dit is erg handig als u snel waarden wilt opzoeken. Bovendien zal het begrijpen van een hashtabel ons later helpen een algemene database-join-operatie te begrijpen, een zogenaamde hash-join ( hasj meedoen). Deze datastructuur wordt ook door de database gebruikt om enkele interne zaken op te slaan (bijv. tafel vergrendelen of bufferpool(we zullen beide concepten later zien).

Een hashtabel is een datastructuur die snel een element vindt op basis van zijn sleutel. Om een ​​hashtabel te bouwen, moet u het volgende definiëren:

• ключ voor uw elementen
• hash-functie voor sleutels. De berekende sleutel-hashes geven de locatie van de elementen (genaamd segmenten ).
• functie voor het vergelijken van sleutels. Zodra u het juiste segment heeft gevonden, moet u met behulp van deze vergelijking het element vinden dat u zoekt binnen het segment.

eenvoudig voorbeeld

Laten we een duidelijk voorbeeld nemen:

Deze hashtabel heeft 10 segmenten. Omdat ik lui ben, heb ik maar vijf segmenten in beeld gebracht, maar ik weet dat je slim bent, dus laat ik je de andere vijf zelf in beeld brengen. Ik heb een hashfunctie modulo 5 van de sleutel gebruikt. Met andere woorden, ik sla alleen het laatste cijfer van de sleutel van het element op om het segment ervan te vinden:

• als het laatste cijfer 0 is, valt het element in segment 0,
• als het laatste cijfer 1 is, valt het element in segment 1,
• als het laatste cijfer 2 is, valt het element in gebied 2,
• ...

De vergelijkingsfunctie die ik heb gebruikt, is eenvoudigweg de gelijkheid tussen twee gehele getallen.

Stel dat u element 78 wilt verkrijgen:

• De hashtabel berekent de hashcode voor 78, namelijk 8.
• De hashtabel kijkt naar segment 8 en het eerste element dat wordt gevonden is 78.
• Ze stuurt item 78 naar u terug
• Zoeken kost slechts 2 handelingen (één om de hashwaarde te berekenen en de andere om het element binnen het segment op te zoeken).

Laten we nu zeggen dat je element 59 wilt krijgen:

• De hashtabel berekent de hashcode voor 59, namelijk 9.
• De hashtabel zoekt in segment 9, het eerste gevonden element is 99. Omdat 99!=59 is element 99 geen geldig element.
• Met dezelfde logica worden het tweede element (9), het derde (79), ... en het laatste (29) genomen.
• Element niet gevonden.
• De zoektocht kostte 7 operaties.

Goede hashfunctie

Zoals u kunt zien, zijn de kosten, afhankelijk van de waarde die u zoekt, niet hetzelfde!

Als ik nu de hashfunctie modulo 1 van de sleutel verander (dat wil zeggen, door de laatste 000 cijfers te nemen), kost de tweede zoekopdracht slechts 000 bewerking omdat er geen elementen in segment 6 zitten. De echte uitdaging is het vinden van een goede hashfunctie die buckets creëert die een heel klein aantal elementen bevatten.

In mijn voorbeeld is het vinden van een goede hashfunctie eenvoudig. Maar dit is een eenvoudig voorbeeld: het vinden van een goede hashfunctie is moeilijker als de sleutel is:

• tekenreeks (bijvoorbeeld - achternaam)
• 2 regels (bijvoorbeeld - achternaam en voornaam)
• 2 regels en datum (bijvoorbeeld - achternaam, voornaam en geboortedatum)
• ...

Met een goede hashfunctie kost het opzoeken van hashtabellen O(1).

Array versus hashtabel

Waarom gebruik je geen array?

Hm, goede vraag.

• De hashtabel kan dat zijn gedeeltelijk in het geheugen geladen, en de overige segmenten kunnen op de schijf blijven staan.
• Bij een array moet u aaneengesloten ruimte in het geheugen gebruiken. Als u een grote tafel laadt het is erg moeilijk om voldoende doorlopende ruimte te vinden.
• Voor een hashtabel kunt u de gewenste sleutel selecteren (bijvoorbeeld het land en de achternaam van de persoon).

Voor meer informatie kunt u het artikel lezen over JavaHash kaart, wat een efficiënte implementatie is van een hashtabel; u hoeft Java niet te begrijpen om de concepten die in dit artikel worden behandeld te begrijpen.

Bron: www.habr.com