Get Werte für Schlüssel innerhalb eines Bereichs in Java

Question

nehme ich eine Karte in Java haben, die wie folgt aussieht:

{ 
39:"39 to 41", 
41:"41 to 43", 
43:"43 to 45", 
45:">=45" 
} 

Wenn die Schlüssel in sortierter Reihenfolge (entweder mit treemap oder LinkedHashMap) sind .Nun, wenn ich versuche, um einen Wert zu erhalten, der> = 39 ist und < 41. Dann sollte ich die Zeichenfolge "39 bis 41" bekommen. Wie mache ich das effizient?

Answer 1

Es sieht so aus, als ob Sie mehr als ein SortedMap wollen; Sie wollen ein NavigableMap! Insbesondere können Sie die Operation floorKey verwenden.

Hier ist ein Beispiel:

NavigableMap<Integer,String> map = 
     new TreeMap<Integer, String>(); 

    map.put(0, "Kid"); 
    map.put(11, "Teens"); 
    map.put(20, "Twenties"); 
    map.put(30, "Thirties"); 
    map.put(40, "Forties"); 
    map.put(50, "Senior"); 
    map.put(100, "OMG OMG OMG!"); 

    System.out.println(map.get(map.floorKey(13)));  // Teens 
    System.out.println(map.get(map.floorKey(29)));  // Twenties 
    System.out.println(map.get(map.floorKey(30)));  // Thirties 
    System.out.println(map.floorEntry(42).getValue()); // Forties 
    System.out.println(map.get(map.floorKey(666))); // OMG OMG OMG! 

Hinweis, dass es auch ceilingKey, lowerKey, higherKey, und auch …Entry statt …Key Operationen als auch die eine Map.Entry<K,V> zurück, anstatt nur die K.

Answer 2

Ich bin mir nicht sicher, dass das einfach sein wird. Ein Vorschlag wäre, "die Lücken zu füllen", dh einen Wert von 40->"39 to 41" usw. einzugeben. Ich nehme an, dass das nur möglich ist, wenn Sie den gesamten Zahlenbereich kennen, der in der Karte möglich ist.

Oder mabybe etwas, das die get überschreibt, um zu überprüfen, ob der Wert in der Karte ist, und expandiert, bis es etwas findet. Ich bin mir nicht sicher, ob das in seiner jetzigen Form möglich sein wird, da Sie die Wertzeichenfolgen analysieren müssen.

Answer 3

Sie können rekursiv nach der unteren Grenze suchen.

public String descriptionFor(int value) { 
    String description = map.get(value); 
    return description == null ? descriptionFor(value--) : description; 
} 

Sie müssen eine Mindestgrenze haben.

Answer 4

Mit einer sortierten Karte, können Sie so etwas tun könnte:

SortedMap<Integer,String> head = map.headMap(value+1); 
if (head.isEmpty()) { 
    return null; 
} else { 
    return head.get(head.lastKey()); 
} 

Answer 5

Sie haben würde so eine Karte selbst zu implementieren, glaube ich. Du hast recht, dass es sortiert werden müsste; Die Implementierung von get müsste die Schlüssel durchlaufen, bis der größte Schlüssel gefunden wird, der kleiner oder gleich dem Argument ist.

Wenn Sie die Unterklasse TreeMap ableiten, würde es am Anfang erscheinen, dass Sie diese Funktion erhalten, indem Sie einfach die get() Methode überschreiben. Um jedoch so viel wie möglich vom Map-Vertrag beizubehalten, müssen Sie andere Methoden aus Konsistenzgründen überschreiben.

Und was ist z.B. containsKey()? Enthält Ihr Hauptverzeichnis ein Mapping für 40? Wenn Sie false zurückgeben, kann ein Client basierend auf dieser Information entscheiden, get() nicht aufzurufen; Aus diesem Grund (und der formalen Definition) müssen Sie true zurückgeben. Aber dann ist es schwierig zu bestimmen, ob die Karte ein gegebenes Mapping "wirklich enthält". Wenn Sie etwas aktualisieren möchten, ohne etwas zu überschreiben, das bereits existiert.

Die remove() Methode könnte auch schwierig sein. Aus meiner Lektüre der Schnittstelle,

// Calling map.remove "Removes the mapping for a key from this map if it is present." 
map.remove(x); 

// Now that the mapping is removed, I believe the following must hold 
assert map.get(x) == null; 
assert map.containsKey(x); 

hier konsequent handeln würde sehr schwierig. Wenn Sie beispielsweise ein Mapping von 35-40 haben und Sie remove(38) aufrufen, dann müssten Sie, wie ich es verstehe, null für alle nachfolgenden Gets für den Schlüssel 38 zurückgeben, aber die oben erwähnte Zuordnung für die Schlüssel 35-37 oder 39 zurückgeben -40.

---

So, während Sie einen Start auf diesem durch zwingende TreeMap machen, vielleicht das ganze Konzept von Map ist nicht ganz das, was Sie hier wollen. Wenn Sie dieses Verhalten nicht in vorhandene Methoden einfügen müssen, die Map übernehmen, ist es möglicherweise einfacher, es als eigenständige Klasse zu erstellen, da es nicht ist, sondern eine eine Karte ist, wie Sie es definieren.

Answer 6

Versuchen Sie Java 6 java.util.NavigableMap. http://download.oracle.com/javase/6/docs/api/java/util/NavigableMap.html.

In spezieller Verwendung floorKey/floorEntry.

Beispiel: floorKey(40) sollte 39 zurückgeben. floorEntry würde den Wert zurückgeben, nach dem Sie suchen.