Szia Habr! Figyelmébe ajánlom a cikk fordítását
"Hogyan működik egy relációs adatbázis".

Amikor a relációs adatbázisokról van szó, nem tehetek róla, de azt gondolom, hogy valami hiányzik. Mindenhol használják. Számos különféle adatbázis áll rendelkezésre, a kicsi és hasznos SQLite-tól a nagy teljesítményű Teradata-ig. De csak néhány cikk ismerteti az adatbázis működését. Kereshet saját magának a „hogyan működik a relációs adatbázisban” használatával, hogy megnézze, milyen kevés találat van. Ráadásul ezek a cikkek rövidek. Ha a legújabb buzzy technológiákat keresi (BigData, NoSQL vagy JavaScript), akkor részletesebb cikkeket találhat ezek működéséről.

A relációs adatbázisok túl régiek és túl unalmasak ahhoz, hogy az egyetemi kurzusokon, kutatási munkákon és könyveken kívül elmagyarázzák őket?

Fejlesztőként utálok olyasmit használni, amit nem értek. Ha pedig több mint 40 éve használnak adatbázisokat, annak oka van. Az évek során több száz órát töltöttem azzal, hogy valóban megértsem ezeket a furcsa fekete dobozokat, amelyeket minden nap használok. Relációs adatbázisok nagyon érdekes, mert ők hasznos és újrafelhasználható koncepciókon alapul. Ha érdekli egy adatbázis megértése, de soha nem volt ideje vagy kedve elmélyülni ebben a széles témában, élvezze ezt a cikket.

Bár ennek a cikknek a címe egyértelmű, ennek a cikknek a célja nem az adatbázis használatának megértése. Következésképpen, már tudnia kell, hogyan kell egyszerű csatlakozási kérelmet és alapvető lekérdezéseket írni szifilisz; különben lehet, hogy nem érted ezt a cikket. Ez az egyetlen dolog, amit tudnod kell, a többit elmagyarázom.

Néhány számítástechnikai alapismerettel kezdem, mint például az algoritmusok időbeli összetettsége (BigO). Tudom, hogy néhányan utáljátok ezt a koncepciót, de enélkül nem fogjátok megérteni az adatbázisban rejlő bonyodalmakat. Mivel ez egy hatalmas téma, Én arra koncentrálok amit fontosnak tartok: hogyan dolgozza fel az adatbázis SQL vizsgálat. csak bemutatom adatbázis alapfogalmakhogy a cikk végén legyen fogalmad arról, mi folyik a motorháztető alatt.

Mivel ez egy hosszú és technikai jellegű cikk, amely sok algoritmust és adatstruktúrát foglal magában, szánjon időt az elolvasására. Néhány fogalmat nehéz lehet megérteni; kihagyhatja őket, és továbbra is megkaphatja az általános elképzelést.

A hozzáértőbbek számára ez a cikk 3 részre oszlik:

• Az alacsony és magas szintű adatbázis-összetevők áttekintése
• A lekérdezésoptimalizálási folyamat áttekintése
• A tranzakció- és pufferkészlet-kezelés áttekintése

Vissza az alapokhoz

Évekkel ezelőtt (egy messzi-messzi galaxisban...) a fejlesztőknek pontosan tudniuk kellett a kódolt műveletek számát. Fejből tudták algoritmusaikat és adatszerkezeteiket, mert nem engedhették meg maguknak, hogy lassú számítógépeik CPU-ját és memóriáját pazarolják.

Ebben a részben néhány ilyen fogalomra emlékeztetem Önt, mivel ezek elengedhetetlenek az adatbázis megértéséhez. Bemutatom a koncepciót is adatbázis index.

O(1) vs O(n2)

Manapság sok fejlesztő nem törődik az algoritmusok időbeli bonyolultságával... és igazuk van!

