Tabulka hash v datové struktuře: Python Příklad

Od: Sarah Chen Sarah Chen
Hours aktualizováno

Co je hashování?

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 indexování dat se hodnoty hash používají, protože mají pevnou délku bez ohledu na hodnoty, které byly použity k jejich generování. Hodnoty hash zabírají minimální prostor ve srovnání s jinými hodnotami různé délky.

Hašovací funkce využívá matematický algoritmus k převodu klíče na hash. Ke kolizi dojde, když hashovací funkce vytvoří stejnou hodnotu hash pro více než jeden klíč.

Co je hash tabulka?

A HASH TABULKA je datová struktura, která ukládá hodnoty pomocí dvojice klíčů a hodnot. Každé hodnotě je přiřazen jedinečný klíč, který je generován pomocí hashovací funkce.

Název klíče se používá pro přístup k přidružené hodnotě. Díky tomu je vyhledávání hodnot v hašovací tabulce velmi rychlé, bez ohledu na počet položek v hašovací tabulce.

Hašovací funkce

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ěstnanci.

Výše uvedený přístup bude vyžadovat další volné místo v řádu jednotek (m * n2) kde proměnná m je velikost řadaa proměnná n je počet číslic pro číslo zaměstnance. Tento přístup představuje problém s úložným prostorem.

Hashovací funkce řeší výše uvedený problém získáním čísla zaměstnance a jeho použitím ke generování hodnoty hash celého čísla, pevných číslic a optimalizuje úložný prostor. Účelem hashovací funkce je vytvořit klíč, který bude použit k odkazování na hodnotu, kterou chceme uložit. Funkce přijme hodnotu, která se má uložit, a poté použije algoritmus k výpočtu hodnoty 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íč.
  • k1 % m je algoritmus pro naši hašovací funkci, kde k1 je hodnota, kterou chceme uložit, a m je velikost seznamu. K výpočtu klíče používáme modulový operátor.

Příklad

Předpokládejme, že máme seznam s pevnou velikostí 3 a následujícími hodnotami

[1,2,3]

Výše uvedený vzorec můžeme použít k výpočtu pozic, které by měla každá hodnota zaujímat.

Následující obrázek ukazuje dostupné indexy v naší hashovací tabulce.

Hash funkce

Krok 1) Vypočítejte pozici, která bude obsazena první hodnotou takto

h(1) = 1 % 3

= 1

Hodnota 1 obsadí prostor na index 1

Krok 2) Vypočítejte pozici, která bude obsazena druhou hodnotou

h(2) = 2 % 3

= 2

Hodnota 2 obsadí prostor na index 2

Krok 3) Vypočítejte pozici, která bude obsazena třetí hodnotou.

h(3) = 3 % 3

= 0

Hodnota 3 obsadí prostor na index 0

Konečný výsledek

Naše vyplněná hash tabulka bude nyní vypadat následovně.

Hash funkce

SOUVISEJÍCÍ ČLÁNKY

Vlastnosti dobré hashovací funkce

Dobrá hašovací funkce by měla mít následující vlastnosti.

  • Vzorec pro generování hashe by měl používat hodnotu dat, která mají být uložena v algoritmu.
  • Hašovací funkce by měla generovat jedinečné hašovací hodnoty i pro vstupní data, která mají stejné množství.
  • Funkce by měla minimalizovat počet kolizí. Ke kolizím dochází, když je stejná hodnota generována pro více než jednu hodnotu.
  • Hodnoty musí být distribuovány konzistentně v rámci všech možných hashů.

Srážka

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 (k1 % m), kde m je velikost hashovací tabulky.

Následující tabulka ukazuje hodnoty hash, které budou vygenerovány.

