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:
- Az értékeket nem tároljuk sorrendben.
- Ö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_sizeA 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 0Vessü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 0Hash ü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.