De ha sok adattal van dolgod (nem ezrekről beszélek), vagy ha ezredmásodpercek alatt küzdesz, kritikussá válik ennek a koncepciónak a megértése. És ahogy el tudod képzelni, az adatbázisoknak mindkét helyzettel meg kell küzdeniük! Nem fogom rávenni a szükségesnél több időt a lényeg megértésére. Ez később segít megérteni a költségalapú optimalizálás fogalmát (költség alapján optimalizálás).

koncepció

Az algoritmus időbeli összetettsége arra szolgál, hogy megnézze, mennyi ideig tart egy algoritmus befejezése egy adott adatmennyiség esetén. Ennek a bonyolultságnak a leírására nagy O matematikai jelölést használunk, amelyet egy olyan függvénynél használunk, amely leírja, hogy egy algoritmusnak hány műveletre van szüksége adott számú bemenethez.

Például, amikor azt mondom, hogy "ennek az algoritmusnak a komplexitása O(some_function())", ez azt jelenti, hogy az algoritmusnak bizonyos_függvény(egy_bizonyos_adatmennyiség) műveletekre van szüksége egy bizonyos mennyiségű adat feldolgozásához.

Ebben az esetben a Nem az adatmennyiség számít**, másképp ** hogyan növekszik a műveletek száma az adatmennyiség növekedésével. Az időbonyolultság nem adja meg a műveletek pontos számát, de jó módszer a végrehajtási idő becslésére.

Ezen a grafikonon láthatja a műveletek számát a bemeneti adatok mennyiségével szemben a különböző típusú algoritmusok időbeli bonyolultságaihoz. Ezek megjelenítéséhez logaritmikus skálát használtam. Más szóval, az adatmennyiség gyorsan növekszik 1-ről 1 milliárdra. Láthatjuk, hogy:

• O(1) vagy állandó komplexitás állandó marad (egyébként nem neveznénk állandó komplexitásnak).
• O(log(n)) még több milliárd adat mellett is alacsony marad.
• Legrosszabb nehézség - O(n2), ahol a műveletek száma gyorsan növekszik.
• A másik két szövődmény ugyanolyan gyorsan fokozódik.

Примеры

Kis adatmennyiség mellett az O(1) és O(n2) közötti különbség elhanyagolható. Tegyük fel például, hogy van egy algoritmusa, amelynek 2000 elemet kell feldolgoznia.

• Az O(1) algoritmus 1 műveletbe kerül
• Az O(log(n)) algoritmus 7 műveletbe kerül
• Az O(n) algoritmus 2 műveletbe kerül
• Az O(n*log(n)) algoritmus 14 000 műveletbe fog kerülni
• Az O(n2) algoritmus 4 000 000 műveletbe kerül

Az O(1) és O(n2) közötti különbség nagynak tűnik (4 millió művelet), de legfeljebb 2 ms-ot veszíthet, csak ideje pislogni. Valójában a modern processzorok képesek feldolgozni több száz millió művelet másodpercenként. Ez az oka annak, hogy a teljesítmény és az optimalizálás sok informatikai projektben nem probléma.

Mint mondtam, még mindig fontos ismerni ezt a fogalmat, amikor hatalmas mennyiségű adattal dolgozunk. Ha az algoritmusnak ezúttal 1 000 000 elemet kell feldolgoznia (ami nem sok egy adatbázisnál):

• Az O(1) algoritmus 1 műveletbe kerül
• Az O(log(n)) algoritmus 14 műveletbe kerül
• Az O(n) algoritmus 1 000 000 műveletbe kerül
• Az O(n*log(n)) algoritmus 14 000 000 műveletbe kerül
• Az O(n2) algoritmus 1 000 000 000 000 műveletbe kerül

Nem számoltam, de azt mondanám, hogy az O(n2) algoritmussal van időd meginni egy kávét (akár kettőt is!). Ha még egy 0-t ad hozzá az adatmennyiséghez, lesz ideje szunyókálni.

Menjünk mélyebbre

Az Ön adatai:

