Helló C#! Helló Világ! 2.1

  2. Home
  4. Docs
  6. Helló C#! Helló Világ! 2.1
  8. 6. Adatstruktúrák
  10. Halmaz

Halmaz

A legtöbb programozási nyelv tartalmazza a matematikában tanult halmaz tároló szerkezet megvalósítását. A .NET keretrendszerben ezt a HashSet<T> osztály valósítja meg, amely egy olyan dinamikusan változtatható méretű tömböt (Lista) definiál, amelyben az elem indexét nem az határozza meg, hogy hányadik helyre írtuk be, hanem az elem értékéből képzett hash összeg. Ebből adódóan egy elemet nem tartalmazhat kétszer a kollekció, mivel két egyforma értékű elemnek biztosan azonos a hash értéke.

A kollekció előnye, hogy nagyon gyorsan meg lehet mondani azt, hogy egy elem tagja-e a kollekciónak vagy sem. Kiválóan alkalmas olyan helyzetekben, amikor gyorsan és sokszor kell elemeket keresni.

A HashSet érdekessége, hogy az Add metódus itt nem void visszatérési értékű. Helyette egy bool értéket ad vissza, amely igaz értékű lesz, ha az értéket hozzáadta a halmazhoz. Abban az esetben, ha a halmaz már tartalmazza az értéket, akkor a metódus hamis visszatérési értéket szolgáltat.

A HashSet<T> osztály fontosabb tulajdonságai és metódusai:

HashSet(IEnumerable<T> collection)

Paraméteres konstruktor. A halmaz elemei a paraméterként megadott IEnumerable felületet implementáló osztály elemei lesznek.

void ExceptWith(IEnumerable<T> other)

Különbséget1 képez a megadott IEnumerable<T> felületet megvalósító osztály elemeivel.

void IntersectWith(IEnumerable<T> other)

Metszetet2 képez a megadott IEnumerable<T> felületet megvalósító osztály elemeivel.

bool IsSubsetOf(IEnumerable<T> other)

Igaz értéket ad vissza, ha a paraméterként megadott IEnumerable<T> felületet megvalósító osztály elemeinek részhalmaza3 a jelenlegi halmaz.

bool Overlaps(IEnumerable<T> other)

Igaz értéket ad vissza, ha a paraméterként megadott IEnumerable<T> felületet megvalósító osztály elemeinek és a jelenlegi halmaznak van legalább egy olyan eleme, amely mindkettőben megtalálható.

bool SetEquals(IEnumerable<T> other)

Igaz értéket ad vissza, ha a paraméterként megadott IEnumerable<T> felületet megvalósító osztály összes eleme megtalálható a jelenlegi halmazban.

void SymmetricExceptWith(IEnumerable<T> other)

Szimmetrikus különbséget4 képez a megadott IEnumerable<T> felületet megvalósító osztály elemeivel.

void UnionWith(IEnumerable<T> other)

Uniót5 képez a paraméterként megadott IEnumerable<T> felületet megvalósító osztály elemeivel.

void TrimExcess()

Átméretezi a belső listát úgy, hogy csak annyi elemnek foglaljon helyet, mint amennyi ténylegesen használva van.

Az alábbi példaprogram a HashSet használatát mutatja be:

using System;
using System.Collections.Generic;

namespace PeldaHashset
{
    class Program
    {
        static void Kiir<T>(IEnumerable<T> collection)
        {
            foreach (var item in collection)
            {
                Console.Write("{0}, ", item);
            }
            Console.WriteLine("\n");
        }
        
        static void Main(string[] args)
        {
            var set1 = new HashSet<int>(new int[] { 2, 3, 4, 5, 6, 8, 1, 1 });
            var set2 = new HashSet<int>(new int[] { 1, 2, 3, 4});

            set2.Add(99); //még nincs ezért hozzá lesz adva
            set2.Add(99); //már van, ezért nem lesz hozzá adva

            Console.WriteLine("set1:");
            Kiir(set1);
            Console.WriteLine("set2:");
            Kiir(set2);

            Console.WriteLine("set1 unio set2:");
            set1.UnionWith(set2);

            Kiir(set1);

            Console.WriteLine("set2 metszet set1:");
            set2.IntersectWith(set1);

            Kiir(set2);

            Console.ReadKey();
        }
    }
}

A program kimenete:

$
set1:
2, 3, 4, 5, 6, 8, 1, 

set2:
1, 2, 3, 4, 99, 

set1 unio set2:
2, 3, 4, 5, 6, 8, 1, 99, 

set2 metszet set1:
1, 2, 3, 4, 99,

FrozenSet

A .NET 8 egyik új típusa a FrozenSet<T>, ami egy csak olvasható halmazt valósít meg. Kifejetetten olyan használati esetekre van optimalizálva, ahol többször fordul elő a halmaz olvasása, mint írása. Ezen kollekció a System.Collections.Frozen névtérben található és ugyanúgy használható, mint egy hagyományos HashSet típus, kivéve, hogy menet közben a tartalma nem módosítható.

Halmazokra vonatkozó azonosságok

∪: únió, ∩: Metszet

  1. Idempotencia: A ∪ A = A, A ∩ A = A
  2. kommutativitás: A ∪ B = B ∪ A, A ∩ B = B ∩ A
  3. Asszociativitás: A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∩ (B ∩ C) = (A ∩ B) ∩ C
  4. Disztributivitás: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

Implementált interfészek

HashSet<T> típus által implementált interfészek

HashSet<T> típus által implementált interfészek

A lábjegyzetekben használt definíciók forrása: https://hu.wikipedia.org/wiki/Halmaz

  1. Ha A és B halmazok, akkor az A és B különbségének nevezzük és A ∖ B módon jelöljük az A halmaz azon elemeinek összességét, melyek nem elemei B-nek.↩

  2. Ha A és B halmazok, akkor az A és B metszetének nevezzük és A ∩ B módon jelöljük azon elemek összességét, melyek A-nak és B-nek is elemei.↩

  3. Legyenek A és B tetszőleges halmazok. Azt mondjuk, hogy A részhalmaza a B halmaznak, és így jelöljük A ⊆ B, ha az a A halmaz összes elemét tartalmazza a B halmaz.↩

  4. Ha A és B halmazok, akkor az A és B szimmetrikus különbségének nevezzük és A ∆ B módon jelöljük azon elemek összességét, melyek nem tartoznak a két halmaz metszetébe.↩

  5. Ha A és B halmazok, akkor az A és B egyesítésének (vagy más szóval uniójának) nevezzük és A ∪ B módon jelöljük azon elemek összességét, melyek A illetve B közül legalább az egyikben benne vannak.↩

Tags ,