Johdatus hajautustoimintoon C: ssä
Tässä artikkelissa on lyhyt huomautus hajautuksesta (hash table ja hash function). Tärkein käsite on 'etsiminen', joka määrittelee ajan monimutkaisuuden. Ajan monimutkaisuuden vähentämiseksi otetaan käyttöön mikään muu tietorakenne hajautuskonsepti, jolla on keskimäärin O (1) aika ja pahimmassa tapauksessa se vie O (n) ajan.
Hajautus on tekniikka, jolla on nopeampi pääsy elementteihin, joka kartoittaa annetut tiedot pienemmällä avaimella vertailuja varten. Yleensä tässä tekniikassa avaimet jäljitetään hajautustoiminnon avulla taulukkoksi, joka tunnetaan hajautustaulukkona.
Mikä on hash-toiminto?
Hajautusfunktio on toiminto, joka käyttää vakioajan operaatiota arvon tallentamiseen ja hakemiseen hajautustaulusta, jota käytetään näppäimillä kokonaislukuna ja jota käytetään hash-taulukon arvojen osoitteena.
Hash-toiminnon tyypit
Hajautustoimintojen tyypit selitetään alla:
1. Jakamismenetelmä
Tässä menetelmässä hash-funktio riippuu jäljellä olevasta jaosta.
Esimerkki: hash-taulukkoon asetettavat elementit ovat 42, 78, 89, 64 ja pidetään taulukon kokoa 10.
Hash (avain) = Elementit% taulukon koosta;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
Taulukon esitys voidaan nähdä alla:
2. Keskimmäinen neliömenetelmä
Tässä menetelmässä neliön elementin keskiosa otetaan indeksiksi.
Hajautustaulukkoon asetettava elementti on 210, 350, 99, 890 ja pöydän koko on 100.
210 * 210 = 44100, indeksi = 1, koska tuloksen (44100) keskiosa on 1.
350 * 350 = 122500, indeksi = 25, koska tuloksen (122500) keskiosa on 25.
99 * 99 = 9801, indeksi = 80, koska tuloksen (9801) keskiosa on 80.
890 * 890 = 792100, indeksi = 21, koska tuloksen (792100) keskiosa on 21.
3. Digitaalitaitto
Tässä menetelmässä taulukkoon asetettava elementti uh on singh-avain, joka saadaan jakamalla elementit eri osiin ja yhdistämällä sitten osat suorittamalla joitain yksinkertaisia matemaattisia toimenpiteitä.
Asetettava elementti ovat 23576623, 34687734.
- hash (avain) = 235 + 766 + 23 = 1024
- hash-avain) = 34 + 68 + 77 + 34 = 213
Oletetaan, että tällaisissa hajautustyypeissä on numeroita 1 - 100 ja hajautustaulun koko = 10. Elementit = 23, 12, 32
Hash (avain) = 23% 10 = 3;
Hash (avain) = 12% 10 = 2;
Hash (avain) = 32% 10 = 2;
Yllä olevasta esimerkistä huomaa, että molemmat elementit 12 ja 32 osoittavat taulukon 2. sijalle, jossa ei ole mahdollista kirjoittaa molempia samaan kohtaan, tällainen ongelma tunnetaan törmäyksenä. Tällaisten ongelmien välttämiseksi on olemassa joitain hajautustoimintojen tekniikoita, joita voidaan käyttää.
Törmäysratkaisutekniikoiden tyypit
Keskustelemme törmäyksen ratkaisutekniikoiden tyypeistä:
1. Ketju
Kuten nimestä voi päätellä, se tarjoaa tässä taulukossa olevan ketjun laatikoita tietueen taulukolle, jossa on kaksi elementtiä. Joten aina kun tällaisia törmäyksiä tapahtuu, ruudut toimivat linkitetyn luettelon muodossa.
Esimerkki: 23, 12, 32 pöydän koosta 10.
Hash (avain) = 23% 10 = 3;
Hash (avain) = 12% 10 = 2;
Hash (avain) = 32% 10 = 2;
2. Avaa osoittaminen
- Lineaarinen koetin
Tämä on toinen menetelmä törmäysongelmien ratkaisemiseksi. Kuten nimi kertoo törmäyksen tapahtuessa, kaksi elementtiä tulisi sijoittaa samaan taulukon kohtaan, mutta tällä menetelmällä voimme etsiä seuraavan tyhjän tilan tai merkinnän taulukosta ja sijoittaa toisen elementin. Tämä voi jälleen johtaa toiseen ongelmaan; Jos taulukosta ei löydy tyhjää merkintää, se johtaa klusteroitumiseen. Siksi tätä kutsutaan klusterointiongelmaksi, joka voidaan ratkaista seuraavalla menetelmällä.
Esimerkki: 23, 12, 32 pöydän koosta 10
Hash (avain) = 23% 10 = 3;
Hash (avain) = 12% 10 = 2;
Hash (avain) = 32% 10 = 2;
Tässä kaaviossa 12 ja 32 voidaan sijoittaa samaan kohtaan indeksin 2 kanssa, mutta tällä menetelmällä ne sijoitetaan lineaarisesti.
- Toissijainen koetus
Tämä menetelmä on ratkaisu klusterointiongelmaan lineaarisen koettamisen aikana. Tässä menetelmässä hash-toiminto hash-avaimella lasketaan seuraavasti: hash (avain) = (hash (avain) + x * x)% taulukon koosta (missä x = 0, 1, 2…).
Esimerkki: 23, 12, 32 pöydän koosta 10
Hash (avain) = 23% 10 = 3;
Hash (avain) = 12% 10 = 2;
Hash (avain) = 32% 10 = 2;
Tässä voimme nähdä, että 23 ja 12 voidaan sijoittaa helposti, mutta 32 ei voi jälleen kerran 12 ja 32 jakaa samaa merkintää samalla indeksillä taulukossa, kuten menetelmää kohden hash (avain) = (32 + 1 * 1) % 10 = 3. Mutta tässä tapauksessa taulukon merkintä indeksillä 3 sijoitetaan luvulla 23, joten meidän on lisättävä x-arvoa yhdellä. Hash (avain) = (32 + 2 * 2)% 10 = 6. Joten voimme nyt sijoittaa 32 merkinnässä taulukon indeksillä 6.
- Tuplahajautus
Tämä menetelmä on laskettava kaksi hajautusfunktiota törmäysongelman ratkaisemiseksi. Ensimmäinen lasketaan yksinkertaisella jakomenetelmällä. Toisen on täytettävä kaksi sääntöä; se ei saa olla yhtä suuri kuin 0 ja merkinnät on tutkittava.
- 1 (avain) = näppäimen% taulukon koosta.
- 2 (näppäin) = p - (näppäin mod p), missä p on alkuluvut <taulukon koko.
Esimerkki: 23, 12, 32 pöydän koosta 10
Hash (avain) = 23% 10 = 3;
Hash (avain) = 12% 10 = 2;
Hash (avain) = 32% 10 = 2;
Tässä taas elementti 32 voidaan sijoittaa käyttämällä hash2 (avain) = 5 - (32% 5) = 3. Joten 32 voidaan sijoittaa taulukon hakemistoon 5, joka on tyhjä, koska meidän on hypätä kolme merkintää sen sijoittamiseksi.
Päätelmä-hajautusfunktio C: ssä
Hajautus on yksi tärkeimmistä tekniikoista, kun etsitään dataa erittäin tehokkailla ja nopeilla menetelmillä, joissa käytetään hash-toimintoa ja hash-taulukoita. Jokainen elementti voidaan etsiä ja sijoittaa käyttämällä erilaisia hajautusmenetelmiä. Tämä tekniikka on aikakertoimen suhteen erittäin nopeampi kuin mikään muu datarakenne.
Suositellut artikkelit
Tämä on opas hajautusfunktioon C: ssä. Tässä keskustellaan hajautustoiminnon käyttöönotosta C: ssä, Mikä on hajautusfunktio, hajautusfunktiotyypit jne. Voit myös käydä läpi muiden ehdotettujen artikkeleidemme saadaksesi lisätietoja -
- Hajautus DBMS-järjestelmässä
- Salausprosessi
- Kuinka asentaa CakePHP?
- Kuinka lohkoketju toimii
- Hajautustoiminto Java-sovelluksessa
- Hajautustoiminto PHP: ssä | Kuinka työskennellä?