Java-Collection-Algorithmen

Java-Collection-Algorithmen beziehen sich aufjava.util.Collections, eine Reihe statischer Methoden, die in der Collections-Klasse bereitgestellt werden und dazu dienen, gängige Operationen wie Sortieren, Suchen, Mischen, Füllen usw. für Sammlungen (List, Set, Map usw.) auszuführen.

Diese Algorithmen sind im JDK integriert und hochgradig optimiert. Entwickler müssen sie nicht von Grund auf neu schreiben; sie können sie einfach direkt aufrufen.

Überblick über die Collections-Algorithmen

java.util.CollectionsCollections ist eine Hilfsklasse; alle ihre Methoden sind statisch, ähnlich wie die Arrays-Hilfsklasse für Arrays.

Die folgende Tabelle listet die am häufigsten verwendeten Collection-Algorithmen und ihre Zwecke auf:

AlgorithmuskategorieMethodennameBeschreibung
Sortierungsort()Sortiert eine List in aufsteigender Reihenfolge
Mischenshuffle()Mischt die Reihenfolge der Elemente in einer List zufällig
Umkehrungreverse()Kehrt die Reihenfolge der Elemente in einer Liste um
Binäre SuchebinarySearch()Führt eine binäre Suche nach einem angegebenen Element in einer sortierten Liste durch
Füllenfill()Ersetzt alle Elemente in einer Liste durch ein angegebenes Element
Copycopy()Kopiert Elemente von einer Liste in eine andere Liste
Maximum/Minimummax() / min()Gibt das maximale oder minimale Element in einer Sammlung zurück
Häufigkeitszählungfrequency()Gibt die Anzahl der Vorkommen eines angegebenen Elements in einer Collection zurück
Disjunktheitsprüfungdisjoint()Bestimmt, ob zwei Collections gemeinsame Elemente haben
Unveränderliche CollectionunmodifiableXxx()Gibt eine schreibgeschützte Ansicht einer Collection zurück
ThreadsicherheitsynchronizedXxx()Gibt einen threadsicheren Wrapper für eine Collection zurück

Sortierung

Collections.sort()Er ist der am häufigsten verwendete Collection-Algorithmus und ordnet die Elemente in einer List in aufsteigender Reihenfolge an.

Unter der Haube verwendet er einen optimierten Mergesort (TimSort) mit einer Zeitkomplexität von O(n log n) und stabiler Performance.

Der Sortiervorgang ist in der folgenden Abbildung dargestellt:

Input Original list 5 2 8 1 9 Arrow sort() Output Sorted list 1 2 5 8 9 Custom Sorting Custom sorting methods Natural order Comparable interface Custom comparator Comparator interface Reverse sorting Comparator.reverseOrder()

Sortierung nach natürlicher Reihenfolge

Wenn die Elementklasse das InterfaceComparableimplementiert, können Sie direkt sort() aufrufen, um nach der natürlichen Reihenfolge zu sortieren.

Beispiel

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortExample {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("example");
        names.add("EXAMPLE");
        names.add("apple");
        names.add("banana");

        System.out.println("Before sorting: " + names);

        // Nach natürlicher Reihenfolge sortieren (nach Unicode-Codepunkt)
        Collections.sort(names);

        System.out.println("Nach dem Sortieren: " + names);
    }
}

Ausgabeergebnis:

排序前: [example, EXAMPLE, apple, banana]
排序后: [EXAMPLE, apple, banana, example]

Sortieren mit benutzerdefiniertem Comparator

MitComparatorkönnen Sie nach jeder benutzerdefinierten Regel sortieren, ohne die Elementklasse selbst zu ändern.

Beispiel: Nach Stringlänge sortieren

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class CustomSortExample {
    public static void main(String[] args) {
        List<String> words = new ArrayList<>();
        words.add("example");
        words.add("java");
        words.add("algorithm");
        words.add("C");

        System.out.println("Vor dem Sortieren: " + words);

        // Nach Zeichenkettenlänge in aufsteigender Reihenfolge sortieren
        Collections.sort(words, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.length() - s2.length();
            }
        });

        System.out.println("Nach dem Sortieren nach Länge: " + words);
    }
}

Ausgabeergebnis:

排序前: [example, java, algorithm, C]
按长度排序后: [C, java, example, algorithm]

Mit Java 8+ können Lambda-Ausdrücke verwendet werden, um den Code zu vereinfachen:

Beispiel: Lambda-Syntax

// Nach Länge mithilfe eines Lambda-Ausdrucks sortieren
Collections.sort(words, (s1, s2) -> s1.length() - s2.length());

// Oder Comparator.comparingInt verwenden
Collections.sort(words, Comparator.comparingInt(String::length));

// Umgekehrt sortieren
Collections.sort(words, Comparator.reverseOrder());

// Nach Länge in umgekehrter Reihenfolge sortieren
Collections.sort(words, Comparator.comparingInt(String::length).reversed());

Mischen

Collections.shuffle()Verwendet den Fisher-Yates-Algorithmus, um die Reihenfolge der Elemente in einer List zufällig zu mischen.

Original list A B C D shuffle() After shuffling (random) C D A B ? ? ? Note The result is different each time it runs Fixed seed shuffle(list, new Random(42)) accepts a fixed seed, making the shuffling result reproducible.

Beispiel

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ShuffleExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            numbers.add(i);
        }

        System.out.println("Ursprüngliche Liste: " + numbers);

        // Reihenfolge zufällig mischen
        Collections.shuffle(numbers);
        System.out.println("Erste Mischung: " + numbers);

        Collections.shuffle(numbers);
        System.out.println("Zweite Mischung: " + numbers);
    }
}

Ausgabeergebnis:

原始列表: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
第一次混排: [7, 3, 9, 1, 5, 10, 8, 2, 4, 6]
第二次混排: [4, 10, 1, 8, 6, 3, 2, 9, 5, 7]

Binäre Suche

Collections.binarySearch()Verwendet den binären Suchalgorithmus, um ein Zielelement in einer sortierten Liste zu finden.

Die Zeitkomplexität beträgt O(log n), viel besser als die O(n) einer linearen Traversierung.

Wichtige Voraussetzung: Die Liste muss bereits aufsteigend sortiert sein; andernfalls ist das Ergebnis undefiniert.

Beispiel

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinarySearchExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(10);
        numbers.add(30);
        numbers.add(20);
        numbers.add(50);
        numbers.add(40);

        // Zuerst sortieren
        Collections.sort(numbers);
        System.out.println("Sortierte Liste: " + numbers);

        // Binäre Suche: Der Rückgabewert ist der Index (>= 0 bedeutet gefunden)
        int index = Collections.binarySearch(numbers, 30);
        System.out.println("Indexposition von 30: " + index);

        // Suche nach einem nicht existierenden Element: gibt einen negativen Wert zurück = -(Einfügeposition) - 1
        int notFound = Collections.binarySearch(numbers, 25);
        System.out.println("Rückgabewert für 25 (nicht gefunden): " + notFound);
        // Einfügepunkt = -(notFound + 1) = 2, also sollte es an Index 2 eingefügt werden
    }
}

Ausgabeergebnis:

排序后列表: [10, 20, 30, 40, 50]
30 的索引位置: 2
25 的返回值（不存在）: -3

Wenn binarySearch() ein Element nicht finden kann, wird ein negativer Wert zurückgegeben; die Formel lautet-(Einfügepunkt) - 1Der Einfügepunkt ist der Index, an dem sich das Element befinden würde, wenn es existierte. Die Cleverness dieses Designs besteht darin, dass ein nicht-negativer Index zurückgegeben wird, wenn das Element existiert; wenn es nicht existiert, wird zwangsläufig ein negativer Wert zurückgegeben, sodass keine Mehrdeutigkeit besteht.

Maximum und Minimum

Collections.max()undCollections.min()Gibt das maximale/minimale Element in einer Collection gemäß der natürlichen Ordnung oder einem angegebenen Comparator zurück.

Beispiel

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MaxMinExample {
    public static void main(String[] args) {
        List<String> words = new ArrayList<>();
        words.add("example");
        words.add("algorithm");
        words.add("java");
        words.add("code");

        // Maximum und Minimum nach natürlicher Ordnung (lexikografische Reihenfolge) ermitteln
        String maxWord = Collections.max(words);
        String minWord = Collections.min(words);
        System.out.println("Lexikografisches Maximum: " + maxWord);
        System.out.println("Lexikografisches Minimum: " + minWord);

        // Maximum und Minimum nach Stringlänge ermitteln
        String longest = Collections.max(words,
            Comparator.comparingInt(String::length));
        String shortest = Collections.min(words,
            Comparator.comparingInt(String::length));
        System.out.println("Längste Länge: " + longest);
        System.out.println("Kürzeste Länge: " + shortest);
    }
}

Ausgabeergebnis:

字典序最大: example
字典序最小: algorithm
长度最长: algorithm
长度最短: code

Häufigkeitszählung und Disjunktheitsprüfung

Collections.frequency()Zählt die Anzahl der Vorkommen eines angegebenen Elements in einer Collection.

Collections.disjoint()Ermittelt, ob zwei Collections überhaupt keine gemeinsamen Elemente haben.

Beispiel

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class FrequencyDisjointExample {
    public static void main(String[] args) {
        List<String> items = new ArrayList<>();
        items.add("example");
        items.add("java");
        items.add("example");
        items.add("python");
        items.add("example");

        // Zähle die Vorkommen von "example"
        int count = Collections.frequency(items, "example");
        System.out.println("\"example\""Vorkommen: " + count);

        // Prüfe, ob die beiden Sammlungen disjunkt sind
        List<String> groupA = new ArrayList<>();
        groupA.add("java");
        groupA.add("python");

        List<String> groupB = new ArrayList<>();
        groupB.add("C++");
        groupB.add("go");

        boolean noCommon = Collections.disjoint(groupA, groupB);
        System.out.println("groupA und groupB sind disjunkt: " + noCommon);
    }
}

Ausgabeergebnis:

"example" 出现次数: 3
groupA 与 groupB 不相交: true

Unveränderliche Sammlungen und threadsichere Wrapper

Collections bietet Methoden, um gewöhnliche Sammlungen als unveränderliche Sammlungen oder threadsichere Sammlungen zu verpacken.

Unveränderliche Sammlungen (nicht modifizierbar)

Der Aufruf vonCollections.unmodifiableList()und anderen Methoden kann eine schreibgeschützte Ansicht erzeugen.

Jede Änderungsoperation löst UnsupportedOperationException aus.

Threadsichere Sammlungen (synchronisiert)

Der Aufruf vonCollections.synchronizedList()und anderen Methoden kann einen threadsicheren Wrapper erzeugen.

In einer Multithread-Umgebung sind einzelne Methodenaufrufe auf diesen Sammlungen sicher, aber zusammengesetzte Operationen erfordern weiterhin eine externe Synchronisierung.

Beispiel

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class WrapperExample {
    public static void main(String[] args) {
        List<String> original = new ArrayList<>();
        original.add("example");
        original.add("java");

        // Eine unveränderliche Ansicht erstellen
        List<String> readOnly = Collections.unmodifiableList(original);
        System.out.println("Unveränderliche Ansicht: " + readOnly);

        // readOnly.add("error"); // Die Ausführung hiervon löst eine Ausnahme aus

        // Nachdem die ursprüngliche Liste geändert wurde, spiegelt die unveränderliche Ansicht die Änderungen ebenfalls wider
        original.add("python");
        System.out.println("Nach Änderung des Originals: " + readOnly);

        // Einen threadsicheren Wrapper erstellen
        List<String> syncList = Collections.synchronizedList(
            new ArrayList<>());
        syncList.add("thread-safe");

        // Manuelle Synchronisierung ist beim Iterieren erforderlich
        synchronized (syncList) {
            for (String item : syncList) {
                System.out.println(item);
            }
        }
    }
}

Ausgabeergebnis:

不可变视图: [example, java]
原始修改后: [example, java, python]
thread-safe

Eine unveränderliche Ansicht verhindert nur das Ändern der Sammlung durch diese Ansicht; die zugrunde liegende Sammlung bleibt veränderbar. Wenn Sie eine wirklich unveränderliche Sammlung benötigen, verwenden Sie die MethodenList.of()、Set.of() von Java 9+und weitere Methoden.

Gängige Algorithmusoperationen im Überblick

Das Folgende fasst die Aufrufmethoden und Zeitkomplexitäten gängiger Algorithmen in Collections zusammen:

AktionMethodenaufrufZeitkomplexitätVoraussetzung
SortierungCollections.sort(list)O(n log n)Elemente implementieren Comparable
Benutzerdefiniertes SortierenCollections.sort(list, comp)O(n log n)Einen Comparator bereitstellen
UmkehrenCollections.reverse(list)O(n)Keine
MischenCollections.shuffle(list)O(n)Keine
Binäre SucheCollections.binarySearch(list, key)O(log n)Die Liste ist sortiert
FüllenCollections.fill(list, obj)O(n)Keine
KopierenCollections.copy(dest, src)O(n)dest.size() >= src.size()
MaximumCollections.max(coll)O(n)Elemente implementieren Comparable
MinimumCollections.min(coll)O(n)Elemente implementieren Comparable
Häufigkeit zählenCollections.frequency(coll, obj)O(n)Keine
Elemente vertauschenCollections.swap(list, i, j)O(1)Die Indizes sind gültig
RotierenCollections.rotate(list, distance)O(n)Keine

Hinweise

binarySearch() muss auf einer sortierten Liste aufgerufen werden; das für eine unsortierte Liste zurückgegebene Ergebnis ist undefiniert. Wenn die Liste doppelte Elemente enthält, gibt es keine Garantie, welches gefunden wird.

Der von synchronizedXxx() zurückgegebene Wrapper garantiert Atomarität nur auf der Ebene eines einzelnen Methodenaufrufs. Zusammengesetzte Operationen (wie if(!list.contains(x)) list.add(x)) erfordern weiterhin einen externen synchronized-Block.

Unterschied zwischen sort() und List.sort():

Seit Java 8 wurde der List-Schnittstelle die Default-Methode sort(Comparator) hinzugefügt.

list.sort(null) sortiert unter Verwendung der natürlichen Ordnung und entspricht Collections.sort(list).

Beide haben dieselbe zugrunde liegende Implementierung, aber list.sort() ist syntaktisch prägnanter.

Vorschläge zum Leistungsvergleich:

Bei kleinen Datenmengen (weniger als 100 Elemente) sind die Leistungsunterschiede zwischen verschiedenen Algorithmen vernachlässigbar.

Bei großen Datenmengen ist binarySearch() der linearen Suche von indexOf() weit überlegen.

Wenn häufige Suchvorgänge erforderlich sind, sollten Sie die Verwendung von HashSet anstelle von List in Betracht ziehen, da die Abfragekomplexität O(1) beträgt.

Andere Erweiterungen