Množina (set) je abstraktní datová struktura, která obsahuje hodnoty, aniž by garatovala jejich pořadí. Jelikož se jedná se o implementaci matematického termínu množina, tak tato struktura obsahuje každý prvek vždy maximálně jednou. Podobnou strukturou, která však smí obsahovat daný prvek vícekrát, je multimnožina. Pro implementaci systému navzájem se nepřekrývajících podmnožin používáme datovou strukturu disjoint-set.
Implementace
Nejjednodušším způsobem implementace množiny je použít seznam, zapomenout na pořadí prvků a při vkládání vždy hlídat, aby se daný prvek neobjevil v množině vícekrát. Ač je tento postup přímočarý, tak je velice neefektivní, protože je pro vyhledání prvku nutné v krajním případě projít celou množinu
(tj. asymptotická složitost ). Z tohoto důvodu se pro ukládání dat do množiny používá většinou hashovací tabulka (hash table), která zajistí přístup k jednotlivým prvkům průměrně v konstantním čase.
Kód
01./**02. * Mnozina implementovana jako list03. * @author Pavel Micka04. * @param <ENTITY> typovy parametr obsahu05. */06.public class Set<ENTITY> {07. private List<ENTITY> list;08. /**09. * Konstruktor10. * @param initialCapacity kapacita, se kterou je inicializovan podrizeny seznam11. */12. public Set(int initialCapacity) {13. list = new ArrayList<ENTITY>(initialCapacity);14. }15. 16. /**17. * Vlozi entitu do mnoziny18. * @param e entita19. * @return true - pokud probehne vlozeni uspesne, false pokud jiz mnozina20. * danou entitu obsahuje (dle equals())21. */22. public boolean put(ENTITY e) {23. if (list.contains(e)) return false;24. list.add(e);25. return true;26. }27. 28. /**29. * Vrati nejaky prvek z mnoziny (a z mnoziny jej take odstrani)30. * @return prvek, null pokud je mnozina prazdna31. */32. public ENTITY pick() {33. if(list.size() == 0) return null;34. return list.remove(list.size() - 1);35. }36. 37. /**38. * Odstrani z mnoziny danou entitu39. * @param e entita40. * @return true - pokud mnozina obsahovala danou entitu, false - pokud nikoliv41. */42. public boolean remove(ENTITY e) {43. return list.remove(e);44. }45. 46. /**47. *48. * Dotaz na pritomnost dane entity49. * @param e entita50. * @return true - pokud jej mnozina obsahuje, false - pokud nikoliv51. */52. public boolean contains(ENTITY e) {53. return list.contains(e);54. }55. /**56. * Dotaz na velikost mnoziny57. * @return pocet prvku58. */59. public int size() {60. return list.size();61. }62.}