Beste Komplexität zum Synchronisieren einer Karte mit einer Sammlung

Question

Ich habe das folgende Problem, für das ich eine anständige Lösung möchte.

Ich habe eine HashMap, die einige Objekte in Form von String (E-Mail) und Objekt (Person) enthält.
Diese Karte wird über eine Sammlung bevölkert über eine Methode updatePersonList (Sammlung Liste), wie unten beschrieben:
Jedes Mal, wenn eine neue Kollektion über das obige Verfahren erhalten wird, wird die Karte grundsätzlich die alle Elemente aus der Sammlung hinzufügen Karte. Das ist alles, was die Karte braucht, die neueste Kollektion. Was nicht in der Sammlung ist, sollte von der Karte entfernt werden.

Jetzt möchte ich wissen, wie ich die Karte effizient aktualisieren kann, weil, wie oben gelesen werden kann, die folgenden Szenarien möglich sind: 1. Einige Objekte können sowohl in der Karte als auch in der Sammlung gefunden werden daher sollten nur die neuen Objekte aus der Sammlung behalten werden und nicht alle.
2. Objekte, die sich in der Karte befinden, aber nicht in der Sammlung sind, sollten entfernt werden.

Was ist die beste Lösung in Bezug auf die Komplexität?
Nach einigen Untersuchungen kam ich mit dem Entfernen aller Objekte aus der Karte und füge die aus der Sammlung hinzu. Wenn jemand etwas besser weiß, wäre es schön, wenn es geteilt werden könnte.

Answer 1

helfen Sie nie besser als O (n + m) wobei n die Größe Ihrer Collection ist und m die Größe deiner Map weil Sie immer mindestens beide lesen müssen.

Also in O -notation könnten Sie einfach das Loch Map löschen und ein neues erstellen.

Aber in Wirklichkeit ist die Konstante möglicherweise nicht so unwichtig und Sie möchten vielleicht auch die Speicherbereinigung reduzieren. In diesem Fall kann es sinnvoll sein, beide zu durchlaufen und nur die benötigten Einträge aus der Map zu löschen und die neuen Elemente aus der Collection zur Map hinzuzufügen.

Aber nur Profiling wird Ihnen sagen, ob Sie etwas für diese Anstrengung gewonnen haben.

Answer 2

Nach meiner Sicht Verwenden Treemap statt Liste Ihre Iteration Leistung dh zu verbessern (Treemap wird nur eindeutige Werte annehmen), so dass neu eingefügte Objekte

automatisch

Nach erfolgreichem Design treemap identifizieren keine Markierungen entfernen auf der Karte statt Nachrichten Markierungen hinzufügen, die

in treemap definieren werde ich hoffe, dass es

Answer 3

Wenn die Liste oft den gleichen Inhalt wie die Karte hat, können Sie dies überprüfen, bevor Sie die Karte bereinigen und neue Einträge hinzufügen.