Структуры данных, которые могут отображать диапазон ключей в значение

Ответ 1

Являются ли ваши диапазоны неперекрывающимися? Если это так, вы можете использовать TreeMap:

TreeMap<Double, Character> m = new TreeMap<Double, Character>();
m.put(1.0, 'A');
m.put(2.9, null);
m.put(4.0, 'B');
m.put(6.0, null);
m.put(6.5, 'C');
m.put(10.0, null);

Логика поиска немного усложняется тем фактом, что вы, вероятно, хотите включить инклюзивный поиск (например, 2.9 на "A", а не undefined):

private static <K, V> V mappedValue(TreeMap<K, V> map, K key) {
    Entry<K, V> e = map.floorEntry(key);
    if (e != null && e.getValue() == null) {
        e = map.lowerEntry(key);
    }
    return e == null ? null : e.getValue();
}

Пример:

mappedValue(m, 5) == 'B'

Дополнительные результаты:

0.9 null
1.0 A
1.1 A
2.8 A
2.9 A
3.0 null
6.4 null
6.5 C
6.6 C
9.9 C
10.0 C
10.1 null

Ответ 2

Это кажется естественной ситуацией для использования древовидной структуры.

К сожалению, реализовать интерфейс java.util.Map нецелесообразно, поскольку он задает метод возврата всех ключей, и в вашей ситуации теоретически у вас есть непрактично большое количество ключей.

Каждый node вашего дерева должен иметь минимальный ключ, максимальный ключ и значение, связанное с этим диапазоном. Затем вы можете иметь ссылки на узлы, представляющие следующий более высокий и следующий нижний диапазон (если они существуют). Что-то вроде:

public class RangeMap<K extends Comparable<K>, V> {
    protected boolean empty;
    protected K lower, upper;
    protected V value;
    protected RangeMap<K, V> left, right;

    public V get(K key) {
        if (empty) {
            return null;
        }

        if (key.compareTo(lower) < 0) {
            return left.get(key);
        }

        if (key.compareTo(upper) > 0) {
            return right.get(key);
        }

        /* if we get here it is in the range */
        return value;
    }

    public void put(K from, K to, V val) {
        if (empty) {
            lower = from;
            upper = to;
            value = val;
            empty = false;
            left = new RangeMap<K,V>();
            right = new RangeMap<K,V>();
            return;
        }

        if (from.compareTo(lower) < 0) {
            left.put(from, to, val);
            return;
        }

        if (to.compareTo(upper) > 0) {
            right.put(from, to, val);
            return;
        }

        /* here you'd have to put the code to deal with adding an overlapping range,
           however you want to handle that. */
    }

    public RangeMap() {
        empty = true;
    }
}

Если вам нужны более быстрые поисковые запросы, чем может предоставить дерево, вы можете захотеть просмотреть что-то вроде списка пропусков или разработать собственную хеш-функцию.

Ответ 3

A HashMap не будет работать для диапазонов отображения значений до тех пор, пока вы не найдете способ генерировать хэш-код для диапазонов и одиночных значений, которые соответствуют. Но ниже подход может быть тем, что вы ищете

public class RangeMap {
    static class RangeEntry {
        private final double lower;
        private final double upper;
        private final Object value;
        public RangeEntry(double lower, double upper, Object mappedValue) {
            this.lower = lower;
            this.upper = upper;
            this.value = mappedValue;
        }
        public boolean matches(double value) {
            return value >= lower && value <= upper;
        }
        public Object getValue() { return value; }
    }

    private final List<RangeEntry> entries = new ArrayList<RangeEntry>();
    public void put(double lower, double upper, Object mappedValue) {
        entries.add(new RangeEntry(lower, upper, mappedValue));
    }
    public Object getValueFor(double key) {
        for (RangeEntry entry : entries) {
            if (entry.matches(key))
                return entry.getValue();
        }
        return null;
    }
}

Вы могли бы сделать

RangeMap map = new RangeMap();
map.put(1, 2.9, "A");
map.put(4, 6, "B");

map.getValueFor(1.5); // = "A"
map.getValueFor(3.5); // = null

Это не очень эффективно, поскольку он просто перебирает список, и в этом состоянии он не будет жаловаться, если вы разместите там конфликтующие диапазоны. Вернет только первое, что он найдет.

P.S.: отображение, подобное этому, будет отображать диапазон ключей в значение

Ответ 4

Этот тип структуры данных называется Дерево интервала. (На странице Wikipedia представлен случай, когда интервалы могут перекрываться, но можно представить случай, когда вы хотите удалить сопоставления для любых перекрывающихся интервалов при добавлении нового интервала. Проведите поиск в Google для реализации и посмотрите, соответствуют ли ваши потребности.

Ответ 5

просто имеет список в качестве значения на вашей карте.

Map<String, List<Double>> map = new HashMap<String, List<Double>>();

а также один Sayustion:

не использовать Hashtable, если вы не хотите синхронизировать доступ.

EDIT:

Хэш-таблицы синхронизируются, т.е. ни один из двух потоков не может получить доступ к этим методам в один момент времени. Хендмаш HashMap не синхронизирован. Если вы используете Hashtable, будет удар производительности. используйте HashMap для повышения производительности.

Ответ 6

Guava RangeMap предоставляет специализированное решение из коробки:

RangeMap<Integer, String> rangeMap = TreeRangeMap.create();
rangeMap.put(Range.closed(1, 100), "foo"); // {[1, 100] => "foo"}
rangeMap.put(Range.open(3, 6), "bar"); // {[1, 3] => "foo", (3, 6) => "bar", [6, 100] => "foo"}

rangeMap.get(42); // returns "foo"

Ответ 7

Один из способов: использовать одну из реализаций списка как значение для ключа.

map.put("A", ArrayList<Integer>);