Tabella hash di JavaScript – Hashing associativo di array in JS

Articolo originale: https://www.freecodecamp.org/news/javascript-hash-table-associative-array-hashing-in-js/

Le tabelle Hash sono una struttura dati che consentono di creare un elenco di valori accoppiati. È quindi possibile recuperare un determinato valore utilizzando la chiave per quel valore, che è stata inserita in precedenza nella tabella.

Una tabella Hash trasforma una chiave in un indice intero utilizzando una funzione hash, e l'indice deciderà dove archiviare la coppia chiave/valore in memoria:

Comunemente utilizzerai una tabella Hash per via della velocita delle sue operazioni di ricerca, inserimento ed eliminazione:

Fonte da Wikipedia

Questo tutorial ti aiuterà a comprendere l'implementazione della tabella Hash in JavaScript e come puoi creare la tua classe di tabella Hash.

Per prima cosa, diamo un'occhiata alle classi Object e Map di JavaScript.

Come utilizzare le tabelle Hash con le classi Object e Map in JavaScript

L'esempio più comune di tabella Hash in JavaScript è il tipo di dati Object, in cui è possibile accoppiare il valore della proprietà dell'oggetto con una chiave della proprietà.

Nell'esempio seguente, la chiave Nathan è associata al valore del numero di telefono "555-0182" e la chiave Jane è associata al valore "315-0322":

let obj = {
  Nathan: "555-0182",
  Jane: "315-0322"
}

Ma il tipo Object di JavaScript è un tipo speciale di implementazione della tabella Hash per due motivi:

• Ha proprietà aggiuntive dalla classe Object. Le chiavi che inserisci potrebbero entrare in conflitto e sovrascrivere le proprietà predefinite ereditate dalla classe.
• La dimensione della tabella Hash non viene tracciata. È necessario contare manualmente quante proprietà sono definite dal programmatore oltre quelle ereditate dal prototipo.

Ad esempio, il prototipo Object ha il metodo hasOwnProperty() che permette di verificare se una proprietà non sia stata ereditata:

const obj = {};
obj.name = "Nathan";

console.log(obj.hasOwnProperty("name")); // true

JavaScript non blocca un tentativo di sovrascrivere il metodo hasOwnProperty(), e ciò potrebbe causare un errore come questo:

const obj = {};
obj.name = "Nathan";
obj.hasOwnProperty = true;

console.log(obj.hasOwnProperty("name")); 
// Error: obj.hasOwnProperty is not a function

Per gestire queste carenze, JavaScript ha creato un'altra implementazione della struttura dati Hash Table che viene chiamata Map

Proprio come Object, Map ti consente di archiviare coppie chiave-valore all'interno della struttura dei dati. Ecco un esempio di Map in azione:

const collection = new Map();

collection.set("Nathan", "555-0182");
collection.set("Jane", "555-0182");

console.log(collection.get("Nathan")); // 555-0182
console.log(collection.size); // 2

A differenza del tipo Object, Map richiede l'uso dei metodi set() e get() per definire e recuperare qualsiasi valore di coppia di chiavi che si desidera aggiungere alla struttura dati.

Inoltre, non puoi sovrascrivere le proprietà ereditate di Map. Ad esempio, il codice seguente ha tentato di sovrascrivere il valore della proprietà size in false:

const collection = new Map();

collection.set("Nathan", "555-0182");
collection["size"] = false;

console.log(collection.get("size")); // undefined
console.log(collection.size); // 1

Come puoi vedere dal codice sopra, non puoi aggiungere una nuova voce all'oggetto Map senza usare il metodo set().

Anche la struttura dei dati Map è iterabile, il che significa che puoi scorrere i dati come segue:

const myMap = new Map();

myMap.set("Nathan", "555-0182");
myMap.set("Jane", "315-0322");

for (let [key, value] of myMap) {
  console.log(`${key} = ${value}`);
}

Ora che hai imparato come JavaScript implementa le tabelle Hash sotto forma di strutture dati Object e Map, vediamo come creare la tua implementazione delle tabelle Hash.

