Hash táblázat elmagyarázva: mi ez és hogyan kell végrehajtani

A hash tábla, más néven hash map, olyan adatszerkezet, amely a kulcsokat leképezi az értékekre. A hashnak nevezett technika egyik része, a másik hash függvény. A hash függvény olyan algoritmus, amely indexet állít elő, ahol egy érték megtalálható vagy tárolható a hash táblázatban.

Néhány fontos megjegyzés a hash táblákról:

  1. Az értékeket nem tároljuk sorrendben.
  2. Ön a lehetséges ütközésekért felelős. Ez általában a láncolás nevű technikával történik. A láncolás egy összekapcsolt értéklista létrehozását jelenti, amelynek kulcsai egy bizonyos indexhez kapcsolódnak.

Hash tábla megvalósítása

A kivonatolás alapötlete az, hogy a kulcs / érték párokat szétosztja a hash tábla helyőrzőinek vagy "vödrének" tömbjén.

A hash tábla általában összekapcsolt listák tömbje. Ha kulcs / érték párot szeretne beszúrni, akkor először a hash függvényt kell használnia, hogy a kulcsot a hash tábla indexéhez társítsa. Ha egy kulcsot kap, a hash függvény javasolhat egy indexet, ahol az érték megtalálható vagy tárolható:

index = f(key, array_size)

Ez gyakran két lépésben történik:

hash = hashfunc(key) index = hash % array_size

A módszer használata hashfüggetlen a hash tábla méretétől. hashindexgé csökken - a 0, a tömb kezdete és a tömb array_size - 1vége közötti számra a modulo (%) operátor segítségével.

Vegye figyelembe a következő karakterláncot S:

string S = “ababcd”

Meg kell számolni az összes karakter gyakoriságát S. Ennek legegyszerűbb módja, ha végigvezetjük az összes lehetséges karaktert, és egyesével megszámoljuk az egyes gyakoriságokat.

Ez működik, de lassú - egy ilyen megközelítés időbeli összetettsége O (26 * N), Na karakterlánc mérete Smegszorozva az AZ 26 lehetséges karakterével.

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

Kimenet:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Vessünk egy pillantást a hash-t használó megoldásra.

Vegyünk egy tömböt, és a hash függvény segítségével kivonatoljuk a 26 lehetséges karaktert a tömb indexeivel. Ezután ismételje meg Sés növelje a karakterlánc aktuális karakterének értékét az egyes karakterek megfelelő indexével.

Ennek a hash megközelítésnek a bonyolultsága O (N), ahol N a húr mérete.

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

Kimenet

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Hash ütközések

Mivel a hash térkép valószínűleg lényegesen kisebb lesz, mint a feldolgozott adatok mennyisége, a hash ütközések elkerülhetetlenek. Az ütközések kezelésének két fő megközelítése van: a láncolás és a nyílt címzés .

Láncolás

Mint korábban említettük, a láncolás azt jelenti, hogy a kivonat tábla minden kulcs / érték párja az érték összekapcsolt adatok listája, nem pedig egyetlen cella.

Képzeljük el például, hogy a 152 kulcs a "John Smith" értéket tartja. Ha a "Sandra Dee" értéket hozzáadjuk ugyanahhoz a kulcshoz, akkor a "Sandra Dee" -t további elemként hozzáadjuk a 152-es kulcshoz, közvetlenül a "John Smith" után.

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

A láncolás fő hátránya az idő összetettségének növekedése. 0 (1) helyett, mint egy szokásos hash-táblánál, minden keresés több időt vesz igénybe, mivel minden egyes összekapcsolt listát be kell haladnunk a helyes érték megtalálásához.

Nyitott címzés

A nyitott címzés azt jelenti, hogy ha egy értéket egy már foglalt kulcshoz hozzárendelünk, addig mozogunk a hash tábla kulcsain, amíg meg nem találunk egy üreset. Például, ha a "John Smith" -et 152-re térképezték fel, akkor a "Sandra Dee" a következő nyitott indexhez kerül:

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

A nyitott címzés fő hátránya, hogy az értékek megkeresésekor előfordulhat, hogy nem azok a kulcstérképek szerepelnek, amelyeken elvárja őket. Ehelyett meg kell haladnia a hash-tábla különböző részein, hogy megtalálja a kívánt értéket.