Hašování odkazuje na proces generování výstupu s pevnou velikostí ze vstupu proměnné velikosti pomocí matematických vzorců známých jako hashovací funkce. Tato technika určuje index nebo umístění pro uložení položky v datové struktuře.
Need for Hash datová struktura
Množství dat na internetu každým dnem exponenciálně roste, takže je obtížné je všechny efektivně ukládat. Při každodenním programování nemusí být toto množství dat tak velké, ale přesto je třeba je ukládat, přistupovat a zpracovávat je snadno a efektivně. Velmi běžnou datovou strukturou, která se pro takový účel používá, je datová struktura Array.
Nyní vyvstává otázka, pokud už tam Array bylo, jaká byla potřeba nové datové struktury! Odpověď na to je ve slově efektivita. I když ukládání do Array trvá O(1) čas, hledání v něm zabere minimálně O(log n) čas. Tato doba se zdá být malá, ale pro velký soubor dat to může způsobit mnoho problémů, a to zase činí datovou strukturu Array neefektivní.
Nyní tedy hledáme datovou strukturu, která dokáže data ukládat a vyhledávat v nich v konstantním čase, tedy v O(1) čas. Tak se do hry dostala datová struktura hashování. Se zavedením datové struktury Hash je nyní možné snadno ukládat data v konstantním čase a také je v konstantním čase načítat.
Komponenty hashování
Hash má tři hlavní složky:
- Klíč: A Klíč může být jakýkoli řetězec nebo celé číslo, které je přiváděno jako vstup do hashovací funkce, což je technika, která určuje index nebo umístění pro uložení položky v datové struktuře.
- Hashovací funkce: The hashovací funkce přijme vstupní klíč a vrátí index prvku v poli zvaném hashovací tabulka. Index je známý jako hash index .
- Tabulka hash: Hashovací tabulka je datová struktura, která mapuje klíče na hodnoty pomocí speciální funkce zvané hashovací funkce. Hash ukládá data asociativním způsobem do pole, kde každá hodnota dat má svůj vlastní jedinečný index.
Komponenty hashování
Co je kolize?
Proces hašování generuje malé číslo pro velký klíč, takže existuje možnost, že dva klíče mohou vytvořit stejnou hodnotu. Situace, kdy se nově vložený klíč mapuje na již obsazený a musí být řešen pomocí nějaké technologie pro řešení kolizí.
Kolize v hashování
Výhody hašování v datových strukturách
- Podpora párů klíč–hodnota: Hašování je ideální pro implementaci datových struktur klíč–hodnota.
- Rychlé načítání dat: Hašování umožňuje rychlý přístup k prvkům s konstantní časovou složitostí.
- Účinnost: Operace vkládání, mazání a vyhledávání jsou vysoce efektivní.
- Snížení využití paměti: Hašování vyžaduje méně paměti, protože přiděluje pevný prostor pro ukládání prvků.
- Škálovatelnost: Hashování funguje dobře s velkými datovými sadami a udržuje konstantní přístupový čas.
- Zabezpečení a šifrování: Hašování je nezbytné pro bezpečné ukládání dat a ověřování integrity.
Chcete-li se dozvědět více o hashování, podívejte se prosím na Úvod do hašování – výukové programy pro datovou strukturu a algoritmus