• Egy jó hash tábla keresés talál egy elemet az O(1)-ben.
• Egy jól kiegyensúlyozott fa keresése O(log(n)-ban adja meg az eredményeket).
• Egy tömbben végzett keresés O(n) értékű eredményeket ad.
• A legjobb rendezési algoritmusok bonyolultsága O(n*log(n)).
• Egy rossz rendezési algoritmus bonyolultsága O(n2).

Megjegyzés: A következő részekben ezeket az algoritmusokat és adatstruktúrákat fogjuk látni.

Az algoritmus időbonyolultságának többféle típusa létezik:

• átlagos eseti forgatókönyv
• legjobb forgatókönyv
• és a legrosszabb forgatókönyv

Az idő bonyolultsága gyakran a legrosszabb forgatókönyv.

Csak az algoritmus időbeli összetettségéről beszéltem, de a komplexitás a következőkre is vonatkozik:

• az algoritmus memóriafelhasználása
• lemez I/O felhasználási algoritmus

Természetesen vannak szövődmények, amelyek rosszabbak az n2-nél, például:

• n4: ez szörnyű! Az említett algoritmusok némelyike ​​rendelkezik ezzel a bonyolultsággal.
• 3n: ez még rosszabb! Az egyik algoritmus, amelyet a cikk közepén fogunk látni, ilyen összetettséggel rendelkezik (és valójában sok adatbázisban használják).
• faktoriális n: soha nem kapja meg az eredményeket még kis mennyiségű adattal sem.
• nn: Ha ezzel a bonyolultsággal találkozol, tedd fel magadnak a kérdést, hogy valóban ez a tevékenységi területed...

Megjegyzés: Nem adtam meg a nagy O jelölés tényleges meghatározását, csak egy ötletet. Ezt a cikket a címen olvashatja el Wikipedia a valódi (aszimptotikus) definícióhoz.

MergeSort

Mit csinálsz, ha rendezned kell egy gyűjteményt? Mit? Meghívod a sort() függvényt... Ok, jó válasz... De egy adatbázishoz meg kell értened, hogyan működik ez a sort() függvény.

Számos jó rendezési algoritmus létezik, ezért a legfontosabbakra összpontosítok: összevonási rendezés. Lehet, hogy nem érted, miért hasznos most az adatok rendezése, de a lekérdezésoptimalizálási rész után meg kell tenni. Sőt, az összevonási rendezés megértése segít nekünk később megérteni az úgynevezett közös adatbázis-csatlakozási műveletet összeolvad csatlakozik (összeolvadó egyesület).

Összeolvad

Mint sok hasznos algoritmus, az egyesítési rendezés is egy trükkön alapul: 2 N/2 méretű rendezett tömb N elemű rendezett tömbbé kombinálása csak N műveletbe kerül. Ezt a műveletet összevonásnak nevezik.

Nézzük meg, mit jelent ez egy egyszerű példán:

Ez az ábra azt mutatja, hogy a végső rendezett 8 elemű tömb felépítéséhez csak egyszer kell iterálnia a 2 4 elemű tömbön. Mivel mindkét 4 elemű tömb már rendezve van:

• 1) összehasonlítja mindkét aktuális elemet két tömbben (az elején áram = első)
• 2) majd vegyük a legkisebbet, és tegyük egy 8 elemű tömbbe
• 3) és lépjen a következő elemre a tömbben, ahol a legkisebb elemet vette
• és ismételje meg az 1,2,3-at, amíg el nem éri az egyik tömb utolsó elemét.
• Ezután a másik tömb többi elemét egy 8 elemű tömbbe helyezi.

Ez azért működik, mert mindkét 4 elemű tömb rendezve van, és így nem kell "visszamenni" ezekben a tömbökben.

Most, hogy megértettük a trükköt, itt van az egyesítés pszeudokódja:

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;

Az összevonási rendezés a problémát kisebb problémákra bontja, majd megkeresi a kisebb problémák eredményeit, hogy megkapja az eredeti probléma eredményét (megjegyzés: ezt a fajta algoritmust oszd meg és uralkodj). Ha nem érti ezt az algoritmust, ne aggódjon; Nem értettem, amikor először láttam. Ha ez segíthet, akkor ezt az algoritmust kétfázisúnak látom:

• Osztási fázis, ahol a tömb kisebb tömbökre oszlik
• A rendezési fázisban a kis tömböket egyesítik (egyesítés használatával), hogy egy nagyobb tömböt képezzenek.

Felosztási fázis

Az osztási szakaszban a tömb 3 lépésben egységes tömbökre oszlik. A lépések formális száma log(N) (mivel N=8, log(N)=3).

Honnan tudjam ezt?

zseni vagyok! Egyszóval - matematika. Az ötlet az, hogy minden lépés elosztja az eredeti tömb méretét 2-vel. A lépések száma annyi, hogy hányszor oszthatja ketté az eredeti tömböt. Ez a logaritmus pontos meghatározása (2. bázis).

Rendezési fázis

A rendezési fázisban egységes (egyelemű) tömbökkel kezdjük. Minden egyes lépés során több egyesítési műveletet alkalmaz, és a teljes költség N = 8 művelet:

• Az első szakaszban 4 összevonása van, amelyek mindegyike 2 műveletbe kerül
• A második lépésben 2 összevonása van, amelyek mindegyike 4 műveletbe kerül
• A harmadik lépésben 1 összevonása van, ami 8 műveletbe kerül

Mivel log(N) lépések vannak, teljes költség N * log(N) műveletek.

Az egyesítés rendezés előnyei

Miért olyan erős ez az algoritmus?

Mert:

• Módosíthatja a memóriaterület csökkentésére, így nem hoz létre új tömböket, hanem közvetlenül módosítja a bemeneti tömböt.

Megjegyzés: ezt a fajta algoritmust hívják in-hely (rendezés további memória nélkül).

• Módosíthatja úgy, hogy egyszerre használjon lemezterületet és kis mennyiségű memóriát anélkül, hogy jelentős lemez I/O-többletet okozna. Az ötlet az, hogy csak azokat a részeket töltsék be a memóriába, amelyek éppen feldolgozás alatt állnak. Ez akkor fontos, ha egy több gigabájtos táblát csak 100 megabájtos memóriapufferrel kell rendeznie.

Megjegyzés: ezt a fajta algoritmust hívják külső rendezés.

• Megváltoztathatja, hogy több folyamaton/szálon/szerveren fusson.

Például az elosztott egyesítés rendezése az egyik kulcsfontosságú összetevő Hadoop (ami a big data-ban egy struktúra).

• Ez az algoritmus az ólmot arannyá változtathatja (tényleg!).

Ezt a rendezési algoritmust a legtöbb (ha nem az összes) adatbázisban használják, de nem ez az egyetlen. Ha többet szeretne tudni, ezt elolvashatja kutatómunka, amely a gyakori adatbázis-rendezési algoritmusok előnyeit és hátrányait tárgyalja.

Tömb, fa és hash tábla

Most, hogy megértettük az időbonyolítás és a rendezés fogalmát, három adatszerkezetről kell mesélnem. Ez azért fontos, mert ők a modern adatbázisok alapja. Bemutatom a koncepciót is adatbázis index.

sor

A kétdimenziós tömb a legegyszerűbb adatstruktúra. A táblázat felfogható tömbnek. Például:

Ez a kétdimenziós tömb egy táblázat sorokkal és oszlopokkal:

• Minden sor egy entitást jelöl
• Az oszlopok az entitást leíró tulajdonságokat tárolják.
• Minden oszlop meghatározott típusú adatokat tárol (egész szám, karakterlánc, dátum...).

Ez kényelmes az adatok tárolására és megjelenítésére, de ha egy adott értéket kell találnia, ez nem megfelelő.

Például, ha meg akarja találni az összes olyan srácot, aki az Egyesült Királyságban dolgozik, minden sort meg kell néznie, hogy megállapítsa, az adott sor az Egyesült Királysághoz tartozik-e. N tranzakcióba fog kerülniAhol N - sorok száma, ami nem rossz, de lehet ennél gyorsabb módszer? Itt az ideje, hogy megismerkedjünk a fákkal.

Megjegyzés: A legtöbb modern adatbázis kibővített tömböket kínál a táblák hatékony tárolására: kupacba rendezett táblák és index szerint szervezett táblák. Ez azonban nem változtat azon a problémán, hogy gyorsan megtaláljunk egy adott feltételt egy oszlopcsoportban.

Adatbázis fa és index

A bináris keresőfa egy speciális tulajdonságú bináris fa, a kulcsnak minden csomóponton a következőnek kell lennie:

• nagyobb, mint a bal oldali részfában tárolt összes kulcs
• kevesebb, mint a jobb oldali részfában tárolt összes kulcs

Nézzük meg, mit jelent ez vizuálisan

Ötlet

Ennek a fának N = 15 eleme van. Tegyük fel, hogy a 208-at keresem:

• A gyökérnél kezdem, amelynek kulcsa 136. Mivel 136<208, a 136-os csomópont jobb részfáját nézem.
• 398>208 ezért a 398-as csomópont bal oldali részfáját nézem
• 250>208 ezért a 250-as csomópont bal oldali részfáját nézem
• 200<208, ezért a 200-as csomópont jobb részfáját nézem. De a 200-nak nincs jobb részfája, érték nem létezik (mert ha létezik, akkor a 200-as jobb részfában lesz).

Most mondjuk 40-et keresek

• A gyökérnél kezdem, amelynek kulcsa 136. Mivel 136 > 40, a 136-os csomópont bal oldali részfáját nézem.
• 80 > 40, ezért a 80-as csomópont bal oldali részfáját nézem
• 40 = 40, csomópont létezik. A csomóponton belül lekérem a sorazonosítót (a képen nem látható), és a táblázatban megkeresem az adott sorazonosítót.
• A sorazonosító ismerete lehetővé teszi, hogy pontosan tudjam, hol vannak az adatok a táblázatban, így azonnal visszakereshetem azokat.

Végül mindkét keresés a fán belüli szintek számába fog kerülni. Ha figyelmesen elolvassa az összevonási rendezésről szóló részt, látnia kell, hogy vannak log(N) szintek. Kiderül, keresési költségnapló (N), nem rossz!

Térjünk vissza a problémánkhoz

De ez nagyon elvont, úgyhogy térjünk vissza a problémánkhoz. Egyszerű egész szám helyett képzeljünk el egy karakterláncot, amely az előző táblázatban szereplő személy országát jelöli. Tegyük fel, hogy van egy fája, amely tartalmazza a táblázat „ország” mezőjét (3. oszlop):

• Ha tudni szeretné, ki dolgozik az Egyesült Királyságban
• ránézel a fára, hogy megkapd a Nagy-Britanniát jelképező csomópontot
• az "UKnode"-on belül megtalálja az Egyesült Királyság munkavállalói nyilvántartásának helyét.

Ez a keresés log(N) műveletekbe kerül N művelet helyett, ha közvetlenül használja a tömböt. Amit most bemutattál, az volt adatbázis index.

Bármely mezőcsoporthoz (karakterlánc, szám, 2 sor, szám és karakterlánc, dátum...) készíthet indexfát, ha van funkciója a kulcsok (azaz mezőcsoportok) összehasonlítására, így beállíthatja sorrendben a kulcsok között (ez az adatbázis bármely alaptípusára így van).

B+TreeIndex

Bár ez a fa jól működik egy adott érték megszerzésére, NAGY probléma van, amikor szükség van rá több elemet kap két érték közé. Ez O(N)-ba fog kerülni, mert meg kell néznie a fa minden csomópontját, és ellenőriznie kell, hogy e két érték között van-e (például a fa rendezett bejárásával). Ráadásul ez a művelet nem lemez I/O-barát, mivel a teljes fát be kell olvasnia. Meg kell találnunk a hatékony végrehajtás módját tartomány kérése. A probléma megoldására a modern adatbázisok az előző fa módosított változatát, a B+Tree-t használják. Egy B+fa fában:

• csak a legalsó csomópontok (levelek) raktárinformáció (a sorok helye a kapcsolódó táblázatban)
• a többi csomópont itt van az útválasztáshoz a megfelelő csomóponthoz keresés közben.

Mint látható, itt több csomópont van (kétszer). Valójában vannak további csomópontjai, "döntési csomópontjai", amelyek segítenek megtalálni a megfelelő csomópontot (amely a kapcsolódó táblázatban tárolja a sorok helyét). De a keresés bonyolultsága továbbra is O(log(N)) (csak egy szint van még). A nagy különbség az az alsó szinten lévő csomópontok utódaikhoz kapcsolódnak.

Ezzel a B+Fával, ha 40 és 100 közötti értékeket keres:

• Csak meg kell keresnie a 40-et (vagy a 40 utáni legközelebbi értéket, ha nem létezik 40), mint az előző fánál.
• Ezután gyűjts össze 40 örököst a közvetlen örökös linkek segítségével, amíg el nem éred a 100-at.

Tegyük fel, hogy M utódot talál, és a fának N csomópontja van. Egy adott csomópont keresése log(N) költséget jelent, mint az előző fa esetében. De amint megkapja ezt a csomópontot, M utódokat fog kapni az M műveletekben az utódaikra való hivatkozásokkal. Ez a keresés csak M+log(N) műveletek az előző fán lévő N művelethez képest. Ráadásul nem kell a teljes fát olvasni (csak M+log(N) csomópont), ami kevesebb lemezhasználatot jelent. Ha M kicsi (pl. 200 sor), N pedig nagy (1 000 000 sor), akkor NAGY különbség lesz.

De itt (megint!) új problémák vannak. Ha hozzáad vagy töröl egy sort az adatbázisban (és így a kapcsolódó B+Tree indexben):

• fenn kell tartania a rendet a B+Fán belüli csomópontok között, különben nem fogja megtalálni a csomópontokat egy rendezetlen fán belül.
• meg kell tartani a lehetséges minimális szintek számát a B+Tree-ben, különben az O(log(N)) időbonyolultság O(N) lesz.

Más szóval, a B+Tree-nek önrendezőnek és kiegyensúlyozottnak kell lennie. Szerencsére ez intelligens törlési és beszúrási műveletekkel lehetséges. Ennek azonban ára van: a beszúrások és törlések egy B+ fában O(log(N)). Néhányan ezért hallották ezt túl sok index használata nem jó ötlet. Igazán, lelassítja egy sor gyors beszúrását/frissítését/törlését egy táblázatbanmert az adatbázisnak frissítenie kell a tábla indexeit egy drága O(log(N)) művelettel minden indexhez. Ezenkívül az indexek hozzáadása nagyobb munkaterhelést jelent tranzakció menedzser (a cikk végén lesz leírva).

További részletekért tekintse meg a Wikipédia cikkét B+Fa. Ha példát szeretne a B+Tree megvalósítására egy adatbázisban, nézze meg ez a cikk и ez a cikk egy vezető MySQL fejlesztőtől. Mindkettő arra összpontosít, hogy az InnoDB (a MySQL-motor) hogyan kezeli az indexeket.

Megjegyzés: Egy olvasó azt mondta, hogy az alacsony szintű optimalizálás miatt a B+ fának teljesen kiegyensúlyozottnak kell lennie.

Hashtable

Az utolsó fontos adatszerkezetünk a hash tábla. Ez nagyon hasznos, ha gyorsan szeretne kikeresni értékeket. Ezen túlmenően a hash tábla megértése segít nekünk a későbbiekben megérteni egy közös adatbázis-illesztési műveletet, amelyet hash join-nak neveznek ( hash csatlakozás). Ezt az adatstruktúrát használja az adatbázis bizonyos belső dolgok tárolására is (pl. zár asztal vagy puffer medence, mindkét fogalmat később látni fogjuk).

A hash tábla olyan adatstruktúra, amely kulcsa alapján gyorsan megtalál egy elemet. Hash tábla készítéséhez meg kell határoznia:

• a kulcs az elemeidért
• hash függvény kulcsokhoz. A kiszámított kulcskivonatok megadják az elemek helyét (úgynevezett szegmensek ).
• funkció a billentyűk összehasonlítására. Miután megtalálta a megfelelő szegmenst, meg kell találnia a keresett elemet a szegmensen belül ezzel az összehasonlítással.

Egyszerű példa

Vegyünk egy világos példát:

Ez a hash táblázat 10 szegmensből áll. Mivel lusta vagyok, csak 5 szegmenst képzeltem el, de tudom, hogy okos vagy, ezért hagyom, hogy a másik 5-öt egyedül képzeld el. A kulcs modulo 10 hash függvényét használtam. Más szóval, csak az elem kulcsának utolsó számjegyét tárolom, hogy megtaláljam a szegmensét:

• ha az utolsó számjegy 0, az elem a 0 szegmensbe esik,
• ha az utolsó számjegy 1, az elem a 1 szegmensbe esik,
• ha az utolsó számjegy 2, az elem a 2-es területre esik,
• ...

Az általam használt összehasonlító függvény egyszerűen két egész szám egyenlősége.

Tegyük fel, hogy a 78-as elemet szeretné megszerezni:

• A hash tábla kiszámítja a 78 hash kódot, ami 8.
• A hash-tábla a 8-as szegmenst nézi, és az első talált elem a 78.
• Visszaküldi Önnek a 78-as tételt
• A keresés mindössze 2 műveletbe kerül (az egyik a hash érték kiszámításához, a másik pedig a szegmensen belüli elem megkereséséhez).

Most tegyük fel, hogy szeretné megszerezni az 59-es elemet:

• A hash tábla kiszámítja a 59 hash kódot, ami 9.
• A hash tábla a 9. szegmensben keres, az első talált elem a 99. Mivel 99!=59, a 99 elem nem érvényes elem.
• Ugyanezt a logikát alkalmazva a második elemet (9), a harmadikat (79), ..., az utolsót (29) veszik.
• Az elem nem található.
• A keresés 7 műveletbe került.

Jó hash funkció

Amint látja, a keresett értéktől függően a költség nem ugyanaz!

Ha most megváltoztatom a kulcs modulo 1 000 000 hash függvényét (azaz az utolsó 6 számjegyet veszem), a második keresés csak 1 műveletbe kerül, mivel a 000059 szegmensben nincsenek elemek. Az igazi kihívás az, hogy találjunk egy jó hash függvényt, amely nagyon kis számú elemet tartalmazó vödröket hoz létre.

Az én példámban könnyű egy jó hash függvényt találni. De ez egy egyszerű példa, a jó hash függvény megtalálása nehezebb, ha a kulcs a következő:

• karakterlánc (például - vezetéknév)
• 2 sor (például - vezetéknév és keresztnév)
• 2 sor és dátum (például - vezetéknév, keresztnév és születési dátum)
• ...

Jó hash funkcióval a hash tábla keresése O(1).

Tömb vs hash tábla

Miért nem használunk tömböt?

Hmm, jó kérdés.

• A hash tábla lehet részben betöltve a memóriába, és a fennmaradó szegmensek a lemezen maradhatnak.
• Egy tömb esetén a memóriában összefüggő helyet kell használni. Ha nagy asztalt tölt be nagyon nehéz elegendő egybefüggő teret találni.
• Kivonattábla esetén kiválaszthatja a kívánt kulcsot (például ország és személy vezetéknevét).

További információkért olvassa el a cikket JávaHashMap, amely egy hash tábla hatékony megvalósítása; nem kell értened a Java nyelvet ahhoz, hogy megértsd a cikkben tárgyalt fogalmakat.

Forrás: will.com