hash table c programs implement hash table
Tento výukový program vysvětluje hashovací tabulky C ++ a hashovací mapy. Dozvíte se také o aplikacích a implementaci tabulky Hash v C ++:
Hashing je technika, pomocí které můžeme pomocí „hash funkce“ mapovat velké množství dat na menší tabulku.
Pomocí hashovací techniky můžeme vyhledávat data rychleji a efektivněji ve srovnání s jinými vyhledávacími technikami, jako je lineární a binární vyhledávání.
Pojďme pochopit hashovací techniku s příkladem v tomto kurzu.
=> Přečtěte si sérii školení Easy C ++.
Co se naučíte:
Hašování v C ++
Vezměme si příklad univerzitní knihovny, která obsahuje tisíce knih. Knihy jsou uspořádány podle témat, oddělení atd. Každá sekce však bude mít mnoho knih, díky nimž bude hledání knih velmi obtížné.
Abychom tedy překonali tuto obtíž, přiřadíme každé knize jedinečné číslo nebo klíč, abychom okamžitě poznali umístění knihy. Toho je skutečně dosaženo hašováním.
Pokračujeme v našem příkladu z knihovny, namísto identifikace každé knihy na základě jejího oddělení, předmětu, sekce atd., Které mohou vést k velmi dlouhému řetězci, vypočítáme jedinečnou celočíselnou hodnotu nebo klíč pro každou knihu v knihovně pomocí jedinečné funkce a uložte tyto klíče do samostatné tabulky.
Výše uvedená jedinečná funkce se nazývá „Hash funkce“ a samostatná tabulka se nazývá „Hash Table“. Hašovací funkce se používá k mapování dané hodnoty na konkrétní jedinečný klíč v tabulce hash. Výsledkem je rychlejší přístup k prvkům. Čím efektivnější je hashovací funkce, tím efektivnější bude mapování každého prvku na jedinečný klíč.
Uvažujme hashovací funkci h (x) která mapuje hodnotu „ X ' v ' x% 10 “V poli. Pro daná data můžeme zkonstruovat hashovací tabulku obsahující klíče nebo hashovací kódy nebo hash, jak je znázorněno na následujícím diagramu.
Ve výše uvedeném diagramu vidíme, že položky v poli jsou mapovány na své pozice v hash tabulce pomocí hash funkce.
Můžeme tedy říci, že hašování je implementováno pomocí dvou kroků, jak je uvedeno níže:
# 1) Hodnota je převedena na jedinečný celočíselný klíč nebo hash pomocí funkce hash. Používá se jako index k uložení původního prvku, který spadá do hash tabulky.
Ve výše uvedeném diagramu je hodnota 1 v hash tabulce jedinečným klíčem k uložení prvku 1 z datového pole uvedeného na LHS diagramu.
#dva) Prvek z datového pole je uložen v hašovací tabulce, kde jej lze rychle načíst pomocí hashovaného klíče. Ve výše uvedeném diagramu jsme viděli, že jsme uložili všechny prvky do hash tabulky po výpočtu jejich příslušných míst pomocí hash funkce. Následující výrazy můžeme použít k načtení hodnot hash a indexu.
hash = hash_func(key) index = hash % array_sizeFunkce hash
Již jsme zmínili, že účinnost mapování závisí na účinnosti hash funkce, kterou používáme.
Hašovací funkce by v zásadě měla splňovat následující požadavky:
- Snadný výpočet: Funkce hash by měla být snadno vypočítatelná jedinečnými klávesami.
- Méně kolize: Když se prvky rovnají stejným klíčovým hodnotám, dojde ke kolizi. Ve funkci hash, která se používá, by měla být pokud možno minimální kolize. Vzhledem k tomu, že ke kolizím pravděpodobně dojde, musíme se o tyto kolize postarat pomocí vhodných technik řešení kolizí.
- Jednotná distribuce: Funkce hash by měla mít za následek rovnoměrné rozdělení dat napříč hašovací tabulkou a tím zabránit shlukování.
Tabulka hash C ++
Hash tabulka nebo hash mapa je datová struktura, která ukládá ukazatele na prvky původního datového pole.
V našem příkladu knihovny bude hash tabulka pro knihovnu obsahovat ukazatele na každou z knih v knihovně.
Mít položky v hash tabulce usnadňuje hledání konkrétního prvku v poli.
Jak již bylo vidět, hash tabulka používá hašovací funkci k výpočtu indexu do řady kbelíků nebo slotů, pomocí kterých lze najít požadovanou hodnotu.
Zvažte další příklad s následujícím datovým polem:
převaděč z youtube na wav ke stažení zdarma
Předpokládejme, že máme hashovací tabulku velikosti 10, jak je znázorněno níže:
Nyní použijeme hashovací funkci uvedenou níže.
Hash_code = Key_value % size_of_hash_tableTo se bude rovnat Hash_code = Key_value% 10
Pomocí výše uvedené funkce mapujeme klíčové hodnoty na umístění tabulky hash, jak je znázorněno níže.
| Datová položka | Funkce hash | Hash_kód |
|---|---|---|
| 22 | 22% 10 = 2 | dva |
| 25 | 25% 10 = 5 | 5 |
| 27 | 27% 10 = 7 | 7 |
| 46 | 46% 10 = 6 | 6 |
| 70 | 70% 10 = 0 | 0 |
| 89 | 89% 10 = 9 | 9 |
| 31 | 31% 10 = 1 | 1 |
Pomocí výše uvedené tabulky můžeme reprezentovat hashovací tabulku následujícím způsobem.
Když tedy potřebujeme přistupovat k prvku z hashovací tabulky, bude hledání trvat jen O (1).
Kolize
Obvykle vypočítáme hash kód pomocí hash funkce, abychom mohli namapovat hodnotu klíče na hash kód v hash tabulce. Ve výše uvedeném příkladu datového pole vložme hodnotu 12. V takovém případě bude hash_code pro klíčovou hodnotu 12 hodnotu 2. (12% 10 = 2).
Ale v hash tabulce již máme mapování na pár klíč – hodnota 22 pro hash_code 2, jak je znázorněno níže:
Jak je uvedeno výše, máme stejný hash kód pro dvě hodnoty, 12 a 22, tj. 2. Když se jedna nebo více klíčových hodnot rovná stejnému umístění, vede to ke kolizi. Místo hash kódu je tedy již obsazeno jednou hodnotou klíče a na stejném místě je třeba umístit další hodnotu klíče.
V případě hašování, i když máme hashovací tabulku velmi velké velikosti, pak tam musí být kolize. Je to proto, že obecně najdeme malou jedinečnou hodnotu pro velký klíč, a proto je zcela možné, aby jedna nebo více hodnot mělo v daném okamžiku stejný hash kód.
Vzhledem k tomu, že při hašování je srážka nevyhnutelná, měli bychom vždy hledat způsoby, jak srážce zabránit nebo ji vyřešit. Existují různé techniky řešení kolizí, které můžeme použít k vyřešení kolize, ke které dochází během hašování.
Techniky řešení kolizí
Následují techniky, které můžeme použít k vyřešení kolize v hash tabulce.
Samostatné řetězení (otevřené hashování)
Toto je nejběžnější technika řešení kolizí. Toto se také nazývá otevřené hashování a implementuje se pomocí propojeného seznamu.
jak otevřít binární soubor
V samostatné technice řetězení je každá položka v hash tabulce propojeným seznamem. Když se klíč shoduje s hashovacím kódem, je zapsán do seznamu odpovídajícího danému hashovacímu kódu. Takže když dva klíče mají stejný hash kód, pak se obě položky zadají do propojeného seznamu.
U výše uvedeného příkladu je níže uvedeno Samostatné řetězení.
Výše uvedený diagram představuje zřetězení. Zde používáme funkci mod (%). Vidíme, že když se dvě klíčové hodnoty rovnají stejnému hash kódu, spojíme tyto prvky s tímto hash kódem pomocí propojeného seznamu.
Pokud jsou klíče rovnoměrně rozloženy v hašovací tabulce, pak průměrné náklady na vyhledávání konkrétního klíče závisí na průměrném počtu klíčů v tomto propojeném seznamu. Samostatné zřetězení tedy zůstává účinné, i když dojde ke zvýšení počtu vstupů než slotů.
Nejhorší případ pro samostatné zřetězení je, když se všechny klíče rovnají stejnému hash kódu a jsou tedy vloženy pouze do jednoho propojeného seznamu. Proto musíme vyhledat všechny položky v hašovací tabulce a náklady, které jsou úměrné počtu klíčů v tabulce.
Lineární sondování (otevřené adresování / uzavřený hash)
V otevřené technice adresování nebo lineárního sondování jsou všechny vstupní záznamy uloženy v samotné hash tabulce. Když se klíč – hodnota mapuje na hashovací kód a pozice ukazovaná hashovacím kódem je neobsazená, pak se klíčová hodnota vloží na dané místo.
Pokud je pozice již obsazená, pak se pomocí zkušební sekvence vloží hodnota klíče na další pozici, která je v hašovací tabulce neobsazena.
U lineárního snímání se funkce hash může změnit, jak je znázorněno níže:
hash = hash% hashTableSize
hash = (hash + 1)% hashTableSize
hash = (hash + 2)% hashTableSize
hash = (hash + 3)% hashTableSize
Vidíme, že v případě lineárního snímání je interval mezi sloty nebo po sobě následujícími sondami konstantní, tj. 1.
Ve výše uvedeném diagramu vidíme, že v 0thumístění zadáme 10 pomocí hash funkce „hash = hash% hash_tableSize“.
Nyní prvek 70 také odpovídá umístění 0 v hash tabulce. Ale toto místo je již obsazené. Proto pomocí lineárního sondování najdeme další místo, které je 1. Protože toto místo není obsazené, umístíme klíč 70 na toto místo, jak je znázorněno pomocí šipky.
Výsledná tabulka hash je uvedena níže.
Lineární sondování může trpět problémem „primárního shlukování“, ve kterém existuje šance, že se spojité buňky mohou obsadit a pravděpodobnost vložení nového prvku se sníží.
Také pokud dva prvky získají stejnou hodnotu při první hashovací funkci, budou oba tyto prvky sledovat stejnou sekvenci sondy.
Kvadratické sondování
Kvadratické snímání je stejné jako lineární snímání, přičemž jediným rozdílem je interval použitý pro snímání. Jak název napovídá, tato technika využívá nelineární nebo kvadratickou vzdálenost k obsazení slotů, když dojde ke kolizi místo lineární vzdálenosti.
V kvadratické sondě je interval mezi sloty vypočítán přidáním libovolné polynomiální hodnoty k již hašovanému indexu. Tato technika významně omezuje primární shlukování, ale při sekundárním shlukování se nezlepšuje.
Double Hashing
Technika dvojitého hašování je podobná lineárnímu sondování. Jediný rozdíl mezi dvojitým hashováním a lineárním sondováním je ten, že v technice dvojitého hashování je interval použitý pro sondování počítán pomocí dvou hash funkcí. Vzhledem k tomu, že na klíč jednu po druhé aplikujeme hashovací funkci, eliminuje primární shlukování i sekundární shlukování.
Rozdíl mezi řetězením (otevřené hashování) a lineárním sondováním (otevřené adresování)
| Řetězení (otevřené hashování) | Lineární sondování (otevřené adresování) |
|---|---|
| Klíčové hodnoty lze uložit mimo tabulku pomocí samostatného propojeného seznamu. | Klíčové hodnoty by měly být uloženy pouze uvnitř tabulky. |
| Počet prvků v zatřiďovací tabulce může překročit velikost zatřiďovací tabulky. | Počet prvků přítomných v hašovací tabulce nepřekročí počet indexů v hašovací tabulce. |
| Odstranění je efektivní v technice řetězení. | Odstranění může být těžkopádné. Lze se mu vyhnout, pokud to není nutné. |
| Protože je pro každé místo udržován samostatný propojený seznam, je zabraný prostor velký. | Vzhledem k tomu, že všechny položky jsou umístěny ve stejné tabulce, je odebraný prostor menší. |
Implementace tabulky hash C ++
Můžeme implementovat hashování pomocí polí nebo propojených seznamů k programování hash tabulek. V C ++ máme také funkci zvanou „hash map“, což je struktura podobná hašovací tabulce, ale každá položka je pár klíč – hodnota. V C ++ se nazývá hash mapa nebo jednoduše mapa. Hash mapa v C ++ je obvykle neuspořádaná.
Existuje záhlaví definované v Standard Template Library (STL) v C ++, které implementuje funkčnost map. Kryli jsme Mapy STL podrobně v našem tutoriálu o STL.
Následující implementace slouží k hašování pomocí propojených seznamů jako datové struktury pro hashovací tabulku. V této implementaci také používáme „Chaining“ jako techniku řešení kolizí.
#include #include using namespace std; class Hashing { int hash_bucket; // No. of buckets // Pointer to an array containing buckets list *hashtable; public: Hashing(int V); // Constructor // inserts a key into hash table void insert_key(int val); // deletes a key from hash table void delete_key(int key); // hash function to map values to key int hashFunction(int x) { return (x % hash_bucket); } void displayHash(); }; Hashing::Hashing(int b) { this->hash_bucket = b; hashtable = new list (hash_bucket); } //insert to hash table void Hashing::insert_key(int key) { int index = hashFunction(key); hashtable(index).push_back(key); } void Hashing::delete_key(int key) { // get the hash index for key int index = hashFunction(key); // find the key in (inex)th list list :: iterator i; for (i = hashtable(index).begin(); i != hashtable(index).end(); i++) { if (*i == key) break; } // if key is found in hash table, remove it if (i != hashtable(index).end()) hashtable(index).erase(i); } // display the hash table void Hashing::displayHash() { for (int i = 0; i ' << x; cout << endl; } } // main program int main() { // array that contains keys to be mapped int hash_array() = {11,12,21, 14, 15}; int n = sizeof(hash_array)/sizeof(hash_array(0)); Hashing h(7); // Number of buckets = 7 //insert the keys into the hash table for (int i = 0; i < n; i++) h.insert_key(hash_array(i)); // display the Hash table cout<<'Hash table created:'< Výstup:
Tabulka hash vytvořena:
0 -> 21 -> 14
1 -> 15
dva
3
4 -> 11
5 -> 12
6
Tabulka hash po odstranění klíče 12:
0 -> 21 -> 14
1 -> 15
dva
3
4 -> 11
5
6
Výstup ukazuje hashovací tabulku, která je vytvořena o velikosti 7. Ke vyřešení kolize používáme řetězení. Po odstranění jedné z kláves zobrazíme hashovací tabulku.
Aplikace hashování
# 1) Ověření hesel: Ověření hesel se obvykle provádí pomocí kryptografických hashovacích funkcí. Po zadání hesla systém vypočítá hodnotu hash hesla a poté se odešle na server k ověření. Na serveru jsou uloženy hodnoty hash původních hesel.
# 2) Datové struktury: Různé datové struktury jako unordered_set a unordered_map v C ++, slovníky v pythonu nebo C #, HashSet a hash mapa v Javě, všechny používají pár klíč – hodnota, přičemž klíče jsou jedinečné hodnoty. Hodnoty mohou být stejné pro různé klíče. K implementaci těchto datových struktur se používá hashing.
# 3) Přehled zpráv: Toto je další aplikace, která používá kryptografický hash. V přehledech zpráv vypočítáme hash pro odesílaná a přijímaná data nebo dokonce soubory a porovnáváme je s uloženými hodnotami, abychom zajistili, že s datovými soubory nebude manipulováno. Nejběžnějším algoritmem je zde „SHA 256“.
# 4) Provoz kompilátoru: Když kompilátor kompiluje program, klíčová slova pro programovací jazyk jsou uložena odlišně od ostatních identifikuje. Kompilátor používá k ukládání těchto klíčových slov tabulku hash.
# 5) Indexování databáze: Hash tabulky se používají pro indexování databází a diskové datové struktury.
# 6) Asociativní pole: Asociativní pole jsou pole, jejichž indexy jsou datového typu jiného než celočíselné řetězce nebo jiné typy objektů. Hash tabulky lze použít k implementaci asociativních polí.
Závěr
Hašování je nejpoužívanější datová struktura, protože operace vložení, odstranění a hledání zabere konstantní čas O (1). Hashing je většinou implementován pomocí hashovací funkce, která počítá jedinečnou menší hodnotu klíče pro velké datové položky. Můžeme implementovat hashování pomocí polí a propojených seznamů.
Kdykoli se jedna nebo více položek dat rovná stejným hodnotám klíčů, vede to ke kolizi. Viděli jsme různé techniky řešení kolizí včetně lineárního sondování, řetězení atd. Také jsme viděli implementaci hashování v C ++.
Na závěr můžeme říci, že hašování je zdaleka nejúčinnější datovou strukturou ve světě programování.
=> Podívejte se na celou sérii školení C ++ zde.
Doporučené čtení
- Jak psát složité testovací scénáře obchodní logiky pomocí techniky rozhodovací tabulky
- Field Validation Table (FVT): A Test Design Technique for Field Validation
- Výukový program QTP č. 15 - Používání textových oblastí, tabulek a kontrolních bodů stránek v QTP
- MAPY V STL
- Vše o směrovačích: Typy směrovačů, směrovací tabulka a směrování IP
- Top 40 nejlepších otázek a odpovědí na rozhovor s MySQL (2021 otázek)
- Top 90 SQL Interview Questions and Answer Answer (LATEST)
- Příkazy unixových obslužných programů: Which, Man, Find Su, Sudo (Part D)