Arrays e HashTables sono entrambe le mappe; una mappa converte una chiave in un valore (o fornisce un luogo in cui memorizzare un valore).
Per gli array, le chiavi sono indici integrali, per Java (e molte lingue) a partire da zero.
Gli elementi degli array sono memorizzati in modo tale che l'aritmetica del puntatore semplice possa essere utilizzata sulla chiave integrale, ovvero l'espressione di indicizzazione, per individuare la memoria per l'elemento in quell'indice. Nessuna "ricerca" è necessaria, è piuttosto aritmetica individua l'elemento desiderato.
In pratica ciò significa che gli elementi sono memorizzati in modo contiguo. Tuttavia, si noti che esiste una differenza tra la matrice del tipo di valore primitivo, come int e una matrice di oggetti in Java. La matrice di oggetti è in realtà una matrice di riferimenti agli oggetti e tali riferimenti vengono archiviati in modo contiguo: gli oggetti stessi vengono archiviati più in base a quando sono / sono allocati (nell'heap concettuale). Quindi, per accedere a un elemento di una matrice di oggetti, l'aritmetica del puntatore normale individua il riferimento all'oggetto e quindi un'ulteriore indirezione (tramite il riferimento ottenuto) accede all'oggetto stesso.
Le tabelle hash sono anche mappe; tuttavia, consentono di scegliere un tipo di chiave arbitraria (oltre al tipo di valore) in fase di compilazione (sebbene sia possibile scegliere il tipo di oggetto molto generale). La tabella hash utilizza il valore hash di una chiave per distribuire coppie chiave / valore tra gli elementi nel suo array bucket interno. La tabella hash è O (1) perché anche con molti elementi nella tabella hash, la ricerca è relativamente costante. L'oggetto può essere posizionato: il valore hash della chiave viene utilizzato per calcolare l'indice del bucket. Quindi viene applicata la normale indicizzazione dell'array (aritmetica del puntatore) per ottenere il bucket, che cerca la corrispondenza perfetta.
Quindi, descriverlo a grandi linee (vale a dire per la ricerca e l'inserimento) come O (1) è un po 'troppo semplicistico, a causa della ricerca. La ricerca è necessaria perché le collisioni nel calcolo dell'indice del bucket significano che più elementi devono essere memorizzati nello stesso bucket (ecco perché è un bucket non un semplice slot).
Tuttavia, quando la tabella hash funziona correttamente, manterrà il numero di elementi nel bucket qualsiasi su un numero piccolo (ad esempio tra 0 e 10, a seconda dell'applicazione), e lo fa espandendo il numero bucket array periodicamente quando più elementi vengono inseriti nella tabella hash. Questa espansione periodica ha un costo reale, in particolare, quando viene superato un trigger che la tabella hash decide di espandersi; tuttavia, tale espansione può essere considerata ammortizzata su molti inserti perché quando non si espande l'inserimento è relativamente libero, anche O (1).
Le ricerche, in media, richiederanno un numero limitato di ricerche, dove anche (l'espansione funziona correttamente, le funzioni di hash funzionano bene), questo numero in realtà non dipende dal numero di elementi totali nella tabella hash. Per questo motivo, le ricerche sono sostanzialmente costanti.
La tabella hash di base non offre alcuna accelerazione particolare per la ricerca di chiavi o coppie chiave / valore per valore (cioè dato un valore senza chiave). La ricerca di un valore in una tabella hash di base sarebbe O (N). Ci vorrebbe un secondo hash table comparabile di key & swapped valore per accelerare.
Si noti che la memoria stessa (semplificata, ovviamente) è una grande matrice, e i puntatori sono variabili che contengono gli indirizzi, proprio come le variabili di indice contengono indici di array. il sistema di memoria consente l'accesso diretto alla memoria memorizzata in un determinato indirizzo. Come per gli array, il sistema di memoria non memorizza gli indirizzi, ma memorizza solo i byte dei dati; tuttavia, semplicemente sa come tradurre un indirizzo in un byte o una parola.