Entfernung von Duplikaten aus einem Array in JavaScript: Analyse unter der Haube

Woher kommen Duplikate und warum sind sie ein Problem?

Stellen Sie sich vor: Sie sammeln Daten von einer API, parsen eine CSV-Datei oder verarbeiten Benutzereingaben. In 90% der Fälle stoßen Sie auf Arrays, in denen dasselbe Element mehrmals vorkommt. Dies ist nicht nur ein ästhetisches Problem – Duplikate können Statistiken verfälschen, das Rendern von Listen stören oder zu Endlosschleifen in Algorithmen führen.

Die Frage "Remove duplicate values from a JavaScript array" auf Stack Overflow hat tausende Aufrufe nicht ohne Grund. Es handelt sich um eine grundlegende, aber kritisch wichtige Operation, die jeder Entwickler kennen sollte. Heute schauen wir unter die Haube und analysieren, wie verschiedene Ansätze funktionieren – von naiven bis zu den leistungsfähigsten.

Methode Nr. 1: Set – die eleganteste und schnellste

Wenn Sie einen modernen JavaScript-Entwickler fragen: "Wie entfernt man Duplikate?", wird er als Erstes Set nennen. Und das zu Recht. Aber wie funktioniert das?

const numbers = [1, 2, 2, 3, 4, 4, 5];\nconst uniqueNumbers = [...new Set(numbers)];\nconsole.log(uniqueNumbers); // [1, 2, 3, 4, 5]

Was passiert unter der Haube von Set?

Das Objekt Set speichert eindeutige Werte beliebigen Typs. Wenn Sie das Array an den Konstruktor new Set(numbers) übergeben, führt die JavaScript-Engine (V8, SpiderMonkey usw.) die folgenden Schritte aus:

\n
• Iteration über das Array: Die Engine durchläuft jedes Element des ursprünglichen Arrays.
\n
• Prüfung auf Eindeutigkeit: Für jedes Element wird eine interne Hash-Funktion aufgerufen. Wenn das Element bereits in einem "Bucket" vorhanden ist, wird es ignoriert. Wenn nicht, wird es hinzugefügt.
\n
• Zusammenstellung des Ergebnisses: Der Operator [...set] (Spread) entfaltet das iterierbare Set-Objekt zurück in ein Array.
\n

Ein wichtiger Punkt: Set verwendet den Vergleichsalgorithmus SameValueZero. Das bedeutet, dass NaN als gleich zu NaN betrachtet wird (im Gegensatz zu ===), während +0 und -0 als unterschiedliche Werte gelten. In der Praxis spielt dies selten eine Rolle, aber es ist gut zu wissen.

Leistung von Set

Die Komplexität der Operation beträgt O(n). Jedes Element wird genau einmal geprüft. Dies ist der beste Wert unter allen Methoden. Bei Arrays mit 10.000 Elementen kann der Unterschied zwischen Set und anderen Methoden Dutzende Millisekunden betragen – kritisch für stark ausgelastete Anwendungen.

Methode Nr. 2: filter + indexOf – der Klassiker

Vor der Einführung von ES6 (2015) verwendeten Entwickler die Kombination von filter und indexOf. Diese Methode ist immer noch in Legacy-Code zu finden:

const numbers = [1, 2, 2, 3, 4, 4, 5];\nconst uniqueNumbers = numbers.filter((value, index, self) => {\n    return self.indexOf(value) === index;\n});\nconsole.log(uniqueNumbers); // [1, 2, 3, 4, 5]

Wie funktioniert das?

\n
• filter durchläuft jedes Element des Arrays.
\n
• Für jedes Element wird indexOf(value) aufgerufen, das den ersten Index zurückgibt, an dem dieser Wert vorkommt.
\n
• Wenn der aktuelle Index des Elements mit dem ersten gefundenen Index übereinstimmt, handelt es sich um das erste Vorkommen, und das Element bleibt erhalten. Wenn nicht, handelt es sich um ein Duplikat, und es wird verworfen.
\n

Fallstricke

Das Hauptproblem ist die Leistung. indexOf verwendet intern eine lineare Suche (O(n) für jeden Aufruf). Dadurch wird die Komplexität für ein Array mit N Elementen zu O(n²). Bei 1000 Elementen ist dies noch akzeptabel, aber bei 100.000 werden Verzögerungen spürbar.

Ein weiterer Nachteil: indexOf funktioniert nicht korrekt mit NaN. Wenn das Array NaN enthält, gibt indexOf(NaN) immer -1 zurück, und das Element wird erneut hinzugefügt. Für die Prüfung auf NaN muss