Hashing är en populär teknik som används för att lagra och hämta data så snabbt som möjligt. Den främsta anledningen till att använda hash är att den utför infogning, radering, sökning och andra operationer

Varför använda Hashing?

I hashing kan alla operationer som infogning, sökning och radering utföras i O(1) dvs konstant tid. Den värsta fallets tidskomplexitet för hashing förblir O(n) men den genomsnittliga fallets tidskomplexitet är O(1).

HashTable

Används för att skapa en ny hashtabell.

Syntax:

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

Grundläggande funktioner med syntax

Skaffa sig:

Används för att söka efter en nyckel i hashtabellen och returnera värdet som är associerat med den nyckeln.

Syntax:

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

Föra in:

Används för att infoga ett nytt nyckel-värdepar i hashtabellen.

Syntax:

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

Sök:

Används för att söka efter ett värde.

Syntax:

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

Radera:

Används för att ta bort ett särskilt nyckel-värdepar från hashtabellen.

Syntax:

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

Komponenter av hashing i Javascript

1. Hashtabell: En hashtabell är en generalisering av arrayen. Det ger den funktionalitet i vilken en samling av data lagras på ett sådant sätt att det är lätt att hitta dessa objekt senare om det behövs. Detta gör sökningen efter ett element mycket effektivt.

lejon jämfört med en tiger

2. Hash-funktion: En hash-funktion används för att omvandla en given nyckel till ett specifikt slotindex. den används för att mappa varje möjlig nyckel till ett unikt slotindex. Om varje nyckel mappas till ett unikt slotindex, är hashfunktionen känd som en perfekt hashfunktion. Det är väldigt svårt att skapa en perfekt hashfunktion men vårt jobb som programmerare är att skapa en sådan hashfunktion med hjälp av vilken antalet kollisioner är så få som möjligt.

En bra hashfunktion bör ha följande egenskaper:

jämförbar java

• Effektivt beräkningsbar.
• Bör fördela nycklarna jämnt (Varje bordsposition är lika sannolikt för varje).
• Ska minimera kollisioner.
• Bör ha en låg belastningsfaktor (antalet artiklar i tabellen dividerat med tabellens storlek).

3. Kollisionshantering: Eftersom en hashfunktion ger oss ett litet tal för en stor nyckel, finns det en möjlighet att två nycklar resulterar i samma värde. Situationen där en nyligen införd nyckel mappar till en redan upptagen plats i hashtabellen kallas kollision och måste hanteras med någon kollisionshanteringsteknik. Följande är sätten att hantera kollisioner:

• Kedja: Tanken är att få varje cell i hashtabellen att peka på en länkad lista med poster som har samma hashfunktionsvärde. Kedja är enkelt men kräver ytterligare minne utanför bordet.
• Öppna adressering: Vid öppen adressering lagras alla element i själva hashtabellen. Varje tabellpost innehåller antingen en post eller NIL. När vi söker efter ett element undersöker vi tabellplatserna en efter en tills det önskade elementet hittas eller det är tydligt att elementet inte finns i tabellen.

Implementering med exempel:

Steg 1: Skapa en HashTable-klass med initialegenskaper för tabell och storlek.

Steg 2: Lägg till en privat setKey(key)-funktion för att omvandla nycklar till index.

Steg 3: Lägg till funktionerna insert() och get() för att lägga till och komma åt nyckel-värdepar från tabellen.

Steg 4: Lägg till en remove()-funktion för att ta bort en nyckel från hashtabellen.

Exempel 1: Anta att vi måste lagra 5 nummer 100,87,86,12,25 och 9 i en hashtabell. I det här fallet kommer vi att skapa en setKey-funktion där vi tar värdet som ett argument och konverterar det till ett index för hashtabellen. Nedan följer genomförandet.

Javascript

tvådimensionellt array-program i c

>

>

Produktion:

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

I output eller visar att tabellen har 1 eller 3 på varandra följande tomma utrymmen/index.

Exempel 2: Anta att vi vill lagra kontaktnumren för en familj med 5 medlemmar i en hashtabell. För detta skapar vi en hashtabell i storlek 10 och lagrar kontaktuppgifterna. Indexet kommer att ställas in med den privata setKey-funktionen som konverterar den sista siffran i kontaktnumret till indexet för hashtabellen.

Javascript

pete davidsons ålder

sharwanand

>

>

Produktion:

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

I output eller visar att tabellen har 1 eller 3 på varandra följande tomma utrymmen/index.