Mikä on hajautus? Kuinka hajakoodit toimivat - esimerkkejä

Johdatus hajautukseen

Hajautus on suunniteltu ratkaisemaan ongelma, joka koskee kohteen löytämistä tai tallentamista kokoelmaan.

Esimerkiksi, jos meillä on luettelo 10000 englanninkielisestä sanasta ja haluamme tarkistaa, onko tietty sana luettelossa, olisi tehotonta vertailla sanaa peräkkäin kaikkiin 10000 kappaleeseen, kunnes löydämme osuman. Vaikka sanaluettelo on lajiteltu sanakirjaan, kuten sanakirjassa, tarvitset silti jonkin aikaa etsimäsi sanan löytämiseen.

Hajautus on tekniikka, jolla asioita voidaan tehostaa kaventamalla hakua tehokkaasti alusta alkaen.

Mikä hajautus on?

Hajautus tarkoittaa jonkin toiminnon tai algoritmin käyttämistä kohdetietojen kartoittamiseksi johonkin edustavaan kokonaislukuarvoon.

Tätä ns. Hash-koodia (tai yksinkertaisesti hash-koodia) voidaan sitten käyttää keinona kaventaa hakua, kun etsit kohdetta kartalta.

Yleensä näitä hajautuskoodeja käytetään luomaan indeksi, johon arvo tallennetaan.

Kuinka hajautus toimii

Hajautustaulukoihin tallennat tietoja avain- ja arvopareina. Avaimen, jota käytetään tietojen tunnistamiseen, annetaan syötteenä hajautusfunktiolle. Hajautuskoodi, joka on kokonaisluku, kartoitetaan sitten kiinteään kokoon.

Hash-taulukoiden on tuettava 3 toimintoa.

  • lisää (avain, arvo)
  • saada (avain)
  • poista (avain)

Oletetaan, että puhtaasti esimerkkinä käsitteen ymmärtämisessä haluamme kartoittaa luettelon merkkijonoavain merkkijonojen arvoihin (esimerkiksi kartoittaa luettelo maista niiden pääkaupunkeihin).

Joten sanotaan, että haluamme tallentaa taulukon tiedot karttaan.

Oletetaan, että hash-toimintomme on yksinkertaisesti ottaa merkkijonon pituus.

Yksinkertaisuuden vuoksi meillä on kaksi taulukkoa: yksi avaimillemme ja toinen arvoille.

Joten laittaa kohde hash-taulukkoon laskemme sen hash-koodin (tässä tapauksessa yksinkertaisesti lasketaan merkkien lukumäärä), sitten laitetaan avain ja arvo matriisiin vastaavaan hakemistoon.

Esimerkiksi Kuuballa on hash-koodi (pituus) 4. Joten me säilytämme Kuuban avainten taulukossa 4. paikassa ja Havannan arvoryhmän 4. indeksissä jne. Ja päädymme seuraavaan:

Nyt tässä erityisessä esimerkissä asiat toimivat melko hyvin. Ryhmämme on oltava riittävän suuri, jotta se mahtuisi pisin merkkijono, mutta tässä tapauksessa se on vain 11 paikkaa.

Tuhlaamme vähän tilaa, koska esimerkiksi tiedoissamme ei ole 1-kirjaimisia avaimia eikä 8–10-kirjaimia.

Mutta tässä tapauksessa tuhlattu tila ei myöskään ole niin paha. Merkkijonon pituuden ottaminen on mukavaa ja nopeaa, samoin on prosessi tiettyyn avaimeen liittyvän arvon löytämiseksi (varmasti nopeampi kuin jopa viiden merkkijonon vertailu).

Mutta mitä teemme, jos tietojoukossamme on merkkijono, jossa on yli 11 merkkiä?

Entä jos meillä on toinen sana, jossa on 5 merkkiä, "Intia", ja yritämme määrittää sen hakemistoon hash-funktiomme avulla. Koska hakemisto 5 on jo varattu, meidän on soitettava, mitä siihen tehdään. Tätä kutsutaan törmäykseksi.

Jos tietojoukossamme olisi merkkijono, jossa on tuhat merkkiä, ja teet taulukon tuhannesta indeksistä tietojen tallentamiseksi, se johtaisi tilan tuhlaukseen. Jos avaimemme olisivat satunnaisia ​​sanoja englannista, jossa on niin paljon samanpituisia sanoja, pituuden käyttäminen hajautusfunktiona olisi melko hyödytöntä.

Törmäysten käsittely

Törmäysten käsittelyssä käytetään kahta perusmenetelmää.

  1. Erillinen ketju
  2. Avaa osoite

Erillinen ketju

Hash-törmäysten käsittely erillisellä ketjutuksella käyttää ylimääräistä tietorakennetta, mieluiten linkitetty luettelo dynaamiseen allokointiin, ryhmiin. Esimerkissämme, kun lisätään Intia tietojoukkoon, se liitetään hakemistoon 5 tallennettuun linkitettyyn luetteloon, niin taulukomme näyttäisi tältä.

Löydämme kohteen menemme ensin ämpäriin ja vertaamme sitten avaimia. Tämä on suosittu menetelmä, ja jos käytetään linkkiluetteloa, hajautus ei koskaan täyty. Hinta get(k)on keskimäärin O(n)missä n on ryhmässä olevien avainten lukumäärä, avainten kokonaismäärä on N.

Erillisen ketjutuksen ongelma on, että tietorakenne voi kasvaa ilman rajoja.

Avaa osoite

Avoin osoite ei ota käyttöön uutta tietorakennetta. Jos tapahtuu törmäys, etsimme saatavuutta seuraavasta algoritmin luomasta paikasta. Open Addressingia käytetään yleensä silloin, kun tallennustilaa on rajoitettu, ts. Sulautetut prosessorit. Avoin osoite ei välttämättä ole nopeampaa kuin erillinen ketjutus.

Menetelmät avoimen osoitteen saamiseksi

  • [Lineaarinen koetus
  • Toissijainen koetus
  • Tuplasekoitus

Kuinka hajautusta käytetään koodissasi.

Python

 # Few languages like Python, Ruby come with an in-built hashing support. # Declaration my_hash_table = {} my_hash_table = dict() # Insertion my_hash_table[key] = value # Look up value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2 value = my_hash_table[key] # throws a ValueError exception if the key is not present # Deletion del my_hash_table[key] # throws a ValueError exception if the key is not present # Getting all keys and values stored in the dictionary keys = my_hash_table.keys() values = my_hash_table.values()
:raketti:

Suorita koodi

Java

 // Java doesn't include hashing by default, you have to import it from java.util library // Importing hashmaps import java.util.HashMap; // Declaration HashMap myHashTable = new HashMap(); // declares an empty map. // Insertion myHashTable.put(key, value); // Deletion myHashtable.remove(key); // Look up myHashTable.get(key); // returns null if the key K is not present myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key // Number of key, value pairs in the hash table myHashTable.size();
:raketti:

Suorita koodi

Lisätietoja hajautuksesta

  • Kooditon opas hajautus- ja hajautuspöytiin
  • Kuinka yksinkertainen hash-taulukko otetaan käyttöön JavaScriptissä
  • Hash-taulukot selitetään