Was ist eine Menge und welche Probleme löst sie?

Question

Accepted Answer

Eine **Menge** ist eine ungeordnete Sammlung von **eindeutigen** Elementen. Ihre Kernstärke liegt darin, die Frage "ist X hier?" in **durchschnittlich O(1)** zu beantworten, und sie lehnt automatisch Duplikate ab.

## Beispiel

```python
seen = set()
seen.add('a')
seen.add('a')          # ignored — already present
print(len(seen))       # 1
'a' in seen            # O(1) average membership test

# Set algebra
a = {1, 2, 3}
b = {2, 3, 4}
a & b                  # intersection -> {2, 3}
a | b                  # union        -> {1, 2, 3, 4}
a - b                  # difference   -> {1}
```

Die meisten Mengen werden als **Hash-Mengen** implementiert (eine Hash-Tabelle, die nur Schlüssel speichert), also:

| Operation | Durchschnitt |
|---|---|
| add | O(1) |
| remove | O(1) |
| membership (`in`) | O(1) |

## Häufige Anwendungen

- **Deduplizierung** — Wiederholungen aus einer Liste in einer Zeile entfernen.
- **Schnelle Zugehörigkeit** — "habe ich das schon gesehen?"
- **Beziehungen** — Schnittmenge/Vereinigung/Differenz zwischen Gruppen.

## Warum es wichtig ist

Mengen machen "Eindeutigkeit" und "Zugehörigkeit" trivial und schnell und ersetzen langsame verschachtelte Schleifen über Listen.

Ein häufiger Interviewtrick — Erkennung von Duplikaten oder besuchten Knoten — reduziert sich auf wenige Mengenoperationen.