V tej vadnici boste izvedeli, kaj je Hashing.
Razprševanje je tehnika preslikave velikega števila poljubnih podatkov v tabelarne indekse s pomočjo zgoščevalne funkcije. Je metoda za predstavitev slovarjev za velike nabore podatkov.
Omogoča iskanje, posodabljanje in iskanje v konstantnem času, tj O(1).
Zakaj je potrebno razprševanje?
Po shranjevanju velike količine podatkov moramo na teh podatkih opraviti različne operacije. Iskanje podatkov je za nabore podatkov neizogibno. Linearno iskanje in binarno iskanje opravlja poizvedbe / iskanje s časovno zahtevnostjo O(n)in O(log n)oz. Ko se velikost nabora podatkov povečuje, postanejo te zapletenosti tudi znatno večje, kar ni sprejemljivo.
Potrebujemo tehniko, ki ni odvisna od velikosti podatkov. Razprševanje omogoča iskanje v stalnem času, tj O(1).
Funkcija razpršitve
Razpršilna funkcija se uporablja za preslikavo vsakega elementa nabora podatkov v indekse v tabeli.
Za več informacij o hash tabeli, tehnikah reševanja trkov in hash funkcijah obiščite Hash Table.
