Hashing is een populaire techniek die wordt gebruikt om gegevens zo snel mogelijk op te slaan en op te halen. De belangrijkste reden achter het gebruik van hashing is dat het invoeg-, verwijderings-, zoek- en andere bewerkingen uitvoert

Waarom hashing gebruiken?

Bij hashen kunnen alle bewerkingen zoals invoegen, zoeken en verwijderen worden uitgevoerd in O(1), dat wil zeggen in constante tijd. De tijdscomplexiteit in het slechtste geval voor hashing blijft O(n), maar de gemiddelde tijdscomplexiteit is O(1).

HashTabel

Wordt gebruikt om een ​​nieuwe hashtabel te maken.

Syntaxis:

// 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;  } } 

Basisbewerkingen met syntaxis

Krijgen:

Wordt gebruikt om een ​​sleutel in de hashtabel te zoeken en de waarde terug te geven die aan die sleutel is gekoppeld.

Syntaxis:

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

Invoegen:

Wordt gebruikt om een ​​nieuw sleutelwaardepaar in de hashtabel in te voegen.

Syntaxis:

// 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++; } 

Zoekopdracht:

Wordt gebruikt om naar een waarde te zoeken.

Syntaxis:

// 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'); } 

Verwijderen:

Wordt gebruikt om een ​​bepaald sleutel-waardepaar uit de hashtabel te verwijderen.

Syntaxis:

// 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;  } } 

Onderdelen van hashing in Javascript

1. Hashtabel: Een hashtabel is een generalisatie van de array. Het geeft de functionaliteit waarbij een verzameling gegevens zodanig wordt opgeslagen dat deze indien nodig later gemakkelijk terug te vinden zijn. Dit maakt het zoeken naar een element zeer efficiënt.

2. Hash-functie: Een hashfunctie wordt gebruikt om een ​​bepaalde sleutel om te zetten in een specifieke slotindex. het wordt gebruikt om elke mogelijke sleutel in een unieke slotindex in kaart te brengen. Als elke sleutel wordt toegewezen aan een unieke slotindex, staat de hashfunctie bekend als een perfecte hashfunctie. Het is erg moeilijk om een ​​perfecte hashfunctie te creëren, maar het is onze taak als programmeur om zo'n hashfunctie te creëren met behulp waarvan het aantal botsingen zo min mogelijk is.

Een goede hashfunctie moet de volgende eigenschappen hebben:

• Efficiënt berekenbaar.
• Moet de sleutels gelijkmatig verdelen (elke tafelpositie is voor elke tafel even waarschijnlijk).
• Moet botsingen minimaliseren.
• Moet een lage bezettingsgraad hebben (het aantal items in de tabel gedeeld door de grootte van de tabel).

3. Botsingsafhandeling: Omdat een hashfunctie ons een klein getal oplevert voor een grote sleutel, bestaat de mogelijkheid dat twee sleutels dezelfde waarde opleveren. De situatie waarin een nieuw ingevoegde sleutel wordt toegewezen aan een reeds bezet slot in de hashtabel, wordt botsing genoemd en moet worden afgehandeld met behulp van een techniek voor het afhandelen van botsingen. Hieronder volgen de manieren om met botsingen om te gaan:

• Keten: Het idee is om elke cel van de hashtabel te laten verwijzen naar een gekoppelde lijst met records die dezelfde hashfunctiewaarde hebben. Het koppelen is eenvoudig, maar vereist extra geheugen buiten de tabel.
• Open adressering: Bij open adressering worden alle elementen opgeslagen in de hashtabel zelf. Elke tabelinvoer bevat een record of NIL. Bij het zoeken naar een element onderzoeken we de tabelslots één voor één totdat het gewenste element is gevonden of het duidelijk is dat het element niet in de tabel staat.

Implementatie met voorbeeld:

Stap 1: Maak een HashTable-klasse met initiële eigenschappen voor tabel en grootte.

Stap 2: Voeg een private setKey(key)-functie toe om sleutels om te zetten in indices.

Stap 3: Voeg de functies insert() en get() toe voor het toevoegen en openen van sleutel-waardeparen uit de tabel.

Stap 4: Voeg een remove()-functie toe om een ​​sleutel uit de hashtabel te verwijderen.

Voorbeeld 1: Stel dat we 5 getallen 100,87,86,12,25 en 9 in een hashtabel moeten opslaan. In dit geval maken we een setKey-functie waarin we de waarde als argument nemen en deze converteren naar een index van de hashtabel. Hieronder vindt u de implementatie.

Javascript

Uitgang:

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

In de uitvoer of wordt weergegeven dat de tabel 1 of 3 opeenvolgende lege spaties/indexen heeft.

Voorbeeld 2: Stel dat we de contactnummers van een gezin van vijf leden in een hashtabel willen opslaan. Hiervoor maken we een hashtabel van maat 10 en slaan we de contactgegevens op. De index wordt ingesteld met behulp van de setKey private-functie, die het laatste cijfer van het contactnummer omzet in de index van de hashtabel.

Javascript

Uitgang:

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

In de uitvoer of wordt weergegeven dat de tabel 1 of 3 opeenvolgende lege spaties/indexen heeft.