Accesso casuale

In informatica, con accesso casuale o accesso diretto si indica la caratteristica di poter accedere ad un elemento arbitrario di una sequenza in tempo costante e indipendente dalla dimensione della sequenza stessa. L'elemento è arbitrario nel senso che la sua posizione non è prevedibile, motivo per il quale si usa il termine "casuale". Il concetto opposto è quello di accesso sequenziale, in cui l'accesso ad un elemento richiede più o meno tempo a seconda della sua posizione. La memoria RAM utilizza questo tipo di tecnologia.^[1]

Un'immagine tipica che illustra questa distinzione è quella del manoscritto a rotolo e del libro: il primo è ad accesso sequenziale in quanto bisogna srotolare il manoscritto fino al punto di interesse, il secondo è ad accesso casuale in quanto si può aprire il libro ad una pagina qualsiasi. Un esempio più moderno è quello della musicassetta e del compact disc: la prima è ad accesso sequenziale in quanto bisogna andare avanti veloce per raggiungere la canzone ricercata mentre il secondo è ad accesso casuale in quanto si può saltare direttamente alla traccia desiderata.

Nell'ambito delle strutture dati con accesso casuale si indica la possibilità di accedere ad un qualsiasi elemento di una struttura in tempo costante, cioè indipendente dalla posizione dell'elemento e dalla dimensione della struttura ( $O(1)$ ). Sono poche le strutture dati che godono di questa proprietà oltre agli array e alle strutture dati derivate, come gli array dinamici. L'accesso casuale è essenziale per molti algoritmi quali la ricerca binaria, il counting sort e il crivello di Eratostene. Altre strutture dati, come le liste concatenate, sacrificano l'accesso casuale per ottenere una maggiore efficienza negli inserimenti, nelle eliminazioni e nel riordinamento dei dati. Gli alberi binari di ricerca bilanciati rappresentano un buon compromesso avendo un tempo di accesso costante per tutti i membri di uno stesso insieme e che cresce solo logaritmicamente con la sua dimensione.