Hashing er en populær teknikk som brukes for å lagre og hente data så raskt som mulig. Hovedårsaken bak bruk av hashing er at den utfører innsetting, sletting, søking og andre operasjoner

Hvorfor bruke Hashing?

I hashing kan alle operasjoner som å sette inn, søke og slette utføres i O(1), dvs. konstant tid. Den verste tilfelle-tidskompleksiteten for hashing forblir O(n), men den gjennomsnittlige sakstidskompleksiteten er O(1).

HashTable

Brukes for å lage en ny hashtabell.

Syntaks:

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

Grunnleggende operasjoner med syntaks

Få:

Brukes til å søke etter en nøkkel inne i hash-tabellen og returnere verdien som er knyttet til den nøkkelen.

Syntaks:

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

Sett inn:

Brukes til å sette inn et nytt nøkkelverdi-par i hashtabellen.

Syntaks:

// 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:

Brukes til å søke etter en verdi.

Syntaks:

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

Slett:

Brukes for å slette et bestemt nøkkelverdi-par fra hash-tabellen.

Syntaks:

// 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. Hash-tabell: En hash-tabell er en generalisering av matrisen. Det gir funksjonaliteten som en samling av data lagres i på en slik måte at det er enkelt å finne disse elementene senere hvis nødvendig. Dette gjør det svært effektivt å søke etter et element.

2. Hash-funksjon: En hash-funksjon brukes til å transformere en gitt nøkkel til en spesifikk sporindeks. den brukes til å kartlegge hver mulig nøkkel til en unik sporindeks. Hvis hver nøkkel er tilordnet en unik sporindeks, er hash-funksjonen kjent som en perfekt hash-funksjon. Det er veldig vanskelig å lage en perfekt hash-funksjon, men vår jobb som programmerer er å lage en slik hash-funksjon ved hjelp av hvilken antall kollisjoner er så få som mulig.

En god hash-funksjon bør ha følgende egenskaper:

• Effektivt beregningsdyktig.
• Bør fordele nøklene jevnt (Hver bordposisjon er like sannsynlig for hver).
• Bør minimere kollisjoner.
• Bør ha lav belastningsfaktor (antall elementer i tabellen delt på størrelsen på tabellen).

3. Kollisjonshåndtering: Siden en hash-funksjon gir oss et lite tall for en stor nøkkel, er det en mulighet for at to nøkler resulterer i samme verdi. Situasjonen der en nylig satt inn nøkkel tilordner en allerede opptatt plass i hashtabellen kalles kollisjon og må håndteres ved hjelp av en eller annen kollisjonshåndteringsteknikk. Følgende er måtene å håndtere kollisjoner på:

• Kjede: Ideen er å få hver celle i hashtabellen til å peke til en koblet liste over poster som har samme hashfunksjonsverdi. Kobling er enkelt, men krever ekstra minne utenfor bordet.
• Åpen adressering: Ved åpen adressering lagres alle elementer i selve hashtabellen. Hver tabelloppføring inneholder enten en post eller NIL. Når vi søker etter et element, undersøker vi bordsporene en etter en til ønsket element er funnet eller det er tydelig at elementet ikke er i tabellen.

Implementering med eksempel:

Trinn 1: Opprett en HashTable-klasse med tabell- og størrelsesstartegenskaper.

Steg 2: Legg til en privat setKey(key)-funksjon for å transformere nøkler til indekser.

Trinn 3: Legg til funksjonene insert() og get() for å legge til og få tilgang til nøkkelverdi-par fra tabellen.

Trinn 4: Legg til en remove()-funksjon for å fjerne en nøkkel fra hash-tabellen.

Eksempel 1: Anta at vi må lagre 5 tall 100,87,86,12,25 og 9 i en hashtabell. I dette tilfellet vil vi lage en setKey-funksjon der vi tar verdien som et argument og konverterer den til en indeks av hashtabellen. Nedenfor er gjennomføringen.

Javascript

Produksjon:

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

I output eller viser at tabellen har 1 eller 3 påfølgende tomme mellomrom/indekser.

Eksempel 2: Anta at vi ønsker å lagre kontaktnumrene til en familie på 5 medlemmer i en hash-tabell. For dette lager vi en hashtabell i størrelse 10 og lagrer kontaktinformasjonen. Indeksen vil bli satt ved hjelp av setKey private funksjonen som vil konvertere det siste sifferet i kontaktnummeret til indeksen til hashtabellen.

Javascript

Produksjon:

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

I output eller viser at tabellen har 1 eller 3 påfølgende tomme mellomrom/indekser.