ottenere i valori per le chiavi all'interno di un intervallo in Java

Question

Supponiamo che io ho una mappa in Java che assomiglia a questo:

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

Se le chiavi sono ordinati (sia utilizzando treemap o LinkedHashMap) .Ora se provo per ottenere un valore che è> = 39 e < 41. Allora dovrei ottenere la stringa "da 39 a 41". Come faccio a farlo in modo efficiente?

Answer 1

Sembra che tu voglia più di un SortedMap; vuoi un NavigableMap! Nello specifico è possibile utilizzare l'operazione floorKey.

Ecco un esempio:

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! 

Nota che ci sono anche ceilingKey, lowerKey, higherKey, e anche …Entry invece di …Key operazioni e che restituisce un Map.Entry<K,V> anziché solo la K.

Answer 2

Non sono sicuro che sarà facile. Un suggerimento sarebbe quello di "colmare le lacune", cioè inserire un valore 40->"39 to 41" ecc. Ecc. Suppongo che ciò sarà possibile solo se conoscete l'intera gamma di numeri possibile nella mappa.

Oppure mabybe qualcosa che sovrascrive il get per verificare se il valore è nella mappa e espandersi fino a quando non trova qualcosa. Non sono sicuro che sarà possibile nella sua forma attuale, dato che dovresti finire per analizzare le stringhe di valore.

Answer 3

È possibile cercare in modo ricorsivo il limite inferiore.

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

È necessario disporre di un limite minimo.

Answer 4

Con una mappa ordinata, si potrebbe fare qualcosa di simile:

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

Answer 5

Avresti per attuare tale mappa te, credo. Hai ragione che dovrebbe essere ordinato; l'implementazione di get dovrebbe iterare attraverso le chiavi fino a quando non trova la chiave più grande che è minore o uguale all'argomento.

Se si sottoclasse TreeMap inizialmente sembrerebbe che si possa ottenere questo funzionamento semplicemente ignorando il metodo get(). Tuttavia, per mantenere il più possibile il contratto Map, è necessario sovrascrivere altri metodi per coerenza.

E per esempio, ad es. containsKey()? Il tuo principale contiene una mappatura per 40? Se si restituisce false, un client può decidere di non chiamare get() in base a queste informazioni; per questo motivo (e la definizione formale) devi restituire true. Ma poi rende difficile determinare se la mappa "contiene veramente" una determinata mappatura; se stai cercando di fare qualcosa come l'aggiornamento senza sovrascrivere nulla che già esiste.

Il metodo remove() potrebbe anche essere complicato. Dalla mia lettura dell'interfaccia,

// 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); 

deliberando costantemente qui sarebbe molto difficile. Se si dispone di una mappatura da 35-40 ad esempio, e si chiama remove(38), quindi, a quanto ho capito, si dovrebbe restituire null per ogni successiva ottiene per la chiave 38, ma restituire la suddetta mappatura per le chiavi 35-37 o 39 -40.

---

Così, mentre si può fare un inizio su questo sovrascrivendo TreeMap, forse l'intero concetto di Map non è proprio ciò che si vuole qui. A meno che non si abbia bisogno di questo comportamento per inserire metodi esistenti che richiedono lo Map, potrebbe essere più semplice crearlo da solo come classe distinta poiché non è piuttosto una mappa, il modo in cui lo si sta definendo.

Answer 6

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

In uso speciale floorKey/floorEntry.

Per esempio: floorKey(40) deve restituire 39. floorEntry restituirebbe il valore che stai cercando.