Utilizzo degli Hashmap in JavaScript: Mappare Chiavi a Valori nelle Strutture Dati

Cosa sono le Hashmap?

Le hashmap sono una struttura dati che memorizza coppie chiave-valore, dove ogni chiave è unica e corrisponde a un valore. La chiave viene utilizzata per indicizzare il valore, consentendo un rapido recupero del valore associato. Le hashmap usano una funzione hash per calcolare un indice per memorizzare e recuperare i valori. La funzione hash prende la chiave come input e genera un codice hash unico, che viene poi utilizzato per determinare l'indice dove il valore verrà memorizzato nell'array o nel bucket.

Hashmap vs Oggetti JavaScript

Anche gli oggetti JavaScript possono memorizzare coppie chiave-valore, in modo simile alle hashmap. Tuttavia, le hashmap offrono vantaggi rispetto agli oggetti:

1. Tipi di Chiave: Le hashmap permettono di utilizzare qualsiasi tipo di dato come chiave, inclusi oggetti, array e funzioni. Gli oggetti JavaScript sono limitati all'uso di stringhe e simboli come chiavi.

   const hashmap = new Map();
   hashmap.set({ name: 'John' }, 25);
   hashmap.set([1, 2, 3], 'array');
   
   const obj = {};
   obj[{ name: 'John' }] = 25; // Non valido: Gli oggetti non possono essere usati come chiavi negli oggetti

2. Mantenimento dell'Ordine: Le hashmap mantengono l'ordine di inserimento degli elementi, il che significa che l'ordine in cui le coppie chiave-valore vengono aggiunte alla hashmap viene preservato. Gli oggetti JavaScript non garantiscono alcun ordine delle loro proprietà.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   hashmap.set('c', 3);
   console.log(Array.from(hashmap.keys())); // Output: ['a', 'b', 'c']
   
   const obj = { a: 1, b: 2, c: 3 };
   console.log(Object.keys(obj)); // Output: ['a', 'b', 'c'] (Non garantito)

3. Tracciamento della Dimensione: Le hashmap forniscono metodi come size() per ottenere il numero di elementi memorizzati nella hashmap. Con gli oggetti JavaScript, dovresti tenere traccia manualmente del numero di proprietà o usare Object.keys(obj).length per determinare la dimensione.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   console.log(hashmap.size); // Output: 2
   
   const obj = { a: 1, b: 2 };
   console.log(Object.keys(obj).length); // Output: 2

Complessità Temporale delle Operazioni Hashmap

Uno dei principali vantaggi delle hashmap è la loro complessità temporale per le operazioni base. Le hashmap forniscono una complessità temporale costante, indicata come O(1), per le seguenti operazioni:

1. Inserimento: Aggiungere una nuova coppia chiave-valore alla hashmap è un'operazione O(1). La funzione hash viene utilizzata per calcolare l'indice e la coppia chiave-valore viene memorizzata a quell'indice nell'array o nel bucket.

2. Eliminazione: Rimuovere una coppia chiave-valore dalla hashmap è anch'essa un'operazione O(1). La funzione hash viene utilizzata per individuare l'indice dove è memorizzata la coppia chiave-valore, che viene poi rimossa da quell'indice.

3. Ricerca: Recuperare il valore associato a una determinata chiave è un'operazione O(1). La funzione hash viene utilizzata per calcolare l'indice basato sulla chiave e il valore può essere acceduto a quell'indice.

const cache = new Map();

function fetchData(key) {
  if (cache.has(key)) {
    return cache.get(key); // Recupera i dati dalla cache (ricerca O(1))
  } else {
    const data = fetchFromAPI(key); // Recupera i dati dall'API
    cache.set(key, data); // Memorizza i dati nella cache (inserimento O(1))
    return data;
  }
}

Creare una Hashmap

Per creare una nuova hashmap, usa il costruttore new Map(). Questo crea una hashmap vuota per memorizzare coppie chiave-valore.

const myHashmap = new Map();

Ad esempio, per creare una hashmap per memorizzare dati degli studenti:

const studentMap = new Map();

Aggiungere Coppie Chiave-Valore

