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 se necessario ogni volta.

La terminologia utilizzata quando si fa riferimento a un array associativo può essere leggermente diversa da quella che viene utilizzata quando si parlaun array normale.Quello che sarebbe normalmente chiamato un indice mdash;la posizione numerica di un elemento all'interno di un array mdash;è chiamato la 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 è 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ù complessaPer le chiavi che sono stringhe.Alcuni metodi includono l'aggiunta del valore numerico di ciascun carattere nella stringa e quindi la divisione per un certo 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 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 quell'indicePosizione, 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 valore fino a quando non viene trovato 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.