Klíč Algoritmus hash (k1 % 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 hash hodnotu a na každé 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 snímá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 znázorňuje, jak vypadá zřetězený seznam

Řetězení

2 i 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í lepší výkon při vkládání dat, protože pořadí vkládání je O(1).
  • Není nutné měnit velikost hash 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 vyřešení kolize, je sondování. Při použití metody sondování, pokud dojde ke kolizi, můžeme jednoduše pokračovat a najít prázdný slot pro uložení naší hodnoty.

Zde jsou metody sondování:

Metoda Description
Lineární sondování Jak název napovídá, tato metoda vyhledává prázdné sloty lineárně od místa, kde došlo ke kolizi, a postupuje vpřed. Pokud je dosaženo konce seznamu a není nalezen žádný prázdný slot. Snímání začíná na začátku seznamu.
Kvadratické sondování Tato metoda používá kvadratické polynomiální výrazy k nalezení dalšího volného slotu.
Double Hashing Tato technika používá algoritmus sekundární hašovací funkce k nalezení dalšího volného dostupného slotu.

V našem výše uvedeném příkladu by hashovací tabulka po použití sondování vypadala takto:

Sondování

Operace hashovací tabulky

Tady jsou Operationy podporované hashovacími tabulkami:

  • Vložení - tento Operation se používá k přidání prvku do hash tabulky
  • Vyhledávání - tento Operation se používá k vyhledávání prvků v hash tabulce pomocí klíče
  • mazání - tento Operation se používá k odstranění prvků z hash tabulky

Operace vkládání dat

Operace vložení se používá k uložení hodnot do hashovací tabulky. Když je do hashovací tabulky uložena nová hodnota, je jí přiděleno indexové číslo. Indexové číslo se vypočítá pomocí hashovací funkce. Hašovací funkce řeší všechny kolize, které nastanou při výpočtu indexového čísla.

Vyhledejte datovou operaci

Operace vyhledávání se používá k vyhledání hodnot v tabulce hash pomocí čísla indexu. Operace vyhledávání vrátí hodnotu, která je spojena s číslem indexu vyhledávání. Pokud například uložíme hodnotu 6 do indexu 2, vyhledávací operace s číslem indexu 2 vrátí hodnotu 6.

Operace smazání dat

Operace odstranění se používá k odstranění hodnoty z hašovací tabulky. Chcete-li odstranit Operase provádí pomocí indexového čísla. Jakmile je hodnota vymazána, indexové číslo se uvolní. Lze jej použít k uložení dalších hodnot pomocí operace vložení.

Implementace hash tabulky s Python Příklad

Podívejme se na jednoduchý příklad, který vypočítá hash hodnotu klíče

def hash_key( key, m):
    return key % m


m = 7

print(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 hash tabulky

Vysvětlení kódu hash tabulky

TADY,

  1. Definuje funkci hash_key, která přijímá parametry key am.
  2. K určení hodnoty hash používá jednoduchou modulovou operaci
  3. Definuje proměnnou m, která je inicializována na hodnotu 7. Toto je velikost naší hashovací tabulky
  4. Vypočítá a vytiskne hash hodnotu 3
  5. Vypočítá a vytiskne hash hodnotu 2
  6. Vypočítá a vytiskne hash hodnotu 9
  7. Vypočítá a vytiskne hash hodnotu 11
  8. Vypočítá a vytiskne hash hodnotu 7

Provedení výše uvedeného kódu vede k následujícím výsledkům.

The hash value for 3 is 3
The hash value for 2 is 2
The hash value for 9 is 2
The hash value for 11 is 4
The hash value for 7 is 0

Python Příklad slovníku

Python přichází s vestavěným datovým typem s názvem Dictionary. Slovník je příkladem hashovací tabulky. Ukládá hodnoty pomocí dvojice klíčů a hodnot. Hodnoty hash jsou automaticky generovány za nás a případné kolize jsou řešeny za nás na pozadí.

Následující příklad ukazuje, jak můžete použít datový typ slovníku v python 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)

Python Příklad slovníku

TADY,

  1. Definuje slovníkovou proměnnou zaměstnanec. Název klíče se používá k uložení hodnoty John Doe, věk ukládá 36 a pozice ukládá hodnotu Business Manager.
  2. Načte hodnotu názvu klíče a vytiskne ji v terminálu
  3. Aktualizuje hodnotu pozice klíče na hodnotu Software Engineer
  4. Vytiskne hodnoty názvu a pozice klíčů
  5. Smaže všechny hodnoty, které jsou uloženy v našem slovníku proměnné zaměstnanec
  6. Vytiskne hodnotu zaměstnance

Spuštění výše uvedeného kódu poskytuje 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

Hashovací tabulky mají v nejlepším případě průměrnou časovou složitost O (1). Nejhorší případ časové složitosti je O(n). Nejhorší scénář nastane, když mnoho hodnot generuje stejný hash klíč a my musíme kolizi vyřešit sondováním.

Aplikace v reálném světě

V reálném světě se k ukládání dat používají hashovací tabulky

  • Databáze
  • Asociativní pole
  • soupravy
  • Mezipaměť

Výhody hashovacích tabulek

Zde jsou výhody/výhody používání hashovacích tabulek:

  • Hashovací tabulky mají vysoký výkon při vyhledávání dat, vkládání a mazání existujících hodnot.
  • Časová složitost pro hashovací tabulky je konstantní bez ohledu na počet položek v tabulce.
  • Pracují velmi dobře i při práci s velkými datovými sadami.

Nevýhody hashovacích tabulek

Zde jsou nevýhody použití hashovacích tabulek:

  • Jako klíč nelze použít hodnotu null.
  • Při generování klíčů pomocí kolizí se nelze vyhnout. hashovací funkce. Ke kolizím dochází, když je vygenerován klíč, který se již používá.
  • Pokud má hašovací funkce mnoho kolizí, může to vést ke snížení výkonu.

Shrnutí

  • Hash tabulky se používají k ukládání dat pomocí dvojice klíčů a hodnot.
  • Hašovací funkce používá k výpočtu hašovací hodnoty matematický algoritmus.
  • Ke kolizi dochází, když je stejná hodnota hash generována pro více než jednu hodnotu.
  • Řetězení řeší kolizi vytvořením propojených seznamů.
  • Sondování řeší kolizi nalezením prázdných slotů v hashovací tabulce.
  • Lineární sondování hledá další volný slot pro uložení hodnoty počínaje slotem, kde došlo ke kolizi.
  • Kvadratické sondování používá polynomiální výrazy k nalezení dalšího volného slotu, když dojde ke kolizi.
  • Double hašování používá algoritmus sekundární hašovací funkce k nalezení dalšího volného slotu, když dojde ke kolizi.
  • Hashovací tabulky mají lepší výkon ve srovnání s jinými datovými strukturami.
  • Průměrná časová složitost hashovacích tabulek je O (1)
  • Datový typ slovníku v pythonu je příkladem hashovací tabulky.
  • Hashovací tabulky podporují operace vkládání, vyhledávání a mazání.
  • Hodnotu null nelze použít jako hodnotu indexu.
  • V hašovacích funkcích se kolizím nelze vyhnout. Dobrá hašovací funkce minimalizuje počet kolizí, ke kterým dochází, aby se zlepšil výkon.

Máš rád: