Ensemble (informatique)

Un ensemble stocke des valeurs, sans ordre défini, et ne contient pas de données en double (la tentative d'insertion d'une donnée déjà présente est sans effet)[1]. Contrairement à la plupart des autres types de collections[2] les ensembles sont plus utilisés pour tester l'appartenance d'une valeur à cet ensemble que pour en extraire des données.

Certaines structures de données de type ensemble sont conçues pour être statiques (ou « gelées ») : elles ne peuvent pas être modifiées après leur conception. Ces ensembles statiques ne permettent que des opérations de requête sur leurs éléments — telles que vérifier si une valeur donnée est présente dans l'ensemble, ou énumérer les valeurs dans un ordre arbitraire. Il existe généralement sur les serveurs les supportant des opérateurs tels qu'union, intersection et différence permettant des opérations de requête rapides[1]. D'autres variantes, appelées ensembles dynamiques ou modifiables, permettent également l'insertion et la suppression d'éléments de l'ensemble.

Une structure de données de type abstrait est une collection, ou agrégat, de données. Les données peuvent être des opérateurs booléens, des nombres, des caractères ou autres structures de données. Si l'on prend en compte les fonctionnalités d'empaquetage[3] ou d'indexation[4], il existe quatre grandes structures de données :

• non empaquetée, non indexée: collection d'objets (bunch)
• empaquetée, non indexée : ensemble
• non empaquetée, indexée : chaîne (séquence)
• empaquetée, indexée : liste (array).

Dans cette structuration, les ensembles contiennent des éléments, alors que la collection d'objets consiste en ces éléments[5].

Une structure de données probabiliste implémentant ce type est le filtre de Bloom.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Set (abstract data type) » (voir la liste des auteurs).

• NoSQL
• Filtre de Bloom