Come implementare una struttura dati di una tabella Hash in JavaScript

Sebbene JavaScript abbia già due implementazioni di tabelle Hash, scrivere la propria implementazione di tabelle Hash è una delle domande più comuni nel colloquio in JavaScript.

Puoi implementare una tabella Hash in JavaScript in tre passaggi:

• Crea una classe HashTable con le proprietà iniziali table e size
• Aggiungi una funzione hash() per trasformare le chiavi in ​​indici
• Aggiungere i metodi set() e get() per aggiungere e recuperare le coppie chiave/valore dalla tabella.

Bene, iniziamo con la creazione della classe HashTable. Il codice seguente creerà una table di contenitori con la dimensione di 127:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }
}

Tutte le tue coppie chiave/valore verranno archiviate all'interno della proprietà table.

Come scrivere il metodo hash()

Successivamente, è necessario creare il metodo hash() che accetterà un valore key e lo trasformerà in un indice.

Un modo semplice per creare l'hash sarebbe sommare il codice ASCII dei caratteri nella chiave usando il metodo charCodeAt() come segue. Nota che il metodo è nominato usando _ per indicare che si tratta di una classe privata:

_hash(key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash;
}

Ma poiché la classe HashTable ha solo 127 contenitori, questo significa che il metodo _hash() deve restituire un numero compreso tra 0 e 127.

Per garantire che il valore hash non ecceda la dimensione del contenitore, è necessario utilizzare l'operatore modulo come mostrato di seguito:

_hash(key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % this.table.length;
}

Ora che hai completato il metodo _hash(), è il momento di scrivere i metodi set() e get()

Come scrivere il metodo set()

Per impostare la coppia chiave/valore nella tua tabella Hash, devi scrivere un metodo set() che accetti come parametri (key, value):

• Il metodo set() chiamerà il metodo _hash() per ottenere il valore index.
• La coppia [key, value] verrà assegnata a table all'indice specificato in index
• Quindi, la proprietà size verrà incrementata di uno

set(key, value) {
  const index = this._hash(key);
  this.table[index] = [key, value];
  this.size++;
}

Ora che il metodo set() è completo, scriviamo il metodo get() per recuperare un valore tramite la sua chiave.

Come scrivere il metodo get()

Per ottenere un determinato valore dalla tabella Hash, è necessario scrivere un metodo get() che accetti un valore key come parametro:

• Il metodo chiamerà il metodo _hash() per recuperare ancora una volta l' index della tabella
• Restituisce il valore memorizzato intable[index]

get(key) {
  const index = this._hash(key);
  return this.table[index];
}

In questo modo, il metodo get() restituirà la coppia chiave/valore o undefined quando non è presente alcuna coppia chiave/valore memorizzata nell'index specificato.

Fin qui tutto bene. Aggiungiamo ora un altro metodo, per eliminare la coppia chiave/valore dalla tabella Hash.

Come scrivere il metodo remove()

Per eliminare una coppia chiave/valore dalla tabella Hash, è necessario scrivere un metodo remove() che accetti un valore key come parametro:

• Recupera l'index corrispondente usando il metodo _hash()
• Controlla se table[index] ha un valore veritiero e la proprietà length sia maggiore di zero. Se così è, assegna il valore undefined al corrispondente index e decrementa la proprietà size di uno.
• In caso contrario, restituisce semplicemente false

remove(key) {
  const index = this._hash(key);

  if (this.table[index] && this.table[index].length) {
    this.table[index] = undefined;
    this.size--;
    return true;
  } else {
    return false;
  }
}

Con questo, ora hai un metodo remove() funzionante. Vediamo se la classe HashTable funziona correttamente.

Come testare l'implementazione della tabella Hash

È ora di testare l'implementazione della tabella Hash. Ecco di nuovo il codice completo:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  set(key, value) {
    const index = this._hash(key);
    this.table[index] = [key, value];
    this.size++;
  }

  get(key) {
    const target = this._hash(key);
    return this.table[target];
  }

  remove(key) {
    const index = this._hash(key);

    if (this.table[index] && this.table[index].length) {
      this.table[index] = [];
      this.size--;
      return true;
    } else {
      return false;
    }
  }
}

Per testare la classe HashTable, creerò una nuova istanza di class e imposterò alcune coppie chiave/valore come mostrato di seguito. Le coppie chiave/valore di seguito sono solo valori numerici arbitrari abbinati a nomi di paesi senza alcun significato speciale:

const ht = new HashTable();
ht.set("Canada", 300);
ht.set("France", 100);
ht.set("Spain", 110);

Quindi, proviamo a recuperarli usando il metodo get():

console.log(ht.get("Canada")); // [ 'Canada', 300 ]
console.log(ht.get("France")); // [ 'France', 100 ]
console.log(ht.get("Spain")); // [ 'Spain', 110 ]

Infine, proviamo a cancellare uno di questi valori con il metodo remove():

console.log(ht.remove("Spain")); // true
console.log(ht.get("Spain")); // undefined

Bene, tutti i metodi funzionano come previsto. Proviamo un altro inserimento con una nuova istanza di HashTable e recuperiamo quei valori:

const ht = new HashTable();

ht.set("Spain", 110);
ht.set("ǻ", 192);

console.log(ht.get("Spain")); // [ 'ǻ', 192 ]
console.log(ht.get("ǻ")); // [ 'ǻ', 192 ]

Ops! Sembra che siamo finiti nei guai qui. 😨

Come gestire il conflitto dell'indice

A volte, la funzione hash in una tabella Hash può restituire lo stesso numero index. Nel caso precedente, le stringhe "Spain" ed "ǻ" restituiscono entrambi lo stesso valore hash perché il numero 507 è per entrambi la somma dei rispettivi codici ASCII.

Lo stesso valore hash farà collidere l'indice , sovrascrivendo la voce precedente con quella nuova.

Al momento, i dati archiviati nella nostra implementazione della tabella Hash sono i seguenti:

[
    [ "Spain", 110],
    [ "France", 100]
]

Per gestire il conflitto dei numeri index, è necessario memorizzare la coppia chiave/valore in un secondo array in modo che il risultato finale appaia come segue:

[
    [
        [ "Spain", 110 ],
        [ "ǻ", 192 ]
    ],
    [
        ["France", 100]
    ],
]

Per creare il secondo array, è necessario aggiornare il metodo set() in modo che:

• Guardi table[index] e gli passi i valori dell'array.
• Se la chiave in uno degli array è uguale alla key passata al metodo, sostituisce il valore in index 1 e interrompere qualsiasi ulteriore esecuzione con l'istruzione return.
• Se non viene trovata alcuna corrispondenza con key, esegue il push di un nuovo array di chiave e valore nel secondo array.
• Altrimenti, inizializza un nuovo array e invia la coppia chiave/valore al valore index specificato
• Ogni volta che viene chiamato il metodo push(), incrementa la proprietà size di uno.

Il codice completo del metodo set() sarà il seguente:

set(key, value) {
  const index = this._hash(key);
  if (this.table[index]) {
    for (let i = 0; i < this.table[index].length; i++) {
      // Find the key/value pair in the chain
      if (this.table[index][i][0] === key) {
        this.table[index][i][1] = value;
        return;
      }
    }
    // not found, push a new key/value pair
    this.table[index].push([key, value]);
  } else {
    this.table[index] = [];
    this.table[index].push([key, value]);
  }
  this.size++;
}

Quindi, aggiorna il metodo get() in modo che controlli anche l'array di secondo livello con un ciclo for e restituisca la coppia chiave/valore corretta:

get(key) {
  const target = this._hash(key);
  if (this.table[target]) {
    for (let i = 0; i < this.table.length; i++) {
      if (this.table[target][i][0] === key) {
        return this.table[target][i][1];
      }
    }
  }
  return undefined;
}

Infine, è necessario aggiornare il metodo remove() in modo che esegua il ciclo sull'array di secondo livello e rimuova l'array con il valore key corretto utilizzando il metodo splice():

remove(key) {
  const index = this._hash(key);

  if (this.table[index] && this.table[index].length) {
    for (let i = 0; i < this.table.length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index].splice(i, 1);
        this.size--;
        return true;
      }
    }
  } else {
    return false;
  }
}

Con ciò, la tua classe HashTable sarà in grado di evitare qualsiasi conflitto di numeri di indice e memorizzare la coppia chiave/valore all'interno dell'array di secondo livello.

Come bonus, aggiungiamo un metodo display() che visualizzerà tutte le coppie chiave/valore memorizzate nella tabella Hash. Per scorrere la tabella devi solo usare il metodo forEach() , e il metodo map() per riportare i valori in una stringa come mostrato di seguito:

display() {
  this.table.forEach((values, index) => {
    const chainedValues = values.map(
      ([key, value]) => `[ ${key}: ${value} ]`
    );
    console.log(`${index}: ${chainedValues}`);
  });
}

Ecco il nuovo codice completo della classe HashTable con l'eliminazione del conflitto come tuo riferimento:

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  set(key, value) {
    const index = this._hash(key);
    if (this.table[index]) {
      for (let i = 0; i < this.table[index].length; i++) {
        if (this.table[index][i][0] === key) {
          this.table[index][i][1] = value;
          return;
        }
      }
      this.table[index].push([key, value]);
    } else {
      this.table[index] = [];
      this.table[index].push([key, value]);
    }
    this.size++;
  }

  get(key) {
    const index = this._hash(key);
    if (this.table[index]) {
      for (let i = 0; i < this.table.length; i++) {
        if (this.table[index][i][0] === key) {
          return this.table[index][i][1];
        }
      }
    }
    return undefined;
  }

  remove(key) {
    const index = this._hash(key);

    if (this.table[index] && this.table[index].length) {
      for (let i = 0; i < this.table.length; i++) {
        if (this.table[index][i][0] === key) {
          this.table[index].splice(i, 1);
          this.size--;
          return true;
        }
      }
    } else {
      return false;
    }
  }

  display() {
    this.table.forEach((values, index) => {
      const chainedValues = values.map(
        ([key, value]) => `[ ${key}: ${value} ]`
      );
      console.log(`${index}: ${chainedValues}`);
    });
  }
}

Puoi testare l'implementazione creando una nuova istanza HashTable ed eseguendo alcuni inserimenti ed eliminazioni:

const ht = new HashTable();

ht.set("France", 111);
ht.set("Spain", 150);
ht.set("ǻ", 192);

ht.display();
// 83: [ France: 111 ]
// 126: [ Spain: 150 ],[ ǻ: 192 ]

console.log(ht.size); // 3
ht.remove("Spain");
ht.display();
// 83: [ France: 111 ]
// 126: [ ǻ: 192 ]

Ora non ci sono conflitti all'interno dell'istanza HashTable. Ottimo lavoro!

Conclusione

In questo tutorial, hai imparato cos'è una HashTable e come JavaScript la utilizza per creare la struttura di dati Object e Map.

Hai anche imparato come implementare la tua classe HashTable e come prevenire la collisione degli indici delle chiavi della tabella Hash usando la tecnica del concatenamento.

Utilizzando una struttura dati di una tabella Hash, sarai in grado di creare un array associativo con operazioni rapide di ricerca, inserimento ed eliminazione. 😉

Grazie per aver letto questo tutorial

Se vuoi saperne di più su JavaScript, puoi dare un'occhiata al mio sito sebhastian.com, dove ho pubblicato oltre 100 tutorial sulla programmazione con JavaScript (in inglese), tutti usando spiegazioni ed esempi di codice di facile comprensione.

I tutorial includono la manipolazione delle stringhe, la manipolazione degli oggetti Date, metodi di Array e Object, soluzioni di algoritmi JavaScript e molto altro.