Per aggiungere una nuova coppia chiave-valore alla hashmap, usa il metodo set(). Accetta due argomenti: la chiave e il valore.

myHashmap.set('name', 'John');
myHashmap.set('age', 25);

Nell'esempio sopra, aggiungiamo due coppie chiave-valore a myHashmap: 'name' corrisponde a 'John' e 'age' corrisponde a 25.

Aggiungiamo alcuni dati degli studenti alla nostra studentMap:

studentMap.set('1', { name: 'John', age: 20, major: 'Computer Science' });
studentMap.set('2', { name: 'Alice', age: 22, major: 'Mathematics' });
studentMap.set('3', { name: 'Bob', age: 21, major: 'Physics' });

Ottenere Valori

Per ottenere il valore per una determinata chiave, usa il metodo get(). Accetta la chiave come argomento e restituisce il valore.

const name = myHashmap.get('name');
console.log(name); // Output: 'John'

In questo esempio, otteniamo il valore per la chiave 'name' da myHashmap, che è 'John'.

Per ottenere i dati di uno studente specifico da studentMap:

const student = studentMap.get('2');
console.log(student); // Output: { name: 'Alice', age: 22, major: 'Mathematics' }

Verificare l'Esistenza di una Chiave

Per verificare se una chiave esiste nella hashmap, usa il metodo has(). Accetta la chiave come argomento e restituisce un valore booleano.

const hasAge = myHashmap.has('age');
console.log(hasAge); // Output: true

Qui, verifichiamo se la chiave 'age' esiste in myHashmap usando il metodo has(), che restituisce true.

Verificare se uno studente con ID '4' esiste in studentMap:

const hasStudent = studentMap.has('4');
console.log(hasStudent); // Output: false

Rimuovere Coppie Chiave-Valore

Per rimuovere una coppia chiave-valore dalla hashmap, usa il metodo delete(). Accetta la chiave come argomento e rimuove la coppia chiave-valore dalla hashmap.

myHashmap.delete('age');
console.log(myHashmap.has('age')); // Output: false

In questo esempio, rimuoviamo la coppia chiave-valore con la chiave 'age' da myHashmap usando il metodo delete(). Dopo la rimozione, has('age') restituisce false.

Rimuovere uno studente da studentMap:

studentMap.delete('1');
console.log(studentMap.has('1')); // Output: false

Ottenere la Dimensione della Hashmap

Per ottenere il numero di coppie chiave-valore nella hashmap, usa la proprietà size. Restituisce la dimensione della hashmap.

console.log(myHashmap.size); // Output: 1

Qui, accediamo alla proprietà size di myHashmap, che restituisce 1, indicando che c'è una coppia chiave-valore nella hashmap.

Ottenere il numero di studenti in studentMap:

console.log(studentMap.size); // Output: 2

Riepilogo delle Operazioni Hashmap

Queste sono le operazioni base che puoi eseguire su una hashmap usando l'oggetto Map di JavaScript. L'oggetto Map fornisce un modo per lavorare con coppie chiave-valore e offre metodi per manipolare e accedere ai dati nella hashmap.

L'oggetto Map mantiene l'ordine delle coppie chiave-valore, il che significa che quando iteri sulla hashmap usando metodi come forEach() o il ciclo for...of, le coppie chiave-valore saranno accedute nell'ordine in cui sono state aggiunte.

Il Metodo forEach()

Il metodo forEach() è integrato nell'oggetto Map. Ti permette di iterare su ogni coppia chiave-valore nella hashmap. Utilizza una funzione callback che viene eseguita per ogni coppia.

La funzione callback riceve tre parametri:

1. value: Il valore della coppia corrente.
2. key: La chiave della coppia corrente.
3. map: La hashmap su cui è stato chiamato forEach().

const shoppingCart = new Map();
shoppingCart.set('shirt', 25);
shoppingCart.set('pants', 50);
shoppingCart.set('shoes', 75);

let totalPrice = 0;

shoppingCart.forEach((price) => {
  totalPrice += price;
});

console.log(`Total Price: $${totalPrice}`);

Total Price: $150

