Hashovací funkce
V této části budeme diskutovat o hashovací funkci, která pomáhá spustit hash kód souvisejícího klíče datové položky v datové struktuře, jak je uvedeno níže:
Int hashItem ( int klíč ){
vrátit se klíč % velikost tabulky ;
}
Proces provádění indexu pole se nazývá hašování. Někdy je stejný typ kódu spuštěn pro generování stejného indexu pomocí stejných klíčů nazývaných kolize, které se řeší pomocí různého řetězení (vytváření propojených seznamů) a implementace strategií otevřeného adresování.
Práce s hashovací tabulkou v C++
Ukazatele na skutečné hodnoty jsou uloženy v hašovací tabulce. Používá klíč k vyhledání indexu pole, ve kterém je třeba uložit hodnoty proti klíčům na požadované místo v poli. Vzali jsme hashovací tabulku o velikosti 10, jak je uvedeno v následujícím textu:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Vezměme náhodně jakákoli data proti různým klíčům a uložíme tyto klíče do hašovací tabulky pouhým výpočtem indexu. Data jsou tedy uložena proti klíčům ve vypočítaném indexu pomocí hašovací funkce. Předpokládejme, že vezmeme data = {14,25,42,55,63,84} a klíče =[ 15,9,5,25,66,75 ].
Vypočítejte index těchto dat pomocí hashovací funkce. Hodnota indexu je uvedena v následujícím textu:
| Klíč | patnáct | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Vypočítat index | 15 %10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Data | 14 | 25 | 42 | 55 | 63 | 84 |
Po vytvoření indexu pole umístěte data proti klíči na přesný index daného pole, jak bylo popsáno výše.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Poté můžeme vidět, že ke kolizi dojde, pokud dva nebo více klíčů má stejný hash kód, což má za následek stejný index prvků v poli. Máme jedno řešení, jak se vyhnout kolizi: výběr dobré hashovací metody a implementace přesných strategií.
Nyní proberme různé techniky implementace pomocí správných příkladů.
Příklad: Přidejte data do hašovací tabulky pomocí otevřené hašovací techniky
V tomto příkladu používáme implementační techniku, jako je Open Hashing, abychom se vyhnuli kolizi v hašovací tabulce. Při otevřeném hašování nebo řetězení vytváříme propojený seznam pro řetězení hodnot hashovací tabulky. Fragment kódu z tohoto příkladu je připojen v následujícím textu, který popisuje techniku otevřeného hašování:
#include#include
třída HashTable {
soukromé :
statický konst int velikost stolu = 10 ;
std :: seznam < int > tabulkaHas [ velikost stolu ] ;
int hashFunc ( int klíč ) {
vrátit se klíč % velikost stolu ;
}
veřejnost :
prázdnota vložit ( int klíč ) {
int index = hashFunc ( klíč ) ;
tabulkaHas [ index ] . zatlačit zpátky ( klíč ) ;
}
prázdnota zobrazit tabulku ( ) {
pro ( int i = 0 ; i < velikost stolu ; ++ i ) {
std :: cout << '[' << i << ']' ;
pro ( auto to = tabulkaHas [ i ] . začít ( ) ; to ! = tabulkaHas [ i ] . konec ( ) ; ++ to ) {
std :: cout << ' ->' << * to ;
}
std :: cout << std :: endl ;
}
}
} ;
int hlavní ( ) {
HashTable hasTable ;
hasTable. vložit ( patnáct ) ;
hasTable. vložit ( 33 ) ;
hasTable. vložit ( 23 ) ;
hasTable. vložit ( 65 ) ;
hasTable. vložit ( 3 ) ;
hasTable. zobrazit tabulku ( ) ;
vrátit se 0 ;
}
Toto je velmi zajímavý příklad: vytvoříme propojený seznam a vložíme data do hashovací tabulky. Nejprve definujeme knihovny při startu programu. The < seznam > knihovna se používá pro implementaci propojeného seznamu. Poté vytvoříme třídu s názvem „HashTable“ a vytvoříme atributy třídy, které jsou soukromé jako velikost tabulky a pole tabulky pomocí klíčového slova „private:“. Pamatujte, že soukromé atributy nejsou použitelné mimo třídu. Zde bereme velikost tabulky jako „10“. Pomocí toho inicializujeme hashovací metodu a vypočítáme index hashovací tabulky. V hashovací funkci předáme klíč a velikost hashovací tabulky.
Vytvoříme několik požadovaných funkcí a tyto funkce zveřejníme ve třídě. Pamatujte, že veřejné funkce jsou použitelné mimo třídu kdekoli. Ke spuštění veřejné části třídy používáme klíčové slovo „public:“. . Protože chceme do hashovací tabulky přidat nové prvky, vytvoříme funkci s názvem „InsertHash“ s klíčem jako argumentem funkce. Ve funkci „insert“ inicializujeme proměnnou index. Hašovací funkci předáme proměnné index. Poté předejte proměnnou indexu propojenému seznamu tableHas[] pomocí metody „push“ pro vložení prvku do tabulky.
Poté vytvoříme funkci „viewHashTab“, která zobrazí hashovací tabulku, abyste viděli nově vložená data. V této funkci používáme cyklus „for“, který prohledává hodnoty až do konce hashovací tabulky. Zajistěte, aby byly hodnoty uloženy ve stejném indexu, který byl vyvinut pomocí hashovací funkce. Ve smyčce předáme hodnoty na jejich příslušném indexu a zde třídu ukončíme. Ve funkci „main“ vezmeme objekt třídy s názvem „hasTable“. Pomocí tohoto objektu třídy můžeme přistupovat k metodě vkládání předáním klíče v metodě. Klíč, který jsme předali ve funkci „main“, je vypočítán ve funkci „insert“, která vrací pozici indexu v tabulce hash. Hašovací tabulku jsme zobrazili voláním funkce „view“ pomocí objektu „Class“.
Výstup tohoto kódu je připojen v následujícím textu:
Jak vidíme, hashovací tabulka je úspěšně vytvořena pomocí propojeného seznamu v C++. Otevřené řetězení se používá, aby se zabránilo kolizi stejného indexu.
Závěr
Nakonec jsme došli k závěru, že hashovací tabulka je nejvíce se objevující technikou pro ukládání a získávání klíčů s páry hodnot, aby bylo možné efektivně zpracovávat obrovské množství dat. Pravděpodobnost kolize je v hašovací tabulce velmi vysoká a zničí data a jejich úložiště. Tuto kolizi můžeme překonat pomocí různých technik správy hashovacích tabulek. Vývojem hašovací tabulky v C++ mohou vývojáři zvýšit výkon pomocí nejvhodnější techniky pro ukládání dat do hašovací tabulky. Doufáme, že vám tento článek pomůže porozumět hashovací tabulce.