Hashingul este o tehnică populară folosită pentru stocarea și preluarea datelor cât mai rapid posibil. Motivul principal din spatele utilizării hashingului este că efectuează inserarea, ștergerea, căutarea și alte operațiuni

De ce să folosiți Hashing?

În hashing, toate operațiunile precum inserarea, căutarea și ștergerea pot fi efectuate în O(1), adică timp constant. Complexitatea timpului cel mai rău caz pentru hashing rămâne O(n), dar complexitatea medie a timpului cazului este O(1).

HashTable

Folosit pentru a crea un nou tabel hash.

Sintaxă:

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

Operații de bază cu sintaxă

Obține:

Folosit pentru a căuta o cheie în interiorul tabelului hash și a returna valoarea asociată cu acea cheie.

Sintaxă:

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

Introduce:

Folosit pentru a insera o nouă pereche cheie-valoare în interiorul tabelului hash.

Sintaxă:

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

Căutare:

Folosit pentru a căuta o valoare.

Sintaxă:

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

Șterge:

Folosit pentru a șterge o anumită pereche cheie-valoare din tabelul hash.

Sintaxă:

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

Componentele hashingului în Javascript

1. Tabel Hash: Un tabel hash este o generalizare a tabloului. Oferă funcționalitatea în care o colecție de date este stocată în așa fel încât să fie ușor de găsit acele elemente ulterior, dacă este necesar. Acest lucru face căutarea unui element foarte eficientă.

2. Funcția Hash: O funcție hash este utilizată pentru a transforma o anumită cheie într-un index de slot specific. este folosit pentru a mapa fiecare cheie posibilă într-un index unic de slot. Dacă fiecare cheie este mapată într-un index unic de slot, atunci funcția hash este cunoscută ca o funcție hash perfectă. Este foarte dificil să creăm o funcție hash perfectă dar treaba noastră ca programator este să creăm o astfel de funcție hash cu ajutorul căreia numărul de coliziuni este cât mai puțin posibil.

O funcție hash bună ar trebui să aibă următoarele proprietăți:

• Calculabil eficient.
• Ar trebui să distribuie uniform cheile (fiecare poziție de masă este la fel de probabilă pentru fiecare).
• Ar trebui să minimizeze coliziunile.
• Ar trebui să aibă un factor de încărcare scăzut (numărul de articole din tabel împărțit la dimensiunea tabelului).

3. Gestionarea coliziunilor: Deoarece o funcție hash ne aduce un număr mic pentru o cheie mare, există posibilitatea ca două chei să aibă aceeași valoare. Situația în care o cheie nou introdusă se mapează la un slot deja ocupat din tabelul hash se numește coliziune și trebuie tratată folosind o tehnică de gestionare a coliziunilor. Următoarele sunt modalitățile de a gestiona coliziunile:

• Înlănțuire: Ideea este de a face ca fiecare celulă din tabelul hash să indice o listă legată de înregistrări care au aceeași valoare a funcției hash. Înlănțuirea este simplă, dar necesită memorie suplimentară în afara mesei.
• Adresare deschisă: În adresarea deschisă, toate elementele sunt stocate în tabelul hash în sine. Fiecare intrare de tabel conține fie o înregistrare, fie NIL. Când căutăm un element, examinăm sloturile de masă unul câte unul până când este găsit elementul dorit sau este clar că elementul nu se află în tabel.

Implementare cu Exemplu:

Pasul 1: Creați o clasă HashTable cu proprietăți inițiale de tabel și dimensiune.

Pasul 2: Adăugați o funcție privată setKey(key) pentru a transforma cheile în indici.

Pasul 3: Adăugați funcțiile insert() și get() pentru adăugarea și accesarea perechilor cheie-valoare din tabel.

Pasul 4: Adăugați o funcție remove() pentru a elimina o cheie din tabelul hash.

Exemplul 1: Să presupunem că trebuie să stocăm 5 numere 100,87,86,12,25 și 9 într-un hashtable. În acest caz, vom crea o funcție setKey în care vom lua valoarea ca argument și o vom converti într-un index al tabelului hash. Mai jos este implementarea.

Javascript

Ieșire:

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

În ieșire sau arată că tabelul are 1 sau 3 spații/indexuri goale consecutive.

Exemplul 2: Să presupunem că vrem să stocăm numerele de contact ale unei familii de 5 membri într-un tabel hash. Pentru aceasta, vom crea un tabel hash de dimensiunea 10 și vom stoca detaliile de contact. Indexul va fi setat folosind funcția privată setKey, care va converti ultima cifră a numărului de contact ca index al tabelului hash.

Javascript

Ieșire:

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

În ieșire sau arată că tabelul are 1 sau 3 spații/indexuri goale consecutive.