Tässä opetusohjelmassa opit, mikä on hajautus.
Hajautus on tekniikka, jolla suuri joukko mielivaltaisia tietoja kartoitetaan taulukkoindekseihin käyttämällä hajautusfunktiota. Se on menetelmä suurten tietojoukkojen sanakirjojen esittämiseksi.
Sen avulla hakutoiminnot, päivitys- ja hakutoiminnot tapahtuvat vakiona O(1).
Miksi hajautusta tarvitaan?
Suuren tietomäärän tallentamisen jälkeen meidän on suoritettava näille tiedoille erilaisia toimintoja. Hakutiedot ovat väistämättömiä aineistoille. Lineaarinen haku ja binaarihaku suorittavat haun / haun ajan monimutkaisuuden O(n)ja O(log n)vastaavasti. Aineiston koon kasvaessa myös nämä monimutkaisuudet kasvavat merkittävästi, mikä ei ole hyväksyttävää.
Tarvitsemme tekniikan, joka ei riipu tietojen koosta. Hajautus sallii hakujen tapahtua vakiona O(1).
Hash-toiminto
Hajautusfunktiota käytetään tietojoukon jokaisen elementin kartoittamiseen taulukon hakemistoihin.
Lisätietoja hajataulukosta, törmäystarkastustekniikoista ja hajautusfunktioista on Hash-taulukossa.
