Gibt es eine Datenstruktur für diese Art von Liste / Karte?

22

Vielleicht gibt es einen Namen für das, was ich will, aber ich weiß es nicht. Ich brauche etwas Ähnliches wie LinkedHashMapin Java, aber wo gibt es den "vorherigen" Wert zurück, wenn es keinen Wert für den angegebenen Schlüssel gibt.

Das heißt, ich habe eine Liste von Objekten, die von einem Ganzzahlschlüssel gespeichert werden (in meinem Fall in Zeiteinheiten):

; key->value
10->A
15->B
20->C

Wenn ich also nach einem Wert für den Schlüssel 0-9 fragen würde, würde er zurückkehren null. Der spezielle Teil ist, wenn ich nach etwas 10 <= i <= 14 frage, würde es A zurückgeben. Oder für i> = 20 würde es C zurückgeben.

Gibt es dafür eine Datenstruktur?

java data-structures Nick
quelle
Ich weiß nicht, ob es eine implementierte gibt, aber Sie könnten wahrscheinlich die vorhandene erweitern, um dies zu tun. Ob es Ihre Leistungsziele erreicht oder nicht, ohne eine Neufassung, weiß ich nicht ...
Rig
1
+1 für die tolle Frage. Die meisten Leute mit drei niedrigen Stellen stellen die Frage "Bitte mache meine Hausaufgaben". Hier ist das nicht der Fall.
Tulains Córdova

Antworten:

33

Sie suchen eine NavigableMap . Dies ist ein Untertyp von SortedMap, für den neben der Art der zu sortierenden Karte auch einige Funktionen verfügbar sind. Beachten Sie, dass die navigierbare Karte "die SortedMap-Schnittstelle ersetzen soll". ( Verbesserungen des Java SE 6 Collections Framework ). Alles, was derzeit implementiert, SortedMapimplementiert NavigableMapund dies wird wahrscheinlich wahr bleiben.

Insbesondere die Methode, floorKey(K key)die "den größten Schlüssel zurückgibt, der kleiner oder gleich dem angegebenen Schlüssel ist, oder null, wenn es keinen solchen Schlüssel gibt.

Dies ist nur eine von vielen Methoden, mit denen Sie bestimmte Schlüssel oder Unterkarten der Karte abrufen können.

  • Decke / Boden (der Eintrag, der höher / niedriger als der Parameter ist)
  • Zugriff auf Schlüssel oder Karte in absteigender Reihenfolge
  • head / tail (die Einträge kleiner / größer als ein gegebener Schlüssel)
  • höher / niedriger (die nächste Taste, die höher oder niedriger als der Parameter ist)
  • Submap (bei zwei Schlüsseln wird die zwischen den beiden Schlüsseln liegende Map zurückgegeben)

Java hat zwei Implementierungen der NavigableMap - die TreeMap und die ConcurrentSkipListMap .

Wenn Sie sich die Idee / Implementierung einer Sprungliste ansehen, werden Sie sehen, warum sie mit einer solchen Struktur und ihren Abfragen wirklich gut funktionieren würde.


quelle
1+ tolle Antwort. Ich hätte nie gedacht, dass in der Java-API eine so spezielle Map vorhanden ist.
Tulains Córdova
@ user61852 Mein Lieblingsdatentyp ist die Überspringliste und ich habe mich damit beschäftigt. Als ich sah, dass es in 1.6 implementiert wurde, habe ich mir angesehen, was es alles bietet, und die Schnittstellen, die es hat, und damit meine Vertrautheit damit bemerkt.
Das ist die Art von Dingen, die mich davon überzeugen, dass Java eine der am besten gestalteten Sprachen ist, die man finden kann.
Tulains Córdova
1
Beachten Sie, dass dies anscheinend das Problem von OP angeht, es sich jedoch nicht so verhält, wie LinkedHashMaper es erwähnt. Weder werden TreeMapnoch ConcurrentSkipListMapwie nach Einfügezeit geordnet LinkedHashMap, vielmehr werden sie durch eine Comparatoroder die natürliche Reihenfolge des Schlüssels geordnet, wenn sie implementiert werden Comparable.
MikeFHay
1
Sehr guter Punkt. Die Bodenbedienung ist das, wonach ich gesucht habe, den Komparator kann ich leicht hinzufügen. Und in meinem Fall klappt es viel besser, den Komparator zu implementieren, als das Rad neu zu erfinden. Vielen Dank.
Nick
1

Was Sie suchen, ist eine Symboltabelle, die geordnete Operationen unterstützt. Und in Ihrem Fall ist es die Bodenoperation.

Die Hash-Implementierung einer Symboltabelle ist die schnellste, bietet jedoch nicht die geordneten Operationen.

Die Baumimplementierung von Symboltabellen tut dies jedoch. Ein Beispiel dafür in Java ist die TreeMap-Klasse

Moha das allmächtige Kamel
quelle