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
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 gcd();square() Java Basics - Anfänger-Themen 98
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
Poppigescorn Häufigkeit einer zahl zählen Java Basics - Anfänger-Themen 5
B Konkatenieren eines Strings und inkremtierenden Zahl zu einer INT Variablen Java Basics - Anfänger-Themen 7
C Auf die Methode einer anderen Klasse zugreifen Java Basics - Anfänger-Themen 1
C Initialiseren einer Superklasse Java Basics - Anfänger-Themen 2
D Verbesserungsvorschläge zur Struktur einer Client Server Desktop Chat App Java Basics - Anfänger-Themen 24
Poppigescorn Mithilfe einer Arrayliste einen Notenspiegel ausgeben Java Basics - Anfänger-Themen 12
A 2 Strings vergleichen in einer methode wenn man mit Globalen variablen arbeitet Java Basics - Anfänger-Themen 12
J Verdoppeln einer Zahl (in dem Fall Münzen) Java Basics - Anfänger-Themen 4
K Rekursion einer Zahlenfolge (Ab- und Aufzählung) Java Basics - Anfänger-Themen 6
B Static Attribute in einer Klasse, wie geht das? :O Java Basics - Anfänger-Themen 19
L Zufälligen Zahlencode, ohne mehrfacher Verwendung einer Ziffer Java Basics - Anfänger-Themen 15
rafi072001 Sortieren einer HashMap nach Values Java Basics - Anfänger-Themen 2
Vivien Auf eine Variable von einer anderen Klasse aus zugreifen Java Basics - Anfänger-Themen 3
S Verständnis-Frage zu einer HÜ? Java Basics - Anfänger-Themen 1
A Array Ansprache einer Zelle über Punktnotation? Java Basics - Anfänger-Themen 3
Poppigescorn Quersumme Berechnen mit einer While Schleife Java Basics - Anfänger-Themen 13
J Wert in einer json Datei ändern und speichern Java Basics - Anfänger-Themen 3
M Aufruf von statischen Methoden einer anderen Klasse Java Basics - Anfänger-Themen 15
L Längstes Element einer ArrayList ausgeben Java Basics - Anfänger-Themen 9
J Autovervollständigung in einer Tabelle Java Basics - Anfänger-Themen 40
H Den Wert einer rekursiven Funktion bestimmen Java Basics - Anfänger-Themen 5
D Methoden nach einer bestimmten Reihenfolge ausführen. Java Basics - Anfänger-Themen 20
F GSON file mit einer List erstellen Java Basics - Anfänger-Themen 2

Ähnliche Java Themen


Oben