Mikä on hajautus?
Hajautusarvo on arvo, jolla on kiinteä pituus, ja se luodaan matemaattisen kaavan avulla. Hash-arvoja käytetään tietojen pakkaamisessa, salauksessa jne. Tietojen indeksoinnissa käytetään hash-arvoja, koska niiden pituus on kiinteä riippumatta arvoista, joita käytettiin niiden luomiseen. Se saa hash-arvot viemään vähän tilaa verrattuna muihin eripituisiin arvoihin.
Hajautusfunktio käyttää matemaattista algoritmia avaimen muuntamiseksi hashiksi. Törmäys tapahtuu, kun hajautusfunktio tuottaa saman hajautusarvon useammalle kuin yhdelle avaimelle.
Tässä algoritmin opetusohjelmassa opit:
- Mikä on hajautus?
- Mikä on Hash-taulukko?
- Hash-toiminnot
- Hyvän hash-toiminnon ominaisuudet
- Törmäys
- Hash-taulukon toiminnot
- Hash-taulukko Python-esimerkki
- Hash-taulukon koodin selitys
- Esimerkki Python-sanakirjasta
- Monimutkaisuusanalyysi
- Reaalimaailman sovellukset
- Hash-taulukoiden edut
- Hajautustaulukoiden haitat
Mikä on Hash-taulukko?
HASH TAULUKKO on tietorakenne, joka tallentaa arvot käyttäen kahta avainta ja arvoja. Jokaiselle arvolle määritetään yksilöllinen avain, joka on luotu hajautusfunktiolla.
Avaimen nimeä käytetään siihen liittyvän arvon käyttämiseen. Tämä tekee arvojen etsimisen hash-taulukosta erittäin nopeaa riippumatta hash-taulukon kohteiden määrästä.
Hash-toiminnot
Esimerkiksi, jos haluamme tallentaa työntekijätiedot ja jokainen työntekijä tunnistetaan yksilöllisesti työntekijän numerolla.
Voimme käyttää työntekijän numeroa avaimena ja määrittää työntekijän tiedot arvoksi.
Edellä esitetty lähestymistapa vaatii ylimääräistä vapaata tilaa luokkaa (m * n 2 ), jossa muuttuja m on matriisin koko ja muuttuja n on työntekijän numeron numeroiden määrä. Tämä lähestymistapa tuo esiin tallennustilan ongelman.
Hajautusfunktio ratkaisee yllä olevan ongelman hankkimalla työntekijän numeron ja käyttämällä sitä luomaan hash-kokonaisluku, kiinteät numerot ja optimoimalla tallennustila. Hajautusfunktion tarkoituksena on luoda avain, jota käytetään viittaamaan arvoon, jonka haluamme tallentaa. Funktio hyväksyy tallennettavan arvon ja laskee sitten avaimen arvon algoritmilla.
Seuraava on esimerkki yksinkertaisesta hajautusfunktiosta
h(k) = k1 % m
TÄSSÄ,
- h (k) on hash-funktio, joka hyväksyy parametrin k. Parametri k on arvo, jolle avain halutaan laskea.
- k 1 % m on hash-funktion algoritmi, jossa k1 on arvo, jonka haluamme tallentaa, ja m on luettelon koko. Käytämme moduulioperaattoria avaimen laskemiseen.
Esimerkki
Oletetaan, että meillä on luettelo, jonka kiinteä koko on 3 ja seuraavat arvot
[1,2,3]
Voimme käyttää yllä olevaa kaavaa laskeaksesi sijainnit, jotka jokaisen arvon tulisi olla.
Seuraava kuva näyttää hash-taulukon käytettävissä olevat hakemistot.
Vaihe 1)
Laske sijainti, jonka ensimmäinen arvo miehittää
h (1) = 1% 3
= 1
Arvo 1 vie tilan indeksissä 1
Vaihe 2)
Laske sijainti, jonka toinen arvo vie
h (2) = 2% 3
= 2
Arvo 2 vie tilan hakemistossa 2
Vaihe 3)
Laske sijainti, jonka kolmas arvo käyttää.
h (3) = 3% 3
= 0
Arvo 3 vie tilan indeksissä 0
Lopullinen tulos
Täytetty hash-taulukko on nyt seuraava.
Hyvän hash-toiminnon ominaisuudet
Hyvällä hash-toiminnolla tulisi olla seuraavat ominaisuudet.
- Hajautuskoodin luomisen kaavassa on käytettävä algoritmiin tallennettavaa datan arvoa.
- Hajautusfunktion tulisi luoda ainutlaatuiset hajautusarvot jopa saman määrän syöttötiedoille.
- Toiminnon tulisi minimoida törmäysten määrä. Törmäyksiä tapahtuu, kun sama arvo syntyy useammalle kuin yhdelle arvolle.
- Arvot on jaettava johdonmukaisesti koko mahdollisen hajautuksen välillä.
Törmäys
Törmäys tapahtuu, kun algoritmi tuottaa saman hajautuksen useammalle kuin yhdelle arvolle.
Katsotaanpa esimerkkiä.
Oletetaan, että meillä on seuraava luettelo arvoista
[3,2,9,11,7]
Oletetaan, että hash-taulukon koko on 7, ja käytämme kaavaa (k 1 % m), jossa m on hash-taulukon koko.
Seuraava taulukko näyttää syntyvät hajautusarvot.
| Avain | Hash-algoritmi (k 1 % m) | Hash-arvo |
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11 | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
Kuten voimme nähdä yllä olevista tuloksista, arvoilla 2 ja 9 on sama hash-arvo, emmekä voi tallentaa enempää kuin yhtä arvoa kuhunkin kohtaan.
Annettu ongelma voidaan ratkaista joko ketjuamalla tai koettelemalla. Seuraavissa osissa käsitellään ketjutusta ja koettelemista yksityiskohtaisesti.
Ketjutus
Ketjutus on tekniikka, jota käytetään törmäämään törmäysongelmaan käyttämällä linkitettyjä luetteloita, joilla kullakin on ainutlaatuiset indeksit.
Seuraava kuva havainnollistaa ketjutetun luettelon näyttämistä
Sekä 2 että 9 käyttävät samaa hakemistoa, mutta ne tallennetaan linkitettyinä luetteloina. Jokaisella luettelolla on yksilöllinen tunniste.
Ketjutettujen luetteloiden edut
Ketjutettujen luetteloiden edut ovat seuraavat:
- Ketjutetuilla luetteloilla on parempi suorituskyky tietojen lisäämisessä, koska lisäysjärjestys on O (1).
- Ketjutettua luetteloa käyttävän hash-taulukon kokoa ei tarvitse muuttaa.
- Siihen mahtuu helposti suuri määrä arvoja, kunhan tilaa on vapaata.
Koet
Toinen tekniikka, jota käytetään törmäyksen ratkaisemiseen, on tutkinta. Kun käytetään koetusmenetelmää, törmäys tapahtuu, voimme yksinkertaisesti siirtyä eteenpäin ja löytää tyhjä paikka tallentaa arvomme.
Seuraavat ovat koetusmenetelmiä:
| Menetelmä | Kuvaus |
| Lineaarinen koetus | Aivan kuten nimestä voi päätellä, tämä menetelmä etsii tyhjiä paikkoja lineaarisesti alkaen törmäyskohdasta ja eteenpäin. Jos luettelon loppu on saavutettu ja tyhjää paikkaa ei löydy. Koetus alkaa luettelon alusta. |
| Toissijainen koetus | Tämä menetelmä käyttää toisen asteen polynomilausekkeita seuraavan vapaan aikavälin löytämiseen. |
| Tuplasekoitus | Tämä tekniikka käyttää toissijaista hajautusfunktion algoritmia seuraavan vapaan vapaan paikan löytämiseen. |
Yllä olevaa esimerkkiä käyttämällä hajautustaulukko näytteenoton jälkeen näytetään seuraavasti:
Hash-taulukon toiminnot
Tässä ovat Hash-taulukoiden tukemat toiminnot:
- Lisäys - tätä toimintoa käytetään lisäämään elementti hash-taulukkoon
- Haku - tätä operaatiota käytetään elementtien etsimiseen hash-taulukosta avaimen avulla
- Poistaminen - tätä toimintoa käytetään elementtien poistamiseen hash-taulukosta
Lisätään tietoja
Lisäämisoperaatiota käytetään arvojen tallentamiseen hajautustaulukkoon. Kun uusi arvo tallennetaan hajautustaulukkoon, sille annetaan indeksinumero. Indeksinumero lasketaan käyttämällä hajautusfunktiota. Hajautusfunktio korjaa kaikki törmäykset, jotka tapahtuvat indeksinumeroa laskettaessa.
Etsi tietojen käyttöä
Hakutoimintoa käytetään hajautustaulukon arvojen hakemiseen indeksinumeron avulla. Hakutoiminto palauttaa arvon, joka on linkitetty hakuindeksinumeroon. Esimerkiksi, jos tallennamme arvon 6 hakemistoon 2, hakutoiminto indeksinumerolla 2 palauttaa arvon 6.
Poista datatoiminto
Poistotoimintoa käytetään arvon poistamiseen hash-taulukosta. Toiminto poistetaan hakemistonumerolla. Kun arvo on poistettu, indeksinumero poistetaan. Sitä voidaan käyttää tallentamaan muita arvoja lisäystoiminnon avulla.
Hash-taulukon toteutus Python-esimerkillä
Katsotaanpa yksinkertaista esimerkkiä, joka laskee avaimen hajautusarvon
def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')
Hash-taulukon koodin selitys
TÄSSÄ,
- Määrittää funktion hash_key, joka hyväksyy parametrit-avaimen ja m.
- Käyttää yksinkertaista moduulioperaatiota hash-arvon määrittämiseksi
- Määrittää muuttujan m, joka alustetaan arvoon 7. Tämä on hash-taulukon koko
- Laskee ja tulostaa hash-arvon 3
- Laskee ja tulostaa hash-arvon 2
- Laskee ja tulostaa hash-arvon 9
- Laskee ja tulostaa hajautusarvon 11
- Laskee ja tulostaa hash-arvon 7
Yllä olevan koodin suorittaminen tuottaa seuraavat tulokset.
The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0
Esimerkki Python-sanakirjasta
Pythonissa on sisäänrakennettu tietotyyppi nimeltä Sanakirja. Sanakirja on esimerkki hash-taulukosta. Se tallentaa arvot käyttämällä avain- ja arvoparia. Hajautusarvot luodaan meille automaattisesti, ja törmäykset ratkaistaan meille taustalla.
Seuraava esimerkki osoittaa, kuinka voit käyttää sanakirjatietotyyppiä python 3: ssa
employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)
TÄSSÄ,
- Määrittää sanakirjamuuttujan työntekijän. Avaimen nimeä käytetään arvon tallentamiseen John Doe, ikä tallentaa 36 ja sijainti tallentaa arvon Business Manager.
- Hakee avaimen nimen arvon ja tulostaa sen päätelaitteeseen
- Päivittää avainkohdan arvon ohjelmistosuunnittelijaksi
- Tulostaa näppäinten nimen ja sijainnin arvot
- Poistaa kaikki arvot, jotka on tallennettu sanakirjamuuttuja työntekijäämme
- Tulostaa työntekijän arvon
Yllä olevan koodin suorittaminen tuottaa seuraavat tulokset.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Monimutkaisuusanalyysi
Hash-taulukoiden keskimääräinen aikakompleksisuus on O (1) parhaassa tapauksessa. Pahimmassa tapauksessa ajan monimutkaisuus on O (n). Pahin tapaus tapahtuu, kun monet arvot tuottavat saman hash-avaimen, ja meidän on ratkaistava törmäys koettelemalla.
Reaalimaailman sovellukset
Todellisessa maailmassa hash-taulukoita käytetään tietojen tallentamiseen
- Tietokannat
- Assosiatiiviset taulukot
- Sarjat
- Muistivälimuisti
Hash-taulukoiden edut
Tässä on hash-taulukoiden käytön edut / edut:
- Hash-taulukoilla on korkea suorituskyky etsiessään tietoja, lisäämällä ja poistamalla olemassa olevia arvoja.
- Hajautustaulukoiden ajan monimutkaisuus on vakio taulukon alkioiden lukumäärästä riippumatta.
- Ne toimivat erittäin hyvin myös suurten tietojoukkojen kanssa työskenneltäessä.
Hajautustaulukoiden haitat
Tässä on haittoja hash-taulukoiden käytöstä:
- Et voi käyttää nolla-arvoa avaimena.
- Törmäyksiä ei voida välttää, kun avaimet luodaan. hash-toiminnot. Törmäyksiä tapahtuu, kun jo käytössä oleva avain luodaan.
- Jos hajautusfunktiolla on useita törmäyksiä, se voi johtaa suorituskyvyn heikkenemiseen.
Yhteenveto:
- Hash-taulukoita käytetään tietojen tallentamiseen avain- ja arvoparilla.
- Hajautusfunktio laskee hajautusarvon matemaattisella algoritmilla.
- Törmäys tapahtuu, kun sama hash-arvo syntyy useammalle kuin yhdelle arvolle.
- Ketjutus ratkaisee törmäyksen luomalla linkitettyjä luetteloita.
- Luotaaminen ratkaisee törmäyksen löytämällä tyhjät paikat hash-taulukosta.
- Lineaarinen koetus etsii seuraavaa vapaata aukkoa arvon tallentamiseksi lähtöpaikasta alkaen, missä törmäys tapahtui.
- Toissijainen koetus käyttää polynomilausekkeita seuraavan vapaan paikan löytämiseen törmäyksen sattuessa.
- Kaksinkertainen hajautus käyttää toissijaista hajautusfunktion algoritmia seuraavan vapaan paikan löytämiseen törmäyksen sattuessa.
- Hash-taulukoiden suorituskyky on parempi verrattuna muihin tietorakenteisiin.
- Hajataulukoiden keskimääräinen aikakompleksuus on O (1)
- Sanakirjatietotyyppi pythonissa on esimerkki hash-taulukosta.
- Hash-taulukot tukevat lisäys-, haku- ja poistotoimintoja.
- Nolla-arvoa ei voida käyttää indeksiarvona.
- Törmäyksiä ei voida välttää hash-toiminnoissa. Hyvä hash-toiminto minimoi törmäysten määrän suorituskyvyn parantamiseksi.