Cos'è un array associativo?
Un array associativo, chiamato anche tabella hash o mappa hash, è simile a un array standard tranne l'indice dell'array può essere una stringa anziché un numero intero. In molte applicazioni di database e in altri programmi che si occupano di 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. Un algoritmo speciale 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 archiviato ma viene invece calcolato dalla stringa secondo necessità.
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 sarebbe normalmente chiamato un indice - la posizione numerica di un elemento all'interno di un array - è chiamatachiave. 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 è la funzione hash. Questo è un algoritmo utilizzato per determinare l'indice numerico di un valore basato sulla chiave. Esistono diversi tipi di funzioni di hash, alcune progettate per operare su chiavi che sono numeri interi e alcuni progettati per funzionare su chiavi che sono stringhe. Nel caso di una chiave interi, un metodo popolare è quello di dividere il valore chiave per le dimensioni dell'array e utilizzare il resto della divisione per, si spera, ottenere un valore 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 dividerlo per un certo numero,o usando solo i primi caratteri della stringa per ottenere un numero univoco. Esistono molti modi per derivare un numero da una stringa di caratteri.
Quando si tratta di una grande quantità di coppie di valore chiave in un array associativo, un problema che può sorgere si chiama collisione. La collisione avviene quando l'indice intero derivato da una chiave è identico all'indice intero di un'altra chiave. Questi due tasti indicano quindi effettivamente lo stesso indice nell'array di valori. Esistono varie soluzioni alla collisione, principalmente perché ha un'alta probabilità di accadere nella maggior parte delle applicazioni pratiche.
Una soluzione alla collisione è quella di avere ogni indice di valore essere effettivamente un elenco collegato in modo che, quando più di una chiave si risolve a quella posizione dell'indice, la posizione può contenere più di un valore. Questo si chiama 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 trattare con una collisione è chiamato sondaggio lineare.Quando si verifica una collisione, il sondaggio lineare funziona spostandosi attraverso l'array di valori fino a trovare un indice inutilizzato. Questa soluzione può aiutare a mantenere i dati uniformemente distribuiti nell'array associativo, ma può anche aumentare il tempo necessario per cercare un valore.