Vettori Associativi

[luxorl]

Riporto di seguito la definizione di vettore associativo della mia dispensa:


Un particolare tipo di dizionario è costituito dal vettore associativo, che è un vettore a cui è stata aggiunta una funzione di indirizzamento che, dato un valore del vettore, ne restituisce l'indice, che vale 0 nel caso l'elemento non sia stato trovato. Inoltre esiste una funzione che verifica se un elemento è stato inizializzato o meno.


Poi in seguito aggiunge...


La ricerca per valore è lineare. Per ottenere una complessità costante anche per tale ricerca possiamo realizzare l'accesso per valore attraverso l'introduzione di una tabella hash. Per risparmiare spazio, nella tabella hash memorizziamo soltanto gli indici del vettore che permettono di risalire ai relativi valori.


Quello che vorrei capire è come chiave della tabella hash si usano gli indici del vettore o il valore dell'oggetto?

Cioè come fa questa tabella hash a portare a costante la complessità della ricerca per valore?

Usa come <key> i valori degli oggetti e restituisce come <value> l'indice del vettore associativo... ma a questo punto se il vettore associativo è fatto per restituire indici che lo uso a fare se il suo ruolo lo ha già compiuto la tabella hash? aaaahh che confusione

Riuscite a farmi un po' di luce sull'argomento? Per Favore