Hašovanie sa vzťahuje na proces generovania výstupu s pevnou veľkosťou zo vstupu s premenlivou veľkosťou pomocou matematických vzorcov známych ako hašovacie funkcie. Táto technika určuje index alebo umiestnenie pre uloženie položky v dátovej štruktúre.
Potreba štruktúry údajov hash
Množstvo údajov na internete každým dňom exponenciálne rastie, čo sťažuje ich efektívne ukladanie. Pri každodennom programovaní nemusí byť toto množstvo údajov také veľké, no napriek tomu je potrebné ich ukladať, pristupovať a spracovávať ich jednoducho a efektívne. Veľmi bežnou dátovou štruktúrou, ktorá sa používa na takýto účel, je dátová štruktúra Array.
Teraz vyvstáva otázka, ak už tam Array bolo, aká bola potreba novej štruktúry údajov! Odpoveď na to je v slove efektivita. Aj keď ukladanie v Array trvá O(1) čas, hľadanie v ňom trvá minimálne O (log n) čas. Zdá sa, že tento čas je malý, ale pre veľký súbor údajov môže spôsobiť veľa problémov, a preto je dátová štruktúra Array neefektívna.
Teraz teda hľadáme dátovú štruktúru, ktorá dokáže dáta ukladať a vyhľadávať v nich v konštantnom čase, t.j O(1) čas. Takto vstúpila do hry dátová štruktúra hashovania. So zavedením dátovej štruktúry Hash je teraz možné jednoducho ukladať údaje v konštantnom čase a tiež ich v konštantnom čase získavať.
Komponenty hashovania
Hašovanie má hlavne tri zložky:
dynamické pole java
- kľúč: A kľúč môže byť akýkoľvek reťazec alebo celé číslo, ktoré sa privádza ako vstup do hašovacej funkcie, čo je technika, ktorá určuje index alebo miesto na uloženie položky v dátovej štruktúre.
- Hash funkcia: The hašovacia funkcia prijme vstupný kľúč a vráti index prvku v poli nazývanom hašovacia tabuľka. Index je známy ako hash index .
- Tabuľka hash: Hašovacia tabuľka je dátová štruktúra, ktorá mapuje kľúče na hodnoty pomocou špeciálnej funkcie nazývanej hašovacia funkcia. Hash ukladá údaje asociatívnym spôsobom do poľa, kde každá hodnota údajov má svoj vlastný jedinečný index.
Komponenty hashovania
Čo je kolízia?
Proces hashovania generuje malé číslo pre veľký kľúč, takže existuje možnosť, že dva kľúče môžu produkovať rovnakú hodnotu. Situácia, kedy sa novo vložený kľúč mapuje na už obsadený a musí sa riešiť pomocou nejakej technológie na riešenie kolízií.
Kolízia v hashovaní
Výhody hashovania v dátových štruktúrach
- Podpora párov kľúč – hodnota: Hašovanie je ideálne na implementáciu dátových štruktúr kľúč – hodnota.
- Rýchle načítanie údajov: Hašovanie umožňuje rýchly prístup k prvkom s konštantnou časovou zložitosťou.
- Účinnosť: Operácie vkladania, vymazávania a vyhľadávania sú vysoko efektívne.
- Zníženie využitia pamäte: Hašovanie vyžaduje menej pamäte, pretože prideľuje pevný priestor na ukladanie prvkov.
- Škálovateľnosť: Hašovanie funguje dobre pri veľkých súboroch údajov, pričom zachováva konštantný čas prístupu.
- Zabezpečenie a šifrovanie: Hašovanie je nevyhnutné pre bezpečné ukladanie údajov a overenie integrity.
Ak sa chcete dozvedieť viac o hashovaní, pozrite si Úvod do hašovania – Štruktúra údajov a návody na algoritmy