Implementierung einer getNextId Methode

M

Mika34

Bekanntes Mitglied
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.
 
H

httpdigest

Top Contributor
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:
Java:
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.
 
M

Mika34

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

Mika34

Bekanntes Mitglied
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:
Java:
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?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
SexyPenny90 Implementierung einer doubly linked list Java Basics - Anfänger-Themen 5
Y Implementierung einer Potenzturm Funktion Java Basics - Anfänger-Themen 4
T Problem mit Implementierung von einer HashMap aufgabe Java Basics - Anfänger-Themen 2
J Implementierung von Observer und Singleton-Pattern Java Basics - Anfänger-Themen 9
A Implementierung von String toString methode() Java Basics - Anfänger-Themen 4
G Projekt architektur (implementierung) Java Basics - Anfänger-Themen 3
J Implementierung Listen-ADT Java Basics - Anfänger-Themen 131
J Implementierung eines Zustandsdiagramms Java Basics - Anfänger-Themen 19
I GenericQueue / Implementierung als Ringspeicher Java Basics - Anfänger-Themen 4
M Log4j2 implementierung Java Basics - Anfänger-Themen 4
S Interface Interface und seine Implementierung Java Basics - Anfänger-Themen 5
G Array implementierung Java Basics - Anfänger-Themen 23
J ANTLR Installierung und Implementierung Java Basics - Anfänger-Themen 2
E Hilfe bei Implementierung von Methoden Java Basics - Anfänger-Themen 10
S SkipList Implementierung Java Basics - Anfänger-Themen 1
J Methoden Suche effiziente Implementierung für eine Methode Java Basics - Anfänger-Themen 3
J Interface Probleme bei der Implementierung Java Basics - Anfänger-Themen 1
E hashCode implementierung Java Basics - Anfänger-Themen 9
S Implementierung der Klasse Konto und Nutzung bereits vorhandener Klassen Java Basics - Anfänger-Themen 7
H Implementierung eines Interfaces erweitern Java Basics - Anfänger-Themen 13
O Generics - Implementierung Java Basics - Anfänger-Themen 7
A Hilfestellung zur Implementierung des Gaußsches Eliminationsverfahren Java Basics - Anfänger-Themen 4
B OOP Implementierung eines Heaps Java Basics - Anfänger-Themen 13
K Bucketsort Implementierung Java Basics - Anfänger-Themen 0
K Mergesort Fehler in der Implementierung Java Basics - Anfänger-Themen 2
K Quicksort Fehler in der Implementierung Java Basics - Anfänger-Themen 2
S Klassen Klassendiagramm Implementierung? Java Basics - Anfänger-Themen 5
J Bucketsort Implementierung Java Basics - Anfänger-Themen 0
C Stack - listenbasierte Implementierung Java Basics - Anfänger-Themen 4
N Was bedeutet "Implementierung vor dem Client verbergen" bei Design Patterns? Java Basics - Anfänger-Themen 2
T Collections LinkedList<LinkedList<T>> - Implementierung Java Basics - Anfänger-Themen 10
F Implementierung von Interfaces -> Problem mit main Java Basics - Anfänger-Themen 12
D Resourcebundle implementierung Java Basics - Anfänger-Themen 2
M Implementierung des Knuth-Morris-Pratt-Algorithmus Java Basics - Anfänger-Themen 0
Q Implementierung von Listenern Java Basics - Anfänger-Themen 4
B Klassen Hilfe bei Implementierung Java Basics - Anfänger-Themen 5
N Compiler-Fehler Comparable / compareTo implementierung Java Basics - Anfänger-Themen 2
S Fragen zur Implementierung eines Binärbaums Java Basics - Anfänger-Themen 3
I Erste Schritte Implementierung der API Java Basics - Anfänger-Themen 2
S Fragen zur Implementierung eines Adressbuches Java Basics - Anfänger-Themen 20
M falsche implementierung von currentTimeMillis() ? Java Basics - Anfänger-Themen 14
G Implementierung eines Kontos Java Basics - Anfänger-Themen 11
M Quicksort implementierung Java Basics - Anfänger-Themen 23
N Binärbaum/Implementierung Java Basics - Anfänger-Themen 9
U Doppelte Interfcae Implementierung Java Basics - Anfänger-Themen 10
K Kleiner Fehler bei Methoden Implementierung Java Basics - Anfänger-Themen 6
M Collections Problem bei Überschreibung von hashcode() und equals() bei Hashset-Implementierung Java Basics - Anfänger-Themen 5
S OOP Implementierung Komposition, Aggregation, Assoziation und Generalisierung Java Basics - Anfänger-Themen 2
C Klassenhirarchien zur Implementierung von Fahrzegen Java Basics - Anfänger-Themen 26
BinaryLogic Datentypen Statistik Interface - untersch. Implementierung Java Basics - Anfänger-Themen 5
E Performante Implementierung eines "Hintergrundprogramms" Java Basics - Anfänger-Themen 10
S Saubere Implementierung Java Basics - Anfänger-Themen 2
K Dijkstra implementierung 2.0 Java Basics - Anfänger-Themen 19
K dijskral implementierung Java Basics - Anfänger-Themen 14
U Probleme mit Server-Client implementierung Java Basics - Anfänger-Themen 5
K Game of Life Implementierung Java Basics - Anfänger-Themen 30
B OOP Problem bei Implementierung von Interface Java Basics - Anfänger-Themen 6
J HashSet Implementierung Java Basics - Anfänger-Themen 16
R NullPointerException in Queue-Implementierung Java Basics - Anfänger-Themen 11
X Frage zur Implementierung von equals() Java Basics - Anfänger-Themen 2
B Effektive Implementierung für Darstellung großer Datenmengen in Jogl Java Basics - Anfänger-Themen 5
D Datentypen Implementierung eines Binärbaumes Java Basics - Anfänger-Themen 7
B Implementierung Java Basics - Anfänger-Themen 2
N Implementierung Tic tac toc Java Basics - Anfänger-Themen 25
O Stack Implementierung als verkettete Liste Java Basics - Anfänger-Themen 8
S Implementierung gegen Interfaces / List, ArrayList, LinkedList Java Basics - Anfänger-Themen 11
J Quicksort Implementierung-- Exception ArrayOutOfBounds Java Basics - Anfänger-Themen 6
U Implementierung Constructor Java Basics - Anfänger-Themen 7
G Implementierung des Observer/Observable Patterns - Gut so? Java Basics - Anfänger-Themen 3
I Zugriff auf Implementierung verhindern Java Basics - Anfänger-Themen 8
D Implementierung nach MVC Java Basics - Anfänger-Themen 6
B Theoretische Frage zum Programmbau (nun zur Implementierung) Java Basics - Anfänger-Themen 8
H Implementierung von Interfaces Java Basics - Anfänger-Themen 4
G Implementierung von Bäumen Java Basics - Anfänger-Themen 2
N Probleme mit paint() bei Implementierung in ein Panel Java Basics - Anfänger-Themen 4
B Wie funktioniert die implementierung von c code in Java? Java Basics - Anfänger-Themen 7
A Methode in einer anderen Klasse verwenden Java Basics - Anfänger-Themen 1
U Compiler-Fehler Programmierung einer Drehkugel Java Basics - Anfänger-Themen 8
T Bestimmte Zahlen ausgeben mit einer whilfe Schleife Java Basics - Anfänger-Themen 21
JD_1998 Array-Position aus einer Methode in einer anderen ausgeben (Kurze Frage) Java Basics - Anfänger-Themen 2
JD_1998 Random Array sortieren mit Hilfe einer Methode Java Basics - Anfänger-Themen 4
jonny_2k12 Wie kann ich eine ArrayList aus einer Klasse in eine andere übergeben? Java Basics - Anfänger-Themen 21
L Datentypen Deklarierte Felder einer Generic Klasse bestimmen Java Basics - Anfänger-Themen 7
O Namen (mit Umlauten und ß) in einer ArrayList suchen Java Basics - Anfänger-Themen 5
A eine neue normale String-Array von einer String-Array, die in for schleife ist, schaffen Java Basics - Anfänger-Themen 3
itsmejo Erste Schritte Auf Attribut einer anderen Klasse zugreifen. Java Basics - Anfänger-Themen 14
DorFey Schrittweises abändern des GUI während for-Schleife / pausieren einer for-Schleife Java Basics - Anfänger-Themen 3
R Implementieren einer iterativen und rekursiven Klassenmethode. Java Basics - Anfänger-Themen 1
K Übergabe des Wertes einer Variable aus main() in eine Klassenmethode Java Basics - Anfänger-Themen 8
K Übergabe von Werten (zweidimensionales Array) aus einer Methode an zweidimensionales Array in main() Java Basics - Anfänger-Themen 3
J Übergeben einer Objektreferenz Java Basics - Anfänger-Themen 6
M this.object in einer parameterlosen Methode verwenden Java Basics - Anfänger-Themen 3
M Warum dürfen Objekte einer Klasse auf statische Variablen dieser Klasse referenzieren? Java Basics - Anfänger-Themen 10
A Fehler beim Ausführen einer class Datei Java Basics - Anfänger-Themen 6
M Integer aus aus einer Klasse in andere speichern Java Basics - Anfänger-Themen 12
P Problem beim Überschreiben einer vererbten Methode Java Basics - Anfänger-Themen 4
P Veränderungen einer ObservableList Java Basics - Anfänger-Themen 10
N enum Attribut von Objekten einer Hashmap ausgeben Java Basics - Anfänger-Themen 6
O BiPredicate in einer forEach Methode Java Basics - Anfänger-Themen 10
N Typebound Objekte einer Arraylist hinzufügen Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Anzeige

Neue Themen


Oben