Informatica I - dizionari a chiavi numeriche e tabelle

Tabella

È un dizionario le cui chiavi sono numeri interi appartenenti a un intervallo noto a priori. Lo si può realizzare tramite array, con prestazioni O(1) per tutte le operazioni.

• Gli elementi dell'array sono riferimenti ai valori delle coppie.
• Le chiavi delle coppie sono usate come indici nell’array.
• Le celle il cui indice è una chiave non presente nel dizionario hanno valore null.

Definiamo il tipo di dati astratto Table con un comportamento identico al dizionario, l'unica sostanziale differenza è che le chiavi non sono riferimenti a oggetti di tipo Comparable, ma sono numeri interi (che evidentemente sono confrontabili). Una realizzazione dell'ADT Tabella tramite array fornisce prestazioni tutte O(1).

• Prima limitazione: le chiavi devono essere numeri interi.
• Seconda limitazione (più grave): la tabella non utilizza la memoria in modo efficiente, l’intervallo di variabilità delle chiavi deve essere noto a priori per dimensionare la tabella.

La memoria richiesta per contenere n dati dipende dal loro contenuto, in particolare dal valore della chiave massima. Se le chiavi sono molto “disperse”, ovvero se il fattore di riempimento è piccolo, si ha grande spreco di memoria.

Tabella con ridimensionamento

Se l’intervallo di variabilità delle chiavi non è noto a priori e si inserisce una chiave di valore superiore alla lunghezza dell’array, bisogna ridimensionare l’array. Un inserimento richiede un tempo O(n) (qui non si può utilizzare l’analisi ammortizzata perché non si può prevedere il valore della nuova chiave). Il ridimensionamento può avvenire ad ogni inserimento, e le prestazioni nel caso peggiore sono quindi O(n). Può essere necessario un array di milioni di elementi per contenere poche decine di dati.