Multiset-Datenstruktur in Java

1. Optionen zum Implementieren von Multiset in Java
2. Beispiel einer Multiset-Datenstruktur in Java
3. Bequeme Implementierung von Multiset in Java

Multisets sind Datenstrukturen, mit denen Sie mehrere Elemente mit demselben Wert speichern können. In C++ enthält die Standard Template Library (STL) eine Multiset-Implementierung, die praktische Operationen zum Einfügen, Entfernen und Suchen von Elementen bereitstellt.

Diese Datenstruktur ist in verschiedenen Anwendungen nützlich, z. B. wenn Sie die Häufigkeit von Elementen in einer Sammlung zählen müssen.

Aber hat Java eine Multiset-Datenstruktur wie die in C++ STL? Die kurze Antwort ist ja.

Optionen zum Implementieren von Multiset in Java

Java bietet mehrere Optionen zum Implementieren eines Multisets, darunter:

1. Verwendung einer Map: Eine Map ist eine Sammlung, die Schlüssel auf Werte abbildet, und eine Option zur Implementierung eines Multisets besteht darin, eine Map zu verwenden, bei der die Schlüssel die Elemente und die Werte ihre Häufigkeiten sind. Um ein Element einzufügen, können Sie seine Häufigkeit erhöhen, und um ein Element zu entfernen, können Sie seine Häufigkeit verringern.
2. Verwendung einer Liste oder eines Arrays: Eine andere Möglichkeit besteht darin, eine Liste oder ein Array zu verwenden, um die Elemente zu speichern und dann eine Schleife zu verwenden, um die Häufigkeit jedes Elements zu zählen. Dieser Ansatz kann langsam sein, wenn die Sammlungsgröße groß ist, da linear Zeit benötigt wird, um die Häufigkeit eines Elements zu finden.
3. Verwenden einer Drittanbieter-Bibliothek: Mehrere Drittanbieter-Bibliotheken sind verfügbar, die eine Multiset-Implementierung für Java bereitstellen, wie z. B. Googles Guava-Bibliothek und Apache Commons Collections. Diese Bibliotheken bieten eine bequeme Implementierung ähnlich dem C++-STL-Multiset und können eine gute Option sein, wenn Sie vermeiden möchten, Ihre Implementierung zu schreiben.

Java hat also eine Multiset-Datenstruktur wie die in C++ STL, aber die Implementierung ist nicht Teil der Java-Kernbibliotheken. Stattdessen müssen Sie eine Map, eine List oder ein Array oder eine Bibliothek eines Drittanbieters verwenden, um ein Multiset in Java zu implementieren.

Beispiel einer Multiset-Datenstruktur in Java

Hier ist ein einfaches Beispiel einer Multiset-Datenstruktur in Java mit einer Map<E, Integer>:

import java.util.HashMap;
import java.util.Map;

public class MapMultiset<E> {
  private Map<E, Integer> map;

  public MapMultiset() {
    map = new HashMap<>();
  }

  public void add(E element) {
    Integer count = map.get(element);
    if (count == null) {
      count = 0;
    }
    map.put(element, count + 1);
  }

  public int count(E element) {
    Integer count = map.get(element);
    return count == null ? 0 : count;
  }

  public void remove(E element) {
    Integer count = map.get(element);
    if (count == null) {
      return;
    }
    if (count == 1) {
      map.remove(element);
    } else {
      map.put(element, count - 1);
    }
  }

  public static void main(String[] args) {
    MapMultiset<String> multiset = new MapMultiset<>();
    multiset.add("apple");
    multiset.add("banana");
    multiset.add("apple");
    multiset.add("orange");

    System.out.println("Frequency of apple: " + multiset.count("apple"));
    System.out.println("Frequency of banana: " + multiset.count("banana"));
    System.out.println("Frequency of orange: " + multiset.count("orange"));

    multiset.remove("apple");
    System.out.println("Frequency of apple after removing one: " + multiset.count("apple"));
  }
}

In diesem Beispiel verwenden wir eine Map<E, Integer>, um ein Multiset zu implementieren – die Map speichert Elemente als Schlüssel und ihre Häufigkeiten als Werte.

Wir haben die Methoden add, count und remove, die es uns ermöglichen, ein Element zur Multimenge hinzuzufügen, die Häufigkeit eines Elements zu finden und jeweils ein Vorkommen eines Elements zu entfernen.

Die Methode add ruft die aktuelle Anzahl des Elements aus der Map ab und setzt sie, wenn sie null ist, auf 0. Das Verfahren fügt dann 1 zu der Zählung hinzu und speichert die aktualisierte Zählung auf der Karte.

Die Methode count ruft die Anzahl des Elements aus der Map ab und gibt sie zurück oder gibt 0 zurück, wenn sich das Element nicht in der Map befindet.

Die Methode remove ruft die Anzahl der Elemente aus der Map ab und kehrt sofort zurück, wenn sie null ist. Wenn der Zähler 1 ist, entfernt die Methode das Element aus der Karte.

Das Verfahren dekrementiert und speichert den aktualisierten Zählwert in der Karte, wenn der Zählwert größer als 1 ist.

Wenn der Code ausgeführt wird, fügt er dem Multiset mehrere Elemente hinzu, ermittelt die Häufigkeit jedes Elements, entfernt ein Vorkommen des Elements "Apfel" und gibt die Häufigkeit jedes Elements aus.

Klicken Sie hier, um den Code zu überprüfen.

Bequeme Implementierung von Multiset in Java

Angenommen, Sie suchen nach einer bequemen und effizienten Multiset-Implementierung in Java. Die Verwendung einer Bibliothek eines Drittanbieters wie Guava oder Apache Commons Collections ist eine gute Idee.

Diese Bibliotheken bieten eine Vielzahl von Funktionen, einschließlich verschiedener Operationen zum Einfügen, Entfernen und Suchen nach Elementen und anderen Hilfsmethoden.