Che cos'è una matrice associativa?
Un array associativo, chiamato anche tabella hash o mappa hash, è simile a un array standard tranne per il fatto che l'indice dell'array può essere una stringa anziché un numero intero. In molte applicazioni di database e in altri programmi che trattano grandi quantità di dati, un array associativo è un elemento vitale per aiutare a ordinare e accedere alle informazioni in modo efficiente. Al centro di una matrice associativa c'è una matrice standard che è indicizzata con numeri interi, come sarebbe normalmente il caso. Uno speciale algoritmo chiamato funzione hash converte l'indice di stringa in un indice intero per trovare il valore. Questa è una conversione coerente, quindi l'indice intero effettivo non deve mai essere memorizzato ma viene invece calcolato dalla stringa ogni volta che è necessario.
La terminologia utilizzata quando si fa riferimento a un array associativo può essere leggermente diversa da quella utilizzata quando si parla di un array normale. Quello che normalmente sarebbe chiamato un indice - la posizione numerica di un elemento all'interno di un array - è chiamato chiave. I dati associati alla chiave sono chiamati valore. Ciò significa che, all'interno di un array associativo, una chiave è associata a un valore, che è correlato a un indice che fa riferimento a un elemento in un array standard nella struttura dei dati.
Al centro di ogni array associativo c'è la funzione hash. Questo è un algoritmo utilizzato per determinare l'indice numerico di un valore in base alla chiave. Esistono diversi tipi di funzioni hash, alcune progettate per operare su chiavi che sono numeri interi e altre progettate per funzionare su chiavi che sono stringhe. Nel caso di una chiave intera, un metodo popolare è quello di dividere il valore della chiave per la dimensione dell'array e utilizzare il resto della divisione per, si spera, ottenere un valore di indice univoco.
La funzione hash può essere molto più complessa per i tasti che sono stringhe. Alcuni metodi includono l'aggiunta del valore numerico di ciascun carattere nella stringa e la sua divisione per un numero o l'utilizzo dei primi caratteri della stringa per ottenere un numero univoco. Esistono molti modi per derivare un numero da una stringa di caratteri.
Quando si ha a che fare con una grande quantità di coppie chiave-valore in un array associativo, un problema che può sorgere è chiamato collisione. La collisione si verifica quando l'indice intero derivato da una chiave è identico all'indice intero di un'altra chiave. Queste due chiavi puntano quindi effettivamente allo stesso indice nella matrice di valori. Esistono varie soluzioni di collisione, principalmente perché ha un'alta probabilità di accadere nella maggior parte delle applicazioni pratiche.
Una soluzione alla collisione è che ogni indice di valore sia effettivamente un elenco collegato in modo che, quando più di una chiave si risolve in quella posizione di indice, la posizione può contenere più di un valore. Questo si chiama concatenamento ed è un modo semplice di gestire una collisione, anche se può anche rallentare il tempo necessario per recuperare le informazioni. Un altro metodo per gestire una collisione è chiamato sondaggio lineare. Quando si verifica una collisione, il rilevamento lineare funziona spostandosi attraverso l'array di valori fino a quando non viene trovato un indice inutilizzato. Questa soluzione può aiutare a mantenere i dati distribuiti uniformemente nell'array associativo, ma può anche aumentare il tempo necessario per cercare un valore.