Co je hashing?
Hash je hodnota, která má pevnou délku a je generována pomocí matematického vzorce. Hodnoty hash se používají při kompresi dat, kryptologii atd. V indexaci dat se používají hodnoty hash, protože mají pevnou velikost délky bez ohledu na hodnoty, které byly použity k jejich generování. Vytváří hodnoty hash, které zabírají minimální prostor ve srovnání s jinými hodnotami různých délek.
Hašovací funkce využívá matematický algoritmus k převodu klíče na hash. Ke kolizi dochází, když funkce hash produkuje stejnou hodnotu hash pro více než jeden klíč.
V tomto výukovém programu Algoritmus se naučíte:
- Co je hashing?
- Co je hashovací stůl?
- Funkce hash
- Vlastnosti dobré hashovací funkce
- Kolize
- Operace tabulky hash
- Příklad hash tabulky Python
- Vysvětlení kódu tabulky hash
- Příklad slovníku Pythonu
- Analýza složitosti
- Skutečné aplikace
- Výhody hash tabulek
- Nevýhody hash tabulek
Co je hashovací stůl?
Hash tabulka je datová struktura, která ukládá hodnoty pomocí dvojice klíčů a hodnot. Každá hodnota má přiřazen jedinečný klíč, který je generován pomocí hashovací funkce.
Název klíče se používá pro přístup k jeho přidružené hodnotě. Díky tomu je hledání hodnot v hash tabulce velmi rychlé, bez ohledu na počet položek v hash tabulce.
Funkce hash
Například pokud chceme ukládat záznamy o zaměstnancích a každý zaměstnanec je jednoznačně identifikován pomocí čísla zaměstnance.
Jako klíč můžeme použít číslo zaměstnance a jako hodnotu přiřadit údaje o zaměstnancích.
Výše uvedený přístup bude vyžadovat další volné místo v řádu (m * n 2 ), kde proměnná m je velikost pole a proměnná n je počet číslic pro číslo zaměstnance. Tento přístup představuje problém s úložným prostorem.
Funkce hash řeší výše uvedený problém získáním čísla zaměstnance a jeho použitím ke generování celočíselné hodnoty hash, pevných číslic a optimalizaci úložného prostoru. Účelem hashovací funkce je vytvořit klíč, který se použije k odkazu na hodnotu, kterou chceme uložit. Funkce přijímá hodnotu, která má být uložena, a pak pomocí algoritmu vypočítá hodnotu klíče.
Následuje příklad jednoduché hashovací funkce
h(k) = k1 % m
TADY,
- h (k) je hashovací funkce, která přijímá parametr k. Parametr k je hodnota, pro kterou chceme vypočítat klíč.
- k 1 % m je algoritmus pro naši hashovací funkci, kde k1 je hodnota, kterou chceme uložit, a m je velikost seznamu. K výpočtu klíče používáme operátor modulu.
Příklad
Předpokládejme, že máme seznam s pevnou velikostí 3 a následujícími hodnotami
[1,2,3]
Můžeme použít výše uvedený vzorec k výpočtu pozic, které by každá hodnota měla zaujímat.
Následující obrázek ukazuje dostupné indexy v naší hash tabulce.
Krok 1)
Vypočítejte pozici, která bude takto obsazena první hodnotou
h (1) = 1% 3
= 1
Hodnota 1 zabírá prostor na indexu 1
Krok 2)
Vypočítejte pozici, která bude obsazena druhou hodnotou
h (2) = 2% 3
= 2
Hodnota 2 zabírá prostor na indexu 2
Krok 3)
Vypočítejte pozici, která bude obsazena třetí hodnotou.
h (3) = 3% 3
= 0
Hodnota 3 zabírá prostor na indexu 0
Konečný výsledek
Naše vyplněná hash tabulka bude nyní následující.
Vlastnosti dobré hashovací funkce
Dobrá hashovací funkce by měla mít následující vlastnosti.
- Vzorec pro generování hodnoty hash by měl používat hodnotu dat, která má být uložena v algoritmu.
- Funkce hash by měla generovat jedinečné hodnoty hash i pro vstupní data, která mají stejné množství.
- Funkce by měla minimalizovat počet kolizí. Ke kolizím dochází, když je generována stejná hodnota pro více než jednu hodnotu.
- Hodnoty musí být distribuovány konzistentně do všech možných hashů.
Kolize
Ke kolizi dojde, když algoritmus generuje stejný hash pro více než jednu hodnotu.
Podívejme se na příklad.
Předpokládejme, že máme následující seznam hodnot
[3,2,9,11,7]
Předpokládejme, že velikost hashovací tabulky je 7 a použijeme vzorec (k 1 % m), kde m je velikost hashovací tabulky.
V následující tabulce jsou uvedeny hodnoty hash, které budou generovány.
| Klíč | Algoritmus hash (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 |
Jak vidíme z výše uvedených výsledků, hodnoty 2 a 9 mají stejnou hodnotu hash a na každou pozici nemůžeme uložit více než jednu hodnotu.
Daný problém lze vyřešit buď pomocí řetězení nebo sondování. Následující části podrobně pojednávají o řetězení a sondování.
Řetězení
Řetězení je technika, která se používá k řešení problému kolize pomocí propojených seznamů, z nichž každý má jedinečné indexy.
Následující obrázek vizualizuje, jak vypadá zřetězený seznam
Obě 2 a 9 zabírají stejný index, ale jsou uloženy jako propojené seznamy. Každý seznam má jedinečný identifikátor.
Výhody zřetězených seznamů
Výhody zřetězených seznamů jsou následující:
- Zřetězené seznamy mají při vkládání dat lepší výkon, protože pořadí vložení je O (1).
- Není nutné měnit velikost hashovací tabulky, která používá zřetězený seznam.
- Může snadno pojmout velké množství hodnot, pokud je k dispozici volné místo.
Sondování
Další technikou, která se používá k řešení kolize, je sondování. Při použití metody sondování, pokud dojde ke kolizi, můžeme jednoduše přejít a najít prázdný slot pro uložení naší hodnoty.
Metody sondování jsou následující:
| Metoda | Popis |
| Lineární snímání | Stejně jako název napovídá, tato metoda hledá prázdné sloty lineárně počínaje od místa, kde ke kolizi došlo, a pohybuje se vpřed. Pokud je dosaženo konce seznamu a není nalezen žádný prázdný slot. Sondování začíná na začátku seznamu. |
| Kvadratické sondování | Tato metoda používá kvadratické polynomické výrazy k vyhledání dalšího dostupného volného bloku. |
| Double Hashing | Tato technika používá sekundární algoritmus hash funkce k vyhledání dalšího volného dostupného slotu. |
Pomocí našeho výše uvedeného příkladu by se hash tabulka po použití sondování objevila takto:
Operace tabulky hash
Tady jsou operace podporované tabulkami hash:
- Vložení - tato operace se používá k přidání prvku do hash tabulky
- Hledání - tato operace se používá k vyhledání prvků v hash tabulce pomocí klíče
- Odstranění - tato operace se používá k odstranění prvků z hash tabulky
Vkládání datových operací
Operace vložení se používá k ukládání hodnot do hash tabulky. Když je nová hodnota uložena v hašovací tabulce, je jí přiřazeno indexové číslo. Číslo indexu se vypočítá pomocí hashovací funkce. Funkce hash řeší všechny kolize, ke kterým dojde při výpočtu čísla indexu.
Vyhledejte datovou operaci
Vyhledávací operace se používá k vyhledání hodnot v hašovací tabulce pomocí indexového čísla. Operace hledání vrátí hodnotu, která je propojena s číslem indexu vyhledávání. Například pokud uložíme hodnotu 6 na index 2, vyhledávací operace s indexem číslo 2 vrátí hodnotu 6.
Operace mazání dat
Operace odstranění se používá k odebrání hodnoty z hash tabulky. Odstranění Operace se provádí pomocí indexového čísla. Po odstranění hodnoty se číslo indexu uvolní. Lze jej použít k uložení dalších hodnot pomocí operace vložení.
Implementace tabulky hash s příkladem Pythonu
Podívejme se na jednoduchý příklad, který vypočítá hodnotu hash klíče
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)}')
Vysvětlení kódu tabulky hash
TADY,
- Definuje funkci hash_key, která přijímá klíč parametrů am.
- K určení hodnoty hash používá jednoduchou operaci modulu
- Definuje proměnnou m, která je inicializována na hodnotu 7. Toto je velikost naší hash tabulky
- Vypočítá a vytiskne hodnotu hash 3
- Vypočítá a vytiskne hodnotu hash 2
- Vypočítá a vytiskne hodnotu hash 9
- Vypočítá a vytiskne hodnotu hash 11
- Vypočítá a vytiskne hodnotu hash 7
Spuštění výše uvedeného kódu vytvoří následující výsledky.
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
Příklad slovníku Pythonu
Python je dodáván s vestavěným datovým typem nazvaným Dictionary. Příkladem hash tabulky je slovník. Ukládá hodnoty pomocí dvojice klíčů a hodnot. Hodnoty hash se pro nás generují automaticky a jakékoli kolize se řeší pro nás na pozadí.
Následující příklad ukazuje, jak můžete použít datový typ slovníku v pythonu 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)
TADY,
- Definuje zaměstnance proměnné slovníku. Název klíče se používá k uložení hodnoty John Doe, věkové sklady 36 a pozice ukládá hodnotu Business Manager.
- Načte hodnotu názvu klíče a vytiskne ji v terminálu
- Aktualizuje hodnotu pozice klíče na hodnotu Software Engineer
- Vytiskne hodnoty názvu a pozice klíče
- Odstraní všechny hodnoty, které jsou uloženy v naší proměnné slovníku zaměstnanec
- Vytiskne hodnotu zaměstnance
Spuštění výše uvedeného kódu vytvoří následující výsledky.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Analýza složitosti
Hash tabulky mají v nejlepším případě průměrnou časovou složitost O (1). Nejhorší časová složitost je O (n). Nejhorší scénář nastane, když mnoho hodnot vygeneruje stejný hash klíč a my musíme vyřešit kolizi sondováním.
Skutečné aplikace
V reálném světě se hash tabulky používají k ukládání dat pro
- Databáze
- Asociativní pole
- Sady
- Vyrovnávací paměť
Výhody hash tabulek
Zde jsou výhody / výhody používání hash tabulek:
- Hash tabulky mají vysoký výkon při vyhledávání dat, vkládání a mazání stávajících hodnot.
- Časová složitost hash tabulek je konstantní bez ohledu na počet položek v tabulce.
- Vystupují velmi dobře i při práci s velkými datovými sadami.
Nevýhody hash tabulek
Zde jsou nevýhody použití hash tabulek:
- Jako klíč nemůžete použít nulovou hodnotu.
- Při generování klíčů pomocí nelze zabránit kolizím. hashovací funkce. Ke kolizím dochází při generování klíče, který se již používá.
- Pokud má hashovací funkce mnoho kolizí, může to vést ke snížení výkonu.
Souhrn:
- Hash tabulky se používají k ukládání dat pomocí dvojice klíčů a hodnot.
- Hašovací funkce používá matematický algoritmus k výpočtu hodnoty hash.
- Ke kolizi dojde, když je pro více než jednu hodnotu generována stejná hodnota hash.
- Řetězení řeší kolize vytvářením propojených seznamů.
- Sondování řeší kolizi hledáním prázdných slotů v hash tabulce.
- Lineární sondování vyhledá další volný slot a uloží hodnotu počínaje od slotu, kde došlo ke kolizi.
- Kvadratické snímání používá polynomiální výrazy k vyhledání dalšího volného slotu, když dojde ke kolizi.
- Double hashing používá sekundární algoritmus hash funkce k vyhledání dalšího volného slotu, když dojde ke kolizi.
- Hash tabulky mají lepší výkon ve srovnání s jinými datovými strukturami.
- Průměrná časová složitost hash tabulek je O (1)
- Příkladem hašovací tabulky je datový typ slovníku v pythonu.
- Hash tabulky podporují operace vkládání, hledání a mazání.
- Hodnotu null nelze použít jako hodnotu indexu.
- Při hašovacích funkcích nelze zabránit kolizím. Dobrá hashovací funkce minimalizuje počet kolizí, které se vyskytnou, aby se zlepšil výkon.