Hashing on suosittu tekniikka, jota käytetään tietojen tallentamiseen ja hakemiseen mahdollisimman nopeasti. Pääsyy hajautusten käyttämiseen on se, että se suorittaa lisäys-, poisto-, haku- ja muita toimintoja

Miksi käyttää Hashingia?

Hashingissa kaikki toiminnot, kuten lisääminen, etsiminen ja poistaminen, voidaan suorittaa O(1):ssä eli vakioajassa. Hajautusajan pahimman tapauksen monimutkaisuus on edelleen O(n), mutta keskimääräinen tapauksen ajan monimutkaisuus on O(1).

HashTable

Käytetään uuden hash-taulukon luomiseen.

Syntaksi:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

Perustoiminnot syntaksin kanssa

Saada:

Käytetään avaimen etsimiseen hash-taulukon sisällä ja tuohon avaimeen liittyvän arvon palauttamiseen.

Syntaksi:

// function inside hashtable class to  // access a value using its key get(key) {  const target = this._setKey(key);  return this.table[target]; } 

Lisää:

Käytetään uuden avain-arvo-parin lisäämiseen hash-taulukon sisään.

Syntaksi:

// function to insert a value in the  // hash table using setKey function insert(value) {  const index = this._setKey(value);  this.table[index] = value;  this.size++; } 

Hae:

Käytetään arvon etsimiseen.

Syntaksi:

// search a value (by getting its  // key using setKey function) search(value){  const index = this._setKey(value);  if(this.table[index]==value)  console.log('The value is found at index : ',index);  else  console.log('Not found'); } 

Poistaa:

Käytetään tietyn avain-arvo-parin poistamiseen hash-taulukosta.

Syntaksi:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

Hashing-komponentit Javascriptissä

1. Hash-taulukko: Hash-taulukko on taulukon yleistys. Se tarjoaa toiminnallisuuden, johon tietokokoelma tallennetaan siten, että ne on helppo löytää myöhemmin tarvittaessa. Tämä tekee elementin etsimisestä erittäin tehokasta.

2. Hash-funktio: Hajautusfunktiota käytetään muuttamaan tietty avain tietyksi paikkaindeksiksi. sitä käytetään yhdistämään jokainen mahdollinen avain yksilölliseen paikkahakemistoon. Jos jokainen avain on kartoitettu yksilölliseen paikkaindeksiin, tiivistefunktio tunnetaan täydellisenä hash-funktiona. Täydellisen hash-funktion luominen on erittäin vaikeaa, mutta meidän tehtävämme ohjelmoijana on luoda sellainen hash-funktio, jonka avulla törmäyksiä on mahdollisimman vähän.

Hyvällä hash-funktiolla tulee olla seuraavat ominaisuudet:

• Tehokkaasti laskettavissa.
• Pitäisi jakaa avaimet tasaisesti (Jokainen pöytäpaikka on yhtä todennäköinen jokaiselle).
• Pitäisi minimoida törmäykset.
• Pitäisi olla alhainen käyttöaste (taulukon kohteiden määrä jaettuna taulukon koolla).

3. Törmäyskäsittely: Koska hash-funktio saa meille pienen luvun suurelle avaimelle, on mahdollista, että kaksi avainta johtavat samaan arvoon. Tilannetta, jossa äskettäin lisätty avain kohdistuu hash-taulukon jo varattuun paikkaan, kutsutaan törmäykseksi ja se on käsiteltävä jollakin törmäyksenkäsittelytekniikalla. Seuraavat tavat käsitellä törmäyksiä:

• Ketjutus: Ajatuksena on saada jokainen hash-taulukon solu osoittamaan linkitettyä luetteloa tietueista, joilla on sama hash-funktion arvo. Ketjuttaminen on yksinkertaista, mutta vaatii lisämuistia pöydän ulkopuolella.
• Avoin osoite: Avoimessa osoittamisessa kaikki elementit tallennetaan itse hash-taulukkoon. Jokainen taulukkomerkintä sisältää joko tietueen tai NIL:n. Elementtiä haettaessa tarkastellaan taulukkopaikkoja yksitellen, kunnes haluttu elementti löytyy tai on selvää, ettei elementtiä ole taulukossa.

Toteutus esimerkillä:

Vaihe 1: Luo HashTable-luokka taulukon ja koon alkuominaisuuksilla.

Vaihe 2: Lisää yksityinen setKey(avain) -funktio avainten muuntamiseksi indekseiksi.

Vaihe 3: Lisää insert()- ja get()-funktiot avainarvo-parien lisäämistä ja käyttöä varten taulukosta.

Vaihe 4: Lisää poista()-funktio poistaaksesi avaimen hash-taulukosta.

Esimerkki 1: Oletetaan, että meidän on tallennettava 5 numeroa 100, 87, 86, 12, 25 ja 9 hash-taulukkoon. Tässä tapauksessa luomme setKey-funktion, jossa otamme arvon argumenttina ja muunnamme sen hash-taulukon indeksiksi. Alla toteutus.

Javascript

Lähtö:

[ 100,  ,  12,  ,  86,  87,  ,  9 ] The value is found at index : 7 Not found [ 100,  ,  [],  ,  86,  87,  ,  9 ] 

Tulosteessa tai näyttää, että taulukossa on 1 tai 3 peräkkäistä tyhjää tilaa/indeksiä.

Esimerkki 2: Oletetaan, että haluamme tallentaa 5-jäsenisen perheen yhteystiedot hash-taulukkoon. Tätä varten luomme hash-taulukon, jonka koko on 10 ja tallennamme yhteystiedot. Indeksi asetetaan käyttämällä setKey private -toimintoa, joka muuntaa yhteyshenkilön numeron viimeisen numeron hash-taulukon indeksiksi.

Javascript

Lähtö:

[ ,  92752521,  98747512,  94755523,  ,  98754525,  ,  98556529 ] The contact number is found at index : 1 Contact Number not found [ ,  [],  98747512,  94755523,  ,  98754525,  ,  98556529 ] 

Tulosteessa tai näyttää, että taulukossa on 1 tai 3 peräkkäistä tyhjää tilaa/indeksiä.