Set (informatica)

Il set è, in informatica, un tipo di dato astratto consistente in una collezione di valori disposti in ordine casuale e senza valori ripetuti.

Corrisponde al concetto matematico di insieme, ma con la restrizione che deve essere finito. Eccezion fatta per la sequenza e per il fatto che non ci sono valori ripetuti, il set è uguale alla lista. Il set può essere concepito come un vettore associativo (mappatura parziale) in cui il valore di ogni coppia di valori chiave viene ignorato.

Implementazione

I set possono essere implementati usando varie strutture dati. Le strutture dati ideali rendono efficienti alcuni tipi di operazioni: controllare che un oggetto sia in un set, spostarsi attraverso il set passandone in rassegna tutti gli oggetti, realizzare l'unione o l'intersezione di due set o prendere il complementare di un set in un dominio limitato. Per implementare un set si può impiegare qualsiasi struttura dati di vettore associativo, lasciando che le chiavi del set siano gli elementi del set e ignorando i valori. Per via della somiglianza con i vettori (array) associativi i set sono implementati allo stesso modo, cioè come un albero binario di ricerca autobilanciato per quanto riguarda i set ordinati e come una hash table per quanto riguarda i set non ordinati. Altri metodi usati fanno uso degli array (in particolare i bit array). Una bloom map implementa un set in modo probabilistico, impiegando una rappresentazione molto compatta ma con il piccolo rischio di positivi falsi nelle query.

Voci correlate

• Tipo di dato astratto

Collegamenti esterni

• set, su sapere.it, De Agostini.
• (EN) Eric W. Weisstein, Set, su MathWorld, Wolfram Research.
• (EN) Set, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.