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

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

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

Если ключи находятся в отсортированном порядке (либо с помощью treemap, либо связанногоhashmap). Теперь, если я попытаюсь получить значение, равное >= 39 и < 41. Затем я должен получить строку "от 39 до 41". Я делаю это эффективно?

Ответы

Ответ 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.

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

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

Вам понадобится минимальная граница.

Ответ 6

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

Если вы подклассом TreeMap, изначально казалось бы, что вы можете заставить это работать, просто переопределив метод get(). Тем не менее, чтобы поддерживать как можно больше контракта с Картой, вам придется переопределить другие методы для обеспечения согласованности.

А как насчет, например, 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, было бы проще создать его самостоятельно как отдельный класс, так как он не совсем такой Карт, как вы его определяете.