Hashing tarkoittaa prosessia, jossa muodostetaan kiinteäkokoinen tulos muuttuvan kokoisesta syötteestä käyttämällä hash-funktioina tunnettuja matemaattisia kaavoja. Tämä tekniikka määrittää indeksin tai sijainnin kohteen tallennusta varten tietorakenteessa.
Hash-tietorakenteen tarve
Internetin tiedon määrä kasvaa eksponentiaalisesti joka päivä, mikä tekee kaiken tehokkaan tallentamisen vaikeaksi. Päivittäisessä ohjelmoinnissa tämä tietomäärä ei ehkä ole niin suuri, mutta silti se on tallennettava, käytettävä ja käsiteltävä helposti ja tehokkaasti. Hyvin yleinen tietorakenne, jota käytetään tällaiseen tarkoitukseen, on Array-tietorakenne.
Nyt herää kysymys, jos Array oli jo olemassa, mikä oli tarve uudelle tietorakenteelle! Vastaus tähän on sanassa tehokkuus. Vaikka tallennus Arrayssa kestää O(1) aikaa, sen etsiminen kestää ainakin O(log n) aika. Tämä aika näyttää pieneltä, mutta suurelle tietojoukolle se voi aiheuttaa paljon ongelmia ja tämä puolestaan tekee Array-tietorakenteesta tehottomaksi.
Joten nyt etsimme tietorakennetta, joka pystyy tallentamaan tiedot ja hakemaan siitä jatkuvassa ajassa, eli O(1) aika. Näin Hashing-tietorakenne tuli peliin. Hash-tietorakenteen käyttöönoton myötä on nyt mahdollista helposti tallentaa tietoja vakioajassa ja hakea niitä myös vakioajassa.
Hashingin osat
Hajautuksessa on pääasiassa kolme osaa:
- Avain: A Avain voi olla mikä tahansa merkkijono tai kokonaisluku, joka syötetään syötteenä hash-funktioon, tekniikkaan, joka määrittää indeksin tai sijainnin kohteen tallennusta varten tietorakenteessa.
- Hash-funktio: The hash-toiminto vastaanottaa syöttöavaimen ja palauttaa taulukoksi kutsutun taulukon elementin indeksin. Indeksi tunnetaan nimellä hash-indeksi .
- Hash-taulukko: Hash-taulukko on tietorakenne, joka kartoittaa avaimet arvoihin käyttämällä erityistä funktiota, jota kutsutaan hash-funktioksi. Hash tallentaa tiedot assosiatiivisesti taulukkoon, jossa jokaisella data-arvolla on oma yksilöllinen indeksinsä.
Hashingin osat
Mikä on törmäys?
Hajautusprosessi tuottaa pienen luvun suurelle avaimelle, joten on mahdollista, että kaksi avainta voivat tuottaa saman arvon. Tilanne, jossa äskettäin lisätty avain kohdistuu jo varattuun, ja se on käsiteltävä jollakin törmäyksenkäsittelytekniikalla.
Törmäys Hashingissa
Hashingin edut tietorakenteissa
- Avainarvotuki: Hashing on ihanteellinen avainarvotietorakenteiden toteuttamiseen.
- Nopea tiedonhaku: Hashing mahdollistaa nopean pääsyn elementteihin, jotka ovat jatkuvasti monimutkaisia.
- Tehokkuus: Lisäys-, poisto- ja hakutoiminnot ovat erittäin tehokkaita.
- Muistin käytön vähentäminen: Hashing vaatii vähemmän muistia, koska se varaa kiinteän tilan elementtien tallentamiseen.
- Skaalautuvuus: Hashing toimii hyvin suurilla tietojoukoilla ja ylläpitää jatkuvaa käyttöaikaa.
- Suojaus ja salaus: Hashing on välttämätöntä turvallisen tietojen tallennuksen ja eheyden todentamiseksi.
Lisätietoja hajautustoiminnosta on osoitteessa Johdatus tiivistykseen – Tietorakenteen ja algoritmin opetusohjelmat