Implementierung einer getNextId Methode

[Mika34]

Schönen Abend an Alle,

Ich sitze nun seit mehreren Stunden daran mein Problem mit der ID eines Objektes zu lösen. Dieses Problem sieht wie folgt aus:

erstes Objekt: Farbe: schwarz, Länge: 2, ID: 1
zweites Objekt: Farbe:gelb, Länge: 5, ID: 2
drittes Objekt: Farbe: grün, Länge: 7, ID: 3

Wenn ich nun das zweite Objekt entferne bleibt dies übrig:
erstes Objekt: Farbe: schwarz, Länge: 2, ID: 1
drittes Objekt: Farbe: grün, Länge: 7, ID: 3

Füge ich nun ein, theoretisch gesehen, viertes Objekt hinzu, dann muss die Liste so aussehen:
erstes Objekt: Farbe: schwarz, Länge: 2, ID: 1
drittes Objekt: Farbe: grün, Länge: 7, ID: 3
viertes Objekt: Farbe: lila, Länge: 3, ID: 2

Es wird immer die nächste freie ID genommen, wenn ein Objekt erstellt wird. Also wenn ein Objekt entfernt wird, dann wird diese ID für das nächste zu hinzufügende Objekt freigeschaltet und das nächste Objekt erhält diese ID.

Nun versuche ich eine solche Methode in den Konstruktor meiner Objekte (ich muss diese Eigenschaft in alle Objekte implementieren) zu packen, jedoch scheitere ich kläglich, da die Zuweisung auf die nächste freie ID nicht klappen will. Ich habe meine Objekte in einer Map gespeichert, welche eindeutig über die ID hinzugefügt bzw. gelöscht werden können.
Hat jemand eine Idee wie ich hier vorzugehen habe.

Ich bin über jede Hilfe tierisch dankbar.

 

[httpdigest]

Das kannst du speichereffizient lösen, indem du dir die Lücken in der Id-Allokation merkst. Du benutzt also erstmal einen einfachen Sequenzzähler, um die Ids einfach hochzuzählen. Zusätzlich nutzt du eine sortierte Datenstruktur für freigegebene Ids. Wenn du eine neue Id generieren willst, prüfst, du erst, ob eine freigegebene Id wiederverwendet werden kann. Falls nicht, inkrementierst du deinen Sequenzzähler. Für die sortierte Datenstruktur der freigegebenen Ids, kannst du eine PriorityQueue verwenden:

import java.util.PriorityQueue;
public class IdAllocator {
  private final PriorityQueue<Long> items = new PriorityQueue<>();
  private long next = 1;
  /** Gibt die nächste freie Id zurück. */
  public long allocate() {
    return !items.isEmpty() ? items.poll() : next++;
  }
  /** Markiert die gegebene Id als frei. */
  public void free(long id) {
    items.add(id);
  }
}

Wie effizient das ganze ist, hängt nun davon ab, welche Datenstruktur für die freien Ids verwendet wird. Hier kann man sich beliebig austoben, z.B. auch Interval Trees verwenden, wenn es lange Strecken von freien Ids gibt.

 

[Mika34]

Vielen Dank httpdigest, jetzt kann ich beruhigt zu Bett gehen, ach du meine Güte.

 

[Mika34]

Das kannst du speichereffizient lösen, indem du dir die Lücken in der Id-Allokation merkst. Du benutzt also erstmal einen einfachen Sequenzzähler, um die Ids einfach hochzuzählen. Zusätzlich nutzt du eine sortierte Datenstruktur für freigegebene Ids. Wenn du eine neue Id generieren willst, prüfst, du erst, ob eine freigegebene Id wiederverwendet werden kann. Falls nicht, inkrementierst du deinen Sequenzzähler. Für die sortierte Datenstruktur der freigegebenen Ids, kannst du eine PriorityQueue verwenden:

import java.util.PriorityQueue;
public class IdAllocator {
  private final PriorityQueue<Long> items = new PriorityQueue<>();
  private long next = 1;
  /** Gibt die nächste freie Id zurück. */
  public long allocate() {
    return !items.isEmpty() ? items.poll() : next++;
  }
  /** Markiert die gegebene Id als frei. */
  public void free(long id) {
    items.add(id);
  }
}

Wie effizient das ganze ist, hängt nun davon ab, welche Datenstruktur für die freien Ids verwendet wird. Hier kann man sich beliebig austoben, z.B. auch Interval Trees verwenden, wenn es lange Strecken von freien Ids gibt.

Wenn ich hier nun eine ID erhöhe, sprich einen Wert hinzufüge, wie stelle ich das nun an?

 

[temi]

Wenn ich hier nun eine ID erhöhe, sprich einen Wert hinzufüge, wie stelle ich das nun an?

Du "holst" dir die nächste ID vom Allocator und erstellst damit ein Objekt:

ObjectWithId obj = new ObjectWithId(IdAllocator.allocate())

 

[Ullenboom]

https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicLong.html könnte auch dein Freund sein, man sollte sich gegenüber nebenläufigen Zugriffen absichern.