Nehmen wir einen Blick auf der Code . Die Methode retainAll wird von AbstractCollection geerbt und (zumindest in OpenJDK) sieht so aus:
Es gibt ein großes hier zu beachten, wir Schleife über this.iterator() und rufen c.contains . Die Zeitkomplexität ist also n ruft c.contains auf, wo n = this.size() und höchstens n auf it.remove() aufruft.
Wichtig ist, dass die Methode contains für andere Collection aufgerufen wird und die Komplexität daher von der Komplexität der anderen Collection contains abhängt.
Also, während:
%Vor% wäre O(a.length) , da HashSet.contains und HashSet.remove beide O(1) (amortisiert) sind.
Wenn Sie
anrufen würden %Vor% Dann würde dies aufgrund von O(n) contains auf Arrays.ArrayList zu O(a.length * b.length) werden - dh durch das Ausgeben von O(n) beim Kopieren des Arrays in HashSet wird der Aufruf von retainAll viel schneller ausgeführt.
Soweit Raumkomplexität erforderlich ist, wird von Iterator kein zusätzlicher Speicherplatz (über retainAll ) benötigt, aber Ihr Aufruf ist tatsächlich sehr teuer, da Sie zwei neue HashSet -Implementierungen zuweisen, die tatsächlich voll sind flügge HashMap .
Zwei weitere Dinge können angemerkt werden:
HashSet von den Elementen in a zuzuteilen - eine billigere Sammlung, die auch O(1) remove von der Mitte hat, wie zB LinkedList , kann verwendet werden. (billiger im Speicher und auch bauen Zeit - eine Hash-Tabelle ist nicht gebaut) b.size() zurückgeben. Die Implementierung befindet sich in der Klasse java.util.AbstractCollection . Die Art der Implementierung sieht folgendermaßen aus:
Also wird alles in Ihrer common Menge iteriert und geprüft, ob die Sammlung, die als Parameter übergeben wurde, dieses Element enthält.
In Ihrem Fall sind beide HashSet s, also wird es O (n) sein, da contains sollte O (1) amortisiert werden und Iterieren über Ihre common setzt ist O (n).
Eine Verbesserung, die Sie vornehmen können, besteht darin, einfach nicht a in ein neues HashSet zu kopieren, da es sowieso wiederholt wird, wenn Sie eine Liste behalten können.