Čo je hashing?
Hash je hodnota, ktorá má pevnú dĺžku a je generovaná pomocou matematického vzorca. Hašovacie hodnoty sa používajú pri kompresii údajov, kryptológii atď. V indexácii údajov sa používajú hašovacie hodnoty, pretože majú pevnú veľkosť dĺžky bez ohľadu na hodnoty, ktoré sa použili na ich generovanie. Vytvára hodnoty hash, ktoré zaberajú minimálny priestor v porovnaní s inými hodnotami rôznych dĺžok.
Hašovacia funkcia využíva matematický algoritmus na premenu kľúča na hash. Ku kolízii dôjde, keď funkcia hash vytvorí rovnakú hodnotu hash pre viac ako jeden kľúč.
V tomto výučbe algoritmu sa dozviete:
- Čo je hashing?
- Čo je to hashovací stôl?
- Hašovacie funkcie
- Vlastnosti dobrej hashovacej funkcie
- Zrážka
- Operácie tabuľky hash
- Príklad hash tabuľky Python
- Vysvetlenie kódu tabuľky hash
- Príklad slovníka Python
- Analýza zložitosti
- Skutočné aplikácie
- Výhody hash tabuliek
- Nevýhody hash tabuliek
Čo je to hashovací stôl?
Hash tabuľka je dátová štruktúra, ktorá ukladá hodnoty pomocou dvojice kľúčov a hodnôt. Každej hodnote je priradený jedinečný kľúč, ktorý sa generuje pomocou hashovacej funkcie.
Názov kľúča sa používa na prístup k jeho priradenej hodnote. Vďaka tomu je vyhľadávanie hodnôt v hashovacej tabuľke veľmi rýchle, bez ohľadu na počet položiek v hashovacej tabuľke.
Hašovacie funkcie
Napríklad, ak chceme ukladať záznamy zamestnancov, a každý zamestnanec je jedinečne identifikovaný pomocou čísla zamestnanca.
Ako kľúč môžeme použiť číslo zamestnanca a ako hodnotu priradiť údaje o zamestnancovi.
Vyššie uvedený prístup bude vyžadovať extra voľný priestor rádovo (m * n 2 ), kde premenná m je veľkosť poľa a premenná n je počet číslic pre číslo zamestnanca. Tento prístup predstavuje problém s úložným priestorom.
Hašovacia funkcia rieši vyššie uvedený problém získaním čísla zamestnanca a jeho použitím na vygenerovanie celočíselnej hodnoty hash, pevných číslic a optimalizácie úložného priestoru. Účelom hashovacej funkcie je vytvoriť kľúč, ktorý sa použije na odkazovanie na hodnotu, ktorú chceme uložiť. Funkcia akceptuje hodnotu, ktorá sa má uložiť, potom použije algoritmus na výpočet hodnoty kľúča.
Nasleduje príklad jednoduchej hashovacej funkcie
h(k) = k1 % m
TU,
- h (k) je hashovacia funkcia, ktorá akceptuje parameter k. Parameter k je hodnota, pre ktorú chceme vypočítať kľúč.
- k 1 % m je algoritmus pre našu hashovaciu funkciu, kde k1 je hodnota, ktorú chceme uložiť, a m je veľkosť zoznamu. Na výpočet kľúča používame operátor modulu.
Príklad
Predpokladajme, že máme zoznam s pevnou veľkosťou 3 a nasledujúcimi hodnotami
[1,2,3]
Vyššie uvedený vzorec môžeme použiť na výpočet pozícií, ktoré by mala každá hodnota obsadzovať.
Nasledujúci obrázok zobrazuje dostupné indexy v našej hašovacej tabuľke.
Krok 1)
Vypočítajte pozíciu, ktorá bude takto obsadená prvou hodnotou
h (1) = 1% 3
= 1
Hodnota 1 zaberie miesto v indexe 1
Krok 2)
Vypočítajte pozíciu, ktorá bude obsadená druhou hodnotou
h (2) = 2% 3
= 2
Hodnota 2 zaberie miesto v indexe 2
Krok 3)
Vypočítajte pozíciu, ktorá bude obsadená treťou hodnotou.
h (3) = 3% 3
= 0
Hodnota 3 zaberie miesto na indexe 0
Konečný výsledok
Naša vyplnená hash tabuľka bude teraz nasledovná.
Vlastnosti dobrej hashovacej funkcie
Dobrá funkcia hash by mala mať nasledujúce vlastnosti.
- Vzorec na generovanie hodnoty hash by mal používať hodnotu údajov, ktorá sa má uložiť v algoritme.
- Funkcia hash by mala generovať jedinečné hodnoty hash aj pre vstupné údaje, ktoré majú rovnaké množstvo.
- Funkcia by mala minimalizovať počet kolízií. K kolíziám dôjde, keď je rovnaká hodnota generovaná pre viac ako jednu hodnotu.
- Hodnoty musia byť distribuované konzistentne medzi všetky možné hašovania.
Zrážka
Ku kolízii dôjde, keď algoritmus vygeneruje rovnaký hash pre viac ako jednu hodnotu.
Pozrime sa na príklad.
Predpokladajme, že máme nasledujúci zoznam hodnôt
[3,2,9,11,7]
Predpokladajme, že veľkosť hashovacej tabuľky je 7 a použijeme vzorec (k 1 % m), kde m je veľkosť hashovacej tabuľky.
Nasledujúca tabuľka zobrazuje hodnoty hash, ktoré sa vygenerujú.
| Kľúč | Hašovací algoritmus (k 1 % m) | Hodnota hash |
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11 | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
Ako vidíme z vyššie uvedených výsledkov, hodnoty 2 a 9 majú rovnakú hodnotu hash a na každú pozíciu nemôžeme uložiť viac ako jednu hodnotu.
Daný problém je možné vyriešiť buď pomocou reťazenia alebo sondovania. Nasledujúce časti podrobne pojednávajú o reťazení a sondovaní.
Reťazenie
Reťazenie je technika, ktorá sa používa na riešenie problému kolízie pomocou prepojených zoznamov, z ktorých každý má jedinečné indexy.
Nasledujúci obrázok predstavuje, ako vyzerá reťazený zoznam
Čísla 2 a 9 zaberajú rovnaký index, ale sú uložené ako prepojené zoznamy. Každý zoznam má jedinečný identifikátor.
Výhody reťazených zoznamov
Výhody reťazených zoznamov sú nasledujúce:
- Reťazené zoznamy majú pri vkladaní údajov lepší výkon, pretože poradie vloženia je O (1).
- Nie je potrebné meniť veľkosť hashovacej tabuľky, ktorá používa zreťazený zoznam.
- Môže ľahko prispôsobiť veľké množstvo hodnôt, pokiaľ je k dispozícii voľné miesto.
Sondovanie
Ďalšou technikou, ktorá sa používa na riešenie kolízie, je sondovanie. Ak pri použití metódy sondovania dôjde ku kolízii, môžeme jednoducho pokračovať ďalej a nájsť prázdny slot na uloženie našej hodnoty.
Nasledujú metódy sondovania:
| Metóda | Popis |
| Lineárne sondovanie | Rovnako ako názov napovedá, táto metóda vyhľadáva prázdne sloty lineárne počnúc od polohy, kde ku kolízii došlo, a pohybuje sa vpred. Ak dôjde na koniec zoznamu a nenájde sa žiadny prázdny slot. Sondovanie sa začína na začiatku zoznamu. |
| Kvadratické sondovanie | Táto metóda používa kvadratické polynomické výrazy na nájdenie ďalšieho dostupného voľného slotu. |
| Double Hashing | Táto technika používa sekundárny algoritmus hash funkcie na nájdenie ďalšieho voľného dostupného slotu. |
Pomocou nášho vyššie uvedeného príkladu by sa hash tabuľka po použití sondovania javila takto:
Operácie tabuľky hash
Tu sú operácie podporované tabuľkami Hash:
- Vloženie - táto operácia sa používa na pridanie prvku do tabuľky hash
- Vyhľadávanie - táto operácia sa používa na hľadanie prvkov v hashovacej tabuľke pomocou klávesu
- Vymazanie - táto operácia sa používa na odstránenie prvkov z hashovacej tabuľky
Operácia vkladania údajov
Operácia vloženia sa používa na ukladanie hodnôt do hashovacej tabuľky. Keď sa do hashovacej tabuľky uloží nová hodnota, priradí sa jej indexové číslo. Číslo indexu sa počíta pomocou hashovacej funkcie. Hašovacia funkcia rieši všetky kolízie, ku ktorým dôjde pri výpočte čísla indexu.
Vyhľadajte dátovú operáciu
Operácia vyhľadávania sa používa na vyhľadanie hodnôt v hashovacej tabuľke pomocou indexového čísla. Operácia vyhľadávania vráti hodnotu, ktorá je spojená s číslom indexu vyhľadávania. Napríklad, ak uložíme hodnotu 6 na index 2, operácia vyhľadávania s indexom číslo 2 vráti hodnotu 6.
Operácia odstránenia údajov
Operácia mazania sa používa na odstránenie hodnoty z hashovacej tabuľky. Vymazanie Operácia sa vykonáva pomocou indexového čísla. Po odstránení hodnoty sa indexové číslo uvoľní. Môže sa použiť na uloženie ďalších hodnôt pomocou operácie vloženia.
Implementácia tabuľky hash s príkladom Pythonu
Pozrime sa na jednoduchý príklad, ktorý počíta hodnotu hash kľúča
def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')
Vysvetlenie kódu tabuľky hash
TU,
- Definuje funkciu hash_key, ktorá akceptuje kľúč parametrov am.
- Na určenie hodnoty hash použije jednoduchú operáciu modulu
- Definuje premennú m, ktorá je inicializovaná na hodnotu 7. Toto je veľkosť našej hash tabuľky
- Vypočíta a vytlačí hodnotu hash 3
- Vypočíta a vytlačí hodnotu hash 2
- Vypočíta a vytlačí hodnotu hash 9
- Vypočíta a vytlačí hodnotu hash 11
- Vypočíta a vytlačí hodnotu hash 7
Vykonanie vyššie uvedeného kódu vedie k nasledujúcim výsledkom.
The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0
Príklad slovníka Python
Python je dodávaný so zabudovaným dátovým typom s názvom Slovník. Príkladom hashovacej tabuľky je slovník. Hodnoty ukladá pomocou dvojice kľúčov a hodnôt. Hodnoty hash sa pre nás generujú automaticky a akékoľvek kolízie sa pre nás riešia na pozadí.
Nasledujúci príklad ukazuje, ako môžete použiť dátový typ slovníka v pythone 3
employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)
TU,
- Definuje premennú slovníka zamestnanec. Názov kľúča sa používa na ukladanie hodnoty John Doe, vekových skladov 36 a pozícií na ukladanie hodnoty obchodný manažér.
- Načíta hodnotu názvu kľúča a vytlačí ho v termináli
- Aktualizuje hodnotu pozície kľúča na hodnotu Softvérový inžinier
- Vytlačí hodnoty názvu a polohy kľúčov
- Vymaže všetky hodnoty, ktoré sú uložené v našej premennej slovníka zamestnanec
- Vytlačí hodnotu zamestnanca
Spustenie vyššie uvedeného kódu prinesie nasledujúce výsledky.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Analýza zložitosti
Hašovacie tabuľky majú v najlepšom prípade priemernú časovú zložitosť O (1). Najhoršia časová zložitosť je O (n). Najhorší scenár nastane, keď veľa hodnôt vygeneruje rovnaký hash kľúč a my musíme kolíziu vyriešiť sondovaním.
Skutočné aplikácie
V skutočnom svete sa hašovacie tabuľky používajú na ukladanie údajov pre
- Databázy
- Asociatívne polia
- Sady
- Vyrovnávacia pamäť
Výhody hash tabuliek
Tu sú výhody a výhody použitia hash tabuliek:
- Hašovacie tabuľky majú vysoký výkon pri vyhľadávaní údajov, vkladaní a odstraňovaní existujúcich hodnôt.
- Časová zložitosť hash tabuliek je konštantná bez ohľadu na počet položiek v tabuľke.
- Majú veľmi dobrý výkon, aj keď pracujú s veľkými súbormi údajov.
Nevýhody hash tabuliek
Tu sú nevýhody použitia hash tabuliek:
- Ako kľúč nemôžete použiť nulovú hodnotu.
- Kolíziám sa nedá vyhnúť pri generovaní kľúčov pomocou. hašovacie funkcie. Pri generovaní kľúča, ktorý sa už používa, dôjde ku kolízii.
- Ak má funkcia hash veľa kolízií, môže to viesť k zníženiu výkonu.
Zhrnutie:
- Hašovacie tabuľky sa používajú na ukladanie údajov pomocou dvojice kľúčov a hodnôt.
- Hašovacia funkcia používa na výpočet hašovacej hodnoty matematický algoritmus.
- Ku kolízii dôjde, keď sa pre viac ako jednu hodnotu vygeneruje rovnaká hodnota hash.
- Reťazenie rieši kolíziu vytvorením prepojených zoznamov.
- Sondovanie rieši kolíziu nájdením prázdnych slotov v hashovacej tabuľke.
- Lineárne sondovanie vyhľadá ďalší voľný blok, aby uložila hodnotu začínajúcu od bloku, kde došlo ku kolízii.
- Kvadratické sondovanie používa polynomické výrazy na nájdenie ďalšieho voľného slotu, keď dôjde ku kolízii.
- Double hash používa sekundárny algoritmus hash funkcie na nájdenie ďalšieho voľného slotu, keď dôjde ku kolízii.
- Hašovacie tabuľky majú lepší výkon v porovnaní s inými dátovými štruktúrami.
- Priemerná časová zložitosť hash tabuliek je O (1)
- Príkladom hašovacej tabuľky je dátový typ slovníka v pythone.
- Tabuľky hash podporujú operácie vkladania, vyhľadávania a mazania.
- Nulovú hodnotu nie je možné použiť ako hodnotu indexu.
- Kolíziám sa nedá vyhnúť pri hašovacích funkciách. Dobrá funkcia hash minimalizuje počet kolízií, ktoré sa vyskytnú, aby sa zlepšil výkon.