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 un array associativo c’è un array standard indicizzato con numeri interi, come sarebbe normalmente il caso. Uno speciale algoritmo chiamato funzione hash converte l’indice della 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 si chiamerebbe 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 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 interi e altre progettate per funzionare su chiavi che sono stringhe. Nel caso di una chiave intera, un metodo popolare consiste nel dividere il valore della chiave per la dimensione dell’array e utilizzare il resto della divisione per ottenere, si spera, un valore di indice univoco.
La funzione hash può essere molto più complessa per le chiavi che sono stringhe. Alcuni metodi includono l’aggiunta del valore numerico di ciascun carattere nella stringa e quindi la sua divisione per un numero o l’utilizzo solo 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 nell’array di valori. Esistono varie soluzioni alla collisione, principalmente perché ha un’alta probabilità di verificarsi nella maggior parte delle applicazioni pratiche.
Una soluzione alla collisione consiste nel fare in modo che ogni indice di valore sia effettivamente un elenco collegato in modo che, quando più di una chiave si risolva in quella posizione dell’indice, la posizione può contenere più di un valore. Questo è chiamato concatenamento ed è un modo semplice per gestire una collisione, anche se può anche rallentare il tempo necessario per recuperare le informazioni. Un altro metodo per affrontare una collisione è chiamato sondaggio lineare. Quando si verifica una collisione, il rilevamento lineare funziona spostandosi attraverso l’array di valori finché non viene trovato un indice inutilizzato. Questa soluzione può aiutare a mantenere i dati distribuiti uniformemente nell’array associativo, ma può anche aumentare la quantità di tempo necessaria per cercare un valore.