Il Ciclo for...of

Puoi anche usare un ciclo for...of per iterare su una hashmap. Il ciclo for...of funziona con oggetti iterabili come array, stringhe e map.

Quando usi for...of con una hashmap, ogni ciclo restituisce un array con la coppia [key, value].

Visualizzare l'Iterazione della Hashmap

Ecco un diagramma che mostra come funziona l'iterazione su una hashmap:

Il diagramma mostra la hashmap e l'iterazione su ogni coppia chiave-valore. Per ogni coppia, la elaboriamo in base a ciò che dobbiamo fare, come calcoli, confronti o altre operazioni.

Sia forEach() che for...of ti permettono di iterare sulle coppie chiave-valore di una hashmap in JavaScript. Quale usare dipende dalle tue esigenze specifiche. forEach() è utile quando vuoi fare qualcosa per ogni coppia, mentre for...of è pratico quando hai bisogno sia delle chiavi che dei valori in ogni ciclo.

Tieni presente che l'ordine di iterazione in una hashmap è basato sull'ordine in cui le coppie sono state aggiunte. L'oggetto Map di JavaScript mantiene questo ordine.

Iterare sulle hashmap è comune quando si lavora con coppie chiave-valore, e JavaScript offre questi metodi per renderlo più facile e veloce. Per maggiori informazioni sugli oggetti Map e l'iterazione, consulta la documentazione MDN Web Docs.

Cosa sono le Collisioni?

In una hashmap, le collisioni si verificano quando due o più chiavi vengono hashate allo stesso indice. Questo significa che più coppie chiave-valore devono essere memorizzate nella stessa posizione nell'array o nel bucket. Se non gestite bene, le collisioni possono portare alla sovrascrittura dei dati o al rallentamento del recupero dei valori.

Ecco un esempio di collisione in una hashmap:

In questo esempio, sia le chiavi 'John' che 'Alice' vengono hashate allo stesso indice (Indice 0), causando una collisione.

Se le collisioni non vengono corrette, possono verificarsi questi problemi:

1. Sovrascrittura dei Dati: Se una nuova coppia chiave-valore viene hashata allo stesso indice di una coppia esistente, la coppia esistente potrebbe essere sovrascritta, causando perdita di dati.

2. Recupero Rallentato: Quando si verificano collisioni, trovare i valori diventa più lento poiché la hashmap deve eseguire più passaggi per trovare il valore corretto tra le coppie in collisione.

Per risolvere questi problemi, le hashmap utilizzano tecniche di gestione delle collisioni.

Modi per Gestire le Collisioni

Ci sono due modi principali per gestire le collisioni nelle hashmap:

1. Concatenamento Separato (Separate Chaining)

• Ogni indice dell'array o bucket della hashmap memorizza una lista concatenata di coppie chiave-valore.
• Quando si verifica una collisione, la nuova coppia chiave-valore viene aggiunta alla lista concatenata a quell'indice.
• Trovare un valore significa scorrere la lista concatenata all'indice hashato per trovare la coppia chiave-valore desiderata.

2. Indirizzamento Aperto (Open Addressing)

• L'indirizzamento aperto non usa liste concatenate per gestire le collisioni. Invece, cerca il prossimo indice libero nell'array quando si verifica una collisione.
• Ci sono diversi modi per trovare il prossimo indice, come linear probing, quadratic probing e double hashing.
• Quando si verifica una collisione, la hashmap usa il metodo di probing per trovare il prossimo slot vuoto nell'array per memorizzare la coppia chiave-valore.

Best Practice per l'Utilizzo delle Hashmap

1. Scegli una buona funzione hash che riduca le collisioni e distribuisca le chiavi uniformemente.
2. Considera il numero previsto di elementi e le prestazioni desiderate quando scegli la dimensione iniziale della hashmap.
3. Sii consapevole di come le collisioni possono influenzare la velocità delle operazioni hashmap, specialmente con molte collisioni.
4. Usa il concatenamento separato o l'indirizzamento aperto in base alle esigenze della tua applicazione, considerando aspetti come l'uso della memoria e la velocità di recupero.