Ricordiamo l'equazione di N. Wirth: Programmi = Algoritmo + Strutture di Dati

e formalizziamo l'equazione Struttura di Dati = Insiemi + Operazioni

attraverso la nozione di

Definizione [algebra eterogenea]

$A=\lang[A_1,..., A_n], [f_1, ..., f_k]\rang$ dove

• $A_i$ sono insiemi
• $f_j: A_{c_{j1}} * ...* A_{c_{jr_j}} \rarr A_{i_j}, \ \ \ \ c_{pq}, i_j\in\{1, ..., n\}$.

Parti di A

Studiamo possibili implementazioni per la struttura dati PA

• Liste concatenate

  Vantaggi: semplicità

  Svantaggi: costo medio di ciascuna operazione $O(n)$

• Tabelle hash

  Vantaggi: costo medio di ciascuna operazione $O(1)$

  Svantaggi: costo di ciascuna operazione $O(n)$ se si sbaglia a impostare alcuni parametri

Tabelle Hash

Una tabella Hash costituisce un'implementazione valida per PA. Distinguiamo tra:

• Hash statico: la tabella ha dimensione fissa
• Hash dinamico: la dimensione della tabella varia dinamicamente

In funzione di dove sono memorizzati i dati si presentano 2 metodi di gestione

• Concatenazioni separate: i dati risiedono in liste concatenate (la tabella contiene dei riferimenti)
• Indirizzamento diretto: i dati risietono all'interno della tabella

Abbiamo quindi 4 casi possibili...