Получить значения для ключей в диапазоне в Java

Question

Предположим, у меня есть карта на Java, которая выглядит следующим образом:

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

Если ключи расположены в отсортированном порядке (с использованием treemap или связанныйhashmap). Теперь, если я пытаюсь получить значение> = 39 и <41. Затем я должен получить строку «39 - 41». Как я могу получить сделать это эффективно? </p>

Answer 1

Похоже, вы хотите больше, чем SortedMap;Вы хотите NavigableMap!В частности, вы можете использовать операцию floorKey.

Вот пример:

    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!

Обратите внимание, что есть также ceilingKey, lowerKey, higherKey, а также …Entry вместо операций …Key, которые возвращают Map.Entry<K,V> вместо просто K.

Answer 2

Попробуйте Java 6 java.util.NavigableMap.http://download.oracle.com/javase/6/docs/api/java/util/NavigableMap.html.

При специальном использовании floorKey / floorEntry.

Например: floorKey(40) должно вернуть 39floorEntry вернет искомое значение.

Answer 3

С отсортированной картой вы можете сделать что-то вроде этого:

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

Answer 4

Я полагаю, вы должны реализовать такую ​​карту самостоятельно.Вы правы, что это должно быть отсортировано;реализация get должна будет перебирать ключи до тех пор, пока не найдет самый большой ключ, который меньше или равен аргументу.

Если вы подклассом TreeMap, первоначально может показаться, что вы можете получитьработая через простое переопределение get() метода.Однако, чтобы сохранить как можно большую часть контракта Map, вам придется переопределить другие методы для согласованности.

А как насчет, например, containsKey()?Содержит ли ваша основная карта для 40?Если вы вернете false, клиент может принять решение не звонить get() на основании этой информации;по этой причине (и формальному определению) вы должны вернуть true.Но тогда становится трудно определить, действительно ли карта «содержит» данное отображение;если вы хотите что-то сделать, например обновить, не перезаписывая ничего, что уже существует.

Метод remove() также может быть сложным.Из моего прочтения интерфейса,

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

Действовать последовательно здесь было бы очень сложно.Если у вас есть сопоставление от 35-40, например, и вы звоните remove(38), то, насколько я понимаю, вам придется вернуть null для любого последующего получения ключа 38, но вернуть вышеупомянутое сопоставление для ключей 35-37 или 39-40.

---

Таким образом, хотя вы можете начать с переопределения TreeMap, возможно, концепция Map не совсем то, что вам нужно.Если вам не нужно это поведение для вставки в существующие методы, которые принимают Map, может быть проще создать его самостоятельно как отдельный класс, поскольку это не вполне Карта, как вы ее определяете.

Answer 5

Вы можете рекурсивно искать нижнюю границу.

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

У вас должна быть минимальная граница.

Answer 6

Я не уверен, что это будет легко. Одним из предложений было бы «заполнить пробелы», т.е. ввести значение 40->"39 to 41" и т. Д. И т. Д. Я полагаю, это будет возможно, только если вы знаете весь диапазон чисел, возможных на карте.

Или mabybe что-то, что переопределяет get, чтобы проверить, есть ли значение на карте, и расширяется, пока не найдет что-то. Я не уверен, что это будет возможно в его нынешнем виде, так как вам придется в конечном итоге анализировать строки значений.