Hashing er en populær teknik, der bruges til at gemme og hente data så hurtigt som muligt. Hovedårsagen til at bruge hashing er, at den udfører indsættelse, sletning, søgning og andre handlinger

Hvorfor bruge Hashing?

I hashing kan alle operationer som indsættelse, søgning og sletning udføres i O(1), dvs. konstant tid. Den værste tidskompleksitet for hashing forbliver O(n), men den gennemsnitlige sagstidskompleksitet er O(1).

HashTabel

Bruges til at oprette en ny hash-tabel.

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

Grundlæggende handlinger med syntaks

Få:

Bruges til at søge efter en nøgle inde i hash-tabellen og returnere den værdi, der er knyttet til denne nøgle.

Syntaks:

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

Indsæt:

Bruges til at indsætte et nyt nøgle-værdi-par i hash-tabellen.

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øg:

Bruges til at søge efter en værdi.

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

Slet:

Bruges til at slette et bestemt nøgle-værdi-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 af hashing i Javascript

1. Hash-tabel: En hash-tabel er en generalisering af arrayet. Det giver den funktionalitet, hvori en samling af data lagres på en sådan måde, at det er nemt at finde disse elementer senere, hvis det kræves. Dette gør det meget effektivt at søge efter et element.

2. Hash-funktion: En hash-funktion bruges til at transformere en given nøgle til et specifikt slotindeks. det bruges til at kortlægge hver eneste mulig nøgle til et unikt slotindeks. Hvis hver nøgle er mappet til et unikt slotindeks, er hash-funktionen kendt som en perfekt hash-funktion. Det er meget svært at skabe en perfekt hash-funktion, men vores opgave som programmør er at skabe en sådan hash-funktion, ved hjælp af hvilken antallet af kollisioner er så få som muligt.

En god hash-funktion skal have følgende egenskaber:

• Effektivt beregnelig.
• Bør fordele nøglerne ensartet (Hver bordposition er lige sandsynlig for hver).
• Bør minimere kollisioner.
• Bør have en lav belastningsfaktor (antallet af genstande i tabellen divideret med bordets størrelse).

3. Kollisionshåndtering: Da en hash-funktion giver os et lille tal for en stor nøgle, er der mulighed for, at to nøgler resulterer i samme værdi. Situationen, hvor en nyligt indsat nøgle mapper til en allerede optaget plads i hashtabellen, kaldes kollision og skal håndteres ved hjælp af en eller anden kollisionshåndteringsteknik. Følgende er måderne at håndtere kollisioner på:

• Kædning: Ideen er at få hver celle i hash-tabellen til at pege på en sammenkædet liste over poster, der har samme hashfunktionsværdi. Kædning er enkel, men kræver ekstra hukommelse uden for bordet.
• Åbn adressering: Ved åben adressering gemmes alle elementer i selve hash-tabellen. Hver tabelpost indeholder enten en post eller NIL. Når vi søger efter et element, undersøger vi bordpladserne en efter en, indtil det ønskede element er fundet, eller det er tydeligt, at elementet ikke er i tabellen.

Implementering med eksempel:

Trin 1: Opret en HashTable-klasse med tabel- og størrelsesstartegenskaber.

Trin 2: Tilføj en privat setKey(key) funktion for at omdanne nøgler til indekser.

Trin 3: Tilføj funktionerne insert() og get() for at tilføje og få adgang til nøgleværdi-par fra tabellen.

Trin 4: Tilføj en remove()-funktion for at fjerne en nøgle fra hash-tabellen.

Eksempel 1: Antag, at vi skal gemme 5 numre 100,87,86,12,25 og 9 i en hashtabel. I dette tilfælde vil vi oprette en setKey-funktion, hvor vi tager værdien som et argument og konverterer den til et indeks for hash-tabellen. Nedenfor er implementeringen.

Javascript

Produktion:

[ 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å hinanden følgende tomme mellemrum/indekser.

Eksempel 2: Antag, at vi ønsker at gemme kontaktnumrene for en familie på 5 medlemmer i en hash-tabel. Til dette opretter vi en hash-tabel i størrelse 10 og gemmer kontaktoplysningerne. Indekset vil blive indstillet ved hjælp af setKey private-funktionen, som vil konvertere det sidste ciffer i kontaktnummeret som indekset for hash-tabellen.

Javascript

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 viser, at tabellen har 1 eller 3 på hinanden følgende tomme mellemrum/indekser.