set data type

Angol

Főnév

set data type (tsz. set data types)

1. (informatika) A Set (halmaz) ADT (Abstract Data Type) egy olyan kollekció, amely a különböző (egyedi) elemek tárolására szolgál, és ahol az elemek sorrendje nem számít, csak az, hogy adott elem benne van-e vagy sem. A Set ADT fő célja a gyors tag-ellenőrzés (membership test)—vagyis hogy hatékonyan meg tudjuk mondani, hogy egy adott érték megtalálható-e a halmazban.

---

1. Alapműveletek

Egy Set ADT tipikus, kötelező műveletei:

1. Create() Üres halmaz létrehozása.
2. isEmpty() → bool Igaz, ha a halmaz nem tartalmaz elemet.
3. size() → int Az elemek száma a halmazban.
4. insert(x) Az x elem hozzáadása a halmazhoz (ha még nincs benne). Duplikáció esetén általában semmi sem történik.
5. remove(x) Az x elem eltávolítása (ha benne van).
6. contains(x) → bool Visszaadja, hogy x eleme-e a halmaznak.
7. iterate() A halmaz elemeinek bejárása (random, rendezett vagy beillesztési sorrendben, az implementációtól függően).

Opcióként további műveletek is értelmezettek:

• clear(): minden elem törlése.
• union(Set B) → Set C: két halmaz egyesítése.
• intersection(Set B) → Set C: közös elemek halmaza.
• difference(Set B) → Set C: az elsőből a másodikban található elemek eltávolítása.
• isSubsetOf(Set B): ellenőrzi, hogy minden elem az A halmazból B-ben is benne van-e.

---

2. Implementációs stratégiák

2.1. Hash‐tábla alapú (Unordered Set)

• Adatszerkezet: kulcs→bucket via hash function.
• Beszúrás:
  1. h = hash(x) % M (tömbméret)
  2. ha a bucketben még nincs x, hozzáadjuk (pl. láncolással vagy nyílt címzéssel).
• Törlés: a bucketből eltávolítjuk az x-et.
• Tag‐ellenőrzés: ugyanaz a hash lookup.
• Amortizált idő: O(1) mindhárom (insert, remove, contains), feltéve, hogy a terhelési tényező (n/M) kis marad.

Java: HashSet<E> C++: std::unordered_set<T>

2.2. Feszített fa alapú (Ordered Set)

• Adatszerkezet: általában kiegyensúlyozott bináris fa (pl. Red-Black Tree).
• Műveletek: mind insert/remove/find O(log n).
• Előny: rendezett bejárás (in-order traversal), subset műveletek (helyközi) könnyen támogatott.

Java: TreeSet<E> C++: std::set<T>

2.3. Statikus tömb + indexes

• Adatszerkezet:
  • Egy tömb az elemeknek, egy párhuzamos hash‐tábla vagy bit‐vektor a jelenlét jelölésére,
  • vagy „next‐index” láncolás statikus tömbbel, ha fix méretű univerzum.
• Műveletek: O(1) vagy amortizált O(1), de fix méretezésű.

Használható, ha az univerzum kicsi és előre ismert (pl. karakterkészlet).

---

3. Komplexitás összefoglaló

Implementáció	insert	remove	contains	memory overhead
HashSet	O(1) amort.	O(1) amort.	O(1) amort.	nagy (buckets)
TreeSet	O(log n)	O(log n)	O(log n)	közepes (fa)
LinkedHashSet	O(1) amort.	O(1) amort.	O(1) amort.	plusz sorrendlisták
Static bit‐vector	O(1)	O(1)	O(1)	minimális

---

4. Mikor melyiket válasszuk?

1. Gyors tagság‐ellenőrzés, sorrend nem kell → HashSet / std::unordered_set
2. Rendezett bejárás szükséges (pl. min/max lekérdezés között) → TreeSet / std::set
3. Ismétlődések engedélyezettek → Multiset / std::multiset / HashMultiset
4. Párhuzamos hozzáférés → Concurrent hash‐táblák (Java: ConcurrentHashMap/KeySetView)

---

5. Halmazműveletek

• union(A,B):

  C = emptySet()
  for x in A: C.insert(x)
  for x in B: C.insert(x)
  return C

• intersection(A,B):

  C = emptySet()
  // végig a kisebbik halmazon
  for x in (|A|<|B| ? A:B)
    if B.contains(x): C.insert(x)
  return C

• difference(A,B):

  C = emptySet()
  for x in A:
    if not B.contains(x): C.insert(x)
  return C

Amennyiben a set impl. TreeSet, akkor ez mind O(n log n). HashSet‐tel amortizált O(n).

---

6. Standard könyvtárak

• C++

  #include <unordered_set>
  std::unordered_set<int> S;
  S.insert(42);
  if (S.count(5)) /* benne van? */;
  for (auto &x : S) cout<<x;
  

  #include <set>
  std::set<string> T;
  T.insert("alma");
  auto it = T.find("korte");
  

• Java

  Set<String> s = new HashSet<>();
  s.add("foo");
  boolean ok = s.contains("bar");
  Set<String> t = new TreeSet<>();
  

• Python (built-in)

  s = set()
  s.add(5)
  if 5 in s: …
  

---

7. Összefoglalás

A Set ADT a gyors ismétlődés‐mentesség és tagság‐ellenőrzés kulcsszava. A megfelelő implementáció (hash vs. fa vs. statikus tömb) a műveleti profiltól, memória‐korlátoktól és sorrendiség‐igénytől függ. Gyakori építőelem a szoftverekben: eltávolítandó duplikátumok, kulcstartományok, relációs műveletek (unió, metszet, differencia), és bármilyen helyzet, ahol csak a „benne van-e” kérdés érdekes.

További információk

• set data type - Szótár.net (en-hu)
• set data type - Sztaki (en-hu)
• set data type - Merriam–Webster
• set data type - Cambridge
• set data type - WordNet
• set data type - Яндекс (en-ru)
• set data type - Google (en-hu)
• set data type - Wikidata
• set data type - Wikipédia (angol)