Zgoščevanje se nanaša na postopek generiranja izhoda fiksne velikosti iz vhoda spremenljive velikosti z uporabo matematičnih formul, znanih kot zgoščevalne funkcije. Ta tehnika določa indeks ali lokacijo za shranjevanje postavke v podatkovni strukturi.
Potreba po podatkovni strukturi Hash
Količina podatkov na internetu eksponentno narašča vsak dan, zato jih je težko vse učinkovito shraniti. Pri vsakodnevnem programiranju ta količina podatkov morda ni tako velika, a vseeno jih je treba enostavno in učinkovito shraniti, dostopati do njih in jih obdelovati. Zelo pogosta podatkovna struktura, ki se uporablja za tak namen, je podatkovna struktura Array.
Zdaj se postavlja vprašanje, če je Array že obstajal, kakšna je bila potreba po novi strukturi podatkov! Odgovor na to je v besedi učinkovitost. Čeprav shranjevanje v Array traja O(1) časa, iskanje v njem traja najmanj O(log n) čas. Zdi se, da je ta čas majhen, vendar lahko pri velikem naboru podatkov povzroči veliko težav, zaradi česar je struktura podatkov Array neučinkovita.
Zdaj torej iščemo podatkovno strukturo, ki lahko shranjuje podatke in išče v njih v konstantnem času, tj O(1) čas. Tako je prišla v poštev podatkovna struktura zgoščevanja. Z uvedbo podatkovne strukture Hash je zdaj mogoče enostavno shranjevati podatke v konstantnem času in jih tudi pridobivati v konstantnem času.
Komponente zgoščevanja
Obstajajo večinoma tri komponente zgoščevanja:
- ključ: A Ključ je lahko karkoli niz ali celo število, ki je podano kot vhod v zgoščevalno funkcijo tehnika, ki določa indeks ali lokacijo za shranjevanje postavke v podatkovni strukturi.
- Funkcija zgoščevanja: The hash funkcija prejme vhodni ključ in vrne indeks elementa v matriki, imenovani zgoščena tabela. Indeks je znan kot zgoščeni indeks .
- Zgoščevalna tabela: Zgoščevalna tabela je podatkovna struktura, ki preslika ključe v vrednosti z uporabo posebne funkcije, imenovane zgoščevalna funkcija. Hash asociativno shrani podatke v matriko, kjer ima vsaka podatkovna vrednost svoj edinstveni indeks.
Komponente zgoščevanja
Kaj je trčenje?
Postopek zgoščevanja ustvari majhno število za velik ključ, zato obstaja možnost, da dva ključa ustvarita isto vrednost. Situacija, ko se na novo vstavljeni ključ preslika na že zasedenega in ga je treba obravnavati s tehnologijo za obravnavanje trkov.
Trk pri zgoščevanju
Prednosti zgoščevanja v podatkovnih strukturah
- Podpora za ključ-vrednost: Zgoščevanje je idealno za implementacijo podatkovnih struktur ključ-vrednost.
- Hitro pridobivanje podatkov: Zgoščevanje omogoča hiter dostop do elementov s konstantno časovno kompleksnostjo.
- Učinkovitost: Operacije vstavljanja, brisanja in iskanja so zelo učinkovite.
- Zmanjšanje porabe pomnilnika: Zgoščevanje zahteva manj pomnilnika, saj dodeli fiksen prostor za shranjevanje elementov.
- Razširljivost: Zgoščevanje deluje dobro pri velikih naborih podatkov, pri čemer ohranja stalen dostopni čas.
- Varnost in šifriranje: Zgoščevanje je bistveno za varno shranjevanje podatkov in preverjanje celovitosti.
Če želite izvedeti več o zgoščevanju, glejte Uvod v zgoščevanje – Vadnice za strukturo podatkov in algoritme