Hei, Habr! Jeg presenterer for deg oversettelsen av artikkelen
.
NÄr det gjelder relasjonelle databaser, kan jeg ikke la vÊre Ä tenke at noe mangler. De brukes overalt. Det finnes mange forskjellige databaser: fra den lille og nyttige SQLite til den kraftige Teradata. Men det finnes bare noen fÄ artikler som forklarer hvordan en database fungerer. Du kan sÞke selv med forespÞrselen "howdoesarelationaldatabasework" for Ä se hvor fÄ resultater det er. Dessuten er disse artiklene korte. Hvis du derimot leter etter de siste mote-teknologiene (BigData, NoSQL eller JavaScript), vil du finne flere dybdeartikler som forklarer hvordan de fungerer.
Er relasjonelle databaser for gamle og kjedelige til Ă„ forklare utenfor universitetets kurs, forskningsarbeid og bĂžker?

Som utvikler hater jeg Ä bruke det jeg ikke forstÄr. Og hvis databaser har vÊrt i bruk i over 40 Är, mÄ det vÊre en grunn. I lÞpet av disse Ärene har jeg brukt hundrevis av timer pÄ Ä virkelig forstÄ disse merkelige svarte boksene jeg bruker hver dag. Relasjonsdatabaser svÊrt interessante, fordi de er basert pÄ nyttige og gjenbrukbare konsepter.Hvis du er interessert i Ä forstÄ databaser, men aldri har hatt tid eller lyst til Ä grave deg inn i dette omfattende temaet, vil du like denne artikkelen.
Selv om tittelen pÄ denne artikkelen er Äpenbar, er mÄlet med denne artikkelen ikke Ä forstÄ hvordan man bruker en database.FÞlgende, bÞr du allerede vite hvordan man skriver en enkel sammenkobling og grunnleggende spÞrringer, CRUD; ellers vil du kanskje ikke forstÄ denne artikkelen. Dette er det eneste du trenger Ä vite, jeg vil forklare alt annet.
Jeg begynner med noen grunnleggende konsepter innen datavitenskap, som tidskompleksitet av algoritmer (BigO). Jeg vet at noen av dere hater dette konseptet, men uten det vil du ikke kunne forstÄ nyansene inne i databasen. Siden dette er et stort tema, skal jeg fokusere pÄ det som jeg anser for viktig: hvordan databasen behandler SQL spÞrring.Jeg vil bare presentere grunnleggende databaskonsepter, slik at du ved slutten av artikkelen har en forstÄelse av hva som skjer under panseret.
Sidan detta Àr en lÄng och teknisk artikel som omfattar mÄnga algoritmer och datastrukturer, ta dig tid att lÀsa den. Vissa koncept kan vara svÄra att förstÄ; du kan hoppa över dem och ÀndÄ fÄ en allmÀn uppfattning.
För er som Àr mer insatta Àr denna artikel uppdelad i 3 delar:
- Ăversikt över lĂ„gnivĂ„- och högnivĂ„databasekomponenter
- Ăversikt över frĂ„gaoptimeringsprocessen
- Ăversikt över transaktionshantering och buffertpoolen
à tergÄ till grunderna
MĂ„nga Ă„r sedan (i en avlĂ€gsen, avlĂ€gsen galaxâŠ), var utvecklare tvungna att exakt veta hur mĂ„nga operationer de kodade. De visste sina algoritmer och datastrukturer utan och innan, eftersom de inte kunde ha rĂ„d med att slösa CPU och minne av sina lĂ„ngsamma datorer.
I denna del pÄminner jag dig om nÄgra av dessa koncept, eftersom de Àr nödvÀndiga för att förstÄ databaser. Jag kommer ocksÄ att introducera konceptet databasindex.
O(1) vs O(n2)
För nÀrvarande bryr sig mÄnga utvecklare inte om tidskomplexiteten av algoritmer⊠och de har rÀtt!
Men nÀr du hanterar stora mÀngder data (jag pratar inte om tusentals) eller om du kÀmpar för millisekunder, blir det avgörande att förstÄ detta koncept. Och som du förstÄr mÄste databaser hantera bÄda situationerna! Jag ska inte lÄta dig spendera mer tid Àn nödvÀndigt för att fÄnga kÀrnan. Detta kommer hjÀlpa oss senare att förstÄ kostnadsbaserad optimering (cost based optimization).
Konseptet
Tidskomplexiteten av en algoritm anvÀnds för att se hur lÄng tid det tar för algoritmen att utföra för en given mÀngd data. För att beskriva denna komplexitet anvÀnds matematiska beteckningar för stora O. Denna notation anvÀnds med en funktion som beskriver hur mÄnga operationer algoritmen behöver för en given mÀngd inmatningsdata.
Till exempel, nÀr jag sÀger "denna algoritm har komplexitet O (some_function() )", betyder det att för att bearbeta en viss mÀngd data behövs some_function(a_certain_amount_of_data) operationer.
Samtidig det viktiga Àr inte mÀngden data**, utan hur ** antalet operationer ökar med ökande datamÀngd. Tidskomplexiteten ger inte det exakta antalet operationer, men Àr ett bra sÀtt att uppskatta körtiden.

I denne grafen kan du se forholdet mellom antall operasjoner og mengden inndata for ulike typer tidskompleksitet. Jeg har brukt en logaritmisk skala for Ă„ vise dem. Med andre ord, mengden data Ăžker raskt fra 1 til 1 milliard. Vi kan se at:
- O(1) eller konstant kompleksitet forblir konstant (ellers ville det ikke bli kalt konstant kompleksitet).
- O(log(n)) forblir lav selv med milliarder av data.
- Verste kompleksitet â O(n2), hvor antallet operasjoner vokser raskt.
- De to Þvrige kompleksitetene Þker ogsÄ raskt.
Eksempler
Ved en liten mengde data er forskjellen mellom O(1) og O(n2) ubetydelig. La oss for eksempel anta at du har en algoritme som mÄ behandle 2000 elementer.
- Algoritmen O(1) vil koste deg 1 operasjon
- Algoritmen O(log(n)) vil koste deg 7 operasjoner
- Algoritmen O(n) vil koste deg 2 000 operasjoner
- Algoritmen O(n * log(n)) vil koste deg 14 000 operasjoner
- Algoritmen O(n2) vil koste deg 4 000 000 operasjoner
Forskjellen mellom O(1) og O(n2) virker stor (4 millioner operasjoner), men du vil miste maksimalt 2 ms, bare tiden til Ä blinke med Þynene. Faktisk kan moderne prosessorer hÄndtere . Det er derfor ytelse og optimalisering ikke er et problem i mange IT-prosjekter.
Som jeg allerede har sagt, er det fortsatt viktig Ä vite om dette konseptet nÄr man arbeider med store mengder data. Hvis algoritmen denne gangen mÄ behandle 1 000 000 elementer (som ikke er sÄ mye for en database):
- Algoritmen O(1) vil koste deg 1 operasjon
- Algoritmen O(log(n)) vil koste deg 14 operasjoner
- Algoritmen O(n) vil koste deg 1 000 000 operasjoner
- Algoritmen O(n * log(n)) vil koste deg 14 000 000 operasjoner
- Algoritmen O(n2) vil koste deg 1 000 000 000 000 operasjoner
Jeg gjorde ikke beregningene, men jeg vil si at med algoritmen O(n2) har du tid til Ă„ ta en kaffe (kanskje til og med to!). Hvis du legger til enda en 0 til mengden data, har du tid til Ă„ ta en lur.
La oss gÄ dypere
Til informasjon:
- SÞk i en god hashtabell finner et element pÄ O(1).
- SÞk i et godt balansert tre gir resultatet pÄ O(log(n)).
- SÞk i en liste gir resultatet pÄ O(n).
- De beste sorteringsalgoritmene har kompleksitet O(n * log(n)).
- En dÄrlig sorteringsalgoritme har kompleksitet O(n2).
Merk: I de neste delene vil vi se disse algoritmene og datastrukturene.
Det finnes flere typer tidskompleksitet for algoritmer:
- den gjennomsnittlige scenariet
- det beste utfallet
- og det dÄrligste scenariet
Tidskompleksitet er ofte det dÄrligste scenariet.
Jeg har bare snakket om tidskompleksiteten til algoritmen, men kompleksiteten gjelder ogsÄ for:
- minneforbruket til algoritmen
- disk I/O-forbruket til algoritmen
SelvfĂžlgelig finnes det komplekser som er verre enn nÂČ, som for eksempel:
- nâŽ: dette er fryktelig! Noen av de nevnte algoritmene har denne kompleksiteten.
- 3n: dette er enda verre! En av algoritmene vi skal se pÄ senere i artikkelen har denne kompleksiteten (og den brukes faktisk i mange databaser).
- fakultet n: du fÄr aldri resultatene dine selv med et lite datasett.
- nn: hvis du stĂžter pĂ„ denne kompleksiteten, bĂžr du spĂžrre deg selv om dette virkelig er ditt felt âŠ
Merk: Jeg har gitt deg ikke en reell definisjon av betegnelsen «stor O», men bare en idé. Du kan lese denne artikkelen i for den reelle (asymptotiske) definisjonen.
MergeSort (SammenslÄing sortering)
Hva gjÞr du nÄr du trenger Ä sortere en samling? Hva? Du kaller funksjonen sort()⊠Ok, godt svar⊠Men for databaser mÄ du forstÄ hvordan denne sort()-funksjonen fungerer.
Det finnes flere gode sorteringsalgoritmer, sÄ jeg vil fokusere pÄ den viktigste: sammenslÄingssortering. Kanskje du ikke forstÄr nÄ hvorfor datainndeling er nyttig, men du mÄ forstÄ det etter delen om optimalisering av forespÞrslene. Videre vil forstÄelse av sammenslÄingssortering hjelpe oss senere med Ä forstÄ den generelle join-operasjonen i databaser, kalt merge join (sammenslÄing).
Merge (SammenslÄing)
Som mange nyttige algoritmer er sammenslÄingssorteringen basert pÄ en gimmik: Ä slÄ sammen 2 sorterede arrays av stÞrrelse N/2 i et N-element sortert array koster bare N operasjoner. Denne operasjonen kalles sammenslÄing.
La oss se hva dette betyr med et enkelt eksempel:

I denne illustrasjonen ser vi at for Ä konstruere det endelige sorterte arrayet pÄ 8 elementer, trenger du bare Ä iterere én gang over 2x 4-element arrays. Siden begge 4-element arrays allerede er sortert:
- 1) du sammenligner begge nÄvÊrende elementer i de to arrayene (i starten er det nÄvÊrende = fÞrste)
- 2) sÄ ta det minste tallet, og plasser det i et array med 8 elementer
- 3) og gÄ videre til neste element i arrayet der du tok det minste elementet
- og gjenta 1, 2, 3, inntil du nÄr det siste elementet i et av arrayene.
- Deretter tar du de Ăžvrige elementene fra det andre arrayet for Ă„ plassere dem i et array med 8 elementer.
Dette fungerer fordi begge 4-element arrayene er sortert, og dermed trenger du ikke Ä "gÄ tilbake" i disse arrayene.
NÄ som vi har forstÄtt dette trikset, her er pseudokoden min for sammenslÄing:
array mergeSort(array a)
if(length(a)==1)
return a[0];
end if
//rekursive kall
[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);
//kombinere de 2 smÄ ordnede arrayene til et stort
array result := merge(new_left_array,new_right_array);
return result;SammenslÄingssortering deler opp oppgaven i mindre oppgaver, og deretter finner resultatene av de mindre oppgavene for Ä fÄ resultatet av den opprinnelige oppgaven (merk: denne typen algoritme kalles del og hersk). Hvis du ikke forstÄr denne algoritmen, ikke bekymre deg; jeg forsto det ikke fÞrste gangen jeg sÄ den. Hvis det kan hjelpe deg, ser jeg denne algoritmen som en to-fase algoritme:
- Delingsfase, hvor arrayet deles opp i mindre array
- Sorteringsfase, hvor smÄ array kombineres (ved hjelp av sammenslÄing) for Ä danne et stÞrre array.
Delingsfase (Division phase)

I delingsfasen deles arrayet opp i enhetlige array i 3 trinn. Det formelle antallet trinn er log(N) (siden N=8, log(N) = 3).
Hvordan vet jeg dette?
Jeg er et geni! Kort sagt â matematikk. Ideen er at hvert trinn deler stĂžrrelsen pĂ„ det opprinnelige arrayet i 2. Antallet trinn er antallet ganger du kan dele det opprinnelige arrayet i to. Dette er den nĂžyaktige definisjonen av logaritmen (med base 2).
Sorteringsfase (Sorting phase)

I sorteringsfasen begynner du med enhetlige (enkelt-element) arrays. I lÞpet av hvert trinn bruker du flere sammenslÄingsoperasjoner, og den totale kostnaden er N = 8 operasjoner:
- I fÞrste trinn har du 4 sammenslÄinger som koster 2 operasjoner hver
- I andre trinn har du 2 sammenslÄinger som koster 4 operasjoner hver
- I tredje trinn har du 1 sammenslÄing som koster 8 operasjoner
Siden det er log (N) trinn, den totale kostnaden N * log(N) operasjoner.
Fordelene med sammenslÄingssortering
Hvorfor er denne algoritmen sÄ kraftig?
Fordi:
- Du kan endre den for Ă„ redusere minnebruken, slik at du ikke oppretter nye matriser, men i stedet direkte endrer inngangsmatrisen.
Merk: denne typen algoritmer kalles (sortering uten ekstra minne).
- Du kan endre den for samtidig Ä bruke diskplass og lite minne uten betydelige kostnader for disk-I/O. Ideen er Ä laste inn i minnet bare de delene som for Þyeblikket behandles. Dette er viktig nÄr du mÄ sortere en tabell som er flere gigabyte stor, kun med en minnebuffer pÄ 100 megabyte.
Merk: denne typen algoritmer kalles .
- Du kan endre den for Ä kjÞre pÄ flere prosesser / trÄder / servere.
For eksempel er distribuert sammenslÄingssortering en av nÞkkelkomponentene (som er en struktur i store data).
- Denne algoritmen kan forvandle bly til gull (sant!).
Denne sorteringsalgoritmen brukes i de fleste (om ikke alle) databaser, men den er ikke den eneste. Hvis du vil lĂŠre mer, kan du lese dette , som diskuterer fordeler og ulemper ved vanlige sorteringsalgoritmer i databaser.
Array, Tre og Hash-tabell
NÄ som vi forstÄr ideen om tidskompleksitet og sortering, mÄ jeg fortelle deg om 3 datatyper. Dette er viktig, fordi de er grunnlaget for moderne databaser.. Jeg vil ogsÄ introdusere begrepet databasindex.
Array
Et todimensjonalt array er den enkleste datatypen. En tabell kan betraktes som et array. For eksempel:

Dette 2-dimensjonale arrayet representerer en tabell med rader og kolonner:
- Hver rad representerer en enhet.
- Kolonnene lagrer egenskaper som beskriver enheten.
- Hver kolonne lagrer data av en bestemt type (integer, string, date âŠ).
Det er sÄ praktisk Ä lagre og visualisere data, men nÄr du mÄ finne en bestemt verdi, passer det ikke.
For eksempel, hvis du Ăžnsker Ă„ finne alle guttene som jobber i Storbritannia, mĂ„ du gĂ„ gjennom hver rad for Ă„ bestemme om denne raden tilhĂžrer Storbritannia. Dette vil koste deg N operasjoner., hvor N â antall rader, som er bra, men kan det vĂŠre en raskere mĂ„te? NĂ„ er det pĂ„ tide Ă„ bli kjent med trĂŠr.
Merk: de fleste moderne databaser tilbyr utvidede matriser for effektiv lagring av tabeller: heap-organizedtables og index-organizedtables. Men dette endrer ikke problemet med rask sĂžking av bestemte betingelser i en gruppe kolonner.
Database-tre og indeks
Et binÊrt sÞketre er et binÊrt tre med en spesiell egenskap, nÞkkelen i hver node mÄ vÊre:
- stĂžrre enn alle nĂžklene som er lagret i venstre undertre
- mindre enn alle nĂžklene som er lagret i hĂžyre undertre
La oss se hva dette betyr visuelt
Ideen

Dette treet har N = 15 elementer. La oss si at jeg leter etter 208:
- Jeg begynner med roten, hvis nÞkkel er 136. Siden 136<208, ser jeg pÄ hÞyre undertre til node 136.
- 398>208, derfor ser jeg pÄ venstre undertre til node 398
- 250>208, derfor ser jeg pÄ venstre undertre til node 250
- 200<208, derfor ser jeg pÄ hÞyre undertre til node 200. Men 200 har ikke noe hÞyre undertre, verdien finnes ikke (fordi, hvis den fantes, ville den vÊrt i hÞyre undertre til 200).
NĂ„, la oss si at jeg leter etter 40
- Jeg begynner med roten, hvis nÞkkel er 136. Siden 136 > 40, ser jeg pÄ venstre undertre til node 136.
- 80 > 40, derfor ser jeg pÄ venstre undertre til node 80
- 40= 40, noden eksisterer. Jeg henter radidentifikatoren inne i noden (dette er ikke pÄ bildet) og ser i tabellen for den gitte radidentifikatoren.
- Ă kjenne radidentifikatoren lar meg vite hvor dataene faktisk ligger i tabellen, og derfor kan jeg hente dem umiddelbart.
Til slutt vil begge sÞkene koste meg antall nivÄer inne i treet. Hvis du leser nÞye delen om sammenfletting, mÄ du se at det her er log (N) nivÄer. SÄ det viser seg at kostnaden for sÞk er log(N), ikke dÄrlig!
La oss gÄ tilbake til problemet vÄrt
Men dette er veldig abstrakt, sÄ la oss gÄ tilbake til problemet vÄrt. I stedet for et enkelt heltall, forestill deg en streng som representerer et lands navn i den forrige tabellen. La oss si at du har et tre som inneholder feltet "country" (kolonne 3) i tabellen:
- Hvis du vil vite hvem som jobber i Storbritannia
- ser du pÄ treet for Ä fÄ noden som representerer Storbritannia
- inni "UKnode" finner du plasseringen av postene til arbeidstakere i Storbritannia.
Denne sĂžket vil koste log(N) operasjoner i stedet for N operasjoner hvis du bruker et array direkte. Det du nettopp har presentert, var databaseindeks.
Du kan bygge et indeks tre for hvilken som helst gruppe av felt (streng, tall, 2 strenger, tall og streng, dato...) sÄ lenge du har en funksjon for Ä sammenligne nÞkler (dvs. grupper av felt) slik at du kan sette rekkefÞlgen mellom nÞklene (som er tilfelle for alle grunnleggende typer i databasen).
B+TreIndeks
Selv om dette treet fungerer godt for Ä fÄ en bestemt verdi, er det et STORT problem nÄr du trenger Ä hente flere elementer mellom to verdier. Dette vil koste O(N) fordi du mÄ se pÄ hver node i treet og sjekke om den ligger mellom disse to verdiene (for eksempel ved en sortert traversering av treet). Videre, denne operasjonen er ikke praktisk for disk I/O, da du mÄ lese hele treet. Vi trenger Ä finne en mÄte Ä effektivt utfÞre intervalforespÞrselen. For Ä lÞse dette problemet, bruker moderne databaser en modifisert versjon av det tidligere treet kalt B+Tre. I B+Tre treet:
- bare de nederste nodene (bladene) lagrer informasjonen (plasseringen av radene i den tilknyttede tabellen)
- de andre nodene er her for ruting til riktig node under sĂžk.

Som du kan se, er det flere noder her (dobbelt sÄ mange). Faktisk har du ekstra noder, "beslutningstagere", som hjelper deg Ä finne riktig node (som lagrer plasseringen av radene i den tilknyttede tabellen). Men sÞke kompliserteheten er fortsatt O(log(N)) (det er bare et annet lag). Den store forskjellen er at nodene pÄ det nederste nivÄet er knyttet til sine etterkommere.
Med dette B+Tre, hvis du leter etter verdier fra 40 til 100:
- Du trenger bare Ă„ sĂžke etter 40 (eller den nĂŠrmeste verdien etter 40, hvis 40 ikke eksisterer), som du gjorde med det tidligere treet.
- Deretter samler du etterkommerne til 40, ved Ä bruke direkte referanser til etterkommerne, til du nÄr 100.
Anta at du fant M etterkommere, og treet har N noder. à sÞke etter en bestemt node koster log(N) slik som i det tidligere treet. Men, nÄr du har fÄtt denne noden, fÄr du M etterkommere i M operasjoner med referanser til deres etterkommere. Dette sÞket koster bare M+log(N) operasjoner sammenlignet med N operasjoner med det forrige treet. Dessuten trenger du ikke Ä lese hele treet (kun M + log (N) noder), noe som betyr mindre diskbruk. Hvis M er lite (for eksempel 200 rader) og N er stort (1 000 000 rader), vil dette vÊre en STOR forskjell.
Men her er det nye problemer (igjen!). Hvis du legger til eller fjerner en rad i databasen (og dermed i den tilknyttede B+Tree-indeksen):
- mÄ du opprettholde rekkefÞlgen mellom nodene inne i B+Tree, ellers kan du ikke finne nodene inne i et usortert tre.
- du mÄ bevare et minimum av nivÄer i B+Tree, ellers vil den tidsmessige kompleksiteten i O(log(N)) bli O(N).
Med andre ord, B+Tree mÄ vÊre selvordnende og balansert. Heldigvis er dette mulig med smarte slettings- og innsettingsoperasjoner. Men det kommer til en kostnad: innsetting og sletting i B+ treet koster O(log(N)). Det er derfor noen av dere har hÞrt at Ä bruke for mange indekser ikke er en sÄ god idé. Faktisk, du bremser rask innsetting / oppdatering / sletting av rader i tabellen, siden databasen mÄ oppdatere tabelens indekser med kostbare O(log(N)) operasjoner for hver indeks. I tillegg betyr det Ä legge til indekser en stÞrre belastning for transaksjonsbehandleren (som vil bli beskrevet mot slutten av artikkelen).
For mer informasjon, kan du se artikkelen pÄ Wikipedia om . Hvis du Þnsker et eksempel pÄ implementering av B+Tree i en database, se og fra en ledende MySQL-utvikler. Begge fokuserer pÄ hvordan InnoDB (MySQL-motoren) hÄndterer indekser.
Merk: leseren fortalte meg at, pÄ grunn av lavnivÄoptimaliseringer, mÄ B+ treet vÊre fullstendig balansert.
Hashtable (Hash-table)
VÄr siste viktige datastruktur er hashtabellen. Den er veldig nyttig nÄr du vil raskt sÞke etter verdier. I tillegg vil forstÄelsen av hashtabeller hjelpe oss senere med Ä forstÄ den generelle operasjonen for sammenkobling i databasen, kalt hash-sammenkobling ( hash join). Denne datastrukturen brukes ogsÄ av databasen for Ä lagre noen interne ting (for eksempel, lÄsetabell eller bufferpool, vi vil se begge disse konseptene senere).
En hash-tabell er en datakonstruksjon som raskt finner et element basert pÄ nÞkkelen. For Ä bygge en hash-tabell mÄ du definere:
- nĂžkkel for elementene dine
- en hash-funksjon for nĂžklene. De beregnede hashene for nĂžklene gir plasseringen av elementene (kalt segmenter ).
- en funksjon for Ä sammenligne nÞkler. NÄr du har funnet riktig segment, mÄ du finne elementet du leter etter i segmentet, ved hjelp av denne sammenligningen.
Et enkelt eksempel
La oss ta et konkret eksempel:

Denne hash-tabellen har 10 segmenter. Siden jeg er lat, har jeg bare illustrert 5 segmenter, men jeg vet at du er smart, sÄ jeg lar deg forestille deg de 5 andre selv. Jeg har brukt en hash-funksjon som tar modulus 10 av nÞkkelen. Med andre ord, beholdere bare det siste sifferet av nÞkkelen for Ä finne segmentet:
- hvis det siste sifferet er 0, gÄr elementet til segment 0,
- hvis det siste sifferet er 1, gÄr elementet til segment 1,
- hvis det siste sifferet er 2, gÄr elementet til segment 2,
- âŠ
Sammenligningsfunksjonen jeg brukte er rett og slett likhet mellom to heltall.
Anta at du Ăžnsker Ă„ hente elementet 78:
- Hash-tabellen beregner hash-koden for 78, som er 8.
- Hash-tabellen ser i segment 8, og det fĂžrste elementet den finner, er 78.
- Den returnerer elementet 78 til deg
- SĂžket kostet bare 2 operasjoner (en for Ă„ beregne hash-funksjonsverdien og en annen for Ă„ finne elementet innen segmentet).
NĂ„, antatt at du vil hente elementet 59:
- Hash-tabellen beregner hash-koden for 59, som er 9.
- Hash-tabellen sĂžker i segment 9, det fĂžrste funnet elementet er 99. Siden 99!=59, er ikke elementet 99 det riktige elementet.
- Ved Ă„ bruke denne samme logikken, tas det andre elementet (9), tredje (79), âŠ, siste (29).
- Elementet ble ikke funnet.
- SĂžket kostet 7 operasjoner.
En god hash-funksjon
Som du ser, avhenger kostnaden av verdien du leter etter!
Hvis jeg nÄ endrer hash-funksjonen til modulus 1 000 000 av nÞkkelen (det vil si, tar de siste 6 sifrene), vil det andre sÞket koste bare 1 operasjon, siden det ikke finnes elementer i segment 000059. Den virkelige oppgaven er Ä finne en god hash-funksjon som lager segmenter som inneholder svÊrt fÄ elementer..
I mitt eksempel er det enkelt Ä finne en god hash-funksjon. Men dette er et enkelt eksempel; det er vanskeligere Ä finne en god hash-funksjon nÄr nÞkkelen er:
- en streng (for eksempel et etternavn)
- to strenger (for eksempel et etternavn og et fornavn)
- to strenger og en dato (for eksempel et etternavn, et fornavn og fĂždselsdato)
- âŠ
Med en god hash-funksjon finner du i en hash-tabell i O(1).
Array vs. hash-tabell
Hvorfor ikke bruke array?
Hmm, godt spÞrsmÄl.
- Hash-tabellen kan vÊre delvis lastet inn i minnet, mens de Þvrige segmentene kan vÊre lagret pÄ disken.
- Med et array mÄ du bruke kontinuerlig minneplass. Hvis du laster inn en stor tabell, er det veldig vanskelig Ä finne tilstrekkelig kontinuerlig plass.
- For hash-tabellen kan du velge Ăžnsket nĂžkkel (for eksempel landet og etternavnet til en person).
For mer informasjon kan du lese artikkelen om , som er en effektiv implementering av hash-tabellen; du trenger ikke Ä forstÄ Java for Ä forstÄ konseptene som er presentert i denne artikkelen.
Kilde: habr.com
