L'hashing è una tecnica popolare utilizzata per archiviare e recuperare i dati il ​​più velocemente possibile. Il motivo principale alla base dell'utilizzo dell'hashing è che esegue l'inserimento, l'eliminazione, la ricerca e altre operazioni

Perché usare l'hashing?

Nell'hashing, tutte le operazioni come l'inserimento, la ricerca e l'eliminazione possono essere eseguite in O(1), ovvero in tempo costante. La complessità temporale del caso peggiore per l'hashing rimane O(n), ma la complessità temporale del caso medio è O(1).

HashTable

Utilizzato per creare una nuova tabella hash.

Sintassi:

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

Operazioni di base con la sintassi

Ottenere:

Utilizzato per cercare una chiave all'interno della tabella hash e restituire il valore associato a quella chiave.

Sintassi:

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

Inserire:

Utilizzato per inserire una nuova coppia chiave-valore all'interno della tabella hash.

Sintassi:

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

Ricerca:

Utilizzato per cercare un valore.

Sintassi:

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

Eliminare:

Utilizzato per eliminare una particolare coppia chiave-valore dalla tabella hash.

Sintassi:

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

Componenti dell'hashing in Javascript

1. Tabella hash: Una tabella hash è una generalizzazione dell'array. Fornisce la funzionalità in cui una raccolta di dati viene archiviata in modo tale che sia facile trovare tali elementi in seguito, se necessario. Ciò rende la ricerca di un elemento molto efficiente.

2. Funzione hash: Una funzione hash viene utilizzata per trasformare una determinata chiave in un indice di slot specifico. viene utilizzato per mappare ogni possibile chiave in un indice di slot univoco. Se ogni chiave viene mappata in un indice di slot univoco, la funzione hash è nota come funzione hash perfetta. È molto difficile creare una funzione hash perfetta, ma il nostro compito come programmatori è creare una funzione hash con l'aiuto della quale il numero di collisioni sia il minore possibile.

Una buona funzione hash dovrebbe avere le seguenti proprietà:

• Calcolabile in modo efficiente.
• Dovrebbero distribuire uniformemente le chiavi (ogni posizione nella tabella è ugualmente probabile per ciascuna).
• Dovrebbe ridurre al minimo le collisioni.
• Dovrebbe avere un fattore di carico basso (il numero di elementi nella tabella diviso per la dimensione della tabella).

3. Gestione delle collisioni: Poiché una funzione hash ci fornisce un numero piccolo per una chiave grande, esiste la possibilità che due chiavi diano lo stesso valore. La situazione in cui una chiave appena inserita si associa a uno slot già occupato nella tabella hash è chiamata collisione e deve essere gestita utilizzando alcune tecniche di gestione delle collisioni. Di seguito sono riportati i modi per gestire le collisioni:

• Concatenamento: L'idea è di fare in modo che ogni cella della tabella hash punti a un elenco collegato di record che hanno lo stesso valore della funzione hash. Il concatenamento è semplice ma richiede memoria aggiuntiva all'esterno della tabella.
• Indirizzamento aperto: Nell'indirizzamento aperto, tutti gli elementi vengono memorizzati nella tabella hash stessa. Ogni voce della tabella contiene un record o NIL. Durante la ricerca di un elemento, esaminiamo gli slot della tabella uno per uno finché non viene trovato l'elemento desiderato o è chiaro che l'elemento non è nella tabella.

Implementazione con esempio:

Passo 1: Crea una classe HashTable con le proprietà iniziali della tabella e della dimensione.

Passo 2: Aggiungi una funzione privata setKey(key) per trasformare le chiavi in ​​indici.

Passaggio 3: Aggiungi le funzioni insert() e get() per aggiungere e accedere alle coppie chiave-valore dalla tabella.

Passaggio 4: Aggiungi una funzione Remove() per rimuovere una chiave dalla tabella hash.

Esempio 1: Supponiamo di dover memorizzare 5 numeri 100,87,86,12,25 e 9 in una tabella hash. In questo caso creeremo una funzione setKey in cui prenderemo il valore come argomento e lo convertiremo in un indice della tabella hash. Di seguito è riportata l'implementazione.

Javascript

Produzione:

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

Nell'output o mostra che la tabella contiene 1 o 3 spazi/indici vuoti consecutivi.

Esempio 2: Supponiamo di voler memorizzare i numeri di contatto di una famiglia di 5 membri in una tabella hash. Per questo, creeremo una tabella hash di dimensione 10 e memorizzeremo i dettagli di contatto. L'indice verrà impostato utilizzando la funzione privata setKey che convertirà l'ultima cifra del numero di contatto come indice della tabella hash.

Javascript

Produzione:

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

Nell'output o mostra che la tabella contiene 1 o 3 spazi/indici vuoti